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

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

$$L(\mathbf{w})=\sum_{n=1}^N (\mathbf{x}_n^T\mathbf{w}-y_n)^2\to\min_{\mathbf{w}}$$

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

Тип векторов

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

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

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

$$g(x)=\vert x \vert + 1,\quad f(x)=x^2$$

Но может быть и невыпуклой, как $f(g(x))=(\vert x \vert-1)^2$ для

$$g(x)=\vert x \vert - 1,\quad f(x)=x^2$$

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

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

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

$$\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}$$

Найдем решение аналитически:

$$\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$$ $$\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\in\mathbb{R}^{N\times D}$ и вектора откликов $Y\in \mathbb{R}^N$:

$$X^{T}X\widehat{\mathbf{w}}=X^T Y$$

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

$$\widehat{\mathbf{w}}=(X^{T}X)^{-1}X^{T}Y$$

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

Задача

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

Последнее, в свою очередь, означает линейную зависимость между признаками, т.е. что найдётся такой набор весов $\bm{\alpha}=[\alpha_0,\alpha_1,...\alpha_D]$, что

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

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

$$\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{\alpha}=\mathbf{x}^T(\mathbf{w}+k\bm{\alpha})$$

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