![image](https://habrastorage.org/getpro/habr/post_images/b51/ff6/39b/b51ff639b3923b170de1d4d2cc8f4d22.png)
Источник: xkcd
Линейная регрессия является одним из базовых алгоритмов для многих областей, связанных с анализом данных. Причина этому очевидна. Это очень простой и понятный алгоритм, что способствует его широкому применению уже многие десятки, если не сотни, лет. Идея заключается в том, что мы предполагаем линейную зависимость одной переменной от набора других переменных, а потом пытаемся эту зависимость восстановить.
Но в этой статье речь пойдет не про применение линейной регрессии для решения практических задач. Здесь будут рассмотрены интересные особенности реализации распределенных алгоритмов её восстановления, с которыми мы столкнулись при написании модуля машинного обучения в Apache Ignite. Немного базовой математики, основ машинного обучения и распределенных вычислений помогут разобраться, как восстанавливать линейную регрессию, даже если данные распределены между тысячами узлов.
О чём речь?
Перед нами стоит задача восстановления линейной зависимости. В качестве входных данных дается множество векторов предположительно независимых переменных, каждому из которых ставится в соответствие некоторое значение зависимой переменной. Эти данные можно представить в виде двух матриц:
Теперь, раз уж предполагается зависимость, да к тому же еще и линейная, запишем наше предположение в виде произведения матриц (для упрощения записи здесь и далее предполагается, что свободный член уравнения скрывается за
Очень похоже на систему линейных уравнений, не так ли? Похоже, но решений у такой системы уравнений скорее всего не будет. Причиной тому является шум, который присутствует практически в любых реальных данных. Так же причиной может быть отсутствие линейной зависимости как таковой, с которой можно пытаться бороться введением дополнительных переменных, нелинейно зависящих от исходных. Рассмотрим следующий пример:
![image](https://habrastorage.org/getpro/habr/post_images/d87/fbd/00f/d87fbd00faae5966747b5afbcd80117f.png)
Источник: Wikipedia
Это простой пример линейной регрессии, который демонстрирует зависимость одной переменной (по оси
Метод максимального правдоподобия
Итак, мы предположили наличие случайного нормально распределенного шума. Как же быть в такой ситуации? На этот случай в математике существует и широко используется метод максимального правдоподобия. Если кратко, его суть заключается в выборе функции правдоподобия и последующей её максимизации.
Возвращаемся к восстановлению линейной зависимости по данным с нормальным шумом. Заметим, что предполагаемая линейная зависимость является математическим ожиданием
Подставим теперь вместо
Осталось только найти вектор
Что, в свою очередь, сводится к минимизации следующей функции:
Кстати, это называется методом наименьших квадратов. Зачастую все приведенные выше рассуждения опускаются и просто используется этот метод.
QR разложение
Минимум приведенной выше функции можно найти, если найти точку в которой градиент этой функции равен нулю. А градиент будет записан следующим образом:
QR разложение является матричным методом решения задачи минимизации используемом в методе наименьших квадратов. В связи с этим перепишем уравнение в матричной форме:
Итак, мы раскладываем матрицу
Матрица
А если заменить
Это можно решать методом подстановки. Элемент
Здесь стоит отметить, что сложность получившегося алгоритма за счет использования QR разложения равна
Градиентный спуск
Говоря о минимизации некоторой функции, всегда стоит вспоминать метод (стохастического) градиентного спуска. Это простой и эффективный метод минимизации, основанный на итеративном вычислении градиента функции в точке и последующем её смещении в сторону, противоположную градиенту. Каждый такой шаг приближает решение к минимуму. Градиент при этом выглядит все так же:
Ещё этот метод хорошо распараллеливается и распределяется за счет линейных свойств оператора градиента. Заметим, что в приведенной выше формуле под знаком суммы находятся независимые слагаемые. Другими словами, мы можем посчитать градиент независимо для всех индексов
С точки зрения реализации, это укладывается в парадигму MapReduce. На каждом шаге градиентного спуска на каждый узел данных отправляется задание на вычисление градиента, затем вычисленные градиенты собираются вместе, и результат их суммирования используется для улучшения результата.
Несмотря на простоту реализации и возможность выполнения в парадигме MapReduce градиентный спуск обладает и своими недостатками. В частности, количество шагов, необходимое для достижения сходимости, существенно больше в сравнении с другими более специализированными методами.
LSQR
LSQR — еще один метод решения поставленной задачи, который подходит как для восстановления линейной регрессии, так и для решения систем линейных уравнений. Его главная особенность заключается в том, что он совмещает в себе преимущества матричных методов и итеративного подхода. Реализации этого метода можно найти как в библиотеки SciPy, так и в MATLAB. Описание данного метода приводиться здесь не будет (его можно найти в статье LSQR: An algorithm for sparse linear equations and sparse least squares). Вместо этого будет продемонстрирован подход, позволяющий адаптировать LSQR к выполнению в распределенной среде.
В основе метода LSQR лежит процедура бидиагонализации. Это итеративная процедура, каждая итерация которой состоит из следующих шагов:
![image](https://habrastorage.org/webt/7b/wj/6y/7bwj6yfndq8idrsn8bos7maxapo.png)
Но если исходить из того, что матрица
![image](https://habrastorage.org/webt/gt/di/mv/gtdimv7wsgptkxtdrmwnfonjvg0.png)
Именно этот подход используется при реализации линейной регрессии в Apache Ignite ML.
Заключение
Существует много алгоритмов восстановления линейной регрессии, но не все из них могут применяться в любых условиях. Так QR разложение отлично подходит для точного решения на небольших массивах данных. Градиентный спуск просто реализуется и позволяет быстро найти приближенное решение. А LSQR сочетает в себе лучшие свойства предыдущих двух алгоритмов, так как он может быть распределен, быстрее сходится в сравнении с градиентным спуском, а так же позволяет раннюю остановку алгоритма в отличие от QR-разложения для поиска приближенного решения.