Как устроен RBF SVM: глубокий разбор математики, ядра Гаусса и алгоритма SMO

Нелинейное разделение данных: в чем сложность маленьких выборок

В машинном обучении регулярно возникают ситуации, когда требуется построить модель классификации на небольшой выборке — например, для сотни пациентов с десятком лабораторых параметров. На графике такие классы часто выглядят перемешанными, и стандартная линейная классификация оказывается бессильна. Простая прямая линия неспособна адекватно разделить целевые группы, какую бы ориентацию весов мы ни выбрали.

Почему обычные алгоритмы подводят

Попытки усложнить модель часто приводят к противоположным проблемам. Использование полиномиальных функций слегка повышает точность, но оставляет критическое число ошибок. Сигмоидальные границы в условиях сильного перекрытия показывают еще более слабые результаты. Использование глубоких нейросетей на малом объеме данных противопоказано: из-за огромного количества параметров модель быстро переобучается, просто запоминая тренировочные точки.

Здесь мы сталкиваемся с двумя препятствиями сразу: нелинейной природой границы и острым дефицитом обучающих примеров. Большинство традиционных алгоритмов вынуждены жертвовать либо гибкостью, либо устойчивостью. Именно эту дилемму элегантно решает метод опорных векторов с радиально-базисным ядром (RBF SVM).

Пример с диагностическими показателями: переход в 3D

Рассмотрим практическую иллюстрацию. Представим таблицу с показателями пациентов: температурой тела, пульсом и уровнем С-реактивного белка (СРБ). В норме показатель СРБ минимален (менее 5 мг/л), при вирусных поражениях возрастает умеренно, а при тяжелых воспалениях превышает 100 мг/л.

Если выстроить график только по двум параметрам (температура и пульс), отдельные заболевшие пациенты на плоскости практически неотличимы от здоровых. Однако добавление третьего измерения — концентрации СРБ — мгновенно разносит группы в пространстве. В 2D мы были вынуждены искать сложноизогнутую кривую, тогда как в 3D классы легко разделяются плоским срезом — гиперплоскостью.

Главная идея RBF SVM заключаются именно в этом: исходное пространство признаков виртуально отображается в пространство более высокой размерности, где разделение классов становится линейно возможным.

Геометрия разделяющих границ: от точек к гиперплоскости

Для математического описания перехода применяется отображение φ: &mathbbR^d → &mathbbR^D, трансформирующее d-мерный вектор исходных данных в D-мерное пространство. В качестве наглядного примера рассмотрим перевод одномерных данных на плоскость с помощью функции φ(x) = (x, x²). Точки на прямой выстраиваются вдоль параболы, благодаря чему исходно неразделимые отрезки разделяются прямой связующей линией.

Математическое описание гиперплоскости

В векторном виде гиперплоскость задается уравнением ⟨w, x⟩ + b = 0, где:

• x — вектор-столбец признаков анализируемого объекта;
• w — вектор нормали (веса модели), задающий перпендикуляр к гиперплоскости;
• ⟨w, x⟩ — скалярное произведение векторов, представляющее собой сумму произведений соответствующих компонент;
• b — сдвиг (смещение), определяющий расстояние от начала координат до гиперплоскости.

Для принятия решения о принадлежности к классу применяется функция знака: sign(f(x)) = sign(⟨w, x⟩ + b). Если значение результирующего выражения больше нуля, объект относится к положительному классу (+1), если меньше — к отрицательному (-1).

Роль весовых коэффициентов и сдвига

Масштабирование векторов весов и выбор смещения напрямую влияют на наклон и положение границы:

• Пропорциональное увеличение весов w без изменения их соотношения не меняет геометрического положения разделяющей линии, но масштабирует уверенность модели f(x).
• Изменение соотношения между компонентами вектора w разворачивает плоскость, перераспределяя важность признаков.
• Параметр b отвечает за параллельный перенос плоскости. При b = 0 граница строго привязана к началу координат, что сильно ограничивает гибкость модели, если классы расположены на удалении от центра.

Метод опорных векторов (SVM) и геометрия зазора

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

Функциональный и геометрический отступы

Функциональный отступ для объекта вычисляется как y_i(⟨w, x_i⟩ + b). Он показывает правильность и уверенность классификации. Однако у него есть уязвимость: при домножении всех весов и смещения на произвольную константу значение отступа увеличивается, хотя геометрия границы остается неизменной. Чтобы избежать этого обмана, используют геометрический отступ, нормированный на длину вектора весов:

r = y_i(⟨w, x_i⟩ + b) / ||w||

Формулировка оптимизационной задачи

Для зафиксированного масштаба задается условие, что для ближайших точек (опорных векторов) функциональный отступ равен ровно 1, а для всех остальных — больше 1. В таком случае ширина разделяющей полосы составляет 2 / ||w||.

Максимизация ширины зазора эквивалентна минимизации знаменателя ||w||. Чтобы избавиться от квадратного корня при вычислении нормы и упростить дифференцирование, задачу сводят к минимизации квадратичной формы:

min ¹/₂ ||w||² при условии y_i(⟨w, x_i⟩ + b) ≥ 1 для всех i.

Двойственная задача и функция Лагранжа

Поиск оптимальной гиперплоскости при наличии ограничений-неравенств выполняется с помощью функции Лагранжа. Для классического метода SVM она записывается в виде:

L(w, b, α) = ¹/₂ ||w||² – ∑ α_i [ y_i(⟨w, x_i⟩ + b) – 1 ]

где α_i ≥ 0 — множители Лагранжа, отражающие степень важности каждого обучающего объекта.

Условия Каруша — Куна — Таккера и роль опорных векторов

Согласно условиям дополняющей нежесткости (ККТ), для каждого объекта выполняется соотношение α_i [ y_i(⟨w, x_i⟩ + b) – 1 ] = 0. Из этого следует важнейший вывод:

• Если объект лежит строго на границе зазора (y_i f(x_i) = 1), то коэффициент α_i > 0. Такой объект является опорным вектором.
• Если объект находится дальше границы зазора (y_i f(x_i) > 1), то его коэффициент α_i = 0. Это означает, что удаление подобных точек из выборки никак не изменит положение гиперплоскости.

Переход к функции W(α)

Приравнивая к нулю частные производные L по w и b, мы получаем выражение для вектора весов: w = ∑ α_i y_i x_i, а также условие баланса: ∑ α_i y_i = 0. Подстановка этих условий в функцию Лагранжа дает двойственную задачу максимизации:

W(α) = ∑ α_i – ¹/₂ ∑ ∑ α_i α_j y_i y_j ⟨x_i, x_j⟩

при ограничениях α_i ≥ 0 и ∑ α_i y_i = 0. Вся геометрия исходных данных в этой формуле сведена исключительно к скалярным произведениям пар объектов ⟨x_i, x_j⟩ (матрице Грама).

Алгоритм последовательной минимальной оптимизации (SMO)

Прямой аналитический перебор систем уравнений для поиска всех α при большом количестве объектов приведет к комбинаторному взрыву. Чтобы оптимизировать W(α), применяется алгоритм SMO (Sequential Minimal Optimization).

Пошаговый выбор пар коэффициентов

SMO разбивает сложную задачу на последовательность минимальных шагов. На каждой итерации выбераются два коэффициента (α_i, α_j), а остальные фиксируются. Использование именно пары обусловлено необходимостью строго соблюдать уравнение баланса ∑ α_i y_i = 0.

• Если выбранные объекты принадлежат разным классам, их коэффициенты изменяются в одном направлении на равную величину.
• Если объекты одного класса — коэффициенты изменяются в противоположные стороны.

Алгоритм выбирает для шага те пары объектов, для которых ошибка предсказания E_i = f(x_i) – y_i максимально нарушает условия оптимизации. Шаг за шагом SMO сходится к единственному глобальному максимуму вогнутой функции W(α).

Радиально-базисное ядро (RBF): математика бесконечных измерений

Когда данные невозможно разделить плоскостью даже приблизительно, на помощь приходит ядро RBF (Radial Basis Function / Гауссово ядро):

K(x, y) = exp( – γ ||x – y||² )

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

Теорема Мерсера и «трюк с ядром»

Теорема Мерсера гарантирует, что если непрерывное симметричное ядро K(x, y) является положительно определенным, то существует скрытое отображение φ(x), для которого K(x, y) = ⟨φ(x), φ(y)⟩. Нам не требуется явно пересчитывать координаты объектов в новом пространстве — достаточно заменить скалярное произведение в формуле W(α) на функцию ядра K(x, y_i).

Почему RBF работает в бесконечномерном пространстве

Раскладывая экспоненту ядра RBF через ряд Маклорена (Тейлора), мы получаем бесконечную сумму степенных членов:

exp(⟨x, y⟩) = ∑ (⟨x, y⟩^k / k!)

Это математически доказывает, что вектор φ(x) для Гауссова ядра имеет бесконечное число координат. Выполняя простую операцию вычисления экспоненты над расстоянием в исходном пространстве, мы фактически производим скалярное произведение в бесконечномерном гильбертовом пространстве. В таком пространстве любые непротиворечивые классы становятся гарантированно разделяемыми.

Сравнительное тестирование RBF SVM на реальных датасетах

Чтобы объективно оценить возможности RBF SVM, я провел серию экспериментов на четырех практических наборах данных разного профиля:

• Sonar: 208 объектов, 60 признаков (бинарная классификация эхосигналов).
• Digits: 1797 изображений рукописных цифр 8×8 (10 классов, 64 признака).
• Breast Cancer: 569 медицинских карт опухолей (бинарная классификация, 30 параметров).
• UCI HAR: 10 299 записей показаний датчиков смартфона (6 видов активности, 561 признак).

Методология бенчмарка и параметры моделей

Тестирование проводилось с помощью вложенной 5-фолдовой кросс-валидации (Nested Cross-Validation). Предсказания собирались по схеме Out-Of-Fold (OOF). В качестве соперников RBF SVM выступили: Linear SVM, Random Forest, HistGradientBoosting, KNN и Logistic Regression.

Анализ результатов: Sonar, Digits, Breast Cancer и UCI HAR

Проведенное тестирование наглядно продемонстрировало сильные и слабые стороны алгоритма:

• На датасете Sonar (малая выборка, высокое число признаков, сильное перекрытие классов) RBF SVM показал безусловное превосходство, опередив линейный аналог на 0.114 по метрике ROC-AUC. В условиях геометрической запутанности нелинейное ядро дало решающий прирост.
• На наборе Digits RBF SVM также занял первое место, однако выигрыш по метрике оказался невеликолепен при увеличении времени вычислений почти в 4 раза по сравнению с Linear SVM.
• На датасете Breast Cancer показатели RBF SVM и линейных моделей оказались практически идентичными, так как данные были хорошо разделены изначально.
• Датасет UCI HAR стал важным контрпримером: здесь Linear SVM обставил RBF SVM как по точности, так и по скорости (почти в 10 раз быстрее). При большом количестве измерений (561 признак) пространство исходно обладало достаточной размерностью для линейного разделения, а высокая гибкость RBF приводя к небольшому улавливанию специфического шума отдельных субъектов.

Выводы и рекомендации

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

Источник: habr.com