Статистика

Эмпирические процессы и VC-теория

Почему статистический алгоритм, хорошо работающий на обучающих данных, обобщается на новые примеры? Какова математическая причина генерализации?

  • **TensorFlow Probability:** тест Колмогорова-Смирнова для goodness-of-fit за O(n log n) - следствие теоремы Донскера об эмпирическом процессе
  • **Теория обучения (PAC-learning):** гарантии обобщения нейросетей через сложность Радемахера класса функций
  • **Обнаружение data drift:** двухвыборочные тесты в продакшн-ML системах для мониторинга сдвига входного распределения
  • **Квантильная регрессия:** равномерная сходимость эмпирических квантилей - следствие теории VC и эмпирических процессов

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

  • Закон больших чисел
  • Центральная предельная теорема
  • Эмпирическая функция распределения
  • Высокоразмерная статистика
  • Непараметрические тесты

Эмпирические процессы и теорема Гливенко-Кантелли

Эмпирическая мера P_n = (1/n)∑δ_{X_i} аппроксимирует истинное распределение P. Теорема Гливенко-Кантелли гарантирует равномерную сходимость sup_x|F̂_n(x) − F(x)| → 0 почти наверное - это «фундаментальная теорема статистики». Эмпирический процесс G_n(f) = √n(P_nf − Pf) изучает скорость и предельное распределение этого отклонения для целого класса функций F. Теорема Донскера: при конечном энтропийном интеграле G_n сходится к гауссовскому процессу в пространстве ограниченных функций.

Чем теорема Гливенко-Кантелли сильнее поточечного закона больших чисел?

УЗБЧ: для каждого фиксированного x предел F̂_n(x) → F(x) п.н. - сходимость в одной точке. Гливенко-Кантелли: sup по всем x одновременно стремится к 0 п.н. Это равномерная сходимость, более мощное утверждение. Скорость у обоих O(1/√n) по неравенству Дворецкого-Кифера-Вольфовица: P(√n·sup|F̂_n−F| > t) ≤ 2e^{−2t²}.

VC-размерность и равномерная сходимость (теорема Донскера)

VC-размерность d_VC(F) - комбинаторная характеристика сложности класса функций: максимальное число точек, которые F может разбить (shatter) во всех 2^n конфигурациях бинарных меток. Ключевой результат Вапника-Червоненкиса: равномерный УЗБЧ выполняется тогда и только тогда, когда d_VC(F) < ∞. Это обеспечивает теоретическое основание PAC-обучаемости: конечная VC-размерность эквивалентна тому, что класс F PAC-обучаем.

Почему функция sin(kx) имеет VC-размерность ∞, хотя зависит только от одного параметра k?

Для любых n точек x₁ < x₂ < ... < xₙ и любой бинарной разметки (y₁,...,yₙ) ∈ {±1}ⁿ существует k (с достаточно высокой частотой), такое что sign(sin(kxᵢ)) = yᵢ для всех i. Это означает, что {sign(sin(kx)): k > 0} разбивает любое конечное множество. Число параметров не определяет VC-размерность: важна функциональная форма.

Функциональные классы и сложность Радемахера

Сложность Радемахера R_n(F) - более тонкая, зависящая от данных мера гибкости класса функций F. Она измеряет, насколько хорошо F согласуется со случайным шумом: если F может подогнать любой случайный паттерн, R_n высокая. Неравенства обобщения через R_n острее VC-bounds: они зависят от конкретного распределения P, а не от наихудшего случая. Неравенство Дудли связывает R_n с энтропийным интегралом - метрикой сложности функционального класса.

Почему bounds обобщения через сложность Радемахера R_n острее, чем через VC-размерность d_VC?

d_VC(F) - наихудший случай: максимальное число разбиваемых точек при любом распределении. R_n(F) измеряет сложность F именно на данных из P. Для «хорошего» P класс F может быть гораздо проще, чем d_VC предсказывает. Эмпирическая R̂_n ещё острее: она зависит от конкретной обучающей выборки X₁,...,Xₙ, а не только от P.

Эмпирические процессы и машинное обучение

Теория эмпирических процессов обеспечивает теоретическое основание для гарантий обобщения в ML.

  • PAC-обучение — Теоретическая основа: PAC-обучаемость эквивалентна конечной VC-размерности
  • Глубокое обучение — Bounds обобщения нейросетей через сложность Радемахера и норму весов
  • Множественное тестирование — Контроль FWER через эмпирические процессы и неравенство Дворецкого-Кифера-Вольфовица

Итоги

  • Гливенко-Кантелли: sup_x|F̂_n(x)−F(x)| → 0 п.н. - равномерная сходимость эмпирической CDF
  • Эмпирический процесс G_n(f) = √n(P_nf − Pf); теорема Донскера: G_n →d G (гауссовский процесс) при конечном энтропийном интеграле
  • VC-размерность d_VC(F): max число shattering-точек; равномерный УЗБЧ ↔ d_VC < ∞
  • Лемма Сауэра-Шелаха: m_F(n) ≤ (en/d)^d при d_VC = d - полиномиальный рост функции роста
  • Неравенство VC: sup|P_nf−Pf| ≤ C√(d_VC·log n / n) с высокой вероятностью
  • Сложность Радемахера R_n(F): distribution-dependent мера гибкости; bound ≤ 2R_n + √(log(1/δ)/(2n))
  • Неравенство Дудли: R_n(F) ≤ (12/√n)·∫√(log N(ε))dε - связь метрики и генерализации
  • PAC-обучаемость ↔ d_VC < ∞ (теорема Блумера-Эренфейхта)
Эмпирические процессы и VC-теория

0

1

Войти