Tinkoff Generation

Что делает линейная регрессия?

Положим в $X$ какие-то трёхмерные векторы:
$X = \begin{pmatrix} 1& 1& 2& 2& 10& 14& 20\\ 1& 2& 2& 3& 5& 3& 3\\ 7& 6& 10& 11& 2& 6& 50 \end{pmatrix}$

Построим $y$ по такой формуле:
$y =100x-200y+70z+35+\epsilon$
Где $\epsilon$ — это какой-то шум с нормальный распределением с дисперсией $10$, чтобы линейная формула не была уж совсем точной.

Если мы запустим линейную регрессию и посмотрим, сможет ли она восстановить параметры модели $100$, $200$, $70$, $35$, то внезапно заметим, что линейная регрессия как-то примерно угадала наши коэффициенты. Примерно, потому что мы добавили шум. Как же она это делает?

Как работает линейная регрессия?

По сути мы хотим подобрать числа $a_0, a_1, a_2, a_3$ для вот такой модели:
$f(x_1, x_2, x_3) = a_0 + a_1 x_1 + a_2 x_2 + a_3 x_3$

Мы хотим подобрать их так, чтобы функция потерь на наших данных была минимальна. В LinearRegression используют функцию потерь MSE — сумму квадратов отклонений от настоящего значения.

То есть задача такая:
$\sum\limits_{i=1}^n (f(x_{i1}, x_{i2}, x_{i3}) - y_i)^2 \rightarrow min$
$\sum\limits_{i=1}^n (a_0 = a_1 x_{i1} + a_2 x_{i2} + a_3 x_{i3} - y_i)^2 \rightarrow min$
где $n$ это количество входных данных.

Давайте рассмотрим эту сумму, как функцию от 4 переменных $a_0, a_1, a_2, a_3$, которую нам нужно минимизировать. А числа $x_{ij}$ и $y_i$ будут обычными константами.
$MSE(a_0, a_1, a_2, a_3) \rightarrow min$

Давайте посчитаем частную производную по каждой координате.

Начнём с координаты $a_1$:
$MSE_{a_1}' (a_0, a_1, a_2, a_3) = \sum\limits_{i=1}^n ((a_0 + a_1 x_{i1} + a_2 x_{i2} + a_3 x_{i3} - y_i)^2)'_{a_1}=$
Раскрываем квадрат, вынося отдельно члены, которые делятся на $a_1^2$, $a_1$ и $1$:
$=\sum\limits_{i=1}^n (x_{i1}^2 a_1^2 + 2x_{i 1} (a_0 + a_2 x_{i2} + a_3 x_{i3} - y_i)a_1 + (a_0 + a_2 x_{i2} + a_3 x_{i3} - y_i)^2)'_{a_1}=$
Считаем производную, одна из скобок при этом обнуляется:
$\sum\limits_{i=1}^n(2 x_{i1}^2 a_1 + 2 x_{i1} (a_0 + a_2 x_{i2} + a_3 x_{i3} -y_i)) =$
Теперь вынесем $2$ и $x_{i1}$:
$= 2\sum\limits_{i=1}^n (x_{i1} a_1 + a_0 + a_2 x_{i2} + a_3 x_{i3} - y_i) x_{i1}=$
Заметим, что в скобках получилось очень простое выражение!
$=2\sum\limits_{i=1}^n (f(x_{i1}, x_{i2}, x_{i3}) -y_i) x_{i1}$

Давайте приравняем все 4 производные (по $a_0, a_1, a_2, a_3$) нулю, тогда:
$\sum\limits_{i=1}^n (a_0 + a_1 x_{i1} + a_x x_{i2} + a_3 x_{i3} - y_i) = 0$
$\sum\limits_{i=1}^n (a_0 + a_1 x_{i1} + a_x x_{i2} + a_3 x_{i3} - y_i)x_{i1} = 0$
$\sum\limits_{i=1}^n (a_0 + a_1 x_{i1} + a_x x_{i2} + a_3 x_{i3} - y_i)x_{i2} = 0$
$\sum\limits_{i=1}^n (a_0 + a_1 x_{i1} + a_x x_{i2} + a_3 x_{i3} - y_i)x_{i3} = 0$

Давайте сгруппируем все выражения по $a_0, a_1, a_2, a_3$:
$na_0 + (\sum\limits_{i=1}^n x_{i1})a_1+ (\sum\limits_{i=1}^n x_{i2})a_2+ (\sum\limits_{i=1}^n x_{i3})a_3 = \sum\limits_{i=1}^n y_i$
$(\sum\limits_{i=1}^n x_{i1}) a_0 + (\sum\limits_{i=1}^n x_{i1}^2) a_1 + (\sum\limits_{i=1}^n x_{i1} x_{i2}) a_2 + (\sum\limits_{i=1}^n x_{i1} x_{i3} )a_3 = \sum\limits_{i=1}^n x_{i1} y_i$
$(\sum\limits_{i=1}^n x_{i2}) a_0 + (\sum\limits_{i=1}^n x_{i1}x_{i2}) a_1 + (\sum\limits_{i=1}^n x_{i2}^2) a_2 + (\sum\limits_{i=1}^n x_{i2} x_{i3} )a_3 = \sum\limits_{i=1}^n x_{i2} y_i$
$(\sum\limits_{i=1}^n x_{i3}) a_0 + (\sum\limits_{i=1}^n x_{i1}x_{i3}) a_1 + (\sum\limits_{i=1}^n x_{i2} x_{i3}) a_2 + (\sum\limits_{i=1}^n x_{i3}^2 )a_3 = \sum\limits_{i=1}^n x_{i3} y_i$

Ура, мы получили красивую симметричную систему уравнения, $4$ уравнения, $4$ неизвестных. Если определитель матрицы коэффициентов не равен нулю, то у него есть ровно одно решение, и его мы умеем находить (методом Гаусса, например). Если определитель вдруг стал равен нулю, то решений либо 0, либо бесконечно.

У непрерывно-дифференцируемой функции, которая при стремлении по каждой координате к плюс или минус бесконечности сама стремится к плюс бесконечности, всегда существует глобальный минимум. В точке глобального минимума все производные как раз равны нулю. Следовательно, существует всегда хотя бы одно решение, и мы его найдем.