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

Шаг 1

Представим стандартную задачу

У нас есть очень много каких-то измерений (например, 100)

И всего несколько каких-то признаков (например, 5), несколько входных и один выходной

Наша задача - найти линейную зависимость между признаками, чтобы в среднем выдавать наилучшее предсказание

На примере будет проще:

Пусть у нас есть датасет из 1000 сотрудников с такими данными:

Возраст
Стаж работы
Должность (можно перевести в числа от 0 до 5)
Образование (0 - школа/колледж, 1 - бакалавриат, 2 - магистратура, 3 - PhD)

Как результат у нас зарплата каждого сотрудника

Задача найти наилучшую линейную зависимость между входными данными и зарплатой

Шаг 2

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

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

Попробуем сделать всё наоборот

Возьмём за вектора столбцыданных

В таком случае пространство, в котором будет находится этот вектор имеет огромную размерность (в нашей задаче это 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$

Шаг 3

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

Например, у нас одномерное подпространство (то есть, прямая) и точка не лежащая на этой прямой

Какая точка на прямой ближе всего к точке вне прямой?

Интуитивно понятно, что это точка, получаемая ортогональной проекцией из внешней точки на прямую

Может на картинке будет понятнее:

В данном случае, v задаёт наш один столбец и получается прямая

u - то, что мы должны выразить

Из u падает перпендикуляр на v и мы получаем наилучшее возможное решение

Это называется “псевдорешение”

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

В данном случае жёлтый и фиолетовый вектора образуют плоскость

Красная точка - наше измерение, которое мы хотим приблизить

И проекцией мы получаем нужную нам точку

Остаётся только эту точку разложить по базису жёлтого и фиолетового векторов

Коэффициенты разложения и дадут нужную линейную зависимость

Шаг 4

Алгоритм, который я сейчас описал называется “Метод наименьших квадратов”

Почему квадратов?

Потому что проекция даёт минимальное расстояние от точки до подпространства

А расстояние в евклидовом варианте считается по формуле Пифагора:

\sqrt{\sum_{i=1}^n ({x^i})^2}

Когда мы сравниваем два расстояния корень можно убрать

Поэтому и получается, что задача минимизировать квадраты координат

Шаг 5

Чтобы курс имел хоть какую-то строгость, придётся вывести финальную формулу алгебраически

Вектор разницы между проекцией и изначальным вектором перпендикулярен нашему подпространству

Звучит страшно, но если посмотреть на картинку, это очевидно

Выразим это через стандартное скалярное произведение:

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

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

Шаг 6

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