Теория обучаемости и выпуклость нейросетей

Теория обучаемости и выпуклость нейросетей

Когда алгоритм обучения «работает»?

Машинное обучение кажется эмпирической дисциплиной: попробовал — получилось. Но за кулисами существует математическая теория, объясняющая, почему и когда обучение даёт обобщение на новые данные. VC-теория и PAC-обучаемость — это строгие рамки. Выпуклые задачи имеют особые гарантии: независящие от размерности пространства, зависящие только от «сложности» класса гипотез.

VC-размерность

Разбиение (shattering): набор точек S «разбит» гипотезным классом H, если для любой разметки точек ∈ {−1, +1} существует гипотеза h ∈ H, правильно классифицирующая все точки.

VC-размерность vc(H) = максимальное число точек, которое H может разбить.

Примеры:

• Линейные классификаторы в ℝⁿ: vc = n+1. В ℝ² линейный классификатор разбивает любые 3 точки (в общем положении), но не любые 4.
• RBF-ядро: vc = ∞ (может разбить любое число точек). Но SVM с RBF ядром обобщает через маржу!
• Нейросеть с W параметрами: vc ≈ W log W.

Основная теорема VC: конечная vc(H) ↔ PAC-обучаемость (Probably Approximately Correct). Число примеров для (ε, δ)-обучения: N = O((vc(H) + log(1/δ)) / ε²).

Rademacher-сложность для выпуклых функций

Rademacher-сложность — более современная и точная мера, чем VC:

R_N(F) = E_{σ,x} [sup_{f ∈ F} (1/N) Σᵢ σᵢ f(xᵢ)]

где σᵢ — независимые равновероятные ±1 (Rademacher переменные).

Теорема: с вероятностью ≥ 1−δ:

E[f(x)] − (1/N) Σᵢ f(xᵢ) ≤ 2R_N(F) + O(√(log(1/δ)/N))

Для классов с ограниченной нормой ‖w‖ ≤ B и ‖xᵢ‖ ≤ ρ:

R_N(F) ≤ Bρ/√N

Следствие: обобщение ≤ O(Bρ/√N) — не зависит от размерности пространства! Только маржа (1/B) и норма данных (ρ) имеют значение.

Выпуклость нейросетей при сверхпараметризации

Нейросети — невыпуклые задачи. Почему же SGD работает?

Теорема (Kawaguchi, 2016): линейные сети

Для нейросети без нелинейности (f(x) = WₗWₗ₋₁...W₁x):

• Все критические точки (∇L = 0) — либо глобальные минимумы, либо сёдловые точки
• Нет «плохих» локальных минимумов

Для ReLU-сетей достаточной ширины:

Теорема: если ширина скрытого слоя m ≥ N (число обучающих примеров), то: с высокой вероятностью по случайной инициализации, SGD найдёт глобальный минимум обучающей ошибки.

Интуиция: при перепараметризации (m >> N) «плохих» локальных минимумов нет — вес почти случайного блуждания достаточно, чтобы найти решение.

Неявная регуляризация SGD

Феномен implicit bias: SGD не просто ищет любой глобальный минимум — он находит минимум с минимальной нормой.

Теорема: SGD (и gradient flow) для нейросетей сходится к решению минимальной ‖w‖₂-нормы среди всех глобальных минимумов (при линейных сетях).

Это «выпуклость по умолчанию»: SGD неявно решает min ‖w‖² s.t. Xw = y — задачу Ridge-регрессии без явного штрафа!

Двойное убывание (Double Descent)

Классическое машинное обучение: при увеличении числа параметров ошибка сначала убывает (меньше смещение), потом растёт (больше дисперсия) — «кривая U-образной ошибки».

Феномен двойного убывания (Belkin et al., 2019): при перепараметризации (число параметров > число данных) ошибка снова начинает убывать!

• Зона интерполяции: при M < N — классическое обучение
• Порог интерполяции: M = N — ошибка максимальна
• Зона сверхпараметризации: M >> N — ошибка снова убывает

Причина: SGD в зоне сверхпараметризации находит «плоские» минимумы (малый градиент ∇²L) с хорошим обобщением, а не «острые» (большой ∇²L) с плохим.

Полный пример: сравнение алгоритмов

Задача: классификация MNIST (60000 обучающих, 784 признака, 10 классов).

Выпуклые модели дают строгие гарантии, но ограничены в выразительности. Нейросети мощнее, но теория объясняет их работу лишь частично. Задача математиков и ML-исследователей — строить более точные теоретические гарантии для реальных нейросетей.

Двойной спуск и переобучение

Классическая теория обучения предсказывает рост ошибки на тесте при росте сложности модели — кривая «U-образная». Однако современные нейросети демонстрируют феномен двойного спуска: после первого пика ошибки она снова уменьшается при дальнейшем росте параметров. Это противоречит классическим оценкам PAC и Радемахера, основанным на VC-размерности. Объяснение связано с неявной регуляризацией: SGD предпочитает решения с малой нормой, даже когда не делает явного штрафа. Для линейных моделей с переопределённой системой это эквивалентно решению с минимальной L2-нормой.

Современные направления

• Generalization bounds для глубоких сетей: PAC-Bayes даёт нетривиальные оценки для конкретных обученных моделей, основанные на «плоскости» минимума функции потерь
• Лотерейные билеты (Frankle & Carbin, 2019): крупная сеть содержит малую подсеть, обучаемую до сравнимого качества — связано с выпуклостью локальных бассейнов
• Безопасное обучение: convex-concave оптимизация для adversarial training гарантирует устойчивость к атакам