Метод опорных векторов

Найдите самую широкую улицу между двумя классами. В этом и состоит вся идея.

Тип: Практика Язык: Python Предварительные требования: Фаза 1 (уроки 08 «Оптимизация», 14 «Нормы и расстояния», 18 «Выпуклая оптимизация») Время: ~90 минут

Цели обучения

• Реализовать линейный SVM с нуля, используя hinge loss и градиентный спуск в прямой (primal) формулировке
• Объяснить принцип максимального зазора и находить опорные векторы в обученной модели
• Сравнить линейные, полиномиальные и RBF-ядра и объяснить, как ядерный трюк позволяет избежать явного отображения в пространство высокой размерности
• Оценить компромисс, которым управляет параметр C, между шириной зазора и ошибками классификации

Проблема

У вас есть две группы точек данных, и необходимо провести линию (или гиперплоскость), разделяющую их. Подходящих линий может быть бесконечно много. Какую выбрать?

Ту, у которой самый большой зазор. Зазор — это расстояние между границей решения и ближайшими точками данных с каждой стороны. Более широкий зазор означает, что классификатор увереннее и лучше обобщает на ранее не встречавшиеся данные.

Эта интуиция приводит к методу опорных векторов (Support Vector Machines, SVM) — одному из наиболее математически элегантных алгоритмов ML. До появления глубокого обучения SVM были главным методом классификации и по-прежнему являются хорошим выбором для небольших наборов данных, данных высокой размерности и задач, где нужна принципиальная, хорошо изученная модель с теоретическими гарантиями.

SVM напрямую связаны с фазой 1: оптимизация выпукла (урок 18), зазор измеряется нормами (урок 14), а ядерный трюк использует скалярные произведения, чтобы обрабатывать нелинейные границы, никогда не выполняя вычислений в пространстве высокой размерности.

Концепция

Классификатор максимального зазора

Пусть есть линейно разделимые данные с метками y_i из {-1, +1} и векторами признаков x_i. Нам нужна гиперплоскость w^T x + b = 0, разделяющая классы.

Расстояние от точки x_i до гиперплоскости равно:

distance = |w^T x_i + b| / ||w||

Для правильно классифицированной точки: y_i * (w^T x_i + b) > 0. Зазор вдвое больше расстояния от гиперплоскости до ближайшей точки с любой из сторон.

Задача оптимизации:

maximize    2 / ||w||     (the margin width)
subject to  y_i * (w^T x_i + b) >= 1  for all i

Эквивалентно (минимизировать ||w||^2 проще):

minimize    (1/2) ||w||^2
subject to  y_i * (w^T x_i + b) >= 1  for all i

Это выпуклая квадратичная задача. У неё есть единственное глобальное решение. Точки данных, лежащие точно на границах зазора (где y_i * (w^T x_i + b) = 1), называются опорными векторами. Только они определяют границу решения. Если переместить или удалить любую точку, не являющуюся опорным вектором, граница не изменится.

Опорные векторы: критически важное меньшинство

Большинство обучающих точек несущественны. Значение имеют только опорные векторы. Поэтому SVM экономно используют память на этапе предсказания: нужно хранить лишь опорные векторы, а не весь обучающий набор.

Количество опорных векторов также даёт оценку сверху для ошибки обобщения. Чем меньше опорных векторов относительно размера набора данных, тем лучше обобщение.

Мягкий зазор: работа с шумом при помощи параметра C

Реальные данные редко бывают идеально разделимыми. Некоторые точки могут оказаться по неправильную сторону границы или внутри зазора. Формулировка с мягким зазором допускает такие нарушения, вводя переменные запаса.

minimize    (1/2) ||w||^2 + C * sum(xi_i)
subject to  y_i * (w^T x_i + b) >= 1 - xi_i
            xi_i >= 0  for all i

Переменная запаса xi_i измеряет, насколько сильно точка i нарушает зазор. Параметр C управляет компромиссом:

Значение C	Поведение
Большое C	Сильно штрафует нарушения. Узкий зазор, меньше ошибочных классификаций. Переобучение
Малое C	Допускает больше нарушений. Широкий зазор, больше ошибочных классификаций. Недообучение

C — это обратная сила регуляризации. Большое C = меньше регуляризация. Малое C = больше регуляризация.

Hinge loss: функция потерь SVM

SVM с мягким зазором можно переписать как задачу оптимизации без ограничений:

minimize    (1/2) ||w||^2 + C * sum(max(0, 1 - y_i * (w^T x_i + b)))

Выражение max(0, 1 - y_i * f(x_i)) — это hinge loss. Оно равно нулю, когда точка классифицирована правильно и находится за пределами зазора. Оно линейно, когда точка лежит внутри зазора или классифицирована неверно.

Hinge loss for a single point:

loss
  |
  | \
  |  \
  |   \
  |    \
  |     \_______________
  |
  +-----|-----|-------->  y * f(x)
       0     1

Zero loss when y*f(x) >= 1 (correctly classified, outside margin).
Linear penalty when y*f(x) < 1.

Сравним с логистической потерей (логистической регрессией):

Hinge:     max(0, 1 - y*f(x))          Hard cutoff at margin
Logistic:  log(1 + exp(-y*f(x)))        Smooth, never exactly zero

Hinge loss даёт разреженные решения: ненулевой вклад вносят только опорные векторы. Логистическая потеря использует все точки данных. Это делает SVM более экономными по памяти при предсказании.

Обучение линейного SVM градиентным спуском

Линейный SVM можно обучить градиентным спуском по hinge loss с L2-регуляризацией, не решая квадратичную задачу с ограничениями:

L(w, b) = (lambda/2) * ||w||^2 + (1/n) * sum(max(0, 1 - y_i * (w^T x_i + b)))

Gradient with respect to w:
  If y_i * (w^T x_i + b) >= 1:  dL/dw = lambda * w
  If y_i * (w^T x_i + b) < 1:   dL/dw = lambda * w - y_i * x_i

Gradient with respect to b:
  If y_i * (w^T x_i + b) >= 1:  dL/db = 0
  If y_i * (w^T x_i + b) < 1:   dL/db = -y_i

Это называется прямой (primal) формулировкой. За одну эпоху она работает за O(n * d), где n — число примеров, а d — число признаков. Для больших разреженных данных высокой размерности, например при классификации текста, это быстро.

Двойственная формулировка и ядерный трюк

Двойственная лагранжева формулировка задачи SVM (из урока 18 фазы 1, условия KKT) имеет вид:

maximize    sum(alpha_i) - (1/2) * sum_ij(alpha_i * alpha_j * y_i * y_j * (x_i . x_j))
subject to  0 <= alpha_i <= C
            sum(alpha_i * y_i) = 0

В двойственной формулировке встречаются только скалярные произведения x_i . x_j между точками данных. В этом и состоит ключевое наблюдение. Если заменить каждое скалярное произведение ядерной функцией K(x_i, x_j), SVM сможет выучить нелинейные границы, никогда не вычисляя преобразование явно.

Linear kernel:      K(x, z) = x . z
Polynomial kernel:  K(x, z) = (x . z + c)^d
RBF (Gaussian):     K(x, z) = exp(-gamma * ||x - z||^2)

RBF-ядро отображает данные в бесконечномерное пространство. У близких точек во входном пространстве значение ядра близко к 1. У далёких друг от друга точек оно близко к 0. Оно может выучить любую гладкую границу решения.

Ядерный трюк вычисляет скалярное произведение в пространстве высокой размерности, фактически не переходя в него. Для полиномиального ядра степени d в D измерениях явное пространство признаков имеет O(D^d) измерений. Но K(x, z) вычисляется за O(D).

SVM для регрессии (SVR)

Регрессия на опорных векторах (Support Vector Regression, SVR) подгоняет вокруг данных трубку ширины epsilon. Точки внутри трубки имеют нулевую потерю. Точки вне трубки штрафуются линейно.

minimize    (1/2) ||w||^2 + C * sum(xi_i + xi_i*)
subject to  y_i - (w^T x_i + b) <= epsilon + xi_i
            (w^T x_i + b) - y_i <= epsilon + xi_i*
            xi_i, xi_i* >= 0

Параметр epsilon управляет шириной трубки. Более широкая трубка = меньше опорных векторов = более гладкая подгонка. Более узкая трубка = больше опорных векторов = более плотная подгонка.

Почему SVM уступили глубокому обучению и когда они по-прежнему побеждают

SVM доминировали в ML с конца 1990-х до начала 2010-х. Глубокое обучение превзошло их по нескольким причинам:

Фактор	SVM	Глубокое обучение
Инженерия признаков	Требуется	Признаки изучаются
Масштабируемость	O(n^2)–O(n^3) для ядер	O(n) на эпоху с SGD
Изображения/текст/аудио	Нужны вручную созданные признаки	Обучается на сырых данных
Большие наборы данных (>100k)	Медленно	Хорошо масштабируется
Ускорение на GPU	Ограниченная польза	Огромное ускорение

SVM по-прежнему выигрывают в следующих случаях:

• Небольшие наборы данных: от сотен до нескольких тысяч примеров
• Разреженные данные высокой размерности: текст с признаками TF-IDF
• Нужны математические гарантии: оценки по зазору
• Время обучения должно быть минимальным: линейный SVM очень быстр
• Бинарная классификация с ясной структурой зазора
• Обнаружение аномалий: одноклассовый SVM

svm-margin

Соберите это

Шаг 1: hinge loss и градиент

Основа. Вычислите hinge loss для пакета и её градиент.

def hinge_loss(X, y, w, b):
    n = len(X)
    total_loss = 0.0
    for i in range(n):
        margin = y[i] * (dot(w, X[i]) + b)
        total_loss += max(0.0, 1.0 - margin)
    return total_loss / n

Шаг 2: линейный SVM через градиентный спуск

Обучайте, минимизируя регуляризованную hinge loss. Решатель QP не нужен.

class LinearSVM:
    def __init__(self, lr=0.001, lambda_param=0.01, n_epochs=1000):
        self.lr = lr
        self.lambda_param = lambda_param
        self.n_epochs = n_epochs
        self.w = None
        self.b = 0.0

    def fit(self, X, y):
        n_features = len(X[0])
        self.w = [0.0] * n_features
        self.b = 0.0

        for epoch in range(self.n_epochs):
            for i in range(len(X)):
                margin = y[i] * (dot(self.w, X[i]) + self.b)
                if margin >= 1:
                    self.w = [wj - self.lr * self.lambda_param * wj
                              for wj in self.w]
                else:
                    self.w = [wj - self.lr * (self.lambda_param * wj - y[i] * X[i][j])
                              for j, wj in enumerate(self.w)]
                    self.b -= self.lr * (-y[i])

    def predict(self, X):
        return [1 if dot(self.w, x) + self.b >= 0 else -1 for x in X]

Шаг 3: ядерные функции

Реализуйте линейное, полиномиальное и RBF-ядра.

def linear_kernel(x, z):
    return dot(x, z)

def polynomial_kernel(x, z, degree=3, c=1.0):
    return (dot(x, z) + c) ** degree

def rbf_kernel(x, z, gamma=0.5):
    diff = [xi - zi for xi, zi in zip(x, z)]
    return math.exp(-gamma * dot(diff, diff))

Шаг 4: определение зазора и опорных векторов

После обучения определите, какие точки являются опорными векторами, и вычислите ширину зазора.

def find_support_vectors(X, y, w, b, tol=1e-3):
    support_vectors = []
    for i in range(len(X)):
        margin = y[i] * (dot(w, X[i]) + b)
        if abs(margin - 1.0) < tol:
            support_vectors.append(i)
    return support_vectors

Полную реализацию со всеми демонстрациями смотрите в code/svm.py.

Используйте это

Со scikit-learn:

from sklearn.svm import SVC, LinearSVC, SVR
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", SVC(kernel="rbf", C=1.0, gamma="scale")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")
print(f"Support vectors: {clf['svm'].n_support_}")

Важно: всегда масштабируйте признаки перед обучением SVM. SVM чувствительны к масштабу признаков, потому что зазор зависит от ||w||, а немасштабированные признаки искажают геометрию.

Для больших наборов данных используйте LinearSVC (прямая формулировка, O(n) на эпоху), а не SVC (двойственная формулировка, O(n^2)–O(n^3)):

from sklearn.svm import LinearSVC

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", LinearSVC(C=1.0, max_iter=10000)),
])

Упражнения

1. Создайте двумерный линейно разделимый набор данных. Обучите свой LinearSVM и найдите опорные векторы. Убедитесь, что опорные векторы — это точки, ближайшие к границе решения.

2. На шумном наборе данных меняйте C от 0.001 до 1000. Постройте границу решения для каждого значения C. Проследите переход от широкого зазора (недообучение) к узкому зазору (переобучение).

3. Создайте набор данных, в котором границы классов имеют форму окружностей, а не являются линейными. Покажите, что линейный SVM не справляется. Вычислите матрицу RBF-ядра и покажите, что классы становятся разделимыми в пространстве признаков, индуцированном ядром.

4. Сравните hinge loss и логистическую потерю на одном наборе данных. Обучите линейный SVM и логистическую регрессию. Посчитайте, сколько обучающих точек вносит вклад в границу решения каждой модели: опорные векторы против всех точек.

5. Реализуйте SVR (нечувствительная к epsilon потеря). Подгоните её к y = sin(x) + noise. Постройте трубку epsilon вокруг предсказаний и выделите опорные векторы — точки вне трубки.

Ключевые термины

Термин	Что он на самом деле означает
Опорные векторы	Обучающие точки, ближайшие к границе решения. Только они определяют гиперплоскость
Зазор	Расстояние между границей решения и ближайшими опорными векторами. SVM его максимизируют
Hinge loss	max(0, 1 - y*f(x)). Равна нулю при правильной классификации вне зазора; иначе даёт линейный штраф
Параметр C	Компромисс между шириной зазора и ошибками классификации. Большое C = узкий зазор, малое C = широкий зазор
Мягкий зазор	Формулировка SVM, допускающая нарушения зазора через переменные запаса. Обрабатывает неразделимые данные
Ядерный трюк	Вычисление скалярных произведений в пространстве признаков высокой размерности без явного отображения в это пространство
Линейное ядро	K(x, z) = x . z. Эквивалент стандартного скалярного произведения. Для линейно разделимых данных
RBF-ядро	K(x, z) = exp(-gamma * ||x-z||^2). Отображает в бесконечное число измерений. Выучивает любую гладкую границу
Полиномиальное ядро	K(x, z) = (x . z + c)^d. Отображает в пространство признаков полиномиальных комбинаций
Двойственная формулировка	Переформулировка задачи SVM, которая зависит только от скалярных произведений между точками данных. Делает возможными ядра
SVR	Support Vector Regression. Подгоняет epsilon-трубку вокруг данных. Точки внутри трубки имеют нулевую потерю
Переменные запаса	xi_i: измеряют, насколько точка нарушает зазор. Равны нулю для правильно классифицированных точек вне зазора
Максимальный зазор	Принцип выбора гиперплоскости, максимизирующей расстояние до ближайших точек каждого класса

Дополнительное чтение

• Vapnik: The Nature of Statistical Learning Theory (1995) — основополагающий текст о SVM и статистическом обучении
• Cortes & Vapnik: Support-vector networks (1995) — исходная статья об SVM
• Platt: Sequential Minimal Optimization (1998) — алгоритм SMO, сделавший обучение SVM практичным
• Документация scikit-learn по SVM — практическое руководство с подробностями реализации
• LIBSVM: A Library for Support Vector Machines — библиотека C++ для SVM, лежащая в основе большинства реализаций

---

Источник: Support Vector Machines 02.04 — Деревья решений и случайные леса · Фаза 2 — Основы машинного обучения · Полный каталог · 02.06 — Метод k ближайших соседей и расстояния