Алгебра
Квадратичные формы
Почему Adam быстрее SGD? Потому что Adam неявно оценивает Hessian (diag). Почему GD медленно сходится на вытянутых эллипсоидах? Число обусловленности κ(H). Квадратичные формы - язык локальной геометрии функции потерь.
- Adam/L-BFGS: используют аппроксимацию Гессиана - diag(H) или full H соответственно
- GDA/LDA/QDA: граница решения = квадратичная форма расстояний Махаланобиса
- VAE: KL-дивергенция между гауссианами = квадратичная форма в пространстве параметров
Предварительные знания
Квадратичная форма: геометрия функции потерь
Кривые уровня функции потерь нейронной сети в окрестности минимума - квадратичные формы в пространстве весов. SVM-ядро - квадратичная форма. Ковариационная матрица Гауссовой смеси задаёт квадратичную форму расстояния Махаланобиса. Это язык второго порядка в ML.
**Квадратичная форма** - функция Q: ℝⁿ → ℝ вида Q(x) = xᵀAx = Σᵢⱼ aᵢⱼxᵢxⱼ, где A - симметричная матрица. Симметрию можно всегда обеспечить: xᵀAx = xᵀ((A+Aᵀ)/2)x.
Для n=2: Q(x₁,x₂) = ax₁² + 2bx₁x₂ + cx₂² с матрицей A = [[a,b],[b,c]]. Коэффициент при перекрёстном члене 2bx₁x₂ делится на 2 - это симметризация.
Геометрически: уровневые поверхности Q(x) = c - это эллипсоиды (для PD матриц). Оси эллипсоида - собственные векторы A, полуоси пропорциональны 1/sqrt(lambda_i). Вытянутый эллипсоид = плохая обусловленность = медленная сходимость градиентного спуска.
Матрица квадратичной формы Q(x) = 3x₁² + 4x₁x₂ + x₂²:
Определённость: PD, PSD, неопределённая
Adam optimizer быстрее SGD потому что неявно оценивает кривизну (diag Гессиана). L-BFGS аппроксимирует полный Гессиан. Тип определённости - ключ к геометрии оптимизации.
A **положительно определена** (PD) если Q(x) > 0 для всех x ≠ 0. Эквивалентно: все собственные значения > 0. **Критерий Сильвестра**: все главные угловые миноры (leading principal minors) > 0.
| Тип | Условие на λ | Критерий Сильвестра | Геометрия |
|---|---|---|---|
| PD (полож. опред.) | все λ > 0 | все угл. миноры > 0 | Эллипсоид |
| PSD (полож. полуопред.) | все λ >= 0 | все миноры >= 0 | Цилиндр/плоскость |
| ND (отриц. опред.) | все λ < 0 | чередующиеся знаки | Перевёрнутый эллипсоид |
| Indefinite (неопред.) | λ разных знаков | - | Гиперболоид/Седло |
В глубоких нейронных сетях большинство критических точек - седловые (indefinite Hessian), а не локальные минимумы. Стохастический GD эффективно «убегает» от них из-за шума. Выпуклая оптимизация к DNN не применима напрямую.
Матрица [[2, 1], [1, 3]] является:
Гессиан и оптимальность
Гессиан H(x) - матрица вторых производных: H[i][j] = ∂²f/∂xᵢ∂xⱼ. Квадратичное приближение вокруг точки x₀:
Условия второго порядка: если ∇f(x*) = 0 и H(x*) PD - локальный минимум. H(x*) ND - локальный максимум. H(x*) indefinite - седловая точка. Число обусловленности κ(H) = λ_max/λ_min определяет скорость сходимости GD.
Гессиан в точке x* имеет eigenvalues λ₁ = 3, λ₂ = -1. Что это?
Ковариационные матрицы и расстояние Махаланобиса
Ковариационная матрица Σ = E[(x-mu)(x-mu)^T] всегда PSD: для любого v, v^T Σ v = E[(v^T(x-mu))²] >= 0. При невырожденном распределении - строго PD.
**Расстояние Махаланобиса** - квадратичная форма с матрицей Σ⁻¹, учитывающая корреляции:
Применения: Gaussian Discriminant Analysis (LDA, QDA), детекция аномалий (точка с большим расстоянием Махаланобиса - аномалия), VAE (ELBO содержит KL-дивергенцию, эквивалентную Махаланобис-расстоянию в пространстве скрытых переменных).
Ковариационная матрица Σ всегда является:
Ключевые идеи
- Q(x) = x^T A x с симметричной A; уровни - эллипсоиды, оси - собственные векторы
- PD: все lambda > 0 <=> критерий Сильвестра (угловые миноры > 0)
- Гессиан H: PD -> минимум, ND -> максимум, indefinite -> седло
- κ(H) = lambda_max/lambda_min - число обусловленности определяет скорость GD
- Σ = E[(x-mu)(x-mu)^T] всегда PSD; d²(x,mu) = (x-mu)^T Σ⁻¹(x-mu) - Махаланобис
Связанные темы
Квадратичные формы - второй порядок в оптимизации:
- Собственные значения — Знаки lambda определяют тип критической точки
- SVD — SVD диагонализирует: сингулярные числа sigma_i = sqrt(lambda_i(A^T A))