Orthogonal projections

Из геометрии мы знаем, что для нахождения проекции вектора на прямую или плоскость, надо из его конца опустить перпендикуляр. Вектор, указывающий в точку пересечения перпенидкуляра с прямой/плоскостью, и будет искомой (ортогональной) проекцией. В этом разделе мы займёмся ортогональным проектированием на произвольное подпространство \(\mathbb R^n\).

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

Projection onto a line

Пусть прямая в \(\mathbb R^n\) задана ненулевым вектором \(\boldsymbol a = (a_1, \ldots, a_n)^\mathsf{T}\), и мы хотим найти на этой прямой точку \(\boldsymbol p\), ближайшую к заданной точке \(\boldsymbol x\). Для этого вектор \(\boldsymbol x\) надо спроектировать на прямую \(\mathrm{span}(\boldsymbol a)\); результатом проекции и будет вектор \(\boldsymbol p = c \boldsymbol a\). Проекция \(\boldsymbol p\) характеризуется свойством \(\boldsymbol x - \boldsymbol p \perp \boldsymbol a\), из которого мы и найдём число \(c\):

(47)\[ \boldsymbol a^\mathsf{T}(\boldsymbol x - \boldsymbol p) = 0 \iff \boldsymbol a^\mathsf{T}\boldsymbol x - c\boldsymbol a^\mathsf{T}\boldsymbol a = 0 \iff c = \frac{\boldsymbol a^\mathsf{T}\boldsymbol x}{\boldsymbol a^\mathsf{T}\boldsymbol a}. \]

Итак, наша проекция равна \(\boldsymbol p = \frac{\boldsymbol a^\mathsf{T}\boldsymbol x}{\boldsymbol a^\mathsf{T}\boldsymbol a} \boldsymbol a\). Если вектор \(\boldsymbol a\) единичный, то формула для проекции упрощается до \(\boldsymbol p = \langle \boldsymbol a, \boldsymbol x\rangle \boldsymbol a\).

Отметим два простых, но важных частных случая проекции на прямую:

1. Если точка \(\boldsymbol x\) уже лежит на прямой \(\mathrm{span}(\boldsymbol a)\), \(\boldsymbol x = d \boldsymbol a\), то

   \[ \boldsymbol p = \frac{d\boldsymbol a^\mathsf{T}\boldsymbol a}{\boldsymbol a^\mathsf{T}\boldsymbol a} \boldsymbol a = d \boldsymbol a = \boldsymbol b. \]

   В этом случае проектируемая точка уже лежит на прямой, поэтому ничего искать не надо: её проекция совпадает с ней самой.

2. Если \(\boldsymbol x \perp a\), то \(\boldsymbol a^\mathsf{T}\boldsymbol x = 0\) и \(\boldsymbol p = \boldsymbol 0\). Это хорошо известное из геометрии и физики свойство: проекция перпендикулярного вектора равна нулю.

Проектирование вектора \(\boldsymbol x\) на прямую \(\mathrm{span}(\boldsymbol a)\) можно записать в виде умножения на одноранговую матрицу \(\boldsymbol P\):

\[ \boldsymbol p = \boldsymbol {Px}, \quad \boldsymbol P = \frac{\boldsymbol a \boldsymbol a^\mathsf{T}}{\boldsymbol a^\mathsf{T} \boldsymbol a}. \]

Матрица \(\boldsymbol P\) является частным случаем матрицы проекции и обладает свойством \(\boldsymbol P^2 = \boldsymbol P\).

Simple linear regression

Consider a simple linear regression model without intercept: \(y = a x\). Given training dataset \(\mathcal D = \{(x_i, y_i)\}_{i=1}^n\), how to find optimal value of \(a\)?

In linear regression we minimize the distance from the target vector \(\boldsymbol y = (y_1, \ldots, y_n)\) and the line specified by the feature vector \(\boldsymbol x = (x_1, \ldots, x_n)\). According (47) we can achieve this by putting

(48)\[ \widehat a = \frac{\boldsymbol x^\mathsf{T} \boldsymbol y}{\boldsymbol x^\mathsf{T} \boldsymbol x} = \frac{\sum\limits_{i=1}^n x_i y_i}{\sum\limits_{i=1}^n x_i^2}\]

Projection onto a subspace

Теперь займёмся поиском проекции вектора \(\boldsymbol x \in \mathbb R^m\) на подпространство \(\mathrm{span}(\boldsymbol a_1, \ldots, \boldsymbol a_n)\), \(n\leqslant m\). Будем считать, что все векторы \(\boldsymbol a_1, \ldots, \boldsymbol a_n\) линейно независимы (в противном случае выкинем лишние). Проекция \(\boldsymbol p\) вектора \(\boldsymbol x\) представляет собой линейную комбинацию

\[ \boldsymbol p = c_1 \boldsymbol a_1 + \ldots + c_n\boldsymbol a_n, \]

что эквивалентно матрично-векторному умножению

\[ \boldsymbol p = \boldsymbol {Ac}, \quad \boldsymbol A = [\boldsymbol a_1 \ldots \boldsymbol a_n], \quad \boldsymbol c = (c_1,\ldots, c_n)^\mathsf{T}. \]

Вектор \(\boldsymbol x - \boldsymbol p\) должен быть ортогонален подпространству \(\mathrm{span(\boldsymbol a_1, \ldots, \boldsymbol a_n)}\), поэтому \(\boldsymbol x - \boldsymbol{Ac} \perp \boldsymbol a_j\) при всех \(j=1, \ldots, n\), т.е.

\[ \boldsymbol a_j^\mathsf{T} (\boldsymbol x - \boldsymbol{Ac}) = 0, \; 1 \leqslant j \leqslant n, \;\iff\; \boldsymbol A^\mathsf{T} (\boldsymbol x - \boldsymbol{Ac}) = \boldsymbol 0. \]

Таким образом, справедливо равенство \(\boldsymbol A^\mathsf{T} \boldsymbol x = \boldsymbol A^\mathsf{T} \boldsymbol{Ac}\). Поскольку \(\mathrm{rank}(\boldsymbol A) =n\), матрица \(\boldsymbol A^\mathsf{T} \boldsymbol A\) обратима, и можно домножить предыдущее равенство на \((\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1}\).

В результате получаем, что

(49)\[\boldsymbol c = (\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1} \boldsymbol A^\mathsf{T} \boldsymbol x,\]

а сама проекция равна

\[ \boldsymbol p = \boldsymbol{Ac} = \boldsymbol A(\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1} \boldsymbol A^\mathsf{T} \boldsymbol x. \]

Отметим, что проекция на прямую является частным случаем проекции на подпространство, когда матрица \(\boldsymbol A\) состоит из одного столбца \(\boldsymbol a\). Проекция на подпространство записывается в виде \(\boldsymbol p = \boldsymbol {Px}\) с помощью матрицы проекции

(50)\[ \boldsymbol P = \boldsymbol A (\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1} \boldsymbol A^\mathsf{T}. \]

Linear regression

Цель задачи регрессии — смоделировать зависимость целевой переменной \(y \in \mathbb R\) от признаков объекта \(\boldsymbol x \in \mathbb R^d\) (\(d\) — число признаков). Линейная регрессия строит линейную модель, которая предполагает линейную зависимость \(y\) от \(\boldsymbol x\). Как мы знаем, всякий линейный функционал из \(\mathbb R^d\) в \(\mathbb R\) может быть записан в виде скалярного произведения

(51)\[ y = \boldsymbol x^\mathsf{T} \boldsymbol w\]

для некоторого фиксированного вектора весов \(\boldsymbol w \in \mathbb R^d\). Правда, в таком случае \(y = 0\) при \(\boldsymbol x = \boldsymbol 0\), что может не соответствовать нашим данным. Поэтому к линейному функционалу добавляют ещё один параметр — свободный член (bias) \(w_0\), и тогда линейная модель (51) приобретает вид

\[ y = \boldsymbol x^\mathsf{T} \boldsymbol w + w_0. \]

Записывать в таком виде линейную регрессию не очень удобно, но свободный член можно учесть в первоначальной записи (51), если добавить ещё один (нулевой) признак, всегда равный единице:

\[\begin{split} \boldsymbol x = \begin{pmatrix} 1 \\ x_1 \\ \vdots \\ x_d\\ \end{pmatrix}, \quad \boldsymbol w = \begin{pmatrix} w_0 \\ w_1 \\ \vdots \\ w_d\\ \end{pmatrix}, \quad y = \boldsymbol x^\mathsf{T} \boldsymbol w. \end{split}\]

Далее будем считать, что этот фиктивный принак уже добавлен, и всякая линейная зависимость между признаками объекта \(\boldsymbol x\) и таргетом \(y\) имеет вид (51).

Для решения задачи регрессии (в том числе линейной) нам, разумеется, нужна обучающая выборка — датасет

\[ \mathcal D = (\boldsymbol x_i, y_i)_{i=1}^n, \]

состоящий из признаков \(\boldsymbol x_i \in \mathbb R^d\) и таргетов \(y_i\in \mathbb R\) \(i\)-го обучающего объекта, \(i=1, \ldots, n\). Такие числовые датасеты удобно записывать в матрично-векторной форме: построчно записанные признаки \(\boldsymbol x_i\) образуют матрицу объект-признак \(\boldsymbol X\) размера \(n\times d\), а таргеты — вектор \(\boldsymbol y\):

\[\begin{split} \boldsymbol X = \begin{pmatrix} \boldsymbol x_1^\mathsf{T} \\ \vdots \\ \boldsymbol x_n^\mathsf{T} \end{pmatrix}, \quad \boldsymbol y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix}. \end{split}\]

Такие обозначения позволяют линейную модель (51) записать единой формулой сразу для всего датасета \(\mathcal D\) как

\[ \boldsymbol y = \boldsymbol{Xw}. \]

Задача линейной регрессии состоит в подборе весов \(\boldsymbol w\) таким образом, чтобы \(\boldsymbol{Xw}\) был как можно ближе к вектору \(\boldsymbol y\). Для этого надо спроектировать вектор \(\boldsymbol y\) на \(C(\boldsymbol X)\). Согласно (49) оптимальный вектор весов \(\widehat {\boldsymbol w}\) равен

(52)\[ \widehat {\boldsymbol w} = (\boldsymbol X^\mathsf{T} \boldsymbol X)^{-1} \boldsymbol X^\mathsf{T} \boldsymbol y \]

Чтобы веса линейной регрессии можно было найти по этой формуле, матрица объект-признак \(\boldsymbol X\) должна иметь линейно независимые столбцы. Если это не так, то между признаками в датасете \(\mathcal D\) есть линейная зависимость (её также называют мультиколлинеарностью). Мультиколлинеарность ломает линейную регрессию, поэтому от неё следует избавляться, например, проредив количество признаков.

Exercises

1. Find the projection matrix onto the line \(x + y = 0\).

2. Prove that \(\boldsymbol P = \frac{\boldsymbol a \boldsymbol a^\mathsf{T}}{\boldsymbol a^\mathsf{T} \boldsymbol a}\), \(\boldsymbol a \ne \boldsymbol 0\), is a projection matrix, i.e., \(\boldsymbol P^2 = \boldsymbol P\).

3. Show that matrix (50) is a projection matrix.

4. Let \(\boldsymbol X \in \mathbb R^{n\times d}\). Estimate the complexity of calculations by formula (52) in terms of big-O.

5. Find the feature matrix \(\boldsymbol X\) for simple linear regression \(y = ax + b\). Applying (52) show that the equalities (9) hold.