Линейная алгебра

SVD: рентген любой матрицы

SVD - единственное разложение, которое работает для любой матрицы любого размера и всегда существует. Netflix Prize 2009: победители использовали SVD для рекомендательной системы. LoRA (2021): fine-tuning LLM через матрицы низкого ранга. PCA, LSA, псевдообратная матрица - всё реализовано через SVD.

  • LoRA: fine-tuning GPT через ΔW = BA, где rank(BA) - мал; гипотеза низкого ранга из SVD
  • PCA: главные компоненты - правые сингулярные векторы матрицы данных
  • Рекомендации: матричная факторизация R ≈ UVᵀ - усечённый SVD
  • Шумоподавление изображений: обнуление малых сингулярных значений
  • Псевдообратная матрица: A⁺ = VΣ⁺Uᵀ - обобщение обращения на любые матрицы

**2006 год. Netflix объявил конкурс с призом в миллион долларов** - улучшить рекомендации фильмов на 10%. Победившая команда использовала одно разложение матрицы. **2021 год. Microsoft и другие компании обнаружили, что дообучать GPT можно без переобучения всех 175 миллиардов параметров** - достаточно добавить две маленьких матрицы малого ранга. Идея называется LoRA и основана на том же разложении. **Это ~SVD~{Singular Value Decomposition - сингулярное разложение}.** Единственное разложение, которое существует для любой матрицы и говорит, какая информация в ней главная, а какая - шум.

**О чём этот урок на самом деле**: не "как разложить матрицу", а как одна идея - "матрица = поворот x растяжение x поворот" - объясняет сжатие изображений, семантику текста, рекомендательные системы и современный fine-tuning языковых моделей. После этого урока фраза "низкоранговое приближение" перестаёт быть магией.

Главная идея: любая матрица - это три простых шага

Любая матрица A размера m x n (даже прямоугольная!) раскладывается в произведение трёх матриц:

**Интуиция через единичный круг**: SVD показывает, как матрица превращает единичный круг в эллипс. Полуоси эллипса - это столбцы U, длины полуосей - это σᵢ, а направления входа - это столбцы V. Три числа описывают всю геометрию преобразования.

Сингулярные значения: иерархия важности

Числа σ₁ ≥ σ₂ ≥ ... ≥ 0 на диагонали Σ называются **сингулярными значениями**. Они упорядочены: первые - самые «крупные», последние - самые «мелкие». Это иерархия важности информации внутри матрицы.

Низкоранговое приближение: теорема Эккарта-Янга

Любую матрицу A ранга r можно представить как сумму r матриц ранга 1. Каждый слагаемый - это σᵢ · uᵢ · vᵢᵀ. Если оставить только k первых (самых крупных) - получится **наилучшее** приближение матрицы рангом k. Это не просто «одно из» приближений - это математически доказанное оптимальное.

**Именно это сделала команда-победитель Netflix Prize**: матрица "пользователь x фильм" (480 тысяч x 17 тысяч, но разреженная) - её SVD-приближение рангом ~200 предсказывало оценки лучше, чем все предыдущие алгоритмы. Приз в $1 000 000 был получен. Статья BellKor's Pragmatic Chaos стала классикой recommender systems.

LoRA: как SVD изменил fine-tuning LLM

Дообучить GPT-3 (175B параметров) под конкретную задачу - раньше это стоило сотни тысяч долларов. **LoRA (Low-Rank Adaptation)** снизила стоимость на два порядка. Ключевая идея прямо вытекает из SVD.

**LoRA сейчас везде**: Stable Diffusion fine-tuning, LLaMA инструкционные варианты, QLoRA (4-bit + LoRA). Если встречается термин "rank" при обучении моделей - это прямая ссылка на SVD. Rank=8 значит: допускаем, что полезные изменения весов лежат в 8-мерном подпространстве.

LSA: как SVD находит смысл в тексте

**Latent Semantic Analysis (LSA)** - предшественник word2vec и BERT. Идея: применить SVD к матрице «термин x документ» и получить скрытую семантику. Слова, которые встречаются в похожих контекстах, окажутся близки в SVD-пространстве - даже если никогда не встречались вместе.

**Sklearn TruncatedSVD** - это именно truncated SVD, не полное разложение. Работает быстро даже на матрицах 100 000 x 50 000 через алгоритм Lanczos/ARPACK. Используется в рекомендательных системах, дедупликации документов, поиске похожих статей.

Псевдообратная матрица через SVD

Обратная матрица существует только для квадратных невырожденных. Для всего остального - **псевдообратная Мура-Пенроуза**. SVD делает её вычисление прозрачным.

SVD vs диагонализация: в чём разница

**Связь с PCA**: если центрировать данные (вычесть среднее) и применить SVD к матрице данных X, то правые сингулярные векторы V - это в точности главные компоненты PCA. Sklearn делает именно это внутри `PCA(svd_solver='full')`.

Практика: SVD матрицы 2x2

SVD: любая матрица - поворот × растяжение × поворот

A = UΣVᵀ: U и V ортогональны (вращения), Σ диагональна (масштабирование). Существует для любой матрицы m×n. Сингулярные значения σ₁ ≥ σ₂ ≥ ... ≥ 0 задают иерархию важности информации.

Как связаны сингулярные значения σᵢ матрицы A и собственные значения AᵀA?

AᵀA = VΣᵀUᵀUΣVᵀ = VΣ²Vᵀ - это диагонализация AᵀA. Собственные значения AᵀA равны σᵢ². Поэтому σᵢ = √λᵢ(AᵀA) ≥ 0 всегда.

Теорема Эккарта-Янга: оптимальное приближение

Aₖ = Σᵢ₌₁ᵏ σᵢuᵢvᵢᵀ - наилучшая матрица ранга k. Никакая другая матрица ранга k не даёт меньшую ошибку. Основа сжатия изображений, PCA, LSA.

LoRA использует ранг r=8 для слоёв GPT 4096×4096. Сколько параметров экономится?

Полная ΔW: 4096×4096 = 16.7M. LoRA: B(4096×8) + A(8×4096) = 65K. Экономия 256x. Это применение теоремы Эккарта-Янга к fine-tuning LLM.

SVD в ML: от Netflix до LoRA

LSA: SVD матрицы term-document извлекает латентную семантику. Netflix Prize: ранговое разложение матрицы user-item. LoRA: низкоранговые дельта-веса для fine-tuning LLM. PCA = SVD центрированной матрицы данных.

Почему для переопределённой системы Ax=b (m>n) используется lstsq, а не inv?

При m>n уравнений больше степеней свободы - точного решения нет. lstsq находит x* = A⁺b = VΣ⁺Uᵀb через псевдообратную, минимизируя ||Ax−b||². inv требует квадратную невырожденную матрицу.

A = U · Σ · Vᵀ (m×n) (m×m) (m×n) (n×n) U - ортогональная матрица (левые сингулярные векторы) Σ - диагональная матрица (сингулярные значения σ₁ ≥ σ₂ ≥ ... ≥ 0) Vᵀ - транспонированная ортогональная матрица (правые сингулярные векторы) ГЕОМЕТРИЯ (что происходит с вектором): 1. Vᵀ · v - поворот входного пространства 2. Σ · ... - растяжение по каждой оси (на σᵢ) 3. U · ... - поворот в выходное пространство ПОЧЕМУ ЭТО РАБОТАЕТ ДЛЯ ЛЮБОЙ МАТРИЦЫ: Диагонализация A = PDP⁻¹ требует квадратной матрицы и не всегда существует. SVD - всегда.

МАТЕМАТИЧЕСКИ: σᵢ = √(λᵢ(AᵀA)) - корень из i-го собственного значения AᵀA ВАЖНЫЕ СВОЙСТВА: σᵢ ≥ 0 всегда (в отличие от собственных значений!) σ₁ ≥ σ₂ ≥ ... отсортированы по убыванию σ₁ = ||A||₂ (спектральная норма = максимальное растяжение) √(σ₁²+...+σᵣ²) = ||A||_F (норма Фробениуса) σ₁/σᵣ = число обусловленности (condition number) ИНТЕРПРЕТАЦИЯ: σ₁ - насколько матрица «растягивает» в главном направлении σₙ - насколько «сжимает» в самом тонком направлении σᵢ ≈ 0 - это направление фактически "схлопнулось" (ранговый дефицит)

ПОЛНОЕ SVD: A = σ₁u₁v₁ᵀ + σ₂u₂v₂ᵀ + ... + σᵣuᵣvᵣᵀ ПРИБЛИЖЕНИЕ РАНГОМ k (берём только первые k): Aₖ = σ₁u₁v₁ᵀ + ... + σₖuₖvₖᵀ ТЕОРЕМА: Aₖ - наилучшее приближение A рангом k: ||A - Aₖ||₂ = σₖ₊₁ ||A - Aₖ||_F = √(σₖ₊₁² + ... + σᵣ²) Никакая другая матрица ранга k не даст меньшую ошибку. ПРИМЕР - сжатие изображения 1000×1000: Полная матрица: 1 000 000 чисел k = 100: 100 · (1000 + 1000 + 1) = 200 100 чисел k = 10: 10 · (1000 + 1000 + 1) = 20 010 чисел Сжатие в 50x при визуально приемлемом качестве.

ОБЫЧНЫЙ FINE-TUNING: W_new = W_pretrained + ΔW (ΔW того же размера - миллиарды параметров) LORA-ГИПОТЕЗА: ΔW имеет низкий ранг - достаточно приближения: ΔW ≈ B · A, где B ∈ ℝ^(d×r), A ∈ ℝ^(r×d), r << d ПРИМЕР: d = 4096 (размер слоя GPT), r = 8 (LoRA rank) Обычный ΔW: 4096 × 4096 = 16 777 216 параметров LoRA (A + B): 2 × 4096 × 8 = 65 536 параметров Сжатие в 256x! ПОЧЕМУ ЭТО РАБОТАЕТ: Изменения при fine-tuning лежат в низкоранговом подпространстве. SVD - теоретическое обоснование этого факта. ПОСЛЕ ОБУЧЕНИЯ: B · A складывается обратно в ΔW = нулевых накладных расходов при инференсе.

ЕСЛИ A = UΣVᵀ, ТО: A⁺ = V · Σ⁺ · Uᵀ ГДЕ Σ⁺ - "обратная" диагональная матрица: Σ⁺[i,i] = 1/σᵢ если σᵢ > 0 Σ⁺[i,i] = 0 если σᵢ = 0 СВОЙСТВА: A · A⁺ · A = A A⁺ · A · A⁺ = A⁺ Для квадратной невырожденной A⁺ = A⁻¹ (совпадает) ПРИМЕНЕНИЕ - метод наименьших квадратов: Задача: найти x для Ax = b при m >> n (переопределённая система) Решение: x = A⁺b (минимизирует ||Ax - b||²) ЭТО ТО, ЧТО ДЕЛАЕТ np.linalg.lstsq() под капотом.

СвойствоДиагонализация A = PDP⁻¹SVD A = UΣVᵀ
ПрименимостьТолько квадратные матрицыЛюбые матрицы (m x n)
СуществованиеНе всегдаВсегда
Матрицы P, U, VP может быть плохо обусловленаU, V ортогональны - численно стабильны
Что на диагоналиСобственные значения (могут быть <0)Сингулярные значения (всегда ≥0)
Лучшее приближениеНет встроенного свойстваТеорема Эккарта-Янга - оптимально
Главное применениеСтепени матриц Aⁿ, exp(A)Сжатие, LSA, LoRA, PCA
  • **LoRA / QLoRA fine-tuning** (Низкоранговые дельта-веса): Дообучение LLaMA, Mistral, Stable Diffusion с rank=4-64. Экономия памяти в 100x+
  • **Рекомендательные системы** (Matrix Factorization): Netflix Prize, SVD++ в Spotify, YouTube. Матрица user-item → низкоранговое разложение
  • **LSA / Semantic search (pre-BERT)** (Latent Semantic Analysis): SVD матрицы term-document. До трансформеров - основной метод семантического поиска
  • **Сжатие изображений** (Rank-k approximation): Rank-50 SVD сохраняет ~95% визуальной информации при 5x сжатии матрицы
  • **PCA (sklearn, numpy)** (Снижение размерности): SVD центрированной матрицы данных. TruncatedSVD для разреженных данных
  • **Численное решение СЛАУ** (lstsq, pinv): np.linalg.lstsq, scipy.linalg.lstsq - SVD под капотом для переопределённых систем

Упражнения

  1. Как связаны сингулярные значения матрицы A и собственные значения матрицы AᵀA? — AᵀA = (UΣVᵀ)ᵀ(UΣVᵀ) = VΣᵀUᵀUΣVᵀ = VΣ²Vᵀ Это ровно диагонализация AᵀA - V содержит собственные векторы Собственные значения AᵀA равны σᵢ² - квадратам сингулярных значений A σᵢ = √λᵢ(AᵀA) - поэтому сингулярные значения всегда неотрицательны
  2. LoRA использует ранг r=8 для слоёв GPT размером 4096x4096. Сколько параметров экономится и почему это работает? — Полная ΔW: 4096x4096 = 16.7M параметров. LoRA: 2 x 4096 x 8 = 65K. Экономия в 256x. Гипотеза LoRA: изменения весов при task-specific fine-tuning имеют низкий внутренний ранг SVD теоретически обосновывает это: если ΔW низкоранговая, её и нужно аппроксимировать B·A После обучения B·A можно слить обратно в веса - нулевых накладных расходов на инференс
  3. Почему для решения переопределённой системы Ax = b (больше уравнений, чем неизвестных) используется lstsq, а не inv? — При m > n точное решение Ax = b почти никогда не существует (больше уравнений чем степеней свободы) lstsq находит x*, минимизирующий ||Ax - b||² - это регрессия в матричной форме Решение x* = A⁺b через псевдообратную = VΣ⁺Uᵀb inv требует квадратную невырожденную матрицу - lstsq работает всегда

Что унести из урока

  • **A = UΣVᵀ**: любая матрица = поворот x растяжение x поворот; U и V ортогональны, всегда существует
  • **σ₁ ≥ σ₂ ≥ ...**: иерархия важности - первые сингулярные значения несут главную информацию
  • **Rank-k приближение**: Aₖ - доказуемо наилучшая матрица ранга k по теореме Эккарта-Янга
  • **LoRA = SVD**: fine-tuning LLM на rank=8 - это предположение о низкоранговости ΔW, оправданное SVD
  • **LSA**: SVD матрицы term-document извлекает латентную семантику; sklearn.TruncatedSVD делает это за одну строку
  • **A⁺ = VΣ⁺Uᵀ**: псевдообратная через SVD - основа lstsq и линейной регрессии при m ≠ n

Связанные темы

SVD объединяет несколько больших идей

  • Собственные векторы и диагонализация — SVD - обобщение диагонализации для любых матриц; σᵢ = √λᵢ(AᵀA)
  • Обратная и псевдообратная матрица — A⁺ = VΣ⁺Uᵀ - самый надёжный способ вычислить псевдообратную
  • Применения линейной алгебры — PCA, нейросети, attention - синтез всего курса через матричные операции

Связанные уроки

  • ml-19-pca
  • ml-19-pca
  • ml-35-word-embeddings
  • stat-14-pca
  • stat-15-factor-analysis
SVD: рентген любой матрицы

0

1

Войти