Эпоха 2 · Фундамент · 1995

10 SVM

Support-Vector Networks · Cortes & Vapnik · Machine Learning
🟧 оригинал выборочно~2 чоригинал ↗
Суть за 20 секунд. Классификатор, максимизирующий зазор до ближайших точек («опорных векторов»). Мягкий зазор терпит ошибки, kernel trick строит нелинейные границы в неявном многомерном пространстве, а задача выпукла — единственный оптимум. Доминировал в классификации ~15 лет.

Контекст

90-е, нейросети не в моде. Вапник и Кортес (Bell Labs) дают мощный и теоретически обоснованный классификатор с выпуклой оптимизацией и сильной генерализацией.

Идея и механизм

Среди всех разделяющих гиперплоскостей берём ту, что максимизирует зазор — расстояние до ближайших точек обоих классов. Большой зазор → лучше обобщение. Soft-margin: slack-переменные разрешают точкам нарушать зазор, параметр C балансирует ширину против числа нарушений. Kernel trick: алгоритм зависит от данных только через скалярные произведения, и заменив их ядром K(x, x′), мы строим линейную границу в неявном многомерном пространстве = нелинейную в исходном.

выпуклая оптимизация Двойственная задача: почему решают только опорные векторы

Прямая задача. Максимизировать зазор = минимизировать норму при условии разделимости:

minw,b 12‖w‖²   при   yi(w·xi + b) ≥ 1

Лагранжиан вводит множители αi ≥ 0; из условий стационарности w = Σ αi yi xi и Σ αi yi = 0. Подстановка даёт двойственную задачу (зависит только от скалярных произведений → сюда и вставляется ядро):

maxα Σi αi − 12 Σi,j αi αj yi yj K(xi, xj)  при  0 ≤ αi ≤ C,  Σi αi yi = 0

Soft-margin = «коробочное» ограничение. Именно мягкий зазор превращает простое αi ≥ 0 в box-constraint 0 ≤ αi ≤ C: верхняя граница C ограничивает влияние любой точки, позволяя ей нарушить зазор за конечный штраф (это и есть slack). При C → ∞ возвращаемся к жёсткому зазору, где нарушения запрещены.

Условие KKT (дополняющая нежёсткость): αi [yi(w·xi+b) − 1] = 0. Значит αi > 0 только у точек на самом зазоре — это и есть опорные векторы; остальные не влияют. Решающая функция:

f(x) = Σi ∈ SV αi yi K(xi, x) + b
scikit-learn SVM с RBF-ядром 
from sklearn.svm import SVC

clf = SVC(kernel='rbf', C=1.0).fit(X, y)   # выпуклая задача → единственный оптимум
print(clf.support_vectors_.shape)          # решают лишь опорные векторы
# f(x) = Σ αᵢ yᵢ K(xᵢ, x) + b,  где αᵢ > 0 только у support vectors
w·x+b=0 зазор опорный вектор
Максимально-зазорная граница (синяя) и «улица» зазора (пунктир). Жирно обведённые точки на краю зазора — опорные векторы; только они определяют решение.
Аналогия. Между двумя районами прокладывают максимально широкую улицу так, чтобы дома обоих районов не залезали на проезжую часть. Положение улицы определяют только дома на самой кромке (опорные векторы) — что в глубине района, неважно. Чем шире улица, тем устойчивее граница к новым домам.

Почему это важно

~15 лет SVM — дефолтный сильный классификатор; и сегодня хорош на малых/средних данных. «Максимизация зазора» и «kernel trick» — общематематические идеи далеко за рамками SVM. Знаменитое пари Вапника (1995): к 2000-му «никто в здравом уме не будет использовать нейросети» — он почти угадал, но deep learning взяло реванш в 2012-м.

Связи

↔ перекликается3. Перцептрон

Оба — линейные разделители, завязанные на зазор γ. Перцептрон зазор лишь использует (для гарантии сходимости), SVM его максимизирует — выбирает самую устойчивую плоскость, а не любую разделяющую.

↔ соперник16. AlexNet

SVM был королём классификации, на который Вапник ставил против нейросетей. AlexNet (2012) разгромно выиграл ImageNet и закрыл эпоху доминирования ядровых методов в зрении — прямой исторический ответ на то пари.

↔ другой классик12. Random Forests

Два столпа «классического ML» 2000-х. SVM — выпуклая оптимизация + ядра, силён в высокой размерности; случайный лес — ансамбль деревьев, силён на табличных данных с разнородными признаками. Оба до сих пор — крепкие бейзлайны вне deep learning.

Вопросы пытливого ума

Kernel trick работает в «бесконечномерном» пространстве (RBF) — почему это не приводит к переобучению?

Потому что сложность контролируется не размерностью пространства, а зазором. Теория Вапника связывает обобщение с margin, а не с числом признаков (как и оценка (R/γ)² у перцептрона). Большой зазор + регуляризация через C ограничивают эффективную ёмкость, даже если неявное пространство бесконечномерно.

Если решают только опорные векторы, зачем хранить все данные при обучении?

Заранее неизвестно, какие точки станут опорными — это выясняет оптимизация. После обучения большинство α равны нулю, и для предсказания нужны только SV (часто малая доля данных) — отсюда компактность модели. Но сама задача обучения смотрит на все пары (отсюда её сложность ~O(n²–n³), что и ограничивает SVM на больших данных).

Почему SVM сдали позиции, хотя теоретически так красивы?

Три причины: (1) плохо масштабируются на миллионы примеров (квадратичная сложность по числу точек); (2) ядро нужно выбирать вручную, а нейросети учат представление сами; (3) на больших данных выученные признаки бьют фиксированные ядра. Красота теории не спасла от того, что deep learning масштабируется лучше.

Что читать в оригинале

Читать выборочно: постановку max-margin, опорные векторы, kernel trick. Вывод двойственной задачи (мат-блок) полезен — это образец, как выпуклую задачу переписывают в форму, куда естественно вставляется ядро.