SVM и ядровые методы

SVM и ядровые методы

Идея: максимизировать зазор

Задача классификации: дано N точек (xᵢ, yᵢ), где xᵢ ∈ ℝⁿ и yᵢ ∈ {−1, +1} — метки классов. Нужно найти гиперплоскость, разделяющую два класса. Таких гиперплоскостей бесконечно много — любая разделяющая подойдёт. SVM (Support Vector Machine) выбирает «наилучшую» — ту, которая максимально удалена от обоих классов. Максимальный зазор (margin) означает максимальную устойчивость к новым данным. Элегантность SVM в том, что выбор оптимальной гиперплоскости — задача выпуклого квадратичного программирования.

Примальная задача SVM

Гиперплоскость: wᵀx + b = 0. Класс точки x: sign(wᵀx + b).

Расстояние от точки x₀ до гиперплоскости: |wᵀx₀ + b| / ‖w‖.

Зазор (margin) = 2/‖w‖ (расстояние между двумя параллельными гиперплоскостями wᵀx + b = ±1).

Задача SVM (hard margin): максимизировать зазор при правильной классификации:

max (2/‖w‖) при yᵢ(wᵀxᵢ + b) ≥ 1 для всех i

Эквивалентно:

min_{w, b} (1/2)‖w‖² при yᵢ(wᵀxᵢ + b) ≥ 1

Это выпуклое квадратичное программирование! Уникальное решение (строго выпуклая цель).

Двойственная задача и kernel trick

Лагранжиан: L(w, b, α) = (1/2)‖w‖² − Σᵢ αᵢ [yᵢ(wᵀxᵢ + b) − 1], αᵢ ≥ 0.

Условия ККТ:

• ∂L/∂w = 0: w = Σᵢ αᵢ yᵢ xᵢ
• ∂L/∂b = 0: Σᵢ αᵢ yᵢ = 0

Подставляя в лагранжиан, получаем двойственную задачу:

max Σᵢ αᵢ − (1/2) Σᵢ Σⱼ αᵢ αⱼ yᵢ yⱼ xᵢᵀxⱼ при Σᵢ αᵢ yᵢ = 0, αᵢ ≥ 0

Ключевое наблюдение: входные данные xᵢ входят только через скалярные произведения xᵢᵀxⱼ!

Kernel trick: заменяем xᵢᵀxⱼ на K(xᵢ, xⱼ) — ядровую функцию. Тогда SVM неявно работает в высокоразмерном (возможно, бесконечномерном) пространстве признаков, не вычисляя его явно.

Опорные векторы

Из условий ККТ (дополняющая нежёсткость): αᵢ [yᵢ(wᵀxᵢ + b) − 1] = 0.

Значит αᵢ > 0 только для точек на «марже» — yᵢ(wᵀxᵢ + b) = 1. Это опорные векторы (support vectors) — точки, «ближайшие» к разделяющей гиперплоскости. Их обычно немного: в задаче с 1000 точками — десятки. Только они определяют решение!

Классификация новой точки x: sign(Σᵢ αᵢ yᵢ K(xᵢ, x) + b) — зависит только от ядер с опорными векторами.

Мягкая маржа SVM (Soft Margin)

Когда классы несепарабельны, добавляем «переменные слабины» ξᵢ ≥ 0:

min (1/2)‖w‖² + C Σᵢ ξᵢ при yᵢ(wᵀxᵢ + b) ≥ 1 − ξᵢ, ξᵢ ≥ 0

Параметр C регулирует компромисс: большое C → строгая маржа (мало нарушений), малое C → широкая маржа (разрешено много нарушений). В двойственной задаче: αᵢ ∈ [0, C].

Популярные ядра

Линейное: K(x, y) = xᵀy. SVM становится линейным классификатором.

Полиномиальное: K(x, y) = (xᵀy + 1)^d. Неявно работает в пространстве полиномиальных признаков степени d.

RBF (радиальное): K(x, y) = exp(−‖x−y‖²/(2σ²)). Соответствует бесконечномерному пространству (!) Гауссовых функций. σ — параметр «ширины». При σ → 0: запоминание; при σ → ∞: линейный классификатор.

Полный разбор примера

Данные (2D, 4 точки):

• Класс +1: x₁ = (1, 2), x₂ = (2, 1)
• Класс −1: x₃ = (−1, −2), x₄ = (−2, −1)

Симметрия: w = α₁ y₁ x₁ + α₂ y₂ x₂ + α₃ y₃ x₃ + α₄ y₄ x₄.

По симметрии задачи: α₁ = α₂, α₃ = α₄, и αᵢ yᵢ xᵢ для каждой пары противоположны → w = 2α[(1,2) + (2,1)] = 2α(3,3).

Двойственная задача: max 4α − (1/2) · (4α)² · (5+5+5+5)/(некоторая норма). После вычисления: w = (0.2, 0.2), b = 0. Зазор = 2/‖w‖ = 2/0.283 ≈ 7.07.

Гарантии обобщения

Теорема: с вероятностью ≥ 1−δ (по случайной обучающей выборке), ошибка SVM ограничена:

L(h) ≤ (число ошибок на обучении)/N + O(√((ρ²/γ² + log(1/δ))/N))

Здесь ρ — норма данных, γ — маржа. Размерность пространства не входит! Маржа, а не сложность модели, определяет обобщение. Это теоретическое обоснование: большая маржа = хорошее обобщение.

Метод опорных векторов: математическое ядро

SVM решает задачу классификации, находя гиперплоскость с максимальным зазором между двумя классами. Это естественно формулируется как QP. Двойственная форма имеет особое значение: она зависит только от скалярных произведений xᵢᵀxⱼ между обучающими примерами, что открывает путь к ядерному трюку.

Популярные ядра и их свойства

• Линейное: K(x,y) = xᵀy — для линейно разделимых данных
• Полиномиальное: K(x,y) = (xᵀy + c)^d — для полиномиальной границы степени d
• RBF (Gaussian): K(x,y) = exp(−γ‖x−y‖²) — бесконечномерное ядро, универсальный аппроксиматор
• Sigmoid: K(x,y) = tanh(αxᵀy + c) — связан с нейросетями
• String kernels, graph kernels — для негеометрических данных

Ключевое требование: матрица Грама K_{ij} = K(xᵢ, xⱼ) должна быть положительно полуопределённой (теорема Мерсера). Это гарантирует, что ядро соответствует скалярному произведению в некотором гильбертовом пространстве.

Реализация и масштабирование

Для больших данных стандартный QP не масштабируется. Используются специализированные алгоритмы:

• SMO (Sequential Minimal Optimization, Платт, 1998): итеративно оптимизирует пары множителей Лагранжа
• Pegasos (Шалев-Шварц): стохастический градиентный спуск для линейных SVM
• LIBLINEAR, LIBSVM — стандартные библиотеки

Применения

SVM долгие годы были state-of-the-art в задачах классификации текстов, изображений, биоинформатики. До эры глубокого обучения именно SVM с RBF-ядром выигрывали соревнования по распознаванию рукописных цифр (MNIST), классификации белков, фильтрации спама. Сегодня SVM остаются актуальными для малых датасетов, где глубокие сети переобучаются, и в промышленных применениях с требованием интерпретируемости модели.