Източник:
Линейната регресия е един от основните алгоритми за много области, свързани с анализа на данни. Причината за това е очевидна. Това е много прост и очевиден алгоритъм, което допринася за широко му приложение вече много десетилетия, ако не и стотици години. Идеята е, че предполагаме линейна зависимост на една променлива от набор от други променливи и след това се опитваме да възстановим тази зависимост.
Но в тази статия няма да говорим за прилагането на линейната регресия за решаване на практически задачи. Тук ще разгледаме интересни особености на реализацията на разпределени алгоритми за нейното възстановяване, с които се сблъскахме при написването на модула за машинно обучение в . Малко базова математика, основи на машинното обучение и разпределени изчисления ще помогнат да разберем как да възстановим линейната регресия, дори ако данните са разпределени между хиляди възли.
За какво става дума?
Имаме задача за възстановяване на линейна зависимост. Като входни данни получаваме множество вектори на предполагаемо независими променливи, на които се съответства определена стойност на зависимата променлива. Тези данни могат да бъдат представени под формата на две матрици:
Сега, след като се предполага зависимост, и то линейна, да запишем нашето предположение под формата на произведение на матрици (за опростяване на записа тук и по-нататък се предполага, че свободният член на уравнението е скрит зад 
, а последният стълб на матрицата 
съдържа единици):
Много прилича на система от линейни уравнения, нали? Изглежда, но вероятно такава система уравнения няма да има решения. Причината за това е шумът, който присъства практически във всички реални данни. Другата причина може да бъде отсъствието на линейна зависимост като такава, с която можем да се опитаме да се справим, като въведем допълнителни променливи, които нелинейно зависят от изходните. Нека разгледаме следния пример:
Източник:
Това е прост пример за линейна регресия, който демонстрира зависимостта на една променлива (по оста 
) от друга променлива (по оста 
). За да има система от линейни уравнения решение, всички точки трябва да лежат точно на една права. Но това не е така. А те не лежат на една права именно заради шума (или заради това, че предположението за наличие на линейна зависимост е било погрешно). Така че, за да възстановим линейната зависимост по реални данни обикновено е необходимо да въведем още едно предположение: входните данни съдържат шум и този шум има . Могат да бъдат правени предположения и за други видове разпределение на шума, но в подавляващата част от случаите се разглежда именно нормалното разпределение, за което по-нататък ще става дума.
Метод на максимално правдоподобие
И така, предположихме наличие на случайно нормально разпределен шум. Как да действаме в такава ситуация? За този случай в математиката съществува и широко се използва . В обобщение, сутьта му е в избора на и последващото и максимизиране.
Връщаме се към възстановяването на линейната зависимост по данни с нормален шум. Нека отбележим, че предполагаемата линейна зависимост е математическото очакване 
на наличното нормально разпределение. В същото време, вероятността, че 
приема някаква стойност, при условие, че има наблюдавани 
, изглежда по следния начин:
Сега да поставим на мястото на 
и 
нужните ни променливи:
Остана само да намерим вектор 
, при който тази вероятност е максимална. За да максимизираме такава функция е удобно първо да я прологарим (логаритъмът на функцията ще достига максимум в същата точка, както и самата функция):
Което от своя страна се свежда до минимизиране на следната функция:
Между другото, това се нарича метод на . Често всички горепосочени разсъждения се пропускат и просто се използва този метод.
QR разлагане
Минималната стойност на горепосочената функция може да се намери, ако се открие точка, в която градиентът на тази функция е равен на нула. А градиентът ще бъде записан по следния начин:
е матричен метод за решаване на задача за минимизиране, използван в метода на най-малките квадрати. Във връзка с това да запишем уравнението в матрична форма:
И така, разлагаме матрицата 
на матрици 
и 
и извършваме редица преобразувания (самият алгоритъм за QR разлагане няма да бъде разгледан тук, само неговото приложение към поставената задача):
Матрицата 
е ортогонална. Това ни позволява да се отървем от произведението 
:
А ако замените 
на 
, тогава ще получите 
. Като се има предвид, че 
е горна триъгълна матрица, това изглежда по следния начин:
Това може да се реши чрез метода на подстановката. Елементът 
се намира като 
, предходният елемент 
се намира като 
и така нататък.
Тук следва да се отбележи, че сложността на получения алгоритъм благодарение на използването на QR разлагането е 
. Въпреки че операцията по умножение на матрици се разпаралелизира добре, написването на ефективна разпределена версия на този алгоритъм не е възможно.
Градиентен спуск
Когато става въпрос за минимизиране на определена функция, винаги трябва да се припомня методът (стохастически) градиентен спуск. Това е прост и ефективен метод на минимизиране, основан на итеративното изчисление на градиента на функцията в точка и последващото ѝ изместване в посока, противоположна на градиента. Всеки такъв ход приближава решението до минимума. Градиентът изглежда все така:
Този метод също така добре се разпаралелизира и разпределя благодарение на линейните свойства на оператора градиент. Забележете, че в горната формула под знака на сумата се намират независими съставки. С други думи, можем да изчислим градиента независимо за всички индекси 
от първия до 
, паралелно с това може да се изчисли градиентът за индексите от 
до 
. След това да се съберат получените градиенти. Резултатът от събирането ще бъде същият, както ако бяхме изчислили веднага градиента за индексите от първия до 
. Така, ако данните са разпределени между няколко части данни, градиентът може да бъде изчислен независимо за всяка част, а след това резултатите от тези изчисления могат да бъдат събрани за получаване на окончателния резултат:
От гледна точка на реализацията, това е в парадигмата . На всяка стъпка на градиентния спуск се изпраща задача за изчисление на градиента на всеки узел от данните, след което изчислените градиенти се събират заедно, а резултатът от тяхното събиране се използва за подобряване на резултата.
Въпреки простотата на реализацията и възможността за изпълнение в парадигмата MapReduce, градиентният спуск има и свои недостатъци. В частност, броят на стъпките, необходими за достигане на съвместимост, е значително по-висок в сравнение с други по-специализирани методи.
LSQR
— още един метод за решаване на поставената задача, който е подходящ както за възстановяване на линейна регресия, така и за решаване на системи от линейни уравнения. Неговата главна особеност е, че комбинира предимствата на матричните методи и итеративния подход. Реализациите на този метод могат да бъдат намерени както в библиотеките , така и в . Описанието на този метод няма да бъде приведено тук (може да бъде намерено в статията ). Вместо това ще бъде демонстриран подход, който позволява адаптиране на LSQR за изпълнение в разпределена среда.
В основата на метода LSQR стои . Това е итеративна процедура, всяка итерация от която се състои от следните стъпки:
Но ако вземем предвид, че матрицата 
е хоризонтално партиционирана, то всяка итерация може да бъде представена под формата на две стъпки от MapReduce. По този начин успяваме да минимизираме прехвърлянето на данни по време на всяка от итерациите (само вектори с дължина, равна на броя на неизвестните):
Този подход се използва при реализирането на линейна регресия в .
Заключение
Съществуват много алгоритми за възстановяване на линейната регресия, но не всички от тях могат да бъдат приложени при всякакви условия. Например, QR разлагането е отлично за точно решение на малки масиви от данни. Градиентният спуск се реализира лесно и позволява бързо намиране на приближено решение. А LSQR комбинира най-добрите свойства на предходните два алгоритма, тъй като може да бъде разпределен, по-бързо събира в сравнение с градиентния спуск, а също така позволява ранно спиране на алгоритъма в отличие от QR-разлагането при търсенето на приближено решение.
Източник: habr.com
