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

После этого модуля вы сможете

• Читать скалярное произведение как похожесть, а матрицу — как преобразование, а не как таблицу чисел.
• Вывести линейную регрессию из геометрии, а не запомнить формулу.
• Объяснить, почему остаток регрессии ортогонален признакам, и проверить это численно.
• Посчитать PCA руками через собственные векторы ковариации.
• Сказать по числу обусловленности, будет ли задаче тяжело в модуле 4.

Время: около двух недель. Пререквизиты: модуль 2. Ноутбук: 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\). Тень, которую вектор отбрасывает на прямую. Через две страницы из этого выведется регрессия.

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

Матрица выглядит как таблица чисел. Работает как функция: берёт вектор, возвращает вектор.

\[y = Ax\]

Ключ к пониманию — посмотреть, что происходит со столбцами:

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

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

Отсюда сразу два следствия, которые обычно заучивают отдельно.

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

Умножение матриц \(AB\) — это применить \(B\), потом \(A\). Некоммутативность перестаёт быть странностью: повернуть и растянуть — не то же, что растянуть и повернуть.

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

Теперь первая настоящая задача.

Есть \(n\) объектов, у каждого \(d\) признаков. Матрица \(X\) размера \(n \times d\): строка — объект, столбец — признак. Вектор ответов \(y\) длины \(n\). Ищем веса \(w\), чтобы \(Xw\) было близко к \(y\).

Точного решения обычно нет: \(y\) лежит в \(n\)-мерном пространстве, а \(Xw\) пробегает всего \(d\)-мерное пространство столбцов. При \(n > d\) попасть точно нельзя.

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

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

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

Раскрываем и получаем нормальное уравнение:

\[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 целиком:

1. Центрировать данные.
2. Посчитать ковариационную матрицу.
3. Взять её собственные векторы и числа.
4. Отсортировать по убыванию собственных чисел.
5. Первые \(k\) векторов — новые оси, доля объяснённой дисперсии — доля суммы их собственных чисел.

Пять строк на NumPy, и ни одной библиотечной функции сложнее eigh.

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

Последний сюжет, и он мост в следующий модуль.

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

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

Оно говорит, насколько по-разному матрица растягивает пространство по разным осям. \(\kappa\) около единицы — облако круглое. \(\kappa\) в тысячу — облако вытянуто в тысячу раз, длинный узкий овраг.

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

Для градиентного спуска, который начнётся в модуле 4, большое \(\kappa\) означает, что спуск будет зигзагом по стенкам оврага вместо движения по дну. Это главная причина, по которой признаки нормализуют, и она геометрическая, а не гигиеническая.

Практика

Часть 1. Ноутбук

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

Что внутри:

1. Косинусная близость на игрушечных эмбеддингах. Почему без деления на длину не работает.
2. Матрица как преобразование: смотрим, что происходит с единичным квадратом.
3. Регрессия через нормальное уравнение руками, сверка с lstsq.
4. Проверка ортогональности остатка. Число, которое должно быть нулём.
5. PCA руками через eigh, сверка с перебором направлений.
6. Число обусловленности: делаем два почти одинаковых признака и смотрим, что происходит с весами.

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

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

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

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

Задание

1. Докажите на бумаге, что если \(u\) единичной длины, то проекция \(x\) на \(u\) равна \((x \cdot u)u\). Двух строк достаточно.
2. Выведите нормальное уравнение самостоятельно, не подглядывая в текст. Начните с фразы «остаток перпендикулярен столбцам».
3. Возьмите матрицу \(2 \times 2\) по своему вкусу. Найдите её собственные векторы вручную, через характеристическое уравнение. Проверьте np.linalg.eig.
4. Постройте набор данных, у которого первая главная компонента объясняет больше 95 % дисперсии. Постройте другой, где первые две объясняют меньше 60 %. Опишите словами, чем отличаются облака.
5. Возьмите регрессию из практики и найдите признак с наибольшим по модулю весом. Означает ли это, что он самый важный? Отмасштабируйте признаки и пересчитайте. Ответ изменился?

Проверка себя

1. Что означает скалярное произведение, равное нулю? Большое положительное?
2. Почему косинусная близость делится на длины?
3. Что такое пространство столбцов и почему регрессия не может выйти за его пределы?
4. Из какой геометрической фразы следует нормальное уравнение?
5. Почему остаток ортогонален признакам? Как это проверить одной строкой кода?
6. Что такое собственный вектор на словах, без формулы?
7. Почему первая главная компонента — собственный вектор ковариационной матрицы?
8. Что предвещает большое число обусловленности — для весов регрессии и для градиентного спуска?

Дальше

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

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