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

Квадратичные формы: язык оптимизации и кривизны

Функция потерь нейросети вблизи минимума - квадратичная форма с матрицей Гессе. Скорость сходимости Adam, необходимость BatchNorm, нестабильность GAN - всё это определяется свойствами этой квадратичной формы: положительна ли она определена, каков её спектр. Квадратичные формы - это язык оптимизации.

  • Оптимизация: функция потерь вблизи минимума - L(w) ≈ ½(w-w*)ᵀH(w-w*), H - матрица Гессе
  • SVM: задача максимизации зазора - квадратичная оптимизация с ограничениями
  • Статистика: тест Махаланобиса - квадратичная форма с матрицей ковариации
  • Физика: кинетическая энергия вращения - квадратичная форма с тензором инерции
  • Экономика: функция полезности второго порядка, анализ стабильности равновесия

Определение и классификация

**Каждый раз, когда градиентный спуск сходится к минимуму - он идёт в точку, где гессиан положительно определён.** Каждый раз, когда Adam застревает на седловой точке - гессиан там неопределён (есть и положительные, и отрицательные собственные значения). Каждый раз, когда GMM или Isolation Forest вычисляет расстояние Махаланобиса - внутри стоит квадратичная форма. Всё это - xᵀAx, скаляр, который один объект говорит о кривизне пространства вокруг точки.

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

Что такое квадратичная форма

Квадратичная форма - это функция вектора x, записанная через симметричную матрицу A:

Q(x) = xᵀ A x (скаляр, A - симметричная матрица) ДЛЯ n = 2 (раскрыто): x = (x₁, x₂), A = [a b] [b c] Q(x) = [x₁ x₂] · [a b] · [x₁] = ax₁² + 2bx₁x₂ + cx₂² [b c] [x₂] ДЛЯ n = 3: Q(x) = a₁₁x₁² + a₂₂x₂² + a₃₃x₃² + 2a₁₂x₁x₂ + 2a₁₃x₁x₃ + 2a₂₃x₂x₃ ГЛАВНОЕ СВОЙСТВО: Q(x) - всегда однородный многочлен степени 2. Q(tx) = t² · Q(x) при любом скаляре t

Интуитивно: квадратичная форма - это обобщение параболы ax² на многомерный случай. Вопрос в том, **где направлена эта парабола** - вверх (минимум), вниз (максимум) или в обе стороны (седло).

Классификация: пять типов форм

Знак Q(x) для всех ненулевых x определяет тип формы - и геометрию поверхности, и поведение оптимизатора:

ТипУсловиеСобств. значения AГеометрияВ оптимизации
Положительно определённаяQ(x) > 0 при x ≠ 0Все λᵢ > 0Параболоид (чаша вверх)Локальный минимум
Отрицательно определённаяQ(x) < 0 при x ≠ 0Все λᵢ < 0Перевёрнутый параболоидЛокальный максимум
Положительно полуопределённаяQ(x) ≥ 0Все λᵢ ≥ 0, есть нулиЦилиндрический параболоидГраница (нет строгого min)
Отрицательно полуопределённаяQ(x) ≤ 0Все λᵢ ≤ 0, есть нулиПеревёрнутый цилиндрГраница
НеопределённаяQ(x) меняет знакЕсть λ > 0 и λ < 0Седловая поверхностьСедловая точка

**Мнемоника через собственные значения**: знак Q(x) полностью определяется знаком собственных значений A. Хочешь знать тип формы - найди собственные значения. Именно это делает функция `np.linalg.eigvalsh` при анализе гессиана.

Что означает положительная определённость квадратичной формы Q(x) = xᵀAx?

Положительная определённость означает Q(x) > 0 при x ≠ 0. Эквивалентно: все собственные значения A положительны. Это центральное свойство для оптимизации: положительно определённый гессиан гарантирует, что найденная критическая точка - минимум.

Диагонализация и геометрия линий уровня

Геометрия: линии уровня и диагонализация

Линии уровня Q(x) = c - это квадрики: эллипсоиды, гиперболоиды, параболоиды. Собственные векторы A задают **главные оси** этих квадрик, собственные значения - **кривизну** вдоль каждой оси.

ТЕОРЕМА: любую Q(x) = xᵀAx можно привести к канонической форме заменой x = Py, где P - матрица из собственных векторов A: Q = xᵀAx = (Py)ᵀ A (Py) = yᵀ (PᵀAP) y = yᵀΛy где Λ = diag(λ₁, ..., λₙ) - матрица собственных значений КАНОНИЧЕСКАЯ ФОРМА: Q = λ₁y₁² + λ₂y₂² + ... + λₙyₙ² ЭТО ЗНАЧИТ: в системе координат из собственных векторов - нет перекрёстных слагаемых yᵢyⱼ - каждый λᵢ - кривизна вдоль i-й оси ПРИМЕР: A = [3 1] λ₁ = 4, λ₂ = 2 [1 3] Q(x) = 3x₁² + 2x₁x₂ + 3x₂² → в диагональных координатах: Q(y) = 4y₁² + 2y₂² Эллипс: полуоси 1/√4 = 0.5 и 1/√2 ≈ 0.707

Что задают линии уровня Q(x) = c положительно определённой квадратичной формы?

В ортонормированном базисе из собственных векторов A форма Q(x) = sum lambda_i y_i^2 = c задаёт эллипсоид с полуосями sqrt(c/lambda_i). Главные оси эллипсоида - собственные векторы A. Это объясняет визуализацию ландшафта функции потерь как кривых уровня вокруг минимума.

Критерий Сильвестра и применения в ML

Критерий Сильвестра: как проверить положительную определённость

Нахождение всех собственных значений для большой матрицы - дорогая операция. **Критерий Сильвестра** (ведущих миноров) позволяет проверить положительную определённость, не считая собственные значения:

МАТРИЦА A положительно определена тогда и только тогда, когда все ведущие миноры положительны: Δ₁ = a₁₁ > 0 Δ₂ = det[a₁₁ a₁₂] > 0 [a₂₁ a₂₂] Δ₃ = det(первые 3 строки и столбца) > 0 ... Δₙ = det(A) > 0 ПРИМЕР: A = [2 1] [1 3] Δ₁ = 2 > 0 ✓ Δ₂ = 2·3 - 1·1 = 5 > 0 ✓ → A положительно определена Собственные значения: λ = (5 ± √5)/2 ≈ 3.618 и 1.382 (оба > 0) ✓

ML-применение №1: гессиан и кривизна функции потерь

Функция потерь L(θ) нейросети в окрестности точки θ₀ раскладывается в ряд Тейлора. Квадратичный член - это квадратичная форма гессиана:

РАЗЛОЖЕНИЕ В ОКРЕСТНОСТИ θ₀: L(θ) ≈ L(θ₀) + ∇L(θ₀)ᵀ·Δθ + (1/2)·ΔθᵀH(θ₀)Δθ + ... где H = ∂²L/∂θᵢ∂θⱼ - матрица Гессе (гессиан) Δθ = θ - θ₀ - отклонение от точки КРИТЕРИЙ МИНИМУМА: В точке θ₀ с ∇L = 0: H положительно определена → θ₀ - локальный минимум H отрицательно определена → θ₀ - локальный максимум H неопределена → θ₀ - седловая точка ДЛЯ КВАДРАТИЧНОЙ ПОТЕРИ (MSE): L(θ) = ||Xθ - y||² = θᵀ(XᵀX)θ - 2yᵀXθ + const H = 2XᵀX XᵀX всегда положительно полуопределена → функция выпукла → минимум единственный!

**Почему Adam работает лучше SGD**: SGD использует одинаковый шаг для всех направлений. Adam адаптирует шаг под каждое направление, приближая **метод Ньютона** (шаг ∝ H⁻¹·∇L). На плохо обусловленном гессиане (вытянутый эллипс) это принципиально.

ML-применение №2: метод Ньютона и K-FAC

**Метод Ньютона** обновляет параметры с учётом кривизны: θ → θ - H⁻¹·∇L. На квадратичных функциях он сходится за один шаг. Но для нейросети с миллионами параметров H⁻¹ не посчитаешь. **K-FAC** (Kronecker-Factored Approximate Curvature) - современный метод, аппроксимирующий гессиан через структуру слоёв, и сходится в несколько раз быстрее Adam.

ЗАДАЧА ОПТИМИЗАЦИИ: min L(θ) → в квадратичном случае: min θᵀHθ/2 - bᵀθ МЕТОД НЬЮТОНА (один шаг на квадратичной функции): θ* = θ₀ - H⁻¹·∇L(θ₀) Для MSE регрессии L = ||Xθ - y||²: H = 2XᵀX ∇L = 2Xᵀ(Xθ - y) θ* = θ₀ - (2XᵀX)⁻¹ · 2Xᵀ(Xθ₀ - y) = (XᵀX)⁻¹ Xᵀy ← нормальное уравнение! То есть метод Ньютона для MSE = точный ответ за один шаг. Это работает только потому, что MSE - квадратичная форма (гессиан постоянный, не зависит от θ).

ML-применение №3: расстояние Махаланобиса и аномалии

Евклидово расстояние не учитывает корреляции признаков. Если признаки "рост" и "вес" коррелированы, точка (2m, 100kg) - нормальная, а (2m, 30kg) - аномалия, хотя евклидово расстояние до центра может быть одинаковым. **Расстояние Махаланобиса** - это квадратичная форма от обратной ковариационной матрицы:

d_M(x, μ)² = (x - μ)ᵀ Σ⁻¹ (x - μ) где μ - среднее распределения Σ - ковариационная матрица Σ⁻¹ - её обратная (всегда существует для невырожденных) ЭТО КВАДРАТИЧНАЯ ФОРМА с матрицей A = Σ⁻¹: d_M² = xᵀAx (в центрированных координатах) Σ⁻¹ всегда положительно определена (т.к. Σ - PSD и невырождена) → d_M² > 0 для любой ненулевой разницы (x - μ) → расстояние корректно определено ДЛЯ ИЗОТРОПНОГО СЛУЧАЯ Σ = σ²I: d_M² = (x-μ)ᵀ(σ²I)⁻¹(x-μ) = ||x-μ||²/σ² → совпадает с нормированным евклидовым

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

  • **Q(x) = xᵀAx** - скаляр, описывающий кривизну пространства вокруг точки; все 5 типов - по знаку собственных значений A
  • **Положительно определённая** (все λ > 0) = параболоид, минимум, сходимость оптимизатора
  • **Критерий Сильвестра**: все ведущие миноры > 0 ⟺ A положительно определена
  • **Гессиан** = квадратичная форма для описания кривизны функции потерь; его знакоопределённость решает судьбу критической точки
  • **MSE выпукла**, потому что гессиан 2XᵀX - всегда PSD; линейная регрессия - единственный глобальный минимум
  • **Расстояние Махаланобиса** = квадратичная форма Σ⁻¹ - учитывает корреляции признаков при обнаружении аномалий
  • **Ковариационная матрица** всегда PSD по построению: Σ = E[(x-μ)(x-μ)ᵀ] ≥ 0

Связи

Квадратичные формы - мост между алгеброй и оптимизацией

  • Собственные векторы и диагонализация — Диагонализация квадратичной формы: собственные векторы = главные оси, собственные значения = кривизна
  • Обратная матрица — Расстояние Махаланобиса требует Σ⁻¹; PSD матрица обратима тогда и только тогда, когда она положительно определена
  • SVD (сингулярное разложение) — SVD раскладывает матрицу через ортогональные базисы - обобщение диагонализации квадратичной формы
  • Процесс Грама-Шмидта — Ортонормированный базис из собственных векторов - это и есть диагонализирующее преобразование квадратичной формы

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

  • stats-21
Квадратичные формы: язык оптимизации и кривизны

0

1

Войти

**Где применяется расстояние Махаланобиса**: GMM (Gaussian Mixture Models) - плотность гауссианы содержит xᵀΣ⁻¹x в показателе. Elliptic Envelope в sklearn для обнаружения аномалий. Калман-фильтр для слияния данных датчиков в robotics и self-driving. Классический LDA (Linear Discriminant Analysis).

Ковариационная матрица - всегда положительно полуопределённая

Ковариационная матрица Σ - особый класс матриц. Она симметрична и **всегда положительно полуопределена** (PSD). Это не случайность - это следствие определения:

Σ = E[(x-μ)(x-μ)ᵀ] ← определение ковариации Для любого вектора v: vᵀΣv = vᵀE[(x-μ)(x-μ)ᵀ]v = E[vᵀ(x-μ)(x-μ)ᵀv] = E[(vᵀ(x-μ))²] ← квадрат скалярной величины ≥ 0 → Σ всегда положительно полуопределена. Если Σ строго положительно определена: - нет полностью коррелированных признаков (нет лин. зависимостей) - Σ⁻¹ существует → расстояние Махаланобиса корректно Если Σ вырождена (det = 0): - какие-то признаки - линейная комбинация других - Σ⁻¹ не существует → нужна регуляризация: Σ_reg = Σ + εI

Квадратичные формы в проде

**xᵀAx - скаляр, за которым стоит вся оптимизация** - **Гессиан функции потерь**: Кривизна L(θ) в точке → тип критической точки. Критерий минимума, метод Ньютона, K-FAC, Natural Gradient - **MSE как квадратичная форма**: L = ||Xθ-y||² = θᵀ(XᵀX)θ - .... XᵀX - PSD матрица, гарантирует выпуклость и единственность минимума - **Расстояние Махаланобиса**: (x-μ)ᵀΣ⁻¹(x-μ) - обнаружение аномалий. GMM, Elliptic Envelope, LDA, Kalman Filter, Isolation Forest - **Регуляризация Ridge (L2)**: L = MSE + λ||θ||² = MSE + λθᵀIθ. Штраф - квадратичная форма с I: (XᵀX + λI)⁻¹ всегда обратима - **Гауссово распределение**: p(x) ∝ exp(-xᵀΣ⁻¹x/2) - квадратичная форма в экспоненте. VAE, normalizing flows, Bayesian inference, GP регрессия - **Условное число матрицы**: κ = λ_max/λ_min - плохая обусловленность гессиана. Медленная сходимость SGD при κ >> 1; Adam и preconditioning лечат

Практика: классификация конических сечений

**Q:** Почему MSE (среднеквадратичная ошибка) выпукла и имеет единственный минимум? - MSE = ||Xθ - y||² = θᵀ(XᵀX)θ - 2yᵀXθ + const - Гессиан H = 2XᵀX - матрица Грама, всегда PSD - Если столбцы X линейно независимы, то H положительно определена - единственный минимум - Именно поэтому линейная регрессия с MSE гарантированно решается нормальным уравнением **Q:** В чём разница между расстоянием Махаланобиса и евклидовым расстоянием? - Евклидово предполагает изотропность - все направления равноценны - Махаланобис учитывает корреляцию и дисперсию признаков через Σ⁻¹ - При Σ = I оба расстояния совпадают - Махаланобис инвариантен к линейным преобразованиям признаков - это ключевое свойство для аномалий **Q:** Что такое седловая точка в оптимизации нейросетей и почему она опасна? - В седловой точке гессиан неопределён: есть и положительные, и отрицательные собственные значения - Градиент = 0 (как в минимуме), но это не минимум - вдоль некоторых направлений потеря убывает - SGD с шумом помогает выбраться из седла - шум нарушает точное равенство градиента нулю - В нейросетях седловые точки многочисленнее локальных минимумов; именно это мотивировало изучение non-convex оптимизации

В чём суть критерия Сильвестра для положительной определённости?

Критерий Сильвестра: матрица A положительно определена тогда и только тогда, когда det(A_k) > 0 для всех k = 1,...,n, где A_k - левая верхняя подматрица размера k. Это O(n³) проверка без вычисления собственных значений - удобно для гессиана в оптимизации.