Извор:
Линеарната регресија е еден од основните алгоритми за многу области поврзани со анализа на податоци. Причината за ова е очигледна. Ова е многу едноставен и разбирлив алгоритам, кој придонесе за неговата широка употреба многу десетици, ако не и стотици години. Идејата е да претпоставиме линеарна зависност на една променлива од множество други променливи, а потоа да се обидеме да ја вратиме оваа зависност.
Но, оваа статија не е за користење на линеарна регресија за решавање на практични проблеми. Овде ќе разгледаме интересни карактеристики на имплементацијата на дистрибуирани алгоритми за негово обновување, со кои наидовме при пишување модул за машинско учење во . Малку основна математика, машинско учење и дистрибуирано пресметување може да ви помогнат да сфатите како да извршите линеарна регресија дури и кога вашите податоци се дистрибуираат низ илјадници јазли.
За што зборуваме?
Соочени сме со задача да ја вратиме линеарната зависност. Како влезни податоци, дадени се множество вектори на наводни независни променливи, од кои секоја е поврзана со одредена вредност на зависната променлива. Овие податоци може да се претстават во форма на две матрици:
Сега, бидејќи зависноста е претпоставена, а згора на тоа, линеарна, нашата претпоставка ќе ја запишеме во форма на производ од матрици (за да се поедностави снимањето, овде и подолу се претпоставува дека слободниот член на равенката се крие зад , и последната колона од матрицата содржи единици):
Звучи многу како систем на линеарни равенки, нели? Се чини, но најверојатно нема да има решенија за таков систем на равенки. Причината за тоа е бучавата, која е присутна во речиси сите реални податоци. Друга причина може да биде недостатокот на линеарна зависност како таква, што може да се бори со воведување дополнителни променливи кои нелинеарно зависат од оригиналните. Размислете за следниов пример:
Извор:
Ова е едноставен пример за линеарна регресија што ја покажува врската на една променлива (по должината на оската ) од друга променлива (по оската ). За да може системот на линеарни равенки што одговараат на овој пример да има решение, сите точки мора да лежат точно на иста права линија. Но, тоа не е вистина. Но, тие не лежат на иста права линија токму поради бучавата (или затоа што претпоставката за линеарна врска била погрешна). Така, за да се врати линеарна врска од реални податоци, обично е неопходно да се воведе уште една претпоставка: влезните податоци содржат шум и овој шум има . Можете да направите претпоставки за други видови дистрибуција на бучава, но во огромното мнозинство на случаи се разгледува нормалната дистрибуција, што ќе се дискутира понатаму.
Метод на максимална веројатност
Значи, претпоставивме присуство на случајна нормално дистрибуирана бучава. Што да направите во таква ситуација? За овој случај во математиката постои и е широко користен . Накратко, неговата суштина лежи во изборот и неговото последователно максимизирање.
Се враќаме на враќање на линеарна врска од податоци со нормален шум. Забележете дека претпоставената линеарна врска е математичкото очекување постоечка нормална дистрибуција. Во исто време, веројатноста дека зема една или друга вредност, предмет на присуство на набљудувани , како што следи:
Ајде сега да замениме наместо тоа и Променливите што ни се потребни се:
Останува само да се најде векторот , при што оваа веројатност е максимална. За да се максимизира таквата функција, погодно е прво да се земе логаритам од неа (логаритмот на функцијата ќе достигне максимум во истата точка како и самата функција):
Што, пак, се сведува на минимизирање на следнава функција:
Патем, ова се нарекува метод . Честопати сите горенаведени размислувања се испуштаат и овој метод едноставно се користи.
QR распаѓање
Минимумот од горната функција може да се најде со наоѓање на точката во која градиентот на оваа функција е нула. И градиентот ќе биде напишан на следниов начин:
е матричен метод за решавање на проблемот за минимизирање кој се користи во методот на најмали квадрати. Во овој поглед, ја препишуваме равенката во форма на матрица:
Значи ја разложуваме матрицата до матрици и и изврши серија трансформации (самиот алгоритам за распаѓање QR нема да се разгледува овде, туку само неговата употреба во однос на задачата што е прифатена):
матрица е ортогонален. Ова ни овозможува да се ослободиме од работата :
И ако замените на , тогаш ќе успее . Со оглед на тоа е горната триаголна матрица, изгледа вака:
Ова може да се реши со методот на замена. Елемент се наоѓа како , претходен елемент се наоѓа како и така натаму.
Овде вреди да се напомене дека сложеноста на добиениот алгоритам поради употребата на распаѓање QR е еднаква на . Покрај тоа, и покрај фактот што операцијата за множење на матрицата е добро паралелизирана, не е можно да се напише ефективна дистрибуирана верзија на овој алгоритам.
Спуштање на градиент
Кога зборуваме за минимизирање на функцијата, секогаш вреди да се потсетиме на методот на (стохастичко) спуштање на градиент. Ова е едноставен и ефективен метод за минимизирање базиран на итеративно пресметување на градиентот на функцијата во точка и потоа негово поместување во насока спротивна на градиентот. Секој таков чекор го приближува решението до минимум. Градиентот сè уште изгледа исто:
Овој метод е исто така добро паралелизиран и распределен поради линеарните својства на операторот на градиент. Забележете дека во горната формула, под знакот за сума има независни поими. Со други зборови, можеме да го пресметаме градиентот независно за сите индекси од прво до , паралелно со ова, пресметајте го градиентот за индекси со да . Потоа додадете ги добиените градиенти. Резултатот од собирањето ќе биде ист како веднаш да го пресметаме градиентот за индексите од првиот до . Така, ако податоците се дистрибуираат помеѓу неколку податоци, градиентот може да се пресмета независно на секое парче, а потоа резултатите од овие пресметки може да се сумираат за да се добие конечниот резултат:
Од гледна точка на имплементација, ова одговара на парадигмата . На секој чекор од спуштањето на градиентот, се испраќа задача до секој податочен јазол за да се пресмета градиентот, потоа пресметаните градиенти се собираат заедно, а резултатот од нивниот збир се користи за подобрување на резултатот.
И покрај леснотијата на имплементација и способноста за извршување во парадигмата MapReduce, спуштањето на градиент има и свои недостатоци. Конкретно, бројот на чекори потребни за да се постигне конвергенција е значително поголем во споредба со другите поспецијализирани методи.
LSQR
е уште еден метод за решавање на проблемот, кој е погоден и за враќање на линеарна регресија и за решавање на системи на линеарни равенки. Неговата главна карактеристика е тоа што ги комбинира предностите на матричните методи и итеративниот пристап. Имплементацијата на овој метод може да се најде во двете библиотеки , и внатре . Опис на овој метод нема да биде даден овде (може да се најде во статијата ). Наместо тоа, ќе се покаже пристап за прилагодување на LSQR на извршување во дистрибуирана средина.
Методот LSQR се базира на . Ова е повторувачка процедура, секоја повторување се состои од следните чекори:
Но, ако претпоставиме дека матрицата е хоризонтално поделена, тогаш секоја итерација може да се претстави како два чекори на MapReduce. На овој начин, можно е да се минимизираат преносите на податоци за време на секоја итерација (само вектори со должина еднаква на бројот на непознати):
Токму овој пристап се користи при спроведување на линеарна регресија во .
Заклучок
Постојат многу алгоритми за обновување на линеарна регресија, но не сите од нив можат да се применат во сите услови. Значи, распаѓањето на QR е одлично за прецизно решение на мали збирки податоци. Спуштањето на градиент е едноставно за спроведување и ви овозможува брзо да пронајдете приближно решение. И LSQR ги комбинира најдобрите својства на претходните два алгоритми, бидејќи може да се дистрибуира, се конвергира побрзо во споредба со спуштањето на градиент, а исто така овозможува рано запирање на алгоритмот, за разлика од распаѓањето QR, за да се најде приближно решение.
Извор: www.habr.com