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