Tinkoff Generation

Линейная регрессия

lec3.md

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

Положим в XX какие-то трёхмерные векторы:
X=(112210142012235337610112650)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}

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

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

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

По сути мы хотим подобрать числа a0,a1,a2,a3a_0, a_1, a_2, a_3 для вот такой модели:
f(x1,x2,x3)=a0+a1x1+a2x2+a3x3f(x_1, x_2, x_3) = a_0 + a_1 x_1 + a_2 x_2 + a_3 x_3

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

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

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

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

Начнём с координаты a1a_1:
MSEa1(a0,a1,a2,a3)=i=1n((a0+a1xi1+a2xi2+a3xi3yi)2)a1=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}=
Раскрываем квадрат, вынося отдельно члены, которые делятся на a12a_1^2, a1a_1 и 11:
=i=1n(xi12a12+2xi1(a0+a2xi2+a3xi3yi)a1+(a0+a2xi2+a3xi3yi)2)a1==\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}=
Считаем производную, одна из скобок при этом обнуляется:
i=1n(2xi12a1+2xi1(a0+a2xi2+a3xi3yi))=\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)) =
Теперь вынесем 22 и xi1x_{i1}:
=2i=1n(xi1a1+a0+a2xi2+a3xi3yi)xi1== 2\sum\limits_{i=1}^n (x_{i1} a_1 + a_0 + a_2 x_{i2} + a_3 x_{i3} - y_i) x_{i1}=
Заметим, что в скобках получилось очень простое выражение!
=2i=1n(f(xi1,xi2,xi3)yi)xi1=2\sum\limits_{i=1}^n (f(x_{i1}, x_{i2}, x_{i3}) -y_i) x_{i1}

Давайте приравняем все 4 производные (по a0,a1,a2,a3a_0, a_1, a_2, a_3) нулю, тогда:
i=1n(a0+a1xi1+axxi2+a3xi3yi)=0\sum\limits_{i=1}^n (a_0 + a_1 x_{i1} + a_x x_{i2} + a_3 x_{i3} - y_i) = 0
i=1n(a0+a1xi1+axxi2+a3xi3yi)xi1=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
i=1n(a0+a1xi1+axxi2+a3xi3yi)xi2=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
i=1n(a0+a1xi1+axxi2+a3xi3yi)xi3=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

Давайте сгруппируем все выражения по a0,a1,a2,a3a_0, a_1, a_2, a_3:
na0+(i=1nxi1)a1+(i=1nxi2)a2+(i=1nxi3)a3=i=1nyina_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
(i=1nxi1)a0+(i=1nxi12)a1+(i=1nxi1xi2)a2+(i=1nxi1xi3)a3=i=1nxi1yi(\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
(i=1nxi2)a0+(i=1nxi1xi2)a1+(i=1nxi22)a2+(i=1nxi2xi3)a3=i=1nxi2yi(\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
(i=1nxi3)a0+(i=1nxi1xi3)a1+(i=1nxi2xi3)a2+(i=1nxi32)a3=i=1nxi3yi(\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

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

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