Перейти к основному содержимому

Аналитическое решение для линейной регрессии

Веса линейной регрессии находятся из принципа минимизации наименьших квадратов (МНК, ordinary least squares, OLS):

L(w)=∑n=1N(xnTw−yn)2→min⁡wL(\mathbf{w})=\sum_{n=1}^N (\mathbf{x}_n^T\mathbf{w}-y_n)^2\to\min_{\mathbf{w}}

Этот критерий по w\mathbf{w} является выпуклым как суперпозиция линейной и выпуклой функции.

Тип векторов

Все вектора в этом разделе, как и глобально в книге, будем считать векторами-столбцами (а не строками). Это важно для понимания аналитических выкладок.

Будет ли суперпозиция двух выпуклых функций выпуклой?

Суперпозиция двух выпуклых функций может и не быть выпуклой, например, f(g(x))=(∣x∣−1)2f(g(x))=(\vert x \vert-1)^2 для

g(x)=∣x∣−1,f(x)=x2g(x)=\vert x \vert - 1,\quad f(x)=x^2

Однако суперпозиция линейной и выпуклой функции всегда выпукла - докажите самостоятельно.

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

Мы говорим про градиент, а не про производную, поскольку при дифференцировании скалярной функции L(w)∈RL(\mathbf{w})\in\mathbb{R} по вектору w∈RD+1\mathbf{w}\in \mathbb{R}^{D+1} получим вектор частных производных по каждой компоненте вектора w\mathbf{w}:

∇L(w)=(∂L∂w0∂L∂w1∂L∂w2⋯∂L∂wD)\nabla L(\mathbf{w})= \begin{pmatrix} \frac{\partial L}{\partial w_0} \\ \frac{\partial L}{\partial w_1} \\ \frac{\partial L}{\partial w_2} \\ \cdots \\ \frac{\partial L}{\partial w_D} \\ \end{pmatrix}

Найдем оптимальные веса аналитически. Поскольку функция потерь является выпуклой по весам, то не только необходимым, но и достаточным условием оптимальности будет покомпонентное равенство нулю градиента функции потерь:

∇L(w^)=2∑n=1Nxn(xnTw^−yn)=0\nabla L(\widehat{\mathbf{w}})=2\sum_{n=1}^{N}\mathbf{x}_{n}\left(\mathbf{x}_{n}^{T}\widehat{\mathbf{w}}-y_{n}\right)=0 (∑n=1NxnxnT)w^=∑n=1Nxnyn\left(\sum_{n=1}^{N}\mathbf{x}_{n}\mathbf{x}_{n}^{T}\right)\widehat{\mathbf{w}}=\sum_{n=1}^{N}\mathbf{x}_{n}y_{n}

Перепишем условие, используя обозначения для матрицы объекты-признаки X∈RN×DX\in\mathbb{R}^{N\times D} и вектора откликов Y∈RNY\in \mathbb{R}^N:

XTXw^=XTYX^{T}X\widehat{\mathbf{w}}=X^T Y

Откуда получаем аналитическое итоговое решение для линейной регрессии:

w^=(XTX)−1XTY\widehat{\mathbf{w}}=(X^{T}X)^{-1}X^{T}Y

Обратим внимание, что решение не будет существовать, если матрица XTXX^T X вырождена, что эквивалентно тому, что ранг матрицы rg(XTX)=rg(X)<D\text{rg}(X^T X)=\text{rg}(X)<D.

Задача

Докажите, что rg(XTX)=rg(X)\text{rg}(X^T X)=\text{rg}(X) для любой матрицы XX.

Последнее, в свою очередь, означает линейную зависимость между признаками, т.е. что найдётся такой набор весов a=[a0,a1,...aD]\bm{a}=[a_0,a_1,...a_D], что

xTa=0∀x (выполнено для любых векторов признаков x)\mathbf{x}^T \bm{a}=0 \quad \forall \mathbf{x} \,(\text{выполнено для любых векторов признаков } \mathbf{x})

В этом случае один из признаков лишний, поскольку может быть получен как линейная комбинация других признаков, а само решение неоднозначно, поскольку если w^\hat{\mathbf{w}} - решение, то и w+ka\mathbf{w}+k\bm{a} - тоже решение для любого k∈Rk\in \mathbb{R}, поскольку

y^(x)=xTw^=xTw^+0=xTw^+kxTa=xT(w+ka)\hat{y}(\mathbf{x})=\mathbf{x}^T\hat{\mathbf{w}}=\mathbf{x}^T\hat{\mathbf{w}}+0=\mathbf{x}^T\hat{\mathbf{w}}+k\mathbf{x}^T\bm{a}=\mathbf{x}^T(\mathbf{w}+k\bm{a})

Следовательно, если матрица XTXX^T X необратима и аналитическая оценка весов не определена, то нужно уменьшить число признаков через отбор признаков/снижение размерности.