Модуль 3. Линейная алгебра как язык¶

Чему вы научитесь в этом модуле

Воспринимать скалярное произведение как меру похожести, а матрицу — как преобразование (функцию), а не просто как таблицу чисел.
Выводить формулу линейной регрессии из геометрических соображений, а не заучивать её наизусть.
Объяснять, почему остаток (ошибка) регрессии ортогонален признакам, и проверять это на практике с помощью вычислений.
Вычислять метод главных компонент (PCA) вручную через собственные векторы ковариационной матрицы.
Определять по числу обусловленности матрицы, будет ли задача в следующем модуле (о производных и оптимизации) вести себя хорошо или плохо.

Время: примерно две недели. Пререквизиты: модуль 2. Ноутбук: открыть в Colab · notebooks/03-linear-algebra.ipynb

Зачем нужна линейная алгебра¶

Линейная алгебра — это не отдельный предмет, который нужно освоить перед тем, как приступить к машинному обучению. Это система записи, на которой всё дальнейшее строится. Слой нейронной сети — это умножение входного вектора на матрицу весов. Эмбеддинг (числовое представление слова или объекта) — это вектор. Похожесть двух текстов вычисляется через скалярное произведение их векторов. Процесс обучения модели — это движение точки в пространстве параметров (весов).

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

Задач в этом модуле будет две: линейная регрессия и метод главных компонент (PCA). Обе не просто предъявляются как готовые формулы, а выводятся пошагово из первых принципов.

Вектор¶

Вектор — это упорядоченный список чисел. Его можно интерпретировать двумя способами, и оба способа постоянно используются.

Вектор как точка. Объект, описываемый тремя числовыми признаками, — это точка в трёхмерном пространстве. Объект с тысячей признаков — это точка в тысячемерном пространстве. Представить такое пространство визуально невозможно, но работать с ним можно без всяких проблем: вся арифметика остаётся той же самой, что и в двух-трёх измерениях.

Вектор как направление и длина. Вектор можно представить как стрелку, выходящую из начала координат. При такой интерпретации понятия «расстояние между объектами» и «угол между направлениями» приобретают чёткий геометрический смысл.

Длина вектора (она же норма):

\[\|x\| = \sqrt{\sum_i x_i^2}\]

Расстояние между двумя объектами — это длина разности их векторов: \(\|x - y\|\).

Скалярное произведение¶

Это ключевая операция всего курса. Она же — одна из наиболее недооценённых в учебниках.

\[x \cdot y = \sum_i x_i y_i = \|x\|\,\|y\|\cos\theta\]

Одна и та же величина, записанная двумя способами. Левая запись (сумма произведений компонент) — это то, что вычисляют. Правая (через длины и косинус угла между векторами) — это то, что позволяет понять геометрический смысл.

Из правой записи следует всё, что нужно знать. Если два вектора указывают примерно в одном направлении (угол между ними маленький), произведение получается большим и положительным. Если они перпендикулярны — произведение равно нулю. Если указывают в противоположные стороны — произведение отрицательное.

Скалярное произведение измеряет степень согласованности направлений двух векторов. Именно поэтому его используют для измерения похожести объектов.

Однако у скалярного произведения есть недостаток: длина вектора мешает. Длинный вектор даёт большое произведение просто потому, что он длинный, а не потому, что направления совпадают. Чтобы устранить этот эффект, произведение делят на длины обоих векторов, и получается косинусная близость:

\[\cos\theta = \frac{x \cdot y}{\|x\|\,\|y\|}\]

Это именно та метрика, на которой основан поиск по эмбеддингам — в том числе гибридный поиск, который рассматривается в модуле 22. Никакой дополнительной «магии» там нет: текст превращается в числовой вектор, и близость между текстами вычисляется как косинус угла между этими векторами.

Проекция вектора \(x\) на направление \(u\) (единичной длины) равна \((x \cdot u)\,u\). Геометрически — это «тень», которую вектор \(x\) отбрасывает на прямую, заданную направлением \(u\). Через две страницы из этого понятия будет выведена вся линейная регрессия.

Матрица как преобразование¶

Матрица внешне выглядит как таблица чисел. Но по существу она работает как функция: получает на вход один вектор, возвращает другой.

\[y = Ax\]

Ключ к пониманию того, что делает матрица, — посмотреть, как результат умножения выражается через столбцы матрицы:

\[Ax = x_1 a_1 + x_2 a_2 + \dots + x_n a_n\]

где \(a_i\) — столбцы матрицы \(A\). Другими словами, результат умножения матрицы на вектор — это линейная комбинация столбцов матрицы, в которой координаты вектора \(x\) играют роль весов (коэффициентов).

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

Во-первых, все возможные результаты \(Ax\) (при различных \(x\)) заполняют так называемое пространство столбцов матрицы — множество всех векторов, которые можно собрать (как линейную комбинацию) из столбцов \(A\). Если матрица \(A\) имеет три столбца, а сами столбцы живут в десятимерном пространстве, то результат умножения может попасть только в трёхмерную «плоскость» внутри этого десятимерного пространства.

Во-вторых, умножение двух матриц \(AB\) — это последовательное применение двух преобразований: сначала \(B\), потом \(A\). При таком понимании факт, что умножение матриц некоммутативно (\(AB \neq BA\)), перестаёт казаться странностью: повернуть объект и потом растянуть — это не то же самое, что сначала растянуть, а потом повернуть.

Линейная регрессия из геометрии¶

Теперь переходим к первой настоящей задаче.

Имеется \(n\) объектов, у каждого из которых измерены \(d\) числовых признаков. Матрица \(X\) имеет размер \(n \times d\): каждая строка — это один объект, каждый столбец — один признак. Также задан вектор ответов \(y\) длины \(n\) (целевая переменная для каждого объекта). Задача: найти вектор весов \(w\) размерности \(d\) такой, чтобы произведение \(Xw\) было как можно ближе к \(y\).

Точного решения, как правило, не существует. Вектор \(y\) живёт в \(n\)-мерном пространстве, а результат \(Xw\) при любых \(w\) может пробегать лишь \(d\)-мерное пространство столбцов матрицы \(X\). При \(n > d\) (объектов больше, чем признаков) попасть точно в \(y\) не удастся.

Раз точного совпадения достичь нельзя, будем искать ближайшую точку. А ближайшая точка плоскости к точке, лежащей вне неё, — это основание перпендикуляра, опущенного из этой точки на плоскость. Это и есть проекция. Таким образом, вся линейная регрессия сводится к одному геометрическому понятию — проекции.

Вектор ошибки \(y - Xw\) обязан быть перпендикулярен пространству столбцов матрицы \(X\), то есть ортогонален каждому столбцу \(X\). Это условие записывается так:

\[X^{\mathsf{T}}(y - Xw) = 0\]

Раскрывая скобки и выражая \(w\), получаем нормальное уравнение:

\[X^{\mathsf{T}}Xw = X^{\mathsf{T}}y \quad\Longrightarrow\quad w = (X^{\mathsf{T}}X)^{-1}X^{\mathsf{T}}y\]

Формула, которую в большинстве курсов просто дают заучить, здесь получилась из одной-единственной геометрической идеи: ближайшая точка к плоскости — это основание перпендикуляра.

Проверяемое следствие

Из вывода следует конкретный факт: остаток регрессии (вектор ошибок) ортогонален каждому столбцу матрицы признаков. Это не абстрактная теория — это можно проверить вычислительно: вычислите скалярное произведение остатка с любым столбцом \(X\), и вы получите число, равное нулю с точностью до машинной погрешности. В ноутбуке это третье задание.

Если скалярное произведение не ноль — значит, вы решили не ту задачу или допустили ошибку в коде. Простой и надёжный тест.

На практике матрицу не обращают напрямую

Код вида np.linalg.inv(X.T @ X) @ X.T @ y даст правильный ответ на учебных данных, но потеряет точность на реальных. Явное обращение матрицы является численно неустойчивой операцией. На практике следует использовать np.linalg.lstsq: эта функция решает ту же самую систему уравнений, но через матричное разложение — без явного обращения, и потому численно устойчиво.

Формулу необходимо понимать. Реализовывать её буквально — не нужно.

Собственные векторы и метод главных компонент (PCA)¶

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

\[Av = \lambda v\]

Здесь \(v\) — собственный вектор матрицы, а \(\lambda\) — соответствующее собственное число (скаляр). Собственные векторы — это выделенные оси преобразования, вдоль которых оно устроено максимально просто: как обычное умножение на число.

Вторая настоящая задача этого модуля — метод главных компонент (PCA) — целиком строится на собственных векторах.

Представьте себе облако точек в многомерном пространстве. Вопрос: вдоль какого направления это облако вытянуто сильнее всего?

Разброс (дисперсия) данных вдоль некоторого направления \(u\) определяется выражением \(u^{\mathsf{T}} C u\), где \(C\) — ковариационная матрица данных. Нам нужно найти направление \(u\) единичной длины, которое максимизирует эту величину — то есть направление наибольшей изменчивости данных.

Ответ: это собственный вектор ковариационной матрицы \(C\), соответствующий её наибольшему собственному числу. А само собственное число равно дисперсии данных вдоль этого направления.

Из этого факта вытекает весь алгоритм PCA:

Центрировать данные (вычесть из каждого признака его среднее значение).
Вычислить ковариационную матрицу центрированных данных.
Найти собственные векторы и собственные числа этой матрицы.
Отсортировать собственные векторы по убыванию соответствующих собственных чисел.
Первые \(k\) собственных векторов образуют новые оси координат, а доля объяснённой ими дисперсии определяется как отношение суммы их собственных чисел к общей сумме всех собственных чисел.

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

Обусловленность¶

Последний сюжет этого модуля, и одновременно — мост к модулю следующему.

Число обусловленности матрицы определяется как отношение наибольшего собственного числа к наименьшему:

\[\kappa = \frac{\lambda_{\max}}{\lambda_{\min}}\]

Оно характеризует, насколько по-разному матрица растягивает пространство вдоль различных осей. Число обусловленности около единицы означает, что облако данных «круглое» — примерно одинаково вытянуто во все стороны. Число обусловленности порядка тысячи означает, что облако вытянуто в тысячу раз сильнее в одном направлении, чем в другом, — длинный узкий «овраг».

Для линейной регрессии большое число обусловленности означает, что матрица \(X^{\mathsf{T}}X\) почти вырождена: два или более признака оказываются почти линейно зависимыми, и найденные веса становятся огромными по модулю и крайне неустойчивыми. Стоит изменить один объект в данных — и веса могут скакнуть драматически.

Для градиентного спуска (который будет подробно рассмотрен в модуле 4) большое число обусловленности означает, что алгоритм будет двигаться зигзагами, отскакивая от стенок оврага, вместо того чтобы эффективно спускаться по его дну. Именно это является главной причиной, по которой признаки нормализуют перед обучением, — и причина эта геометрическая, а не «гигиеническая».

Практическая часть¶

Часть 1. Работа с ноутбуком¶

Откройте notebooks/03-linear-algebra.ipynb.

Что содержится внутри:

Косинусная близость на игрушечных эмбеддингах. Демонстрация того, почему простое скалярное произведение без деления на длины даёт неправильную оценку похожести.
Матрица как преобразование. Визуализация того, что происходит с единичным квадратом при умножении на различные матрицы.
Линейная регрессия через нормальное уравнение руками. Решаем задачу «вручную» и сверяем результат с lstsq.
Проверка ортогональности остатка. Вычисляем число, которое по теории должно быть нулём, и убеждаемся в этом.
PCA руками через eigh. Находим главные компоненты и сравниваем их с результатом перебора направлений.
Число обусловленности. Создаём два почти одинаковых признака и наблюдаем, что происходит с весами регрессии.

Часть 2. Регрессия на собственных данных¶

Возьмите любую таблицу с числовой целевой переменной. Своя, учебная, сгенерированная — не принципиально.

Соберите матрицу признаков \(X\) и вектор ответов \(y\). Добавьте к \(X\) столбец из единиц для свободного члена (интерсепта).
Решите нормальное уравнение с помощью lstsq.
Проверьте, что остаток ортогонален каждому столбцу \(X\) (скалярные произведения должны быть нулями).
Вычислите число обусловленности матрицы \(X^{\mathsf{T}}X\).
Добавьте к данным новый признак, равный сумме двух уже имеющихся. Пересчитайте число обусловленности и веса. Объясните письменно, что произошло и почему.

Пятый пункт — это явление коллинеарности (линейной зависимости признаков) в чистом виде. Увидеть его на собственных данных гораздо полезнее, чем просто прочитать определение в учебнике.

Задание¶

Докажите на бумаге, что если вектор \(u\) имеет единичную длину, то проекция вектора \(x\) на направление \(u\) равна \((x \cdot u)\,u\). Для доказательства достаточно двух строк.
Выведите нормальное уравнение самостоятельно, не подглядывая в текст модуля. Начните с фразы «вектор остатка перпендикулярен столбцам матрицы признаков» и дойдите до формулы для \(w\).
Возьмите произвольную матрицу размера \(2 \times 2\). Найдите её собственные векторы вручную, через характеристическое уравнение \(\det(A - \lambda I) = 0\). Проверьте результат с помощью np.linalg.eig.
Сконструируйте набор данных, у которого первая главная компонента объясняет более 95 % общей дисперсии. Затем сконструируйте другой набор, у которого первые две компоненты вместе объясняют менее 60 %. Опишите словами, чем отличаются облака точек в этих двух случаях.
Вернитесь к регрессии из практической части и найдите признак с наибольшим по модулю весом. Означает ли это, что этот признак является самым важным для предсказания? Отмасштабируйте все признаки (приведите к единичной дисперсии) и пересчитайте веса. Изменился ли ответ? Почему?

Проверка усвоения¶

Что означает скалярное произведение, равное нулю? А большое положительное число?
Зачем в формуле косинусной близости деление на длины векторов?
Что такое пространство столбцов матрицы и почему результат линейной регрессии не может выйти за его пределы?
Из какой единственной геометрической фразы следует нормальное уравнение?
Почему остаток регрессии ортогонален каждому признаку? Как проверить это одной строкой кода?
Что такое собственный вектор — объясните словами, без формул?
Почему первая главная компонента PCA — это собственный вектор ковариационной матрицы?
Что предвещает большое число обусловленности — для весов линейной регрессии и для работы градиентного спуска?

Что дальше¶

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

Матрица — это функция. Скалярное произведение — это мера похожести. Регрессия — это перпендикуляр.