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