Статистическая теория обучения

Сложность Радемахера

VC-размерность нейросетей огромна - миллиарды параметров. По VC-теореме никаких полезных гарантий. Но сложность Радемахера видит норму весов, а не число параметров - и даёт реальные оценки.

  • **Глубокое обучение:** Норма весов, а не число параметров, определяет Радемахерову сложность ResNet - объясняет обобщение при миллиардах параметров
  • **Регуляризация:** L2-регуляризация уменьшает норму весов, что напрямую снижает R-hat и улучшает гарантии обобщения через теорему Bartlett-Mendelson
  • **PAC-Bayes:** Байесовский аналог радемахеровского подхода для стохастических классификаторов - используется для анализа dropout-сетей
  • **Спектральная нормализация GAN:** Контроль спектральной нормы слоёв в GAN контролирует сложность Радемахера дискриминатора - обеспечивает стабильность обучения

Предварительные знания

  • Агностическое PAC-обучение
  • Равномерная сходимость
  • Union bound и неравенство Хёффдинга
  • Расширения PAC-обучаемости

Определение сложности Радемахера

Bartlett и Mendelson (2002) доказали: норма весов нейронной сети, а не число параметров, определяет обобщение. ResNet-50 с 25 млн параметров обобщается благодаря неявной регуляризации: сложность Радемахера эффективной гипотезы мала, несмотря на большое число весов.

Что измеряет эмпирическая сложность Радемахера R_n(F)?

R_n(F) = E_sigma[sup_{f ∈ F} (1/n) sum_i sigma_i f(x_i)]. Чем больше класс может коррелировать со случайным шумом, тем выше его сложность. Это distribution-aware замена VC-размерности: учитывает реальное распределение данных.

Границы обобщения через Радемахера

Какая граница обобщения получается через Радемахеровскую сложность?

Mohri-Rostamizadeh-Talwalkar (2018): для любого h ∈ F, с вероятностью 1-delta над выборкой размера n: R(h) <= R_hat(h) + 2*R_n(F) + sqrt(log(2/delta)/(2n)). Радемахер ловит сложность класса; последний член - концентрационная поправка через McDiarmid.

Вычисление Радемахеровской сложности

Радемахерова сложность как измерение памяти класса на случайном шуме - Представьте, что преподаватель показывает студентам случайно помеченные задачи. Если студент может идеально объяснить случайные метки - он зазубрил, а не понял. Сложность Радемахера измеряет эту способность к «зазубриванию». Класс с высокой Радемахеровой сложностью способен объяснить любой шум - значит, он недостаточно ограничен для надёжного обобщения.

Какая граница связывает Радемахеровскую сложность с VC-размерностью?

Объединяя Sauer-Shelah (рост числа дихотомий <= (en/d)^d) с Massart's lemma, получают R_n(F) <= O(sqrt(d * log(n/d) / n)). Это аналог Vapnik-Chervonenkis bounds, но с явной константой. Для классов с конечной нормой Lipschitz - O(L/sqrt(n)).

Связи с другими темами

Радемахерова сложность связывает классическую теорию обобщения с современным анализом нейросетей и байесовскими методами.

  • VC-теория — Связанная тема
  • Спектральная теория нейросетей — Связанная тема
  • PAC-Bayes — Связанная тема
  • Неявная регуляризация SGD — Связанная тема

Итоги

  • R-hat_S(F) - ожидаемая корреляция с Радемахеровским шумом, мера выразительности F на конкретной выборке S
  • Симметризация: L(f) не хуже L-hat_S(f) + 2*R-hat_S(F) + O(sqrt(log(1/δ)/m))
  • Лемма Контрактор: R(φ◦F) <= L_φ · R(F) - позволяет послойный анализ нейросетей
  • Нейросети: R зависит от произведения норм весов, а не числа параметров
  • Связь с VC: R_m(F) <= O(sqrt(VC(F)/m)), но на конкретных данных может быть значительно меньше

Чем сложность Радемахера лучше VC-размерности для анализа нейронных сетей?

Сложность Радемахера учитывает конкретную выборку и норму гипотез. Это позволяет анализировать нейросети с большим числом параметров, где VC-dim даёт слабые гарантии.

Сложность Радемахера

0

1

Войти