Метод опорных векторов и ядерный трюк

SVM — самый «математический» из классических алгоритмов и одновременно самый недопонятый. Его обычно запоминают как «тот, где ядра», хотя главная идея — не ядра, а максимальный зазор: из всех разделяющих поверхностей выбрать ту, вокруг которой больше всего пустого места. Ядерный трюк — следствие того, как выглядит решение этой задачи, а не её суть.

Пройдём путь целиком: от геометрии зазора к квадратичному программированию, от двойственной формулировки к опорным векторам, от них — к ядрам, и наконец к вопросу «стоит ли брать SVM сегодня и когда». Понадобятся линейная алгебра из статьи Математика для ML и линейные модели из Линейной и логистической регрессии.

1. Проблема: разделяющих прямых бесконечно много

Возьмём два линейно разделимых класса. Логистическая регрессия найдёт какую-то прямую; персептрон — другую, зависящую от порядка обхода примеров. Обе дадут нулевую ошибку на обучении, и по обучающей выборке их не различить. Но интуитивно ясно, что прямая впритык к точкам одного класса хуже: сдвиньте новую точку на миллиметр — и она окажется по другую сторону.

Вапник формализовал эту интуицию: берём гиперплоскость, максимально удалённую от ближайших точек обоих классов. Ширина «пустой полосы» вокруг границы называется зазором (margin), и её максимизация — не эстетика, а статистический принцип: чем шире полоса, тем меньше эффективная ёмкость семейства решений. Гиперплоскостей с зазором не меньше γ в шаре радиуса R существенно меньше, чем вообще, и оценки обобщения зависят от R²/γ², а не от размерности пространства. Следствие: SVM работает, когда признаков больше, чем объектов, — там, где линейная регрессия рассыпается. Отсюда его десятилетия в биоинформатике и в классификации текстов.

2. Геометрия: что именно мы максимизируем

Гиперплоскость задаётся как wᵀx + b = 0, расстояние от точки до неё — |wᵀx₀ + b| / ‖w‖. Пусть метки y ∈ {−1, +1} (не каприз: такое кодирование делает формулы симметричными). Тогда y(wᵀx + b) / ‖w‖ — расстояние со знаком корректности, положительное при верной классификации; это геометрический отступ, а без деления на норму — функциональный.

Здесь прячется тонкость, из-за которой задача поначалу кажется неразрешимой. Пары (w, b) и (10w, 10b) задают одну и ту же гиперплоскость, но функциональный отступ у второй в десять раз больше — значит, «максимизируй функциональный отступ» бессмысленно: масштабируй w и расти до бесконечности. Лечится канонической нормировкой: потребуем, чтобы у ближайших к границе точек функциональный отступ был ровно 1. Тогда для всех точек yᵢ(wᵀxᵢ + b) ≥ 1, а ширина полосы между wᵀx + b = ±1 равна 2/‖w‖. Максимизировать 2/‖w‖ — то же, что минимизировать ‖w‖²/2. Получаем hard-margin SVM:

минимизировать   (1/2)‖w‖²
при условиях     yᵢ(wᵀxᵢ + b) ≥ 1,   i = 1..n

Это выпуклая квадратичная задача с линейными ограничениями — у неё единственный глобальный минимум. Никаких локальных оптимумов и зависимости от random seed: два запуска на одних данных дадут побитово одинаковую границу. Для 1990-х, когда нейросети застревали в локальных минимумах, это было решающим аргументом (Boyd & Vandenberghe, Convex Optimization, cvxbook).

3. Мягкий зазор: реальные данные не разделимы

Hard-margin задача не имеет решения, если классы пересекаются хотя бы одной точкой, — а они пересекаются всегда: разметка шумная, признаки неполные. Хуже того, даже при формальной разделимости один выброс может сжать зазор почти до нуля. Решение (Cortes & Vapnik, 1995) — переменные ослабления ξᵢ ≥ 0, разрешающие нарушить условие за штраф:

минимизировать   (1/2)‖w‖² + C · Σᵢ ξᵢ
при условиях     yᵢ(wᵀxᵢ + b) ≥ 1 − ξᵢ,   ξᵢ ≥ 0

Смысл ξᵢ: 0 — точка вне полосы и верна; 0 < ξᵢ < 1 — внутри полосы, но на правильной стороне; ξᵢ > 1 — ошибка. Минимальное ξᵢ, удовлетворяющее ограничению, равно max(0, 1 − yᵢ(wᵀxᵢ + b)). Подставим и избавимся от ограничений — получается безусловная задача

минимизировать   (1/2)‖w‖² + C · Σᵢ max(0, 1 − yᵢ f(xᵢ)),   f(x) = wᵀx + b

то есть ровно «функция потерь + L2-регуляризация», где потеря называется hinge loss (кусочно-линейный шарнир). SVM — не экзотика, а линейная модель с конкретной потерей, родная сестра логистической регрессии:

Именно нулевая зона hinge порождает разреженность и опорные векторы; и именно поэтому логистическая регрессия даёт калиброванные вероятности, а SVM — нет (раздел 9).

Смысл C — обратная сила регуляризации. C → ∞ возвращает hard margin (модель цепляется за выбросы); C → 0 делает ‖w‖ крошечным, полосу — огромной, и модель вырождается в мажоритарный класс. В терминах статьи Переобучение и регуляризация C ≈ 1/(2λn): большое C = слабая регуляризация. Подбирать обязательно и только по логарифмической сетке.

4. Двойственная задача и появление опорных векторов

Пока это просто линейная модель. Магия начинается при переходе к двойственной форме. Строим лагранжиан с множителями αᵢ ≥ 0 для основных ограничений и μᵢ ≥ 0 для ξᵢ ≥ 0, приравниваем производные к нулю:

∂L/∂w = 0  ⇒  w = Σᵢ αᵢ yᵢ xᵢ        ← ключевое: w — линейная комбинация обучающих точек
∂L/∂b = 0  ⇒  Σᵢ αᵢ yᵢ = 0
∂L/∂ξ = 0  ⇒  αᵢ = C − μᵢ  ⇒  0 ≤ αᵢ ≤ C   ← мягкий зазор превращается в «коробку» на α

Подставив обратно, получаем двойственную задачу, где исходные w и b исчезли:

максимизировать   Σᵢ αᵢ − (1/2) ΣᵢΣⱼ αᵢ αⱼ yᵢ yⱼ (xᵢᵀxⱼ)
при условиях      0 ≤ αᵢ ≤ C,   Σᵢ αᵢ yᵢ = 0

Два факта, каждый из которых меняет всё. Первый: данные входят только через скалярные произведения xᵢᵀxⱼ. Ни одна координата по отдельности алгоритму не нужна — достаточно матрицы попарных «похожестей»: это дверь для ядра.

Второй: условия Каруша — Куна — Таккера сортируют точки на три класса. Из дополняющей нежёсткости αᵢ[yᵢ f(xᵢ) − 1 + ξᵢ] = 0:

αᵢ = 0        ⇔  yᵢ f(xᵢ) ≥ 1   — точка вне полосы, на решение НЕ влияет
0 < αᵢ < C    ⇔  yᵢ f(xᵢ) = 1   — точка ровно на границе полосы (свободный опорный вектор)
αᵢ = C        ⇔  yᵢ f(xᵢ) ≤ 1   — точка внутри полосы или с ошибкой (связанный опорный вектор)

Так как w = Σ αᵢ yᵢ xᵢ, точки с αᵢ = 0 можно выбросить из обучающей выборки — граница не сдвинется ни на миллиметр. Опорные векторы — те и только те точки, которые касаются полосы или нарушают её; обычно их единицы процентов на чистых данных и десятки процентов на шумных, а их доля — бесплатная диагностика (раздел 11).

Отсюда же берётся b: для любого свободного опорного вектора yᵢ f(xᵢ) = 1, откуда b выражается явно; на практике усредняют по всем свободным опорным векторам ради численной устойчивости.

5. Ядерный трюк: нелинейность даром

Соберём два наблюдения вместе. Классы редко разделимы прямой — но почти всегда разделимы в пространстве большей размерности. Пример: точки на прямой, где «свои» в центре, а «чужие» по краям; порогом их не разделить, но добавьте признак x² — и задача становится тривиальной.

Общая схема: взять отображение φ: ℝᵈ → ℋ и учить линейный SVM там. Проблема очевидна — для полиномов степени p от d признаков размерность растёт как C(d+p, p): при d = 1000, p = 3 это около 10⁸ координат, такой вектор не построить. Но данные входят в двойственную задачу только через скалярные произведения: после отображения нам нужно φ(xᵢ)ᵀφ(xⱼ) — одно число, а вычислить его часто можно, не строя φ вообще:

φ(x) = (x₁², √2·x₁x₂, x₂²)
φ(x)ᵀφ(z) = x₁²z₁² + 2x₁x₂z₁z₂ + x₂²z₂² = (x₁z₁ + x₂z₂)² = (xᵀz)²

Слева — построение трёхмерного вектора, справа — скалярное произведение в исходном ℝ² и возведение в квадрат; для степени p это разница между O(dᵖ) и O(d). Это и есть ядерный трюк: заменяем xᵢᵀxⱼ на k(xᵢ, xⱼ) и получаем линейный SVM в пространстве, которое никогда явно не строим. Функция k годится в ядра, если она симметрична и матрица Грама положительно полуопределена для любой выборки (условие Мерсера) — тогда гарантированно существует φ с k(x,z) = φ(x)ᵀφ(z), а задача остаётся выпуклой. Если подсунуть не-ядро, солвер не упадёт, но выдаст мусор: выпуклость и все гарантии исчезнут.

Сумма и произведение ядер — снова ядро, на этом строится multiple kernel learning. RBF заслуживает отдельного разговора: его пространство признаков бесконечномерно (разложите экспоненту в ряд — получите все степени сразу), а практически RBF-SVM удобно понимать как сглаженный kNN из статьи k ближайших соседей: решение f(x) = Σ αᵢyᵢ k(xᵢ, x) + b — взвешенное голосование опорных векторов с падающим по расстоянию весом. Параметр γ задаёт радиус влияния:

• слишком мало → все точки «похожи на всё», ядро вырождается в константу, модель недообучается до линейной;
• слишком велико → каждая точка влияет только на себя, число опорных векторов стремится к n — заучивание;
• старт: γ = 1/(d · Var(X)), то есть gamma="scale" в scikit-learn — точка отсчёта, но не замена подбору.

Критично: C и γ взаимодействуют, их нельзя подбирать по очереди — только совместной сеткой (раздел 8).

6. Реализация: упрощённый SMO с нуля

Двойственная задача — квадратичное программирование с n переменными и матрицей n×n. Универсальные QP-солверы захлёбываются уже на десятках тысяч точек, поэтому Платт предложил SMO (Sequential Minimal Optimization): оптимизировать по два множителя за раз. Почему два? Ограничение Σ αᵢyᵢ = 0 связывает переменные — изменить одну, не нарушив равенство, нельзя, а для пары есть аналитическое решение без всякого солвера.

АЛГОРИТМ SMO (упрощённо)
  α ← 0, b ← 0
  пока есть точки, нарушающие KKT:
      выбрать i с нарушением KKT; выбрать j (в полной версии — максимизирующий |Eᵢ − Eⱼ|)
      вычислить границы [L, H] для αⱼ из условий коробки и Σαy = 0
      αⱼ ← clip(αⱼ − yⱼ(Eᵢ − Eⱼ)/η,  L, H),   η = 2k(i,j) − k(i,i) − k(j,j)
      αᵢ ← αᵢ + yᵢyⱼ(αⱼ_old − αⱼ)          # сохраняем равенство
      пересчитать b по KKT для свободных множителей

Рабочая реализация на numpy, совпадающая со scikit-learn до последнего опорного вектора:

import numpy as np


def rbf_kernel(A, B, gamma):
    # ||a - b||^2 = ||a||^2 - 2 a·b + ||b||^2 — матрица попарных квадратов расстояний одним махом
    sq = (A ** 2).sum(1)[:, None] - 2 * A @ B.T + (B ** 2).sum(1)[None, :]
    return np.exp(-gamma * np.maximum(sq, 0))  # maximum — защита от -1e-17 из-за округлений


class SimpleSVC:
    """Учебная реализация мягкого SVM через упрощённый SMO (Platt, 1998)."""

    def __init__(self, C=1.0, gamma=0.5, tol=1e-3, max_passes=20, seed=0):
        self.C, self.gamma, self.tol = C, gamma, tol
        self.max_passes, self.rng = max_passes, np.random.default_rng(seed)

    def fit(self, X, y):                      # y ∈ {-1, +1}
        n = len(y)
        K = rbf_kernel(X, X, self.gamma)      # O(n²d) времени и O(n²) памяти — узкое место
        alpha, b, passes = np.zeros(n), 0.0, 0
        while passes < self.max_passes:       # выходим после max_passes проходов без изменений
            changed = 0
            for i in range(n):
                E_i = (alpha * y) @ K[:, i] + b - y[i]        # ошибка на i-м примере
                # нарушение KKT: точка внутри полосы, но α не упёрлось в границу коробки
                viol = (y[i] * E_i < -self.tol and alpha[i] < self.C) or \
                       (y[i] * E_i > self.tol and alpha[i] > 0)
                if not viol:
                    continue
                j = self.rng.integers(n - 1)                  # упрощение: второй индекс наугад
                j = j + 1 if j >= i else j
                E_j = (alpha * y) @ K[:, j] + b - y[j]
                a_i_old, a_j_old = alpha[i], alpha[j]
                # границы отрезка для αⱼ: пересечение коробки [0,C]² и прямой Σαy = const
                if y[i] != y[j]:
                    L, H = max(0.0, a_j_old - a_i_old), min(self.C, self.C + a_j_old - a_i_old)
                else:
                    L, H = max(0.0, a_i_old + a_j_old - self.C), min(self.C, a_i_old + a_j_old)
                if L >= H:
                    continue
                eta = 2 * K[i, j] - K[i, i] - K[j, j]         # вторая производная вдоль прямой
                if eta >= 0:                                  # не строго вогнуто — пропускаем пару
                    continue
                alpha[j] = np.clip(a_j_old - y[j] * (E_i - E_j) / eta, L, H)
                if abs(alpha[j] - a_j_old) < 1e-5:
                    continue
                alpha[i] = a_i_old + y[i] * y[j] * (a_j_old - alpha[j])   # держим Σαy = 0
                b1 = b - E_i - y[i] * (alpha[i] - a_i_old) * K[i, i] \
                             - y[j] * (alpha[j] - a_j_old) * K[i, j]
                b2 = b - E_j - y[i] * (alpha[i] - a_i_old) * K[i, j] \
                             - y[j] * (alpha[j] - a_j_old) * K[j, j]
                if 0 < alpha[i] < self.C:     # свободный опорный вектор задаёт b точно
                    b = b1
                elif 0 < alpha[j] < self.C:
                    b = b2
                else:
                    b = (b1 + b2) / 2
                changed += 1
            passes = passes + 1 if changed == 0 else 0
        sv = alpha > 1e-8                     # разреженность: храним только опорные векторы
        self.X_sv, self.y_sv, self.a_sv, self.b = X[sv], y[sv], alpha[sv], b
        return self

    def decision_function(self, X):
        # f(x) = Σ αᵢ yᵢ k(xᵢ, x) + b — сумма только по опорным векторам
        return (self.a_sv * self.y_sv) @ rbf_kernel(self.X_sv, X, self.gamma) + self.b

    def predict(self, X):
        return np.where(self.decision_function(X) >= 0, 1, -1)

На «двух лунах» (400 точек, шум 0.25) это даёт долю верных ответов 0.908 и 85 опорных векторов — ровно как sklearn.svm.SVC(C=1.0, gamma=0.5). Библиотека отличается не математикой, а инженерией: эвристикой выбора второй переменной (максимальное нарушение вместо случайного), кэшем строк матрицы ядра, шринкингом — временным исключением точек с α, застрявшим на границе коробки. См. Platt, SMO, и Chang & Lin, LIBSVM.

7. Сложность и главное ограничение метода

Замер на синтетике (20 признаков, RBF, sklearn): n = 1000 → 0.01 с, 2000 → 0.03 с, 4000 → 0.18 с, 8000 → 0.69 с. Учетверение времени на каждое удвоение n — ровно O(n²); экстраполируйте на миллион строк сами.

Отсюда правило выбора. Ядерный SVM — метод для выборок примерно до 50–100 тысяч объектов; дальше либо линейный SVM через liblinear/SGD, либо аппроксимация ядра (раздел 8). Различайте два режима: при d > n (текст, геномика, спектры) линейное ядро почти всегда не хуже RBF — данные и так разделимы, а RBF лишь добавит переобучения; при n >> d (табличные данные) SVM не конкурент бустингу из статьи про ансамбли ни по скорости, ни по работе с категориями.

8. Практика: pipeline, подбор гиперпараметров, большие данные

Масштабирование обязательно, не опционально. RBF оперирует евклидовым расстоянием: признак с разбросом в тысячах единиц полностью подавит признак с разбросом в единицах, и γ будет калиброваться под мусор. В эксперименте умножение одного признака на 1000 без стандартизации уронило долю верных ответов с 0.944 до 0.894 — и это на «удобной» синтетике. Почему StandardScaler должен жить внутри пайплайна — в статье Данные и признаки.

import numpy as np
from sklearn.calibration import CalibratedClassifierCV
from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

# Scaler ВНУТРИ пайплайна: иначе на каждом фолде CV произойдёт утечка статистик из валидации
# class_weight="balanced" — при перекосе классов
pipe = make_pipeline(StandardScaler(), SVC(kernel="rbf", class_weight="balanced"))

# C и gamma ищем СОВМЕСТНО и по логарифмической сетке: линейная сетка тут бесполезна
grid = {"svc__C": np.logspace(-2, 3, 6),        # 0.01 … 1000
        "svc__gamma": np.logspace(-4, 0, 5)}    # 0.0001 … 1
gs = GridSearchCV(pipe, grid, scoring="average_precision", cv=5, n_jobs=-1)
gs.fit(X_train, y_train)
print(gs.best_params_, gs.best_score_)   # {'svc__C': 10.0, 'svc__gamma': 0.1} 0.75

Про average_precision вместо accuracy при дисбалансе — см. Оценку моделей. Рецепт подбора из руководства авторов LIBSVM: сначала грубая сетка C ∈ 2^{−5..15}, γ ∈ 2^{−15..3}, затем мелкая вокруг максимума; для дорогих моделей — RandomizedSearchCV или байесовская оптимизация.

Когда n велико: аппроксимация ядра. Идея Rahimi & Recht (Random Fourier Features, NIPS 2007) — построить явные признаки z(x) размерности m << n так, что z(x)ᵀz(x') ≈ k(x, x'), и учить линейную модель: сложность падает с O(n²) до O(nm).

from sklearn.kernel_approximation import Nystroem   # или RBFSampler
from sklearn.svm import LinearSVC

# Nystroem: аппроксимация ядра по m случайно выбранным «опорным» точкам
approx = make_pipeline(StandardScaler(),
                       Nystroem(gamma=0.05, n_components=300, random_state=0),
                       LinearSVC(C=1.0, dual="auto", max_iter=5000))
approx.fit(X_train, y_train)
# качество 0.952 против 0.958 у точного RBF-SVC — потеря 0.6 п.п. за линейное время

На 2000 строк точный SVC ещё быстрее, но кривые сложности пересекаются в районе десятков тысяч строк. Nystroem обычно точнее RBFSampler при равном m, так как использует сами данные, а не только случайные проекции.

Многоклассовая задача. SVM бинарен по природе: SVC использует one-vs-one (K(K−1)/2 классификаторов на парах классов и голосование), LinearSVC — one-vs-rest (K моделей на полных данных). При большом K one-vs-one учится быстрее — каждая модель видит мало данных при квадратичной сложности, — но опрашивает больше моделей на инференсе.

9. Вероятности, регрессия и поиск аномалий

Вероятности. decision_function возвращает отступ — число со знаком, не вероятность: расстояние 2.7 не означает «вероятность 0.97». Классический приём — Platt scaling: обучить одномерную логистическую регрессию p = σ(a·f(x) + b) поверх отступов на отложенных данных. В scikit-learn SVC(probability=True) делает это через внутреннюю 5-фолдовую CV — обучение дорожает впятеро, а метки от decision_function и от predict_proba могут разойтись у границы. Честнее — явная калибровка:

calibrated = CalibratedClassifierCV(gs.best_estimator_, method="sigmoid", cv=5)
calibrated.fit(X_train, y_train)
proba = calibrated.predict_proba(X_test)[:, 1]

Если вероятности — центральная часть продукта (ставки, риск, ожидаемая ценность), берите логистическую регрессию или бустинг: там они «из коробки». Если нужен порядок или бинарное решение — отступа хватает, подберите порог по бизнес-метрике.

SVR — та же машинерия с ε-нечувствительной потерей: ноль внутри «трубы» ширины ε вокруг предсказания, линейный рост снаружи. Регрессия получается устойчивой к выбросам (линейный, а не квадратичный штраф) и разреженной (точки внутри трубы не опорные). ε задаётся в единицах целевой переменной — единственный интерпретируемый гиперпараметр семейства; на sin(x) с шумом 0.1 SVR(C=10, epsilon=0.1, gamma=0.5) даёт R² = 0.983.

One-Class SVM строит поверхность вокруг «нормальных» данных; всё снаружи — аномалия. Параметр nu — верхняя граница доли выбросов в обучении и нижняя граница доли опорных векторов. Метод чувствителен к γ и склонен завышать долю аномалий (при nu = 0.05 он пометил 35.8% тестовых объектов, потому что тест содержал невиданный класс). Для табличных данных IsolationForest обычно практичнее.

10. SVM в проде: где он действительно работает

Честная картина: на табличных данных SVM вытеснен бустингом, на изображениях и тексте — нейросетями. Но ниши, где он остаётся инструментом первого выбора, никуда не делись:

• Малые выборки с большим числом признаков — медицина, биоинформатика, химия: 200 пациентов, 20 000 генов. Бустинг переобучается, нейросеть не на чем учить, а SVM с линейным ядром и сильной регуляризацией устойчив. SVM-RFE (исключение признаков по весам w), Guyon et al., 2002 — до сих пор стандарт отбора генов.
• Классификация текста на средних корпусах. LinearSVC на TF-IDF обучается за секунды и остаётся сильным бейзлайном, который трансформер обгоняет не всегда на величину, оправдывающую GPU-инференс: Joachims, 1998 объясняет почему — разреженность и высокая размерность — родная среда SVM.
• Данные без векторного представления. Строковые, графовые, Tanimoto-ядра работают с молекулами и последовательностями напрямую: достаточно определить «похожесть».
• Поверх эмбеддингов. Предобученная сеть как экстрактор признаков плюс линейный SVM на небольшом размеченном наборе — быстро, устойчиво, без дообучения сети.
• Воспроизводимость. Выпуклость даёт побитово одинаковый результат; для регулируемых отраслей это не мелочь.

Эксплуатация: модель хранит опорные векторы целиком, поэтому её размер растёт с выборкой (на шумных данных — сотни мегабайт), а латентность инференса пропорциональна их числу: линейное ядро сворачивается в один вектор w, RBF нет. Если модель ушла в прод на RBF и n_support_ близко к n, ищите проблему, а не докупайте железо. Про мониторинг и дрейф — MLOps.

11. Типичные ошибки

1. Не отмасштабировали признаки. Самая дорогая ошибка: RBF без стандартизации — сломанная модель.
2. Масштабирование вне пайплайна. scaler.fit(X) до сплита — утечка статистик и оптимистичная оценка.
3. Подбор C и γ по очереди. Они взаимодействуют, оптимум лежит в «долине» на двумерной поверхности.
4. Линейная сетка гиперпараметров. C ∈ [1, 2, ..., 10] пропускает и 0.01, и 1000. Только logspace.
5. Ядерный SVM на миллионе строк. Обучение не «медленное», а квадратичное — оно не закончится.
6. predict_proba без калибровки. Отступ ≠ вероятность; probability=True может противоречить predict.
7. Игнорирование дисбаланса. SVM оптимизирует зазор, а не accuracy: при 99:1 без class_weight он предскажет мажоритарный класс всем.
8. Не посмотрели на долю опорных векторов. n_support_.sum() / n близко к 1 — модель заучила выборку.
9. Полином высокой степени. degree > 3 — численная неустойчивость (ядро улетает в 10¹⁵) и несходимость.
10. Попытка объяснить предсказание. У RBF-SVM нет весов признаков: нужна интерпретируемость — берите линейное ядро (coef_) или решающие деревья.

12. Мини-итог

• SVM максимизирует зазор; сложность модели управляется R²/γ², а не размерностью — метод выживает при d > n.
• Мягкий зазор превращает задачу в «hinge loss + L2» — SVM родственник логрегрессии, отличие в форме потери.
• Данные входят в двойственную задачу только через скалярные произведения → любое ядро Мерсера даёт нелинейность без построения признаков. RBF — разумный старт, линейное — для d > n и больших n.
• Решение определяется опорными векторами, и их доля — бесплатная диагностика переобучения.
• Цена — квадратичная сложность по n и отсутствие вероятностей из коробки. Потолок — десятки тысяч объектов.

Источники

• Cortes, Vapnik. Support-Vector Networks, 1995 — springer
• Boser, Guyon, Vapnik. A Training Algorithm for Optimal Margin Classifiers, COLT 1992 — acm
• Hsu, Chang, Lin. A Practical Guide to SVM Classification — guide.pdf
• Hastie, Tibshirani, Friedman. The Elements of Statistical Learning, гл. 12 — ESL
• Schölkopf, Smola. Learning with Kernels, MIT Press — mitpress
• Rahimi, Recht. Random Features for Large-Scale Kernel Machines, NIPS 2007 — papers.nips.cc
• Bottou, Lin. Support Vector Machine Solvers — pdf
• scikit-learn: SVM, аппроксимация ядер
• Конспект CS229 (Stanford) — main_notes.pdf

Что дальше

SVM строит одну гладкую границу, где все признаки участвуют одновременно через расстояния. Следующий метод устроен противоположным образом: режет пространство по одному признаку за раз, порождая ступенчатую границу — зато читаемую человеком и не требующую ни масштабирования, ни выбора ядра.

Решающие деревья