Практика блока

Блок закрывается кодом. Ниже — что реализовать и какая теория за каждым пунктом стоит. Проверки внизу закрывают два из этих пунктов; остальные стоит сделать в своём репозитории.

1. Линейная регрессия через нормальное уравнение

Задача: найти $\mathbf{w}$ , минимизирующую $\|X\mathbf{w} - \mathbf{y}\|^2$ .

Решение целиком выводится из урока про проекции. Мы ищем ближайшую к $\mathbf{y}$ точку в образе $X$ — то есть проекцию. Остаток обязан быть ортогонален всем столбцам $X$ :

$X^\top(\mathbf{y} - X\mathbf{w}) = \mathbf{0}$

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

\htmlData{k=gram}{X^\top X}\,\htmlData{k=w}{\mathbf{w}} = \htmlData{k=corr}{X^\top \mathbf{y}}

симметрична и неотрицательно определена — значит для неё работает спектральная теорема. Если столбцы $X$ независимы, она обратима, и $\mathbf{w} = (X^\top X)^{-1}X^\top\mathbf{y}$ . Сравните с формулой проекционной матрицы из урока про ортогональность: это она и есть.

2. То же через SVD, и сравнение устойчивости

Подставив $X = U\Sigma V^\top$ , получаем $\mathbf{w} = X^{+}\mathbf{y}$ — псевдообратная из прошлого урока.

Ключевая разница не в ответе, а в устойчивости. Число обусловленности $X^\top X$ равно квадрату числа обусловленности $X$ :

$\kappa(X^\top X) = \kappa(X)^2$

Если $\kappa(X) = 10^{6}$ — совершенно обычное дело для сырых признаков в разных единицах, — то $\kappa(X^\top X) = 10^{12}$ , и при двойной точности от ответа остаётся три-четыре значащих цифры.

Что реализовать: сгенерируйте плохо обусловленную $X$ (например, два почти коллинеарных столбца), решите обоими способами и сравните с истинным $\mathbf{w}$ . Разница будет наглядной. Это, кстати, объяснение того, почему np.linalg.lstsq предпочтителен inv(X.T @ X) @ X.T @ y.

3. PCA с нуля

Алгоритм в четыре строки, и каждая уже разобрана:

Центрировать данные: вычесть среднее по каждому признаку.
Взять ковариационную матрицу $C = \frac{1}{n-1}X^\top X$ — симметричную и неотрицательно определённую.
Найти её собственные векторы (спектральная теорема гарантирует ортонормированный базис).
Спроецировать данные на первые $k$ векторов — это смена базиса с усечением.

Эквивалентно: взять SVD центрированной $X$ и оставить первые $k$ правых сингулярных векторов. Собственные значения $C$ связаны с сингулярными значениями $X$ как $\lambda_i = \sigma_i^2/(n-1)$ .

Центрирование пропускать нельзя. Без него первая главная компонента укажет в сторону среднего, а не в сторону максимальной изменчивости.

4. Сжатие изображения низкоранговым SVD

Прямое применение Эккарта–Янга: загрузите изображение в градациях серого, посчитайте SVD, оставьте $k$ слагаемых. Постройте график зависимости ошибки от $k$ и посмотрите, где картинка становится «достаточно похожей».

Тот же эксперимент в миниатюре — здесь. Сравните, как спад спектра зависит от структуры:

исходная

приближение · k = 2

ранг k 2

спектр

ошибка: 3.831
хранимых чисел: 82 / 400

Ранг 6 против единицы у соседних картинок: резкая граница не разделяется на функцию от строки и функцию от столбца. Для 95% энергии хватает четырёх слагаемых — приближение работает, но экономия куда скромнее.

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

5. Cosine similarity на эмбеддингах

$\operatorname{cos\_sim}(\mathbf{a}, \mathbf{b}) = \frac{\langle \mathbf{a}, \mathbf{b}\rangle}{\|\mathbf{a}\|\,\|\mathbf{b}\|}$

Проверьте поведение при масштабировании: умножьте один вектор на 100 — значение не изменится. Умножьте на $-1$ — сменит знак. Это то, за что её и выбирают: она измеряет направление и сознательно игнорирует длину.

Заодно посмотрите, что происходит с обычным скалярным произведением в том же эксперименте, и почему в attention нормировки на длину нет — там она заменена делением на $\sqrt{d}$ по совсем другой причине, дисперсионной. Разберём в блоке 6.

скалярное произведение: 7.5
норма a: 2.24
норма b: 3.35
косинус: 1
угол: 0°

Векторы выставлены коллинеарно. Потяните любой из них вдоль той же прямой: скалярное произведение поедет, косинус останется единицей.

Экзамен блока

Возьмите статью про LoRA и прочитайте раздел с методом. К этому моменту в формулах не должно остаться незнакомых объектов: низкоранговая поправка $BA$ , ранг $r$ , инициализация, масштабный множитель. Если формулы читаются — блок закрыт.

Источники

Deisenroth, Faisal, Ong — Mathematics for Machine Learning, гл. 9.2 и 10.1–10.4 — Метод наименьших квадратов, PCA
Trefethen, Bau — Numerical Linear Algebra, лекции 11 и 18 — Наименьшие квадраты через QR и SVD, устойчивость нормального уравнения

Почему нормальное уравнение хуже SVD

Столбцы матрицы признаков $X$ почти коллинеарны, $\kappa(X) \approx 10^{6}$ . Отметьте все верные утверждения.
Наименьшие квадраты для прямой

Реализуйте fit_line(xs, ys) — подгонку прямой $y = ax + b$ методом наименьших квадратов. Верните список [a, b].

Это нормальное уравнение для $X$ из двух столбцов — самого $x$ и столбца единиц. Раскрыв $2 \times 2$ систему, получаем закрытые формулы:

$a = \frac{n\sum x_i y_i - \sum x_i \sum y_i}{n\sum x_i^2 - \left(\sum x_i\right)^2}, \qquad b = \frac{\sum y_i - a\sum x_i}{n}$

Знаменатель обращается в нуль, когда все $x_i$ равны: столбцы $X$ становятся пропорциональными, ранг падает, и прямая не определена однозначно. В этом случае верните null (в Python None).

Стоит заметить, что знаменатель — это $n$ , умноженное на дисперсию $x$ . Ровно поэтому предсказуемость страдает, когда признак почти не меняется: делить приходится на почти ноль. Это тот же разговор про обусловленность, только для самой маленькой из возможных задач.

функция fit_line

Загрузка редактора…

Ctrl/⌘ + Enter