Margin-based bounds: почему SVM обобщает

1995 год: Vapnik и Cortes публикуют SVM. Классификатор работает в пространстве бесконечной размерности - но VC-bound предсказывает катастрофу. Классическая теория говорит: чем больше размерность пространства гипотез, тем хуже обобщение. Бесконечная размерность - бесконечный риск. Но SVM работает. В 1998 году Бартлетт объяснил почему: вопрос был задан неправильно. Правильный параметр - не размерность, а расстояние от классификатора до данных.

• Лица на фото: нейросеть работает в пространстве миллионов пикселей, но хорошо обобщает - потому что margin на обучающих данных большой.
• Спам-фильтры 2000-х: SVM с ядром на мешке слов обобщал на новые письма без переобучения - именно margin-based regularization.
• Modern deep learning: implicit bias SGD контролирует эффективный margin - отсюда обобщение overparameterized нейросетей (объяснение через spectral norm bounds).

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

• Rademacher complexity - мера выразительности класса гипотез через случайные метки
• Линейный классификатор: h(x) = sign(w·x + b)
• Скалярное произведение в гильбертовом пространстве

• Rademacher complexity: data-dependent bound

Геометрический margin: что классификатор максимизирует

Линейный классификатор h(x) = sign(w·x + b) делит пространство гиперплоскостью. Каждая точка обучающей выборки находится по какую-то сторону от этой плоскости - и на каком-то расстоянии от неё. Вопрос: какое расстояние важно? Оказывается - расстояние до ближайшей точки. Оно называется геометрическим margin.

Функциональный margin точки (x_i, y_i) - это y_i (w·x_i + b). Он положителен, если классификатор правильно классифицирует точку, и отрицателен иначе. Геометрический margin - нормированная версия: делим на ||w||. Для всей выборки margin γ = min_i y_i (w·x_i) / ||w||. SVM с жёсткими ограничениями (hard-margin SVM) ищет именно гиперплоскость с максимальным γ.

Для нормированного весового вектора ||w|| = 1: γ = min_i y_i (w·x_i + b) Задача hard-margin SVM: max_{w,b} γ s.t. y_i (w·x_i + b) >= γ для всех i Эквивалентная форма (фиксируем γ = 1, минимизируем ||w||^2): min_{w,b} ||w||^2 s.t. y_i (w·x_i + b) >= 1 для всех i Максимизация margin <=> минимизация ||w||^2.

Важно: максимальный margin получается у опорных векторов (support vectors) - точек, лежащих ровно на краю "коридора" шириной 2/||w||. Все остальные точки дальше от гиперплоскости и на решение не влияют. Это не случайность - это ключ к обобщению.

Bartlett 1998: generalization через margin

В 1998 году Пол Бартлетт доказал результат, перевернувший понимание SVM. До него обобщение объяснялось через VC-размерность: чем больше пространство гипотез, тем хуже bound. Для SVM в RKHS (где размерность бесконечная) VC-bound предсказывал бесконечный риск. Бартлетт показал: правильный параметр - не размерность пространства, а margin γ.

Margin bound (Bartlett, 1998): R(h) <= R̂_γ(h) + O( ||w|| / (γ · sqrt(m)) ) где: R(h) - истинный риск (ошибка на тест-данных) R̂_γ(h) - margin loss на обучающей выборке = (1/m) #{i : y_i (w·x_i) < γ} - доля точек внутри margin ||w|| - норма весового вектора γ - margin (расстояние до ближайшей точки) m - размер обучающей выборки Ключевое: размерность входного пространства d не входит в bound! Стандартизированная форма (||w|| = 1): R(h) <= R̂_γ(h) + O( 1 / (γ · sqrt(m)) )

Откуда берётся этот bound? Идея доказательства идёт через Rademacher complexity. Нужно оценить Rad_m(H_γ) - Rademacher complexity класса классификаторов с margin >= γ. Через covering numbers (размер epsilon-покрытия) и теорему Massart получается, что Rad_m(H_γ) = O(||w|| / (γ sqrt(m))). Финальный bound следует из общей теоремы Rademacher: R(h) <= R̂(h) + 2 Rad_m(H) + O(sqrt(log(1/δ)/m)).

Теперь смотрим на SVM. Hard-margin SVM минимизирует ||w||^2 при условии y_i(w·x_i) >= 1 для всех i. Эквивалентно: он минимизирует числитель ||w|| в bound при R̂_γ(h) = 0 (все точки классифицированы с margin >= γ). Soft-margin SVM (с параметром C) балансирует ||w||^2 и количество нарушений margin - это прямая минимизация generalization bound!

Эксперимент показывает: при слишком большом C SVM начинает «жать» обучающие данные, margin уменьшается, ||w|| растёт, generalization bound ухудшается. Оптимальный C - баланс между margin loss на обучении и обобщением. Именно поэтому cross-validation по C работает: мы ищем минимум реального generalization bound.

RKHS, kernel trick и нейросетевые margins

Kernel trick - это следующий шаг. Вместо того чтобы работать в исходном пространстве R^d, мы неявно отображаем данные в пространство признаков H через φ: R^d -> H. Скалярное произведение в H заменяется ядровой функцией: k(x, x') = φ(x)·φ(x'). Пространство H может быть бесконечномерным - например, RBF ядро k(x,x') = exp(-||x-x'||^2 / (2σ^2)) соответствует гауссову пространству признаков бесконечной размерности.

До Bartlett это казалось теоретической проблемой: как классификатор в бесконечномерном пространстве может обобщать? VC-bound через размерность даёт бесконечность. Но margin bound решает эту проблему элегантно: в RKHS margin γ = min_i y_i (w·φ(x_i)) / ||w||_H, и bound зависит только от ||w||_H и γ. Размерность H не играет роли.

Теорема Мерсера: k(x,x') - допустимое ядро <=> существует H и φ: R^d -> H такое, что k(x,x') = <φ(x), φ(x')>_H. В RKHS SVM ищет: min_{w in H} ||w||_H^2 s.t. y_i <w, φ(x_i)>_H >= 1 для всех i По теореме Representer Theorem: w* = sum_i α_i y_i φ(x_i) (только support vectors, α_i > 0) Тогда предсказание: f(x) = <w*, φ(x)>_H = sum_i α_i y_i k(x_i, x) ||w*||_H^2 = sum_{i,j} α_i α_j y_i y_j k(x_i, x_j) Всё вычисляется через ядро k - φ явно не нужна! Margin bound в RKHS: R(h) <= R̂_γ(h) + O( sqrt(sum_{i,j} α_i α_j k(x_i,x_j)) / (γ sqrt(m)) )

Нейросетевые margins - расширение той же идеи на глубокие сети. Bartlett, Foster и Telgarsky (2017) доказали spectral norm bound: для нейросети с L слоями и матрицами весов W_1,...,W_L generalization error ограничен через произведение спектральных норм sigma_max(W_l) и отношение ||w||_F (норма Фробениуса) к margin. Это объясняет, почему overparameterized нейросети с большим margin обобщают несмотря на огромное число параметров.

Spectral norm bound (Bartlett-Foster-Telgarsky 2017): R(h) <= O( (prod_l sigma_max(W_l)) * (sum_l ||W_l||_F^2 / sigma_max(W_l)^2)^(1/2) / (gamma * sqrt(m)) ) где: sigma_max(W_l) - наибольшее сингулярное число матрицы W_l ||W_l||_F - норма Фробениуса (корень из суммы квадратов весов) gamma - margin нейросети на обучающей выборке m - размер обучающей выборки Следствие: SGD + implicit regularization в нейросетях часто контролирует спектральные нормы -> малый bound -> хорошее обобщение. Это активная область исследований (2017-2025).

Итог

• Margin γ = min_i y_i (w·x_i) / ||w|| - расстояние от гиперплоскости до ближайшей точки.
• Bartlett 1998: R(h) <= R̂_γ(h) + O(||w|| / (γ sqrt(m))) - bound не зависит от размерности пространства.
• SVM минимизирует ||w||^2 при условии корректной классификации - это прямая минимизация generalization bound.
• В RKHS margin bound остаётся конечным через ||w||_H = sqrt(sum_ij α_i α_j k(x_i, x_j)) - kernel trick теоретически обоснован.
• Нейросетевые margins (Bartlett-Foster-Telgarsky 2017): bound через произведение спектральных норм - объясняет обобщение deep nets.

Место в теории обучения

Margin bounds - мост между классической VC-теорией и современным пониманием обобщения. VC-теория смотрит на размерность пространства гипотез; margin bounds смотрят на геометрию решения относительно данных. Этот сдвиг позволил обосновать SVM, kernel methods и дал язык для анализа нейросетей.

• Rademacher complexity — Доказательство margin bound идёт через Rademacher - оцениваем Rad_m(H_γ) через covering numbers
• VC-теория — Margin bounds заменяют VC-bound там, где VC-размерность бесконечна (RKHS, нейросети)
• Boosting и AdaBoost — AdaBoost тоже максимизирует margin на обучающей выборке - отсюда его устойчивость к переобучению

Вопросы для размышления

• Если margin γ уменьшается вдвое, как меняется Bartlett bound? Что это означает для числа нужных примеров m?
• Soft-margin SVM с параметром C балансирует ||w||^2 и число нарушений margin. Как это соответствует минимизации generalization bound?
• Почему spectral norm bound для нейросетей аналогичен margin bound для SVM? Что играет роль ||w|| в нейросетевом случае?
• Можно ли построить классификатор с нулевым margin (γ = 0) на обучающей выборке и при этом хорошо обобщать? Что говорит теория?

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

• stat-01-sampling