Support Vector Machines

Три шага к методу опорных векторов

SVM строился в три шага на протяжении трёх десятилетий. В 1963 году Владимир Вапник и Алексей Червоненкис разработали VC-теорию - статистическую основу, объясняющую, почему широкий зазор между классами ведёт к лучшему обобщению. В 1992 году Бернхард Бозер, Изабель Гийон и Вапник добавили kernel trick: заменив скалярные произведения на ядровые функции, линейный разделитель смог строить нелинейные границы, не вычисляя координаты в пространстве высокой размерности. А в 1995 году Коринна Кортес и Вапник предложили SVM с мягким зазором, допустив несколько ошибок классификации, чтобы метод справлялся с зашумлёнными, пересекающимися данными. Результат доминировал в прикладной классификации, пока спустя десятилетие на сцену не вышло глубокое обучение.

Представьте, что вы охранник в музее и должны натянуть верёвку между двумя группами экспонатов так, чтобы расстояние от верёвки до ближайшего экспоната было максимальным. Чем больше зазор - тем надёжнее разделение: случайный посетитель не перепутает зоны. Именно так работает SVM - он ищет не просто любую границу между классами, а границу с максимальным запасом прочности. А если экспонаты перемешаны и верёвкой их не разделить? Тогда SVM использует kernel trick - математический фокус, который позволяет разделить неразделимое.

• **Распознавание рукописных цифр** - SVM был стандартом для задачи MNIST (70000 изображений цифр 0-9) до прихода deep learning, достигая accuracy 98.5% с RBF kernel, и до сих пор используется как baseline в задачах классификации изображений
• **Классификация текстов** - спам-фильтры, анализ тональности отзывов, категоризация новостей: SVM с линейным kernel обрабатывает тысячи признаков (слов) и остаётся одним из лучших методов для текстовых задач с ограниченным объёмом данных
• **Биоинформатика** - SVM классифицирует белки по функциям, предсказывает активность генов и диагностирует заболевания по генетическим профилям, где типично 20000+ признаков (генов) и всего сотни образцов пациентов

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

• Logistic Regression

Гиперплоскость и максимальный margin

Представьте, что вам нужно провести линию между двумя группами точек на плоскости - красными и синими. Logistic Regression найдёт *какую-нибудь* линию, которая разделяет классы. Но SVM ставит задачу жёстче: найти линию, которая не просто разделяет, а делает это с **максимальным зазором (margin)** между ближайшими точками разных классов. Почему это важно? Большой margin означает, что модель уверена в своём решении и лучше обобщает на новые данные.

**Support vectors** - это ближайшие к разделяющей линии точки каждого класса. Именно они «поддерживают» (support) гиперплоскость и определяют её положение. Ключевое свойство SVM: если убрать любую точку, которая не является support vector, граница решений **не изменится**. Только support vectors влияют на модель - все остальные точки можно удалить без последствий.

Математически задача SVM: **минимизировать ||w||^2 / 2** при условии, что все точки правильно классифицированы: y_i * (w * x_i + b) >= 1 для каждой точки. Здесь w - вектор нормали к гиперплоскости, b - смещение. Это задача **квадратичной оптимизации с ограничениями** - у неё единственное глобальное решение (в отличие от нейросетей, где можно застрять в локальном минимуме).

**Hard margin vs Soft margin (C-SVM):** Hard margin SVM требует, чтобы ВСЕ точки были строго за пределами margin. Но реальные данные часто содержат выбросы или перекрытие классов. **Soft margin** допускает нарушения за штраф C: - **Большой C** (например, 1000) - модель штрафует нарушения жёстко, margin узкий, возможен overfitting - **Маленький C** (например, 0.01) - модель допускает больше нарушений, margin широкий, лучше генерализация C - это компромисс между шириной margin и количеством ошибок на обучающей выборке.

Kernel Trick: нелинейные границы

Линейный SVM прекрасно работает, когда классы можно разделить прямой линией. Но что если данные выглядят как концентрические круги - один класс внутри, другой снаружи? Или задача XOR - четыре точки на плоскости, где диагонально противоположные принадлежат одному классу? Никакая линия их не разделит. Идея решения: **проецировать данные в пространство более высокой размерности**, где они станут линейно разделимыми. Например, для точек (x1, x2) можно добавить признак x3 = x1^2 + x2^2 (расстояние от центра). В 3D точки внутреннего круга поднимутся ниже, а внешнего - выше, и плоскость в 3D легко их разделит.

Но проекция в высокую размерность дорога: если исходных признаков d, polynomial проекция степени p создаёт порядка d^p новых признаков. Для 100 признаков и степени 5 это 10 миллиардов вычислений на каждую точку. **Kernel trick** решает эту проблему элегантно: он позволяет вычислить скалярное произведение двух точек *в высокомерном пространстве*, **никогда не переходя туда явно**.

**Суть kernel trick:** SVM нужны не сами координаты в высокомерном пространстве, а только **скалярные произведения** между точками: phi(x) * phi(z). Kernel-функция K(x, z) вычисляет это скалярное произведение напрямую: - K(x, z) = phi(x) * phi(z) - без вычисления phi! **Пример:** для phi(x1, x2) = (x1^2, x2^2, sqrt(2)*x1*x2) - Вычислить phi и скалярное произведение: 6 операций на phi, 3 на скалярное = 9 - Kernel: K(x, z) = (x * z)^2 = (x1*z1 + x2*z2)^2 = **3 операции** Один и тот же результат, но kernel в 3 раза быстрее. Для высоких размерностей разница - в миллиарды раз.

Популярные kernel-функции: **линейный** K(x,z) = x*z (обычное скалярное произведение, без проекции), **polynomial** K(x,z) = (x*z + c)^d (проекция в пространство полиномов степени d), и **RBF** (радиальная базисная функция), о которой поговорим далее. Выбор kernel зависит от задачи: линейный - когда данные линейно разделимы, polynomial - для умеренных нелинейностей, RBF - универсальный вариант по умолчанию.

RBF Kernel: радиальная базисная функция

RBF (Radial Basis Function) kernel - самый популярный и мощный kernel для SVM. Его формула: **K(x, z) = exp(-gamma * ||x - z||^2)**, где ||x - z||^2 - квадрат евклидова расстояния между точками. Интуитивно: RBF kernel измеряет **похожесть** двух точек. Если точки близко - K велико (около 1), если далеко - K стремится к 0. Параметр gamma определяет, как быстро «похожесть» падает с расстоянием.

Ключевое свойство RBF kernel: он соответствует проекции в **бесконечномерное пространство**. Через разложение в ряд Тейлора exp(-gamma * ||x-z||^2) можно показать, что RBF эквивалентен скалярному произведению в пространстве с бесконечным числом координат. Это означает, что RBF SVM теоретически может разделить *любые* данные, если они в принципе разделимы (с правильными параметрами).

**Параметр gamma - "радиус влияния" каждой точки:** - **Маленький gamma** (0.001): каждая точка влияет на большую область. Граница решений гладкая и простая. Может привести к underfitting. - **Средний gamma** (0.1): баланс между гладкостью и сложностью. Обычно лучший результат. - **Большой gamma** (100): каждая точка влияет только на крошечную окрестность. Граница решений становится сложной, извилистой, повторяющей каждую точку. Классический overfitting. Правило: gamma по умолчанию в sklearn = 1 / (n_features * X.var()), что часто даёт хорошую отправную точку.

RBF kernel - это **default в sklearn.svm.SVC**, и не зря. Он универсален: линейный kernel - частный случай RBF (при очень маленьком gamma RBF ведёт себя почти линейно). При этом RBF справляется со сложными нелинейными границами, которые недоступны линейным и polynomial kernels. Единственный минус - два гиперпараметра (C и gamma), которые нужно подбирать.

Гиперпараметры и практика SVM

У SVM с RBF kernel два ключевых гиперпараметра: **C** (штраф за нарушение margin) и **gamma** (радиус влияния точек). Они взаимодействуют друг с другом: увеличение обоих одновременно ведёт к overfitting, уменьшение обоих - к underfitting. Правильная комбинация C и gamma - ключ к хорошей модели, и находить её нужно через **grid search с cross-validation**.

**Feature scaling обязателен для SVM!** SVM вычисляет расстояния между точками. Если один признак от 0 до 1, а другой от 0 до 1000000, второй полностью доминирует. StandardScaler (z-score) или MinMaxScaler приводят все признаки к одному масштабу. Это отличает SVM от деревьев решений и Random Forest, которые НЕ чувствительны к масштабу признаков (они работают с порогами, а не расстояниями).

**Когда использовать SVM?** Лучший выбор, когда данных немного (тысячи-десятки тысяч), но признаков много - классификация текстов, биоинформатика (тысячи генов, сотни пациентов). В таких условиях нейросети переобучаются, а SVM с правильным kernel обобщает. **Когда НЕ использовать?** При больших объёмах данных (>100K точек) - обучение SVM имеет сложность O(n^2) до O(n^3), что делает его непрактичным на миллионах примеров. Также SVM не подходит, когда нужна интерпретируемость - линейные модели и деревья гораздо прозрачнее.

**Практические советы по SVM:** 1. **Всегда масштабируйте данные** - StandardScaler перед SVM 2. **Начинайте с RBF kernel** - он default не просто так 3. **Grid search для C и gamma** - типичные диапазоны: C от 0.01 до 1000, gamma от 0.0001 до 10 4. **Мало данных, много признаков** - SVM в своей стихии 5. **Много данных (>100K)** - рассмотрите LinearSVC или SGDClassifier с hinge loss 6. **Нужны вероятности** - используйте SVC(probability=True), но это удваивает время обучения через Platt scaling

Ключевые идеи

• **Максимальный margin:** SVM ищет гиперплоскость, которая разделяет классы с максимальным зазором - только support vectors (ближайшие точки) определяют границу, остальные данные можно удалить
• **Kernel trick:** позволяет вычислить скалярное произведение в пространстве высокой размерности без явного перехода туда - polynomial kernel решает нелинейные задачи за доли стоимости явной проекции
• **RBF kernel:** измеряет похожесть точек через расстояние, проецируя в бесконечномерное пространство - параметр gamma контролирует радиус влияния каждой точки (маленький gamma = гладкая граница, большой = overfitting)
• **Практика:** feature scaling обязателен, grid search для C и gamma через cross-validation, SVM лучше всего при малых данных и высокой размерности - как верёвка в музее из нашего примера, он находит самое надёжное разделение с максимальным запасом прочности

Связанные темы

SVM стоит на пересечении линейных методов и нелинейных преобразований, связывая классические алгоритмы с современными подходами:

• Logistic Regression — Линейный классификатор-предшественник SVM: оба ищут разделяющую гиперплоскость, но SVM максимизирует margin, а Logistic Regression оптимизирует правдоподобие. Для линейно разделимых данных SVM даёт большую устойчивость
• Деревья решений — Альтернативный подход к нелинейной классификации без kernel trick: деревья разбивают пространство прямоугольниками, не требуют масштабирования, но менее устойчивы к шуму. Random Forest решает проблему устойчивости ансамблем
• PCA (метод главных компонент) — Снижение размерности перед SVM: при тысячах признаков PCA может ускорить обучение, сохранив основную дисперсию данных. Kernel PCA использует тот же kernel trick, что и SVM
• Нейронные сети — Мощная альтернатива SVM для больших датасетов: нейросети масштабируются на миллионы примеров, но требуют больше данных и вычислений. При малых данных SVM часто выигрывает благодаря принципу максимального margin

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

• Почему SVM, который максимизирует margin, обычно обобщает лучше, чем классификатор, который просто находит любую разделяющую границу? Как это связано с теорией статистического обучения Вапника?
• Kernel trick позволяет работать в бесконечномерном пространстве (RBF). Почему модель при этом не переобучается автоматически, ведь в бесконечномерном пространстве можно разделить любые данные?
• В каких ситуациях вы бы выбрали SVM вместо Random Forest, и наоборот? Какие свойства данных определяют этот выбор?

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

• ml-10-logistic-regression — Logistic regression - отправная точка для понимания SVM margin
• ml-09-gradient-descent — Оптимизация SVM dual problem использует gradient methods
• ml-19-pca — PCA + SVM - классический pipeline для высоких размерностей
• ml-25-neural-networks — SVM kernel trick интуиция переносится в нейросеть как feature extractor
• calc-06-derivative-intro — Понимание margin optimization требует производных
• prob-04-bayes — SVM и Naive Bayes - два полярных подхода к классификации
• la-25-quadratic-forms
• cvx-01