Извор:
Линеарна регресија је један од основних алгоритама за многе области које се односе на анализу података. Разлог за ово је очигледан. Ово је веома једноставан и разумљив алгоритам, који је допринео његовој широкој употреби десетинама, ако не и стотинама година. Идеја је да претпоставимо линеарну зависност једне променљиве од скупа других варијабли, а затим покушамо да вратимо ову зависност.
Али овај чланак није о коришћењу линеарне регресије за решавање практичних проблема. Овде ћемо размотрити занимљиве карактеристике имплементације дистрибуираних алгоритама за његов опоравак, на које смо наишли приликом писања модула машинског учења у . Мало основне математике, машинског учења и дистрибуираног рачунарства могу вам помоћи да схватите како да извршите линеарну регресију чак и када су ваши подаци распоређени на хиљаде чворова.
Шта говоримо?
Пред нама је задатак да обновимо линеарну зависност. Као улазни податак дат је скуп вектора наводно независних променљивих, од којих је свака повезана са одређеном вредношћу зависне променљиве. Ови подаци се могу представити у облику две матрице:
Сада, пошто је зависност претпостављена и, штавише, линеарна, нашу претпоставку ћемо написати у облику производа матрица (да бисмо поједноставили снимање, овде и испод се претпоставља да је слободни члан једначине сакривен иза , и последња колона матрице садржи јединице):
Звучи као систем линеарних једначина, зар не? Чини се, али највероватније неће бити решења за такав систем једначина. Разлог за то је шум, који је присутан у готово свим стварним подацима. Други разлог може бити недостатак линеарне зависности као такве, која се може сузбити увођењем додатних варијабли које нелинеарно зависе од оригиналних. Размотрите следећи пример:
Извор:
Ово је једноставан пример линеарне регресије која показује однос једне променљиве (дуж осе ) из друге променљиве (дуж осе ). Да би систем линеарних једначина који одговара овом примеру имао решење, све тачке морају лежати тачно на истој правој линији. Али то није истина. Али они не леже на истој правој линији управо због буке (или зато што је претпоставка о линеарном односу била погрешна). Дакле, да би се успоставио линеарни однос из стварних података, обично је потребно увести још једну претпоставку: улазни подаци садрже шум и овај шум има . Можете направити претпоставке о другим врстама дистрибуције буке, али у огромној већини случајева се узима у обзир нормална дистрибуција, о чему ће се даље говорити.
Метода максималне вероватноће
Дакле, претпоставили смо присуство насумичне нормално распоређене буке. Шта учинити у таквој ситуацији? За овај случај у математици постоји и широко се користи . Укратко, његова суштина лежи у избору и њено накнадно максимизирање.
Враћамо се враћању линеарне везе из података са нормалним шумом. Имајте на уму да је претпостављена линеарна веза математичко очекивање постојећа нормална дистрибуција. Истовремено, вероватноћа да поприма једну или другу вредност, у зависности од присуства видљивих , као што следи:
Хајде да сада заменимо уместо тога и Променљиве које су нам потребне су:
Остаје само да се пронађе вектор , при чему је ова вероватноћа максимална. Да бисте максимизирали такву функцију, згодно је прво узети њен логаритам (логаритам функције ће достићи максимум у истој тачки као и сама функција):
Што се, пак, своди на минимизирање следеће функције:
Узгред, ово се зове метода . Често се сва горе наведена разматрања изостављају и овај метод се једноставно користи.
КР декомпозиција
Минимум горње функције се може наћи проналажењем тачке у којој је градијент ове функције нула. А градијент ће бити написан на следећи начин:
је матрична метода за решавање проблема минимизације која се користи у методи најмањих квадрата. С тим у вези, преписујемо једначину у матричном облику:
Дакле, разлажемо матрицу на матрице и и извршите серију трансформација (овде се неће разматрати сам алгоритам КР декомпозиције, већ само његова употреба у односу на задатак који је пред вама):
матрица је ортогонална. Ово нам омогућава да се ослободимо посла :
А ако замените на , онда ће успети . С обзиром да је горња троугласта матрица, изгледа овако:
Ово се може решити методом замене. Елемент налази се као , претходни елемент налази се као и тако даље.
Овде је вредно напоменути да је сложеност резултујућег алгоритма услед употребе КР декомпозиције једнака . Штавише, упркос чињеници да је операција множења матрице добро паралелизована, није могуће написати ефективну дистрибуирану верзију овог алгоритма.
Градиент Десцент
Када говоримо о минимизирању функције, увек је вредно запамтити метод (стохастичког) градијентног спуштања. Ово је једноставан и ефикасан метод минимизације заснован на итеративном израчунавању градијента функције у тачки, а затим померању у правцу супротном од градијента. Сваки такав корак приближава решење минимуму. Градијент и даље изгледа исто:
Овај метод је такође добро паралелизован и дистрибуиран због линеарних својстава оператора градијента. Имајте на уму да се у горњој формули под знаком збира налазе независни чланови. Другим речима, градијент можемо израчунати независно за све индексе од првог до , паралелно са овим, израчунајте градијент за индексе са до . Затим додајте добијене градијенте. Резултат сабирања ће бити исти као да смо одмах израчунали градијент за индексе од првог до . Дакле, ако су подаци распоређени на неколико делова података, градијент се може израчунати независно за сваки део, а затим се резултати ових прорачуна могу сумирати да би се добио коначни резултат:
Са становишта имплементације, ово се уклапа у парадигму . На сваком кораку спуштања градијента, сваком чвору података се шаље задатак да израчуна градијент, затим се израчунати градијенти прикупљају заједно, а резултат њиховог збира се користи за побољшање резултата.
Упркос лакоћи имплементације и могућности извршавања у парадигми МапРедуце, спуштање градијента такође има своје недостатке. Конкретно, број корака потребних за постизање конвергенције је знатно већи у поређењу са другим специјализованијим методама.
ЛСКР
је још један метод за решавање проблема, који је погодан и за враћање линеарне регресије и за решавање система линеарних једначина. Његова главна карактеристика је да комбинује предности матричних метода и итеративног приступа. Имплементације овог метода могу се наћи у обе библиотеке , и ин . Опис ове методе неће бити дат овде (може се наћи у чланку ). Уместо тога, биће демонстриран приступ за прилагођавање ЛСКР-а извршењу у дистрибуираном окружењу.
ЛСКР метода се заснива на . Ово је итеративни поступак, свака итерација се састоји од следећих корака:
Али ако претпоставимо да је матрица је хоризонтално подељен, онда се свака итерација може представити као два МапРедуце корака. На овај начин могуће је минимизирати пренос података током сваке итерације (само вектори чија је дужина једнака броју непознатих):
Управо овај приступ се користи када се спроводи линеарна регресија у .
Закључак
Постоји много алгоритама за опоравак линеарне регресије, али не могу се сви применити у свим условима. Дакле, КР декомпозиција је одлична за прецизно решење на малим скуповима података. Градијентно спуштање је једноставно за имплементацију и омогућава вам да брзо пронађете приближно решење. А ЛСКР комбинује најбоља својства претходна два алгоритма, пошто се може дистрибуирати, конвергира брже у поређењу са градијентом спуштања, а такође омогућава рано заустављање алгоритма, за разлику од КР декомпозиције, како би се пронашло приближно решење.
Извор: ввв.хабр.цом