2.4. Приближение – это проекция

Представим стандартную задачу.
У нас есть очень много каких-то измерений (например, 100).
И всего несколько каких-то признаков (например, 5), несколько  входных и один выходной.
Наша задача - найти линейную зависимость между признаками, чтобы в среднем выдавать наилучшее предсказание выходных данных по входным.

На примере будет проще:
Пусть у нас есть датасет из 1000 сотрудников с такими данными:
1. Возраст
2. Стаж работы
3. Должность (можно перевести в числа от 0 до 5)
4. Образование (0 - школа/колледж, 1 - бакалавриат, 2 - магистратура, 3 - PhD)
Как результат у нас зарплата каждого сотрудника
Задача найти наилучшую линейную зависимость между входными данными и зарплатой

Попробуем геометрически проинтерпретировать эту задачу

Обычно мы смотрим на строки данных как на вектора (где каждое число за свой признак отвечает)
Попробуем сделать всё наоборот
Возьмём за вектора столбцы данных

В таком случае пространство, в котором будет находится этот вектор имеет огромную размерность (в нашей задаче это 1000)
И таких векторов у нас будет всего чуть-чуть, а именно столько, сколько признаков

Наша задача через эти вектора выразить последний вектор (в примере - зарплату)
Это тоже самое, что рассматривать подпространство, базис которого - наши столбцы
Но проблема в том, что признаков у нас очень мало, а размерность пространства огромная, поэтому, скорее всего, наш вектор зарплат в это подпространство не попадёт и мы выразить его не сможем
Получается, что задача сводится к тому, чтобы найти наиболее близкий вектор к этому подпространству

Если кому-то проще смотреть на кучу индексов, это для вас:

$\begin{matrix} b^1 & \approx & a_1^1 x^1 + a_2^1 x^2 + \dots + a_n^1 x^n \\ b^2 & \approx & a_1^2 x^1 + a_2^2 x^2 + \dots + a_n^2 x^n \\ \vdots & & \vdots \\ b^N & \approx & a_1^N x^1 + a_2^N x^2 + \dots + a_n^N x^n \end{matrix}$

$\begin{pmatrix} b^1 \\ b^2 \\ \vdots \\ b^N \end{pmatrix} \approx \begin{pmatrix} a_1^1 \\ a_1^2 \\ \vdots \\ a_1^N \end{pmatrix} x^1 + \begin{pmatrix} a_2^1 \\ a_2^2 \\ \vdots \\ a_2^N \end{pmatrix} x^2 + \dots + \begin{pmatrix} a_n^1 \\ a_n^2 \\ \vdots \\ a_n^N \end{pmatrix} x^n$

Попробуем сначала решить аналогичную задачу, но в очень маленькой размерности

Например, у нас одномерное подпространство (то есть, прямая) и точка не лежащая на этой прямой
Какая точка на прямой ближе всего к точке вне прямой?
Интуитивно понятно, что это точка, получаемая ортогональной проекцией из внешней точки на прямую
Может на картинке будет понятнее:

В данном случае, v задаёт наш один столбец и получается прямая
u - то, что мы должны выразить
Из u падает перпендикуляр на v и мы получаем наилучшее возможное решение
Это называется "псевдорешение"

В трёхмерном случае картинка будет выглядеть вот так:

В данном случае жёлтый и фиолетовый вектора образуют плоскость
Красная точка - наше измерение, которое мы хотим приблизить
И проекцией мы получаем нужную нам точку
Остаётся только эту точку разложить по базису жёлтого и фиолетового векторов
Коэффициенты разложения и дадут нужную линейную зависимость

Алгоритм, который я сейчас описал называется "Метод наименьших квадратов"
Почему квадратов?
Потому что проекция даёт минимальное расстояние от точки до подпространства
А расстояние в евклидовом варианте считается по формуле Пифагора:
$$\sqrt{\sum_{i=1}^n ({x^i})^2}$$Когда мы сравниваем два расстояния корень можно убрать
Поэтому и получается, что задача минимизировать квадраты координат

Чтобы курс имел хоть какую-то строгость, придётся вывести финальную формулу алгебраически
Вектор разницы между проекцией и изначальным вектором перпендикулярен нашему подпространству 
Звучит страшно, но если посмотреть на картинку, это очевидно
Выразим это через стандартное скалярное произведение:
$A^T (b - Ax) = 0$
Раскрываем
$A^T b - A^T A x = 0$

Переносим
$A^T A x = A^T b$

Умножаем на $(A^TA)^{-1}$:
$x = (A^T A)^{-1} A^T b$

Всё, это финальная формула

Представьте датасет с 1000 строками (наблюдениями) и З признаками (возраст, стаж, образование). Какая размерность пространства, в котором живут векторы этих признаков согласно концепции «столбцов»?