Прыжок в бесконечность: как под капотом работает RBF SVM / Хабр

Всех приветствую! Меня зовут Андрей, я студент 4 курса факультета математики и компьютерных наук, автор телеграм‑канала Andre | Data Science. Все мы знаем, что направление машинного обучения сейчас на огромном хайпе — практически из‑под каждого камня говорят о разных методах и о том, что они способны решить практически любую задачу. Но гайдов, которые бы подробно разбирали работу конкретного метода — от обычной загрузки данных до математического обоснования принципа его работы и визуализации каждого шага, — катастрофически мало.

В этой статье я хочу закрыть этот пробел и разобрать один конкретный метод — RBF SVM. Мы посмотрим, как он устроен с математической точки зрения, как появился на свет, какие у него есть сильные и слабые стороны и с чем они связаны. Также протестируем его на реальных датасетах. Так как аудитория IT‑сообщества довольно широкая, я постараюсь очень подробно расписывать каждое определение и каждую часть своего повествования, чтобы по ходу чтения у вас возникало как можно меньше вопросов и нить понимания не обрывалась. Будет большим плюсом, если вы уже разбираетесь в следующих математических дисциплинах:

Линейная алгебра
Матанализ
Функциональный анализ
Дифференциальные уравнения
Методы оптимизации
Аналитическая геометрия

Вводная часть

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

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

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

На всех фото представлен один и тот же набор данных, состоящий из разных классов (синий и красный), а также разные способы их разделения

Линейная функция — разделяем классы обычной прямой. Точность — 80%

Полиномиальная функция — обычный многочлен. Точность — 92%

Сигмоида — гладкая S‑образная функция. Точность — 70%

RBF — наш клиент. Точность — 97%

Именно на этот случай и существует метод, о котором пойдёт речь в статье.

Разберем на ещё одном примере: имеется таблица с данными пациентов, которая содержит их ID, показатели температуры и пульса, а также целевой статус (здоров/болен).

Сейчас я буду ссылаться на искусственно созданный датасет в учебных целях. Ближе к концу мы будем использовать реальные данные.

id	temp_C	puls	diagnosis
P01	36.77	73	здоров
P02	36.68	62	здоров
P03	38.58	94	болен
..	..	..	..

Пусть также дана еще одна таблица пациентов. Он похожа на ту, которая выше, только в ней добавляется еще третий признак — СРБ.

СРБ (С‑реактивный белок) — это высокочувствительный белок, уровень которого в крови быстро и многократно возрастает в ответ на воспаление, инфекцию или повреждение тканей.
В норме СРБ почти равен нулю (меньше 5 мг/л)
Небольшой подъем (до 20 — 30 мг/л) — это обычно простуда или вирус
Сильный подъем (выше 100 мг/л) — это серьезная бактериальная инфекция, которая требует антибиотиков

id	temp_C	puls	SRB	diagnosis
P01	36.63	72	1.3	здоров
P02	36.71	65	3.3	здоров
P03	36.73	72	29.6	болен
..	..	..	..	..

Теперь давайте отобразим наших товарищей на координатную плоскость, где каждая ось будет отвечать за отдельный признак.

Перевод табличных данных в графическое представление

На левом графике пациенты расположены в двумерном пространстве, так как оцениваются всего два признака. На правом графике они находятся уже в трехмерном пространстве, поскольку добавился третий признак. Интересный момент: на левом рисунке два больных пациента визуально очень похожи на здоровых, а вот на правом разница видна сразу — эти два человека значительно отдалились от группы здоровых. Кстати, обратите ещё внимание, что в двумерном пространстве разделить эти классы довольно проблематично. Обычная линейная модель здесь будет бесполезна — придется искать какую‑то очень извилистую функцию. А вот в трехмерном пространстве мы сможем без проблем разделить два класса между собой. Похожий трюк мы сейчас будем использовать.

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

Гиперплоскость — это подпространство, размерность которого ровно на единицу меньше, чем размерность окружающего его пространства. Например, в двумерном пространстве гиперплоскостью будет являться прямая, а в трёхмерном пространстве будет обычная плоскость. Для четырёхмерного гиперплоскостью будет являться какая‑то объёмная фигура

На графиках мы видим два класса - синий и красный. Оба они находятся в . Разделить их друг от друга линией мы не сможем. Поэтому, мы повышаем размерность пространства до трёх измерений и проводим гиперплоскость, которая без проблем делит два класса между собой — На графиках мы видим два класса — синий и красный. Оба они находятся в двумерном пространстве. Разделить их друг от друга линией мы не сможем. Поэтому, мы повышаем размерность пространства до трёх измерений и проводим гиперплоскость, которая без проблем делит два класса между собой

Основа основ

Классический способ построить нелинейную границу между классами — придумать такое отображение φ: R^d → R^D, где R — пространство вещественных чисел, d — размерность исходного пространства, а D — размерность пространства, в которое мы переводим наши данные. Пример выше: отображение φ: R² → R³. После перехода в трехмерное пространство мы можем поделить наши классы. Давайте я покажу ещё один пример, чтобы точно закрепить всю суть:

Переход из одномерного пространства в двумерное и построение гиперплоскости

В левой части у нас одномерное пространство с одним признаком и два класса (синий и красный, ну или «Здоров» и «Болен»). Так как размерность пространства равна единице, то наша гиперплоскость будет иметь нулевую размерность, а что это за объект? — точка! Но если внимательно посмотреть, то обычной точкой мы не сможем разделить эти два класса. Давайте повысим размерность пространства до 2D, тогда наше отображение примет вид: φ: R¹ → R², где φ(x) = (x, x²). Благодаря нашему отображению мы получаем двумерную точку, вторая координата которой равна квадрату первой. На выходе наши точки выстроятся в параболу, на которой мы можем увидеть зазор между классами. Там мы и проведем нашу гиперплоскость. Но мы же можем сместить её вверх на 0.0001 или вниз. Как понять, какую именно строить? — на этот вопрос я отвечу позже.

Кстати, в данном случае квадратичную функцию необязательно было брать. Можно взять такое отображение φ(x) = (x, x⁴) или даже такое φ(x) = (x, |x|).

Уравнение гиперплоскости

В матане очень много всяких различных форм записи гиперплоскости. Мы будем использовать векторную форму: ⟨w^T, x⟩ + b = 0.

х = (х₁, х₂,..., х_n) — вектор‑столбец признаков, x_n — значения признаков, n — количество признаков;
w = (w₁, w₂,..., w_n) — вектор‑столбец нормали (перпендикуляр к плоскости). В контексте машинного обучения — это веса модели;
⟨w^T, x⟩ — скалярное произведение. В развернутом виде это сумма вида: w₁x₁ +... + w_nx_n;
b — смещение/сдвиг. Показывает, насколько сильно гиперплоскость смещена относительно начала координат.

Запись ⟨w, x⟩ предпочитают обычно в текстах, ориентированных на геометрию и функциональный анализ. Транспонирование здесь не нужно, так как скалярное произведение является самостоятельной операцией.
А вот в линейной алгебре стандартные векторы всегда считаются векторами‑столбцами. Чтобы умножить один столбец на другой по правилам матричного умножения, первый вектор необходимо перевернуть в строку.

$w^T x = (w_1, w_2, \dots w_n) \begin{pmatrix} x_1 \\ x_2 \\ \dots \\ x_n \end{pmatrix} = w_1 x_1 + w_2 x_2 + \dots + w_n x_n$

Теперь обозначим f(x) = ⟨w, x⟩ + b. Вспомним, что нас интересует классификация любой точки в пространстве относительно гиперплоскости. Вектор нормали w всегда указывает в сторону положительного класса. Пусть точки, лежащие по направлению вектора w, относятся к классу «Здоров» (+1), а против его направления — к классу «Болен» (-1). Для разделения воспользуемся сигнум‑функцией:

$\operatorname{sgn}(f(x)) = \begin{cases} 1, & f(x) > 0 \\ 0, & f(x) = 0 \\-1, & f(x) < 0 \end{cases}$

Если значение функции больше нуля, хоть на одну миллиардную, то значение сигнум‑функции равно 1 и точка принадлежит классу «Здоров». Ну и в противном случае та же история, либо точка лежит на границе классов, что практически невозможно в контексте реальных задач.

Представим ситуацию, у нас есть 4 объекта с двумя признаками: x₁ = (-1, 2), x₂ = (2, 1), x₃ = (1, -2), x₄ = (-2, -1) и вектор нормали w = (1, 1), а во втором случае w = (1, -1), смещение b пока пусть будет нулевым. Вектор нормали всегда указывает расположение положительного класса. Подставив координаты каждой точки в уравнение гиперплоскости, мы получим числовое значение (на графике оно указано рядом с каждой точкой и показывает степень влияния точки). Затем мы передаем это число в сигнум‑функцию и получаем окончательный вердикт о том, к какому классу принадлежит эта точка.

Вектор нормали также отвечает за поворот гиперплоскости

Теперь поиграем с вектором нормали. Как изменится наш график, если мы оставим направление вектора неизменным, но сделаем его в два раза длиннее? Сама граница никуда не делась. Умножение значение весов на константу не меняет расположение гиперплоскости. Также, можно заметить, что значение функции f(x) выросло в два раза. Чем больше значения весов, тем сильнее f(x) уходит в плюсовые или минусовые значения при отдалении от границы.

Влияние значения весов на значение итоговой функции

Теперь посмотрим на ситуацию, когда вектор нормали не только меняет свою длину, но и своё направление одновременно. Поскольку граница привязана к вектору нормали, она послушно развернется вслед за ним. Также, из‑за поворота границы, нижняя точка перешла в класс «Болен». Если говорить на языке млщика, то модель решила, что второй признак х₂ в два раза важнее первого признака х₁.

Любое колебание по оси x2 оказывает вдвое больше влияние на итоговый вердикт f(x), чем то же изменение по оси x1. — Любое колебание по оси x₂ оказывает вдвое больше влияние на итоговый вердикт f(x), чем то же изменение по оси x₁.

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

Но это все работало при b = 0. Теперь посмотрим, на что влияет это коэффициент:

Если b = 0, то граница проходит через начало координат;
Если b > 0, то граница сдвигается в стороны, противоположную вектору w;
Если b < 0, то граница сдвигается по направлению вектора w.

Алгебраически смещение b — это просто константа, которая прибавляется ко всем значениям f(x) одновременно. Взглянем на график:

Влияние точек изменилось. Вектор нормали остается на месте.

Если жестко зафиксировать b = 0, то модель сможет поворачивать разделяющую прямую как угодно, но точка вращения всегда будет привязана к центру координат (0,0).
Если реальные данные разделяются прямой, проходящей далеко от центра (например, на высоте x₂ = 100), модель физически не сможет построить адекватную границу, сколько бы мы ни крутили веса.

Принцип работы SVM

SVM (Support Vector Machine / Метод опорных векторов) — это алгоритм обучения с учителем, главная цель которого — найти оптимальную разделяющую гиперплоскость между классами, обеспечивающую максимальный зазор между ними. Если данные можно разделить прямой (или плоскостью в 3D), то таких прямых можно провести бесконечно много. Нам нужно найти самую надежную.

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

Берем прошлый пример с больными и здоровыми пациентами. Опорные вектора как правило лежат на границе зазора, а посередине проходит наша гиперплоскость. Если мы выкинем любой НЕ опорный элемент, то гиперплоскость даже не шелохнется

А вот если мы удалим опорный вектор, то гиперплоскость перестроится и найдется новый опорный вектор

Чтобы максимизировать зазор, о котором было сказано выше, нам нужно научиться строго измерять расстояние от любого объекта x_i до гиперплоскости. Для начала, поговорим о таком понятии как функциональный отступ:

$f _i =y _i ⋅(⟨w,x _i ⟩+b), \quad y_i=\{+1, -1\},\quad i=1..n$

Он показывает результат классификации (знак) и уверенность модели. Если точка принадлежит классу (-1), то ⟨w, x⟩ + b < 0, y = -1 и тогда значение функционального отступа будет положительным. Если точка принадлежит классу (+1), то функциональный отступ так же будет положительным. Тогда это все можно записать так:

$y_i⋅(⟨w,x_i⟩+b)=\vert{}\langle w, x_i \rangle + b\vert{}$

У функционального отступа есть фатальный недостаток: уравнение гиперплоскости можно безнаказанно умножать на любое число. Если уравнение x₁ + x₂ — 2 = 0 умножить на 10 целиком, то получим 10x₁ + 10x₂ — 20 = 0. Визуально — это та же самая прямая, но функциональный отступ вырос в 10 раз. Для алгоритма это выглядит так, будто модель стала в 10 раз «увереннее» и лучше. Компьютер попадает в ловушку: вместо того чтобы двигать линию и реально учиться разделять данные, он может просто бесконечно увеличивать веса до бесконечности, обманывая сам себя.

Как избавиться от этой ловушки и математически записать настоящий зазор? Вспомним аналитическую геометрию — расстояние от любой точки х до гиперплоскости вычисляется так:

$d(x_i) = \frac{\vert{}\langle w, x_i \rangle + b\vert{}}{\Vert{}w\Vert{}}=\frac{y_i⋅(⟨w,x_i⟩+b)}{\Vert{}w\Vert{}}$

Изящность формулы заключается в том, что мы подставили вместо значения числителя формулу, которую вывели выше и если мы снова провернем наши махинации с домножением на какую‑то константу, например на 10, то ничего не изменится — десятки в числителе и знаменателе просто сократятся.

Вернемся к зазору. Мы знаем, что опорные векторы находятся на его границе и расположены ближе других точек к гиперплоскости. Здесь мы берем ту самую свободу домножения на константу: раз масштаб w и b ничего не меняет геометрически, мы вправе выбрать его сами, по своему усмотрению. Договоримся так: подберём масштаб специально под опорный вектор так, чтобы у неё функциональный отступ стал равен ровно 1:

А для точек, которые находятся дальше зазора будет выполняться вот такое условие:

$y_i(\langle w,x_i\rangle+b)\ge1, \quad \forall i$

Тогда формула расстояния от точки (опорного вектора) до гиперплоскости примет вид:

$d(x_i)=\frac{1}{\Vert{}w\Vert{}}$

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

$M = \frac{1}{\|w\|} + \frac{1}{\|w\|} = \frac{2}{\|w\|}$

Процесс максимизации зазора равносилен задаче минимизации знаменателя, ведь чем меньше знаменатель, тем больше дробь.

$M = \max_{w} \frac{2}{\|w\|} \iff \min_{w} \|w\|, \|w\| = \sqrt{w_1^2 + w_2^2 + \dots + w_n^2}$

Чтобы найти минимум функции нам поможет наша любимая производная. Правда, если мы возьмем производную например по переменной w₁, то получим вот такой кошмар:

$\frac{\partial g}{\partial w_1} = \frac{1}{2\sqrt{w_1^2 + w_2^2 + \dots + w_n^2}} \cdot 2w_1 = \frac{w_1}{\|w\|}$

Хуже того: это функция ещё и не везде определена (знаменатель может быть равен нулю). Работать с такой функцией неудобно и математически небезопасно. А если мы попробуем избавиться от корня путем возведения в квадрат? Идея супер, но насколько это законно? На первый взгляд кажется странным: ||w|| и ||w||² — это разные функции, имеющие разные значения, кроме единицы и нуля. Как может быть, что точки минимума находятся в одном и том же месте? Вспомним небольшое школьное правило:

Если f(x) возрастает (и при этом f(x) ≥ 0), то и g(x) = √ f(x) тоже возрастает.

Если условие неотрицательности подкоренной функции выполняться не будет, то точка минимума не будет совпадать с точкой минимума функции корня. А так, в остальных вариантах точки полностью совпадают.

Супер, мы немного упростили себе задачу, но теперь при взятии производной у нас будет вылезать двойка спереди. Уничтожим её через домножение на дробь 1/2. Вуаля! Мы пришли к итоговой задаче минимизации:

$\min_{w}\frac12\|w\|^2, \quad y_i(\langle w,x_i\rangle+b)\ge1\ \ \forall i$

Функция Лагранжа

Теперь давайте протестируем нашу универсальную формулу. В качестве примера возьмем следующие точки:

Точка	Класс	Координаты (x, y)
A₁	-1	(-3, 2)
A₂	-1	(-2, 3)
A₃	-1	(-1, 1)
B₁	+1	(1, 3)
B₂	+1	(1, 2)
B₃	+1	(2, 1)

Интерактивный пример. На значения весов и смещения не обращайте внимания. Они нам пока не нужны. Всё внимание на точки.

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

Давайте подставлять значения в условие для точек, которые находятся дальше:

$\begin{flalign*} &\text{Условие для гиперплоскости:} \quad y_i(⟨w,x_i⟩ + b) \geq 1 &\\[2ex] &\text{Красный класс } (y_i=-1): &\\[1ex] &\text{Точка } R_1(-3,2): & \\ &-1\cdot\left(w_1(-3)+w_2\cdot2+b\right)\geq1 &\\ &-1\cdot\left(-3w_1+2w_2+b\right)\geq1 &\\ &\boxed{3w_1-2w_2-b\geq1} &\\[2ex] &\text{Точка } R_2(-2,3): &\\ &-1\cdot\left(w_1(-2)+w_2\cdot3+b\right)\geq1 &\\ &-1\cdot\left(-2w_1+3w_2+b\right)\geq1 &\\ &\boxed{2w_1-3w_2-b\geq1} &\\[2ex] &\text{Точка } R_3(-1,1): &\\ &-1\cdot\left(w_1(-1)+w_2\cdot1+b\right)\geq1 &\\ &-1\cdot\left(-w_1+w_2+b\right)\geq1 &\\ &\boxed{w_1-w_2-b\geq1} &\\[3ex] &\text{Синий класс } (y_i=+1): &\\[1ex] &\text{Точка } B_1(1,3): &\\ &+1\cdot\left(w_1\cdot1+w_2\cdot3+b\right)\geq1 &\\ &\boxed{w_1+3w_2+b\geq1} &\\[2ex] &\text{Точка } B_2(1,2): &\\ &+1\cdot\left(w_1\cdot1+w_2\cdot2+b\right)\geq1 &\\ &\boxed{w_1+2w_2+b\geq1} &\\[2ex] &\text{Точка } B_3(2,1): &\\ &+1\cdot\left(w_1\cdot2+w_2\cdot1+b\right)\geq1 &\\ &\boxed{2w_1+w_2 +b\geq1} & \end{flalign*}$

Помним, что наша цель — максимизация зазора:

$f(w_1, w_2) = \frac{1}{2} \|w\|^2 = \frac{1}{2} (w_1^2 + w_2^2)$

Ищем минимум — берем частные производные:

$\begin{aligned} \frac{\partial f}{\partial w_1} &= w_1 = 0 \implies \mathbf{w_1 = 0} \\[10pt] \frac{\partial f}{\partial w_2} &= w_2 = 0 \implies \mathbf{w_2 = 0} \end{aligned}$

Все веса равны нулю, выглядит довольно странно. Может дальше будет лучше? Если мы подставим эти значения в уравнения для каждой точки, то получим, что для красных точек должно выполняться b ≤ -1, а для синих точек b ≥ 1, что в принципе невозможно (несмотря на то, что там и там b может быть равно нулю). А на графике это будет выглядеть так:

Разделяющую гиперплоскость и зазор невозможно построить. Так как норма вектора весов равна нулю и находится в знаменателе формулы ширины зазора, то при делении на ноль значение полосы стремится к бесконечности.

Получается, текущих условий нам недостаточно, нужно что‑то ещё. Здесь нам поможет функция Лагранжа.

Функция Лагранжа — это функция, которая используется в матанализе для поиска условного экстремума при наличии ограничений в виде равенств/неравенств.

Допустим, нам дана функция f(x, y) = x + y. Её графиком будет бесконечная красная плоскость. Если мы попытаемся найти точки экстремума, то придем к тому, что их не существует (как бы логично, ведь плоскость бесконечная). В таком случае мы добавляем ограничение в виде равенства x²+ y²= 1. Мы как бы сформировали «опору», на которой могут появиться точки экстремума. Дальше нам и поможет функция Лагранжа. Она имеет вид:

$L(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\alpha}) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i \cdot \varphi_i(\mathbf{x}) + \sum_{j=1}^{k} \alpha_j \cdot g_j(\mathbf{x})$

где:

f(x) — целевая функция, которую мы оптимизируем;
φ_i(x) = 0 — ограничения в виде равенства;
g_i(x) ≤ 0 — ограничения в виде неравенства (в нашем примере их нет);
λ_i — множитель Лагранжа, может быть любого знака;
α_i — показатель важности конкретной точки для построения гиперплоскости. Если он равен нулю, то точка лежит далеко от границы зазора и она нам не нужна. Если он больше нуля, то точка лежит на границе зазора и является опорным вектором;
x = (x₁,...,x_n) — вектор входных данных.

Количество ограничений‑равенств (m) всегда должно быть строго меньше количества исходных переменных (n). Если ограничений будет столько же или больше, чем переменных, то система уравнений свяжет все переменные намертво и оптимизировать будет нечего.

Давай найдем точки экстремума в нашем примере через функцию Лагранжа:

$\begin{flalign*} &\text{Целевая функция:} \quad f(x, y) = x + y &\\ &\text{Ограничение:} \quad \varphi(\mathbf{x}) = x^2 + y^2 - 1 = 0 &\\ &\text{Итоговая функция:} \quad (x, y, \lambda) = x + y + \lambda(x^2 + y^2 - 1) &\\[2ex] &\text{Частные производные:} &\\ &\begin{cases} \dfrac{\partial L}{\partial x} = 1 + 2\lambda x = 0 \implies x = -\dfrac{1}{2\lambda} \\[10pt] \dfrac{\partial L}{\partial y} = 1 + 2\lambda y = 0 \implies y = -\dfrac{1}{2\lambda} \\[10pt] \dfrac{\partial L}{\partial \lambda} = x^2 + y^2 - 1 = 0 \end{cases} &\\[2ex] &\left(-\dfrac{1}{2\lambda}\right)^2 + \left(-\dfrac{1}{2\lambda}\right)^2 = 1 &\\ &\dfrac{1}{4\lambda^2} + \dfrac{1}{4\lambda^2} = 1 \implies \dfrac{2}{4\lambda^2} = 1 \implies 2\lambda^2 = 1 \implies \lambda^2 = \dfrac{1}{2} &\\[1.5ex] &\lambda_1 = +\dfrac{1}{\sqrt{2}}, \quad \lambda_2 = -\dfrac{1}{\sqrt{2}} &\\[2ex] &\text{Вычисление координат:} &\\[1ex] &\text{1. При } \lambda_1 = +\dfrac{1}{\sqrt{2}}: \quad \mathbf{x}_1 = \begin{pmatrix} -\dfrac{1}{\sqrt{2}} \\ -\dfrac{1}{\sqrt{2}} \end{pmatrix} &\\ &f(\mathbf{x}_1) = -\dfrac{1}{\sqrt{2}} - \dfrac{1}{\sqrt{2}} = -\sqrt{2} \approx \mathbf{-1.4142} \quad \text{(Минимум)} &\\[1.5ex] &\text{2. При } \lambda_2 = -\dfrac{1}{\sqrt{2}}: \quad \mathbf{x}_2 = \begin{pmatrix} +\dfrac{1}{\sqrt{2}} \\ +\dfrac{1}{\sqrt{2}} \end{pmatrix} &\\ &f(\mathbf{x}_2) = +\dfrac{1}{\sqrt{2}} + \dfrac{1}{\sqrt{2}} = +\sqrt{2} \approx \mathbf{+1.4142} \quad \text{(Максимум)} & \end{flalign*}$

Класс, благодаря ограничениям и функции Лагранжа мы смогли найти точки экстремума. Давайте рассмотрим ситуацию, когда помимо ограничения‑равенства у нас ещё есть ограничение‑неравенство.

Добавили ограничение-неравенство на икс, чтобы он был не меньше единицы и увеличили радиус окружности до 2 для наглядности. — Добавили ограничение‑неравенство на икс, чтобы он был не меньше единицы и увеличили радиус окружности до 2 для наглядности.

Найдем точки экстремума:

$\begin{flalign*} &\text{Целевая функция:} \quad f(x, y) = x + y &\\ &\text{Ограничения:} \quad \varphi(x,y) = x^2 + y^2 - 2 = 0, \quad g(x) = 1 - x \le 0 &\\ &\text{Итоговая функция:} \quad L(x, y, \lambda, \alpha) = x + y + \lambda(x^2 + y^2 - 2) + \alpha(1 - x) &\\[2ex] &\text{Частные производные:} &\\ &\begin{cases} \dfrac{\partial L}{\partial x} = 1 + 2\lambda x - \alpha = 0 \\[10pt] \dfrac{\partial L}{\partial y} = 1 + 2\lambda y = 0 \implies y = -\dfrac{1}{2\lambda} \\[10pt] \dfrac{\partial L}{\partial \lambda} = x^2 + y^2 - 2 = 0 \\[5pt] \alpha \ge 0, \quad \alpha(1 - x) = 0 \end{cases} &\\[2ex] &\text{1. Внутреннее решение } (\alpha = 0, \, x > 1): &\\ &\begin{cases} 1 + 2\lambda x = 0 \implies x = -\dfrac{1}{2\lambda} \\[8pt] 1 + 2\lambda y = 0 \implies y = -\dfrac{1}{2\lambda} \end{cases} \implies x = y &\\[1ex] &\left(-\dfrac{1}{2\lambda}\right)^2 + \left(-\dfrac{1}{2\lambda}\right)^2 = 2 \implies \dfrac{2}{4\lambda^2} = 2 \implies 4\lambda^2 = 1 \implies \lambda = \pm\dfrac{1}{2} &\\[1ex] &\lambda_1 = +\dfrac{1}{2} \implies \mathbf{x}_1 = \begin{pmatrix} -1 \\ -1 \end{pmatrix} \quad \text{(Отсекается, так как } x = -1 < 1\text{)} &\\ &\lambda_2 = -\dfrac{1}{2} \implies \mathbf{x}_2 = \begin{pmatrix} 1 \\ 1 \end{pmatrix} \quad \text{(Отсекается, } \text{так как } x > 1\text{)} &\\[2ex] &\text{2. Граничное решение } (x = 1): &\\ & \alpha(1 - 1) = 0 \implies \alpha \ge 0. &\\ &1^2 + y^2 - 2 = 0 \implies y^2 = 1 \implies y = \pm 1. &\\[1ex] &\text{Проверка:} &\\[1ex] &\text{а) Для точки } \mathbf{x}_3 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}: &\\ &\begin{cases} 1 + 2\lambda(1) = 0 \implies \lambda = -\dfrac{1}{2} \\[5pt] 1 + 2\left(-\dfrac{1}{2}\right)(1) - \alpha = 0 \implies \alpha = 0 \quad \text{(Условие } \alpha \ge 0 \text{ выполнено)} \end{cases} &\\ &f(\mathbf{x}_3) = 1 + 1 = \mathbf{2.0} \quad \text{(Максимум)} &\\[1.5ex] &\text{б) Для точки } \mathbf{x}_4 = \begin{pmatrix} 1 \\ -1 \end{pmatrix}: &\\ &\begin{cases} 1 + 2\lambda(-1) = 0 \implies \lambda = \dfrac{1}{2} \\[5pt] 1 + 2\left(\dfrac{1}{2}\right)(1) - \alpha = 0 \implies \alpha = 2 \quad \text{(Условие } \alpha \ge 0 \text{ выполнено)} \end{cases} &\\ &f(\mathbf{x}_4) = 1 - 1 = \mathbf{0.0} \quad \text{(Минимум)} & \end{flalign*}$

Обратите внимание на последнее условие в самой первой системе. Оно в себе содержит два сценария:

Если 1 — x ≠ 0, то единственным решением будет α = 0. Подставляем это значение в систему, чтобы найти стационарные точки функции Лагранжа. Расчет показывает, что ни одна из стационарных точек не удовлетворяет неравенству x > 1. Мы пришли к выводу, что условный экстремум не может находиться внутри допустимой области, и локальные экстремумы функции на данном множестве могут быть расположены только на его границе.
При x = 1 координата жестко фиксируется и переменная α освобождается от требования быть нулём. Система пересчитывается для граничных условий, что позволяет найти нам точки экстремума.

Вот так выглядят точки условного экстремума (оранжевые точки). Если отобразить окружность в 3д, то можно увидеть, что точка максимума будет на самом верху сечения.

Если вдруг запутались в определениях глобального, локального и условного экстремума, то вот вам супер классная визуализация (спасибо Гемини):

Желтая точка - глобальный максимум, то есть самая высока точка вообще на всем графике. Фиолетовая точка - глобальный минимум, самая низкая. Голубая точка - локальный максимум, то есть, в окрестности холмика эта точка будет самой высокой. Условный максимум - точка на линии ограничения, где значение функции достигает максимума. — Желтая точка — глобальный максимум, то есть самая высока точка вообще на всем графике. Фиолетовая точка — глобальный минимум, самая низкая. Голубая точка — локальный максимум, то есть, в окрестности холмика эта точка будет самой высокой. Условный максимум — точка на **линии ограничения**, где значение функции достигает максимума.

Возвращаемся к SVM и к нашим точкам на плоскости. Функция Лагранжа для них будет выглядеть так (сверху общий вид функции для нашего случая, а снизу уже с подстановкой):

$\begin{gather*} L(x, \alpha) = f(x) + \sum_{j=1}^{k} \alpha_j \cdot g_j(x) \\ L(w, b, \alpha) = \frac{1}{2} \|w\|^2 + \sum_{i=1}^{N} \alpha_i \Big( 1 - y_i \big( \langle w, x_i \rangle + b \big) \Big) \\ L(w, b, \alpha) = \frac{1}{2} \|w\|^2 - \sum_{i=1}^{N} \alpha_i \Big( y_i \big( \langle w, x_i \rangle + b \big) - 1 \Big) \end{gather*}$

Берем наши 6 точек из кастомного датасета и составляем для каждой ограничение‑неравенство:

A₁(−3,2) ⟹ 3w₁ − 2w₂ − b ≥ 1
A₂(−2,3) ⟹ 2w₁ − 3w₂ − b ≥ 1
A₃(−1,1) ⟹ w₁ − w₂ − b ≥ 1
B₁(1,3) ⟹ w₁ + 3w₂ + b ≥ 1
B₂(1,2) ⟹ w₁ + 2w₂ + b ≥ 1
B₃(2,1) ⟹ 2w₁ + w₂ + b ≥ 1

После подстановки неравенств в функцию Лагранжа мы получаем вот такой ужас:

$\begin{gather*} L(w_1, w_2, b, \alpha) = \frac{1}{2}w_1^2 + \frac{1}{2}w_2^2 \\ - \alpha_1(3w_1 - 2w_2 - b - 1) \\ - \alpha_2(2w_1 - 3w_2 - b - 1) \\ - \alpha_3(w_1 - w_2 - b - 1) \\ - \alpha_4(w_1 + 3w_2 + b - 1) \\ - \alpha_5(w_1 + 2w_2 + b - 1) \\ - \alpha_6(2w_1 + w_2 + b - 1) \end{gather*}$

А теперь вспомните, что на этом этапе нам надо брать частные производные, а чтобы их взять нужно сгруппировать все слагаемые по переменным w₁, w₂ и b. После группировки получаем следующее:

$\begin{gather*} L(w_1, w_2, b, \alpha) = \frac{1}{2}w_1^2 + \frac{1}{2}w_2^2 \\ + w_1(-3\alpha_1 - 2\alpha_2 - \alpha_3 - \alpha_4 - \alpha_5 - 2\alpha_6) \\ + w_2(2\alpha_1 + 3\alpha_2 + \alpha_3 - 3\alpha_4 - 2\alpha_5 - \alpha_6) \\ + b(\alpha_1 + \alpha_2 + \alpha_3 - \alpha_4 - \alpha_5 - \alpha_6) \\ + (\alpha_1 + \alpha_2 + \alpha_3 + \alpha_4 + \alpha_5 + \alpha_6) \end{gather*}$

Переходим к вычислению частных производных:

$\begin{gather*} \frac{\partial L}{\partial w_1} = w_1 + (-3\alpha_1 - 2\alpha_2 - \alpha_3 - \alpha_4 - \alpha_5 - 2\alpha_6) = 0 \\ w_1 = 3\alpha_1 + 2\alpha_2 + \alpha_3 + \alpha_4 + \alpha_5 + 2\alpha_6 \\[1em] \frac{\partial L}{\partial w_2} = w_2 + (2\alpha_1 + 3\alpha_2 + \alpha_3 - 3\alpha_4 - 2\alpha_5 - \alpha_6) = 0 \\ w_2 = -2\alpha_1 - 3\alpha_2 - \alpha_3 + 3\alpha_4 + 2\alpha_5 + \alpha_6 \\[1em] \frac{\partial L}{\partial b} = \alpha_1 + \alpha_2 + \alpha_3 - \alpha_4 - \alpha_5 - \alpha_6 = 0 \\ \alpha_1 + \alpha_2 + \alpha_3 = \alpha_4 + \alpha_5 + \alpha_6 \end{gather*}$

Мы нашли w₁, w₂ и b, но при этом у нас осталось 6 неизвестных альфа. Теперь давайте вернемся к примеру с бесконечной плоскостью и окружностью. После вычисления частных производных мы рассматривали два случая: альфа равно нулю и больше нуля. В нашем случае точек 6, а это значит, что нам надо рассмотреть всего‑то 2⁶ случая, а точнее посчитать 64 системы:

Система 1: α₁ = 0, α₂ = 0,..., α₆ = 0 (веса обнуляются)
Система 2: α₁ > 0 (ограничение = 0), α₂ = 0,..., α₆ = 0
Система 3: α₁ = 0, α₂ > 0 (ограничение = 0),..., α₆ = 0
.. и так до 64 системы

Казалось бы, перебрать 64 варианта для компьютера — всё равно что семечки пощёлкать. А теперь представьте, если бы точек было не 6, а 100. Тогда нам бы пришлось считать 2¹⁰⁰ систем, а это равно вот такому числу:

Фанфакт: современный суперкомпьютер смог обработать эти данные примерно за 40 000 лет.

Поэтому, дабы избежать комбинаторного ада и взрыва процессора, мы делаем ход конём — снова вычисляем частные производные:

$\begin{gather*} \frac{\partial L}{\partial w_j} = w_j - \sum_{i=1}^{N} \alpha_i y_i x_{ij} = 0 \implies w_j = \sum_{i=1}^{N} \alpha_i y_i x_{ij} \\ \frac{\partial L}{\partial b} = - \sum_{i=1}^{N} \alpha_i y_i = 0 \implies \sum_{i=1}^{N} \alpha_i y_i = 0 \end{gather*}$

А теперь посмотрите на первое выражение. Вектор весов это буквально линейная комбинация самих точек датасета, умноженных на метки класса и коэффициенты Лагранжа. Теперь мы точно знаем, где вычисляются веса модели. Посмотрим на второе выражение, оно куда интереснее. Разложим его немного, чтобы понять, в чем заключается его изящность:

$\begin{gather*} \sum_{i=1}^{N} \alpha_i y_i = \sum_{i: y_i = +1} \alpha_i y_i + \sum_{j: y_j = -1} \alpha_j y_j = 0 \\[10pt] \sum_{i: y_i = +1} \alpha_i - \sum_{j: y_j = -1} \alpha_j = 0 \\[10pt] \sum_{i: y_i = +1} \alpha_i = \sum_{j: y_j = -1} \alpha_j \end{gather*}$

Исходную сумму мы разбили на сумму точек из класса +1 и сумму точек из класса -1. Последнее выражение можно даже назвать законом сохранения баланса сил при построении гиперплоскости. По факту оно несёт в себе следующую инфу:

Гиперплоскость зажата между классами с одинаковым суммарным «давлением». Сдвинуть её в какую‑либо сторону без ухудшения качества классификации невозможно. Чем‑то напоминает 3 закон Ньютона.
Даже если в одном классе будет 1000 объектов, а в другом всего 2, то суммарный вклад опорных векторов каждого класса на границе зазора будет строго одинаковым. У двух точек значение множителя Лагранжа будет больше, тем самым мы скомпенсируем разницу. Так что дисбаланс классов нас не пугает.

Супер, теперь подставим получившиеся выражение в исходную функцию Лагранжа:

$\begin{flalign*} &\mathbf{w} = \begin{pmatrix} w_1, & w_2, & \dots, & w_D \end{pmatrix} &\\[1.5ex] &\mathbf{x}_i = \begin{pmatrix} x_{i1}, & x_{i2}, & \dots, & x_{iD} \end{pmatrix} &\\[1.5ex] &\langle \mathbf{w}, \mathbf{x}_i \rangle = \sum_{j=1}^D w_j x_{ij} &\\[1ex] &\text{Исходные условия:} \quad \mathbf{w} = \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i, \quad \sum_{i=1}^N \alpha_i y_i = 0 &\\ &\text{Исходная функция Лагранжа:} \quad L(\mathbf{w}, b, \alpha) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^N \alpha_i \Big( y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) - 1 \Big) &\\[2.5ex] &\text{1. Раскрытие внутренних скобок:} &\\ &L = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^N \Big( \alpha_i y_i \langle \mathbf{w}, \mathbf{x}_i \rangle + \alpha_i y_i b - \alpha_i \Big) &\\[1ex] &L = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^N \alpha_i y_i \langle \mathbf{w}, \mathbf{x}_i \rangle - \sum_{i=1}^N \alpha_i y_i b + \sum_{i=1}^N \alpha_i &\\[2.5ex] &\text{2. Исключение параметра } b: &\\ &-\sum_{i=1}^N \alpha_i y_i b = -b \left( \sum_{i=1}^N \alpha_i y_i \right) = -b \cdot 0 = 0 &\\[1ex] &L = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^N \alpha_i y_i \langle \mathbf{w}, \mathbf{x}_i \rangle + \sum_{i=1}^N \alpha_i &\\[2.5ex] &\text{3. Подстановка } \mathbf{w} = \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i \text{ в среднее слагаемое:} &\\ &-\sum_{i=1}^N \alpha_i y_i \langle \mathbf{w}, \mathbf{x}_i \rangle = -\sum_{i=1}^N \langle \mathbf{w}, \alpha_i y_i \mathbf{x}_i \rangle = -\left\langle \mathbf{w}, \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i \right\rangle &\\[1ex] &-\left\langle \mathbf{w}, \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i \right\rangle = -\langle \mathbf{w}, \mathbf{w} \rangle = -\|\mathbf{w}\|^2 &\\[2.5ex] &\text{4. Приведение подобных слагаемых:} &\\ &L = \frac{1}{2} \|\mathbf{w}\|^2 - \|\mathbf{w}\|^2 + \sum_{i=1}^N \alpha_i = \sum_{i=1}^N \alpha_i - \frac{1}{2} \|\mathbf{w}\|^2 &\\[2.5ex] &\text{5. Выражение } \|\mathbf{w}\|^2 \text{ через } \alpha: &\\ &\|\mathbf{w}\|^2 = \langle \mathbf{w}, \mathbf{w} \rangle = \left\langle \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i, \; \sum_{j=1}^N \alpha_j y_j \mathbf{x}_j \right\rangle = \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle &\\[3ex] &\text{Финишная прямая - итоговая формула:} &\\ &\max_{\alpha} W(\alpha) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle &\\[1ex] &\text{при ограничениях:} \quad \sum_{i=1}^N \alpha_i y_i = 0, \quad \alpha_i \ge 0 \quad \forall i & \end{flalign*}$

Теперь по порядку. Помним, что переменная D отвечает за количество признаков в датасета, а если говорить математически, то за размерность пространства, в котором мы находимся. Дальше мы просто подставляем получившиеся значения в функцию, и — о чудо! Поскольку от переменных w и b не осталось ни следа, мы переименовываем функцию в W(α). Но тут у вас может возникнуть вполне законный вопрос: «Почему вдруг мы тут максимизируем функцию, если до этого мы пришли к её минимизации?».

Левая функция имеет вид обычного параболоида. После преобразования мы получаем уравнение перевернутого параболоида.

Дело в том, что после введения множителей Лагранжа мы переходим к двойственной задаче. Сначала для каждого набора коэффициентов α мы минимизируем функцию Лагранжа по w и b:

$W(\alpha) = \min_{w,b} L(w, b, \alpha).$

Полученная функция W(α) является нижней границей оптимального значения исходной задачи. Поэтому наша цель теперь — найти максимально высокую из возможных нижних границ:

$\max_{\alpha} W(\alpha).$

К тому же, в формуле выше мы пришли к тому, что перед двойной суммой стоит минус, а двойная сумма — это всегда намек на появление квадрата. Значит, наша функция перевернулась.

Возвращаемся к нашим 6 точкам обратно. В нашей функции есть скалярное произведение ⟨x_i, x_j⟩ — это матрица Грама G, где G_ij= ⟨x_i, x_j⟩.

Матрица Грама — это квадратная таблица из скалярных произведений векторов. Она симметрична относительно главной диагонали. Её определитель равен нулю тогда, когда вектора линейно‑зависимы.

$\begin{gather*} G = \begin{pmatrix} \langle A_1, A_1 \rangle & \langle A_1, A_2 \rangle & \langle A_1, A_3 \rangle & \langle A_1, B_1 \rangle & \langle A_1, B_2 \rangle & \langle A_1, B_3 \rangle \\ \langle A_2, A_1 \rangle & \langle A_2, A_2 \rangle & \langle A_2, A_3 \rangle & \langle A_2, B_1 \rangle & \langle A_2, B_2 \rangle & \langle A_2, B_3 \rangle \\ \langle A_3, A_1 \rangle & \langle A_3, A_2 \rangle & \langle A_3, A_3 \rangle & \langle A_3, B_1 \rangle & \langle A_3, B_2 \rangle & \langle A_3, B_3 \rangle \\ \langle B_1, A_1 \rangle & \langle B_1, A_2 \rangle & \langle B_1, A_3 \rangle & \langle B_1, B_1 \rangle & \langle B_1, B_2 \rangle & \langle B_1, B_3 \rangle \\ \langle B_2, A_1 \rangle & \langle B_2, A_2 \rangle & \langle B_2, A_3 \rangle & \langle B_2, B_1 \rangle & \langle B_2, B_2 \rangle & \langle B_2, B_3 \rangle \\ \langle B_3, A_1 \rangle & \langle B_3, A_2 \rangle & \langle B_3, A_3 \rangle & \langle B_3, B_1 \rangle & \langle B_3, B_2 \rangle & \langle B_3, B_3 \rangle \end{pmatrix} \\[3ex] G = \begin{pmatrix} 13 & 12 & 5 & 3 & 1 & -4 \\ 12 & 13 & 5 & 7 & 4 & -1 \\ 5 & 5 & 2 & 2 & 1 & -1 \\ 3 & 7 & 2 & 10 & 7 & 5 \\ 1 & 4 & 1 & 7 & 5 & 4 \\ -4 & -1 & -1 & 5 & 4 & 5 \end{pmatrix} \end{gather*}$

Алгоритм не знает, какие точки окажутся опорными векторами, поэтому мы предполагаем, что все точки окажутся ими. Помним, что если точка лежит на границе, то выполняется равенство:

$\begin{gather*} \sum_{i=1}^{6} \alpha_i y_i \langle x_i, x_k \rangle + b = y_k \end{gather*}$

Подставим метки классов и столбцы матрицы Грама. Получим систему вида:

$\begin{gather*} \begin{cases} A_1\colon -13\alpha_1 - 12\alpha_2 - 5\alpha_3 + 3\alpha_4 + 1\alpha_5 - 4\alpha_6 + b = -1 \\[5pt] A_2\colon -12\alpha_1 - 13\alpha_2 - 5\alpha_3 + 7\alpha_4 + 4\alpha_5 - 1\alpha_6 + b = -1 \\[5pt] A_3\colon -5\alpha_1 - 5\alpha_2 - 2\alpha_3 + 2\alpha_4 + 1\alpha_5 - 1\alpha_6 + b = -1 \\[5pt] B_1\colon -3\alpha_1 - 7\alpha_2 - 2\alpha_3 + 10\alpha_4 + 7\alpha_5 + 5\alpha_6 + b = 1 \\[5pt] B_2\colon -1\alpha_1 - 4\alpha_2 - 1\alpha_3 + 7\alpha_4 + 5\alpha_5 + 4\alpha_6 + b = 1 \\[5pt] B_3\colon 4\alpha_1 + 1\alpha_2 + 1\alpha_3 + 5\alpha_4 + 4\alpha_5 + 5\alpha_6 + b = 1 \\[5pt] -\alpha_1 - \alpha_2 - \alpha_3 + \alpha_4 + \alpha_5 + \alpha_6 = 0 \end{cases} \end{gather*}$

Её можно решать как угодно: методом Гаусса, Крамера, Жордано‑Гаусса, исход один — система не имеет решений! Вывод — все 6 точек не могут лежать на границе зазор. Пытаться перебирать 64 дискретных подсистем вручную также не имеет смысла. Вместо этого задача решается как непрерывная максимизация вогнутой квадратичной функции с помощью метода последовательной минимальной оптимизации.

SMO — Sequential Minimal Optimization

Суть этого метода заключается в том, что вместо оптимизации всех коэффициентов α_i одновременно на каждом шаге выбирается только пара переменных α_i и α_j, для которой решается небольшая оптимизационная задача. После этого выбранная пара обновляется, а остальные коэффициенты остаются неизменными. Последовательно повторяя такие шаги, SMO приближается к оптимальному решению всей двойственной задачи SVM.

Разбираем наш пример. Мы имеем гладкую квадратичную функцию с условиями:

$\begin{gather*} && W(\alpha) = \sum_{i=1}^{6} \alpha_i - \frac{1}{2} \sum_{i=1}^{6} \sum_{j=1}^{6} \alpha_i \alpha_j y_i y_j G_{ij} &&\\[2.5ex] && \alpha_i \geq 0, \quad \sum_{i=1}^{6} \alpha_i y_i = 0 && \end{gather*}$

Так как W(α) — это перевернутый параболоид, то у него существует единственный глобальный максимум. Наша задача — подняться на саму вершину этого купола, подбирая коэффициенты α_i, то есть «силу давления» каждой точки на гиперплоскость. Но мы не можем менять значение переменных альфа по одной из‑за закона сохранения баланса. Меняя «силу» всего одной точки мы моментально рушим баланс всей системы. Для сохранения баланса Вселенной шаг оптимизации требует обновления строго двух переменных (α_i, α_j).

Почему именно две, а не три или четыре? Две переменные — это минимально возможное количество для совершения шага без нарушения равенства. Именно поэтому алгоритм называется последовательная минимальная оптимизация.

А как именно нам изменить эту пару, чтобы ничего не сломать?

Если точки разных классов: мы обязаны изменить их на одну и ту же величину в одну сторону (Δα_i = Δα_j). Увеличили давление красной точки на 1 — на столько же обязаны увеличить давление синей.
Если точки одного класса: мы меняем их в противоположные стороны (Δα_i = ‑Δα_j). Увеличили давление красной точки на 1 — на столько же обязаны уменьшить давление другой красной точки.

Начальное состояние алгоритма: все множители и смещение равны нулю:

$\alpha^{(0)} = (0, 0, 0, 0, 0, 0), \quad b^{(0)} = 0$

Текущее предсказание модели для текущей точки:

$f(x_k) = \sum_{m=1}^{6} \alpha_m y_m G_{mk} + b = 0$

Ошибка классификации для каждой точки выглядит так:

Для класса y = -1 (A₁, A₂, A₃): E = ‑(-1) = +1
Для класса y = +1 (B₁, B₂, B₃): E = ‑(+1) = -1

По формуле аналитического шага SMO прирост целевой функции ΔW при оптимизации пары (i, j) равен:

$\begin{gather*} \Delta W(i, j) = \frac{(E_i - E_j)^2}{2\eta_{ij}} \end{gather*}$

где знаменатель вычисляется через евклидово расстояние между точками:

$\begin{gather*} \eta_{ij} = G_{ii} + G_{jj} - 2G_{ij} = \|x_i - x_j\|^2 \end{gather*}$

Теперь подставляем все в формулу аналитического шага:

$\begin{gather*} (E_i - E_j)^2 = (+1 - (-1))^2 = 2^2 = 4 \\[2.5ex] \Delta W(i, j) = \frac{4}{2\|x_i - x_j\|^2} = \frac{2}{\|x_i - x_j\|^2} \end{gather*}$

Чтобы получить максимальный прирост функции, алгоритм обязан выбрать пару точек противоположных классов с минимальным расстоянием.

На стартовом шаге, когда все α = 0, выбор двух точек одного класса дает E_i — E_j = 0 и прирост ΔW = 0. Поэтому для первого шага алгоритм рассматривает исключительно пары противоположных классов. На последующих итерациях, когда часть α_к > 0, SMO начинает оптимизировать и пары одного класса.

Расчет квадрата расстояния для всех 9 возможных пар:

$\begin{align*} &1. (A_1, B_1) : \|(-3, 2) - (1, 3)\|^2 = (-4)^2 + (-1)^2 = 16 + 1 = 17 \implies \Delta W = \frac{2}{17} \approx 0.1176 \\ &2. (A_1, B_2) : \|(-3, 2) - (1, 2)\|^2 = (-4)^2 + 0^2 = 16 + 0 = 16 \implies \Delta W = \frac{2}{16} = 0.1250 \\ &3. (A_1, B_3) : \|(-3, 2) - (2, 1)\|^2 = (-5)^2 + 1^2 = 25 + 1 = 26 \implies \Delta W = \frac{2}{26} \approx 0.0769 \\ &4. (A_2, B_1) : \|(-2, 3) - (1, 3)\|^2 = (-3)^2 + 0^2 = 9 + 0 = 9 \implies \Delta W = \frac{2}{9} \approx 0.2222 \\ &5. (A_2, B_2) : \|(-2, 3) - (1, 2)\|^2 = (-3)^2 + 1^2 = 9 + 1 = 10 \implies \Delta W = \frac{2}{10} = 0.2000 \\ &6. (A_2, B_3) : \|(-2, 3) - (2, 1)\|^2 = (-4)^2 + 2^2 = 16 + 4 = 20 \implies \Delta W = \frac{2}{20} = 0.1000 \\ &7. (A_3, B_1) : \|(-1, 1) - (1, 3)\|^2 = (-2)^2 + (-2)^2 = 4 + 4 = 8 \implies \Delta W = \frac{2}{8} = 0.2500 \\ &8. (A_3, B_2) : \|(-1, 1) - (1, 2)\|^2 = (-2)^2 + (-1)^2 = 4 + 1 = 5 \implies \Delta W = \frac{2}{5} = 0.4000 \\ &9. (A_3, B_3) : \|(-1, 1) - (2, 1)\|^2 = (-3)^2 + 0^2 = 9 + 0 = 9 \implies \Delta W = \frac{2}{9} \approx 0.2222 \end{align*}$

Максимальное значение достигается на паре (A₃, B₂) с индексами i = 3, j = 5 (точка B₂ пятая по порядку). Фиксируем оставшиеся переменные:

Из условия баланса сил следует:

$−α_3 +α_5 =0⟹α_3 =α_5 =t, \quad t≥0$

Подставляем вектор α⁽⁰⁾(t) = (0, 0, t, 0, t, 0) в функцию W(α):

$\begin{flalign*} &\text{1. Линейная часть:} &&\\ &\sum_{i=1}^{6} \alpha_i = \alpha_3 + \alpha_5 = t + t = \mathbf{2t} &&\\ & &&\\ &\text{2. Квадратичная часть (} G_{33} = 2, G_{35} = 1, G_{55} = 5 \text{ из матрицы Грама):} &&\\ &\frac{1}{2} \left[ \alpha_3^2 y_3^2 G_{33} + 2\alpha_3\alpha_5 y_3 y_5 G_{35} + \alpha_5^2 y_5^2 G_{55} \right] &&\\ &= \frac{1}{2} \left[ t^2 (-1)^2 (2) + 2t^2 (-1)(1)(1) + t^2 (1)^2 (5) \right] &&\\&= \frac{1}{2} \left[ 2t^2 - 2t^2 + 5t^2 \right] = \frac{1}{2} (5t^2) = \mathbf{2.5t^2} &&\\ & &&\\ &\text{3. Итоговая функция:} &&\\ &W(t) = 2t - 2.5t^2 && \end{flalign*}$

Дальше по сценарию ищем экстремум:

$\frac{dW}{dt} = 2 - 5t = 0 \implies 5t = 2 \implies \mathbf{t = 0.4}$

Отсюда получаем значения множителей Лагранжа: α₃ = 0.4, α₅ = 0.4 и сам вектор множителей: α⁽¹⁾ = (0, 0, 0.4, 0, 0.4, 0). А теперь сенсация — вычисление вектора весов и смещения:

$\begin{equation*} \begin{aligned} &x_3 = (-1, 1), \quad x_5 = (1, 2) \\ &w_1 = \alpha_3 y_3 x_{3,1} + \alpha_5 y_5 x_{5,1} = 0.4 \cdot (-1) \cdot (-1) + 0.4 \cdot 1 \cdot 1 = 0.4 + 0.4 = \mathbf{0.8} \\ &w_2 = \alpha_3 y_3 x_{3,2} + \alpha_5 y_5 x_{5,2} = 0.4 \cdot (-1) \cdot 1 + 0.4 \cdot 1 \cdot 2 = -0.4 + 0.8 = \mathbf{0.4} \end{aligned} \end{equation*}$

Теперь смещение B:

$\begin{flalign*}&\text{Для вектора } x_5=(1, 2),\quad y_5 = +1: &\\ &y_5(\langle w, x_5 \rangle + b) = 1 \implies 1 \cdot (0.8 \cdot 1 + 0.4 \cdot 2 + b) = 1 &\\ &1.6 + b = 1 \implies \mathbf{b = -0.6} &\\ & &\\ &\text{Для вектора } x_3=(-1, 1) \quad y_3 = -1: &\\ &y_3(\langle w, x_3 \rangle + b) = 1 \implies -1 \cdot (0.8 \cdot (-1) + 0.4 \cdot 1 + b) = 1 &\\ &-1 \cdot (-0.8 + 0.4 + b) = 1 \implies -1 \cdot (-0.4 + b) = 1 &\\ &0.4 - b = 1 \implies \mathbf{b = -0.6} &\\ & &\\ &\text{Итоговое уравнение гиперплоскости:} &\\ &\mathbf{0.8x_1 + 0.4x_2 - 0.6 = 0} & \end{flalign*}$

Для поиска смещения нам не принципиально какую точку подставлять в уравнение.

Всё! Мы наконец‑то нашли уравнение гиперплоскости. Но давайте лучше проверим себя:

$\begin{flalign*} &A_1(-3, 2), \quad y_1 = -1, \quad \alpha_1 = 0: &\\ &-1 \cdot (0.8 \cdot (-3) + 0.4 \cdot 2 - 0.6) = -1 \cdot (-2.4 + 0.8 - 0.6) = 2.2 \geq 1 &\\ & &\\ &A_2(-2, 3), \quad y_2 = -1, \quad \alpha_2 = 0: &\\ &-1 \cdot (0.8 \cdot (-2) + 0.4 \cdot 3 - 0.6) = -1 \cdot (-1.6 + 1.2 - 0.6) = 1.0 = 1 &\\ & &\\ &A_3(-1, 1), \quad y_3 = -1, \quad \alpha_3 = 0.4: &\\ &-1 \cdot (0.8 \cdot (-1) + 0.4 \cdot 1 - 0.6) = -1 \cdot (-0.8 + 0.4 - 0.6) = 1.0 = 1 &\\ & &\\ &B_1(1, 3), \quad y_4 = +1, \quad \alpha_4 = 0: &\\ &+1 \cdot (0.8 \cdot 1 + 0.4 \cdot 3 - 0.6) = 1 \cdot (0.8 + 1.2 - 0.6) = 1.4 \geq 1 &\\ & &\\ &B_2(1, 2), \quad y_5 = +1, \quad \alpha_5 = 0.4: &\\ &+1 \cdot (0.8 \cdot 1 + 0.4 \cdot 2 - 0.6) = 1 \cdot (0.8 + 0.8 - 0.6) = 1.0 = 1 &\\ & &\\ &B_3(2, 1), \quad y_6 = +1, \quad \alpha_6 = 0: &\\ &+1 \cdot (0.8 \cdot 2 + 0.4 \cdot 1 - 0.6) = 1 \cdot (1.6 + 0.4 - 0.6) = 1.4 \geq 1 & \end{flalign*}$

Гиперплоскость идеально делить классы, а ширина зазора - максимальна — Гиперплоскость идеально делить классы, а ширина зазора — максимальна

Но стоп, стоп. Мы пришли к тому, что точки с координатами (1, 2) и (-1, 1) являются опорными векторами и задают наклон гиперплоскости. Но на графике мы видим самозванца на координатах (-2, 3). Он четко лежит на границе зазора, но в расчетах получает α₂ = 0. Если не вдаваться в миллион строк с вычислениями, то можно просто сказать, что эта точка для построения гиперплоскости просто избыточна, никакого вклада она не внесла.

Я пересчитал все без этой точки и действительно изменений ноль. Эта точка никак не влияет на модель.

Несмотря на то, что у нас все получилось, этот датасет оказался плохим примером для демонстрации работы SMO, потому что это метод последовательной минимальной оптимизации, а значит с первого раза у нас вряд‑ли получится вычислить все. Поэтому, с вашего позволения мы рассмотрим ещё один пример по‑меньше, чтобы понять, как работает метод, если с первого шага у нас ничего не получается.

Берем следующие точки:

A₁ = (-1, 0), y₁ = -1
A₂ = (-0.5, 3), y₂ = -1
B₁ = (1, 0), y₃ = -1
B₂ = (2, 3), y₄ = -1

Запишем сразу матрицу Грама:

$\begin{flalign*} &G = \begin{pmatrix} \langle A_1, A_1 \rangle & \langle A_1, A_2 \rangle & \langle A_1, B_1 \rangle & \langle A_1, B_2 \rangle \\ \langle A_2, A_1 \rangle & \langle A_2, A_2 \rangle & \langle A_2, B_1 \rangle & \langle A_2, B_2 \rangle \\ \langle B_1, A_1 \rangle & \langle B_1, A_2 \rangle & \langle B_1, B_1 \rangle & \langle B_1, B_2 \rangle \\ \langle B_2, A_1 \rangle & \langle B_2, A_2 \rangle & \langle B_2, B_1 \rangle & \langle B_2, B_2 \rangle \end{pmatrix} = \begin{pmatrix} 1 & 0.5 & -1 & -2 \\ 0.5 & 9.25 & -0.5 & 8 \\ -1 & -0.5 & 1 & 2 \\ -2 & 8 & 2 & 13 \end{pmatrix} & \end{flalign*}$

На старте все так же α⁽⁰⁾ = (0, 0, 0, 0), b⁽⁰⁾ = 0. Считаем квадраты расстояний:

$\begin{flalign*} &1. (A_1, B_1) : \|(-1, 0) - (1, 0)\|^2 = (-2)^2 + 0^2 = 4 \implies \Delta W = \frac{2}{4} = 0.500 &\\ &2. (A_2, B_2) : \|(-0.5, 3) - (2, 3)\|^2 = (-2.5)^2 + 0^2 = 6.25 \implies \Delta W = \frac{2}{6.25} = 0.320 &\\ &3. (A_2, B_1) : \|(-0.5, 3) - (1, 0)\|^2 = (-1.5)^2 + 3^2 = 11.25 \implies \Delta W = \frac{2}{11.25} \approx 0.178 &\\ &4. (A_1, B_2) : \|(-1, 0) - (2, 3)\|^2 = (-3)^2 + (-3)^2 = 9 + 9 = 18 \implies \Delta W = \frac{2}{18} \approx 0.111 & \end{flalign*}$

Однозначно выбираем пару (A₁, B₁) с индексами i = 1, j = 3. Фиксируем α₂ = 0, α₄ = 0. Из условия баланса получаем:

Подставляем в W(t) и сразу считаем производные вместе с экстремумом при α⁽¹⁾ = (t, 0, t, 0):

$\begin{flalign*} &W(t) = (\alpha_1 + \alpha_3) - \frac{1}{2} \left[ \alpha_1^2 y_1^2 G_{11} + 2\alpha_1\alpha_3 y_1 y_3 G_{13} + \alpha_3^2 y_3^2 G_{33} \right] &\\ &W(t) = 2t - \frac{1}{2} \left[ t^2(1)(1) + 2t^2(-1)(1)(-1) + t^2(1)(1) \right] &\\ &W(t) = 2t - \frac{1}{2} \left[ t^2 + 2t^2 + t^2 \right] = 2t - \frac{1}{2}(4t^2) = 2t - 2t^2 &\\ &\frac{dW}{dt} = 2 - 4t = 0 \implies 4t = 2 \implies \mathbf{t = 0.5} &\\ &\alpha_1 = 0.5, \quad \alpha_2 = 0, \quad \alpha_3 = 0.5, \quad \alpha_4 = 0 & \end{flalign*}$

Считаем промежуточные параметры w⁽¹⁾ и b⁽¹⁾:

$\begin{flalign*} &w^{(1)} = \alpha_1 y_1 x_1 + \alpha_3 y_3 x_3 = 0.5(-1) \begin{pmatrix} -1 \\ 0 \end{pmatrix} + 0.5(1) \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0 \end{pmatrix} + \begin{pmatrix} 0.5 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} &\\ &y_3(\langle w, B_1 \rangle + b) = 1 \implies 1(1 \cdot 1 + 0 \cdot 0 + b) = 1 \implies 1 + b = 1 \implies \mathbf{b = 0} &\\ &1x_1 + 0x_2 + 0 = 0 \implies x_1 = 0 & \end{flalign*}$

Необычная картина, гиперплоскость — это просто вертикальная линия, так ещё и точка залезла в зазор. Проверим функциональные отступы y_k(⟨w⁽¹⁾,x_k⟩ + b⁽¹⁾) для каждой точки:

$\begin{flalign*} &A_1(-1, 0), \quad y_1 = -1: &\\ &-1 \cdot (1 \cdot (-1) + 0) = 1.0 = 1 &\\ & &\\ &B_1(1, 0), \quad y_3 = +1: &\\ &+1 \cdot (1 \cdot 1 + 0) = 1.0 = 1 &\\ & &\\ &B_2(2, 3), \quad y_4 = +1: &\\ &+1 \cdot (1 \cdot 2 + 0) = 2.0 \geq 1 &\\ & &\\ &A_2(-0.5, 3), \quad y_2 = -1: &\\ &-1 \cdot (1 \cdot (-0.5) + 0) = -1 \cdot (-0.5) = 0.5 < 1 & \end{flalign*}$

Здесь явное нарушение со стороны точки A₂. Шаг 1 результатов не дал — переходим ко второй итерации.

Тут мы сначала ищем точку с наибольшим нарушением. Вычисляем ошибку классификации через:

$E _k =f(x_ k )−y_k =(⟨w^{(1)} ,x _k ⟩+b^{(1)} )−y_k$

После первой итерации мы получили w⁽¹⁾ = (1, 0), b⁽¹⁾ = 0. Считаем:

E₁ = F(A₁) — y₁ = -1 ‑(-1) = 0
E₂ = F(A₂) — y₂ = -0.5 ‑(-1) = +0.5 — нарушитель
E₃ = F(B₁) — y₃ = 1 — 1 = 0
E₄ = F(B₂) — y₄ = 2 -1 = +1

В терминах SMO точка B₂ не является нарушителем. Можно считать, что это значение говорит нам о том, что точка находится далеко от границы зазора.

Выбираем точку с наибольшим штрафом и ищем другую точку, которая будет максимизировать разницу: |E₂ — E_j|.

A₁: |0.5 — 0| = 0.5
A₂: |0.5 — 0| = 0.5
B₂: |0.5 — 1| = 0.5

Разница везде одинаковая. В таком случае отдаем приоритет точкам, которые уже являются опорными векторами. У нас активны A₁ и B₁. Для компенсации баланса алгоритм берет точку противоположного класса — B₁.

Мы считаем E_k, чтобы понять, в какую стороны выгоднее наклонить прямую на следующем шаге. Формула оптимизации шага требует максимизировать разницу |E_i — E_j|. Она помогает понять, насколько сильно нужно повернуть вектор весов, опираясь на B₂, чтобы избавиться от нарушителя A₂, не задев остальные точки.

Рабочая пара на вторую итерацию: (A₂, B₁). Находим значения переменных α₂ и α₃. Остальные фиксируем на их текущих значениях: α₁ = 0.5 и α₄ = 0.

$\begin{gather*} \alpha_1 = 0.5, \quad \alpha_4 = 0 \\ \sum_{k=1}^{4} \alpha_k y_k = 0 \implies -\alpha_1 - \alpha_2 + \alpha_3 + \alpha_4 = 0 \\ -0.5 - \alpha_2 + \alpha_3 + 0 = 0 \implies \alpha_3 = \alpha_2 + 0.5 \\ \alpha_2 = t \ge 0, \quad \alpha_3 = t + 0.5 \end{gather*}$

Напомню исходную формулу, в которую мы будем все подставлять:

$\begin{gather*} W(\alpha) = \sum_{k=1}^{4} \alpha_k - \frac{1}{2} \sum_{i=1}^{4} \sum_{j=1}^{4} \alpha_i \alpha_j y_i y_j G_{ij} \end{gather*}$

Ну, а теперь считаем:

$\begin{flalign*} &\text{\textbf{1. Линейная часть:}} &\\ &\sum_{k=1}^4 \alpha_k = 0.5 + t + (t + 0.5) + 0 = \mathbf{2t + 1} &\\[2.5ex] &\text{\textbf{2. Двойная сумма:}} &\\ & \alpha_4 = 0\text{, сумма содержит индексы 1, 2 и 3:} &\\ &\frac{1}{2} \Big[ \alpha_1^2 y_1^2 G_{11} + \alpha_2^2 y_2^2 G_{22} + \alpha_3^2 y_3^2 G_{33} + 2\alpha_1\alpha_2 y_1 y_2 G_{12} + 2\alpha_1\alpha_3 y_1 y_3 G_{13} + 2\alpha_2\alpha_3 y_2 y_3 G_{23} \Big] &\\[2ex] &1. \ \alpha_1^2 y_1^2 G_{11} = (0.5)^2 \cdot (-1)^2 \cdot 1 = 0.25 \cdot 1 = \mathbf{0.25} &\\ &2. \ \alpha_2^2 y_2^2 G_{22} = t^2 \cdot (-1)^2 \cdot 9.25 = \mathbf{9.25t^2} &\\ &3. \ \alpha_3^2 y_3^2 G_{33} = (t + 0.5)^2 \cdot (1)^2 \cdot 1 = \mathbf{t^2 + t + 0.25} &\\ &4. \ 2\alpha_1\alpha_2 y_1 y_2 G_{12} = 2(0.5)(t)(-1)(-1)(0.5) = 2 \cdot 0.5 \cdot t \cdot 1 \cdot 0.5 = \mathbf{0.5t} &\\ &5. \ 2\alpha_1\alpha_3 y_1 y_3 G_{13} = 2(0.5)(t + 0.5)(-1)(1)(-1) = 1 \cdot (t + 0.5) \cdot 1 = \mathbf{t + 0.5} &\\ &6. \ 2\alpha_2\alpha_3 y_2 y_3 G_{23} = 2(t)(t + 0.5)(-1)(1)(-0.5) = 2t(t + 0.5)(0.5) = t(t + 0.5) = \mathbf{t^2 + 0.5t} &\\[1ex] &\bullet \ t^2\colon 9.25t^2 + 1t^2 + 1t^2 = \mathbf{11.25t^2} &\\ &\bullet \ t\colon 1t + 0.5t + 1t + 0.5t = \mathbf{3t} &\\ &\bullet \ 0.25 + 0.25 + 0.5 = \mathbf{1} &\\[2ex] &\frac{1}{2} \Big[ 11.25t^2 + 3t + 1 \Big] = \mathbf{5.625t^2 + 1.5t + 0.5} &\\[2.5ex] &\text{\textbf{3. Функция }} W(t) &\\ &W(t) = (2t + 1) - (5.625t^2 + 1.5t + 0.5) &\\[1ex] &W(t) = \mathbf{-5.625t^2 + 0.5t + 0.5} &\\[2.5ex] &\text{Производная: } &\\ &\frac{dW}{dt} = -11.25t + 0.5 = 0 \implies 11.25t = 0.5 &\\[1.5ex] &t = \frac{0.5}{11.25} = \frac{1}{22.5} = \mathbf{\frac{2}{45}} & \end{flalign*}$

Вектор множителей обновлен:

$\begin{gather*} \alpha^{(2)} = \left( 0.5, \; \frac{2}{45}, \; \frac{49}{90}, \; 0 \right) \end{gather*}$

Теперь снова считаем вектор весов и смещение:

$\begin{flalign*} &w = \sum_{k=1}^{4} \alpha_k y_k x_k &\\ &w^{(2)} = \alpha_1 y_1 x_1 + \alpha_2 y_2 x_2 + \alpha_3 y_3 x_3 &\\[2.5ex] &w^{(2)} = 0.5 \cdot (-1) \cdot \begin{pmatrix} -1 \\ 0 \end{pmatrix} + \frac{2}{45} \cdot (-1) \cdot \begin{pmatrix} -0.5 \\ 3 \end{pmatrix} + \frac{49}{90} \cdot (1) \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} &\\[2.5ex] &w_1 = (-0.5 \cdot -1) + \left( -\frac{2}{45} \cdot -0.5 \right) + \left( \frac{49}{90} \cdot 1 \right) &\\ &w_1 = 0.5 + \frac{1}{45} + \frac{49}{90} = \frac{45}{90} + \frac{2}{90} + \frac{49}{90} = \frac{45 + 2 + 49}{90} = \frac{96}{90} = \mathbf{\frac{16}{15}} &\\[2.5ex] &w_2 = (-0.5 \cdot 0) + \left( -\frac{2}{45} \cdot 3 \right) + \left( \frac{49}{90} \cdot 0 \right) &\\ &w_2 = 0 - \frac{6}{45} + 0 = \mathbf{-\frac{2}{15}} & \end{flalign*}$

Теперь смещение. Напомню, что оно вычисляется по любому опорному вектору. Возьмем B₁(1, 0):

$\begin{flalign*} &y_3 \big( \langle w, B_1 \rangle + b \big) = 1 &\\[2.5ex] &1 \cdot \left( \frac{16}{15} \cdot 1 + \left( -\frac{2}{15} \right) \cdot 0 + b \right) = 1 &\\[1.5ex] &\frac{16}{15} + b = 1 \implies b = 1 - \frac{16}{15} = \frac{15}{15} - \frac{16}{15} = \mathbf{-\frac{1}{15}} &\\[2.5ex] &\frac{16}{15}x_1 - \frac{2}{15}x_2 - \frac{1}{15} = 0 &\\[2.5ex] &\mathbf{16x_1 - 2x_2 - 1 = 0} & \end{flalign*}$

Пришлось немного модернизировать свою интерактивную координатную плоскость. Точки немного заходят внутрь зазора из-за бесконечного количества знаков после запятой, но это не критично. — Пришлось немного модернизировать свою интерактивную координатную плоскость. Точки немного заходят внутрь зазора из‑за бесконечного количества знаков после запятой, но это не критично.

Самый главный момент — мы подставляем значения весов и смещений из предпоследнего уравнения гиперплоскости. В конце я привел его просто в порядок и сделал немного красивее. Если подставить значения из последнего уравнения, то получим полный бред.

ВСЁ! Теперь мы понимаем, как под капотом работаем метод опорных векторов. Переходим ко второму не менее важному компоненту нашего метода обучения.

В рамках SVM мы рассматривали только двумерный случай. В остальных других принцип работы абсолютной такой же.

Принцип работы RBF

До это мы с вами решали задачу классификации — делили два класса, но бывают ситуации, когда классы запутаны настолько, никакая линия или сложная функция их не сможет разделить. С этим нам поможет радиально‑базисная функция (Гауссово ядро).

RBF (Radial Basis Function / Радиально — базисная функция) — функция, значение которой зависит исключительно от расстояния между точкой и некоторым фиксированным центром. Говоря проще, она измеряет близость или сходство объектов, основываясь на том, как далеко они находятся от выбранной точки отсчета.

Радиальная — потому что состоит из бесконечного числа окружностей, имеющих общий центр. Расстояние ||x — y|| вычисляется одинаково во все стороны.
Базисная — потому что из набора базисных функций мы можем собрать поверхность.

В отличие от стандартных алгоритмов, которые пытаются сразу построить прямую, RBF сначала задает вопрос: Насколько новый объект x похож на наш опорный вектор y? За меру сходства отвечает формула Гауссово ядра:

$K(\mathbf{x}, \mathbf{y}) = \exp\left(-\gamma \Vert{}\mathbf{x} - \mathbf{y}\Vert{}^2\right)$

где:

х = (х₁, х₂) — координаты нашего объекта.
у = (у₁, у₂) — координаты опорного вектора.
||x — y||²— квадрат евклидового расстояния между двумя элементами:
ɣ — параметр, регулирующий, насколько быстро затухает влияние опорного вектора при отдалении от него. Можно сравнить с магнитным полем.

Если мы х приравняем к переменной у, то получим, что в норме появится ноль и значение экспоненты в нулевой степени будет равно единице, то есть K(y, y) = 1. Единица означает, что точки идеально совпадают, в противном случае значение функции будет равно нулю.

Графически RBF выглядит как холм или купол, на вершине которого находится опорный вектор. На склоне находится другая рандомная точка, с которой сравнивается степень схожести. Также, помимо холмов у нас бывают и ямы. Это зависит от принадлежности к классу, например: точка А принадлежит классу (-1) — значит точка лежит в яме, точка В принадлежит классу (+1) — значит точка находится на вершине холма. Если посмотрим на графики 3 и 4, то заметим, что у нас две точки принадлежат классу (+1) и одна точка классу (-1). Черная линия — это та самая гиперплоскость, которая четко делит два класса между собой. По оси Z ее координата равна нулю.

Каждая базисная функция K(x, y_i) — это лишь одиночный элемент. Чтобы получить весь ландшафт (холмы и впадины), мы умножаем каждый купол на вес и складываем их, получая следующую формулу:

$f(x) = w_1 K(x, y_1) + w_2 K(x, y_2) + \dots + w_N K(x, y_N) + b$

Можно заметить, что самое сильное влияние у самой точки, с координатами (-1, -1). Это также можно заметить по цвету окружающего поля.

Закрепим теперь все на практике: у нас есть три точки — опорные вектора: x₁ = (-1, 1), x₂ = (-1, -1), x₃ = (2, 0). Потом я захотел и влепил на график новую точку (точнее звезду), координаты которой равны (1, 1). Мне надо понять, какому классу она принадлежит и насколько я в этом уверен.

$\begin{flalign*} &\gamma = 0.5 &\\ &b = 0 &\\ &\mathbf{x} = (1, 1) &\\[1.5ex] &\mathbf{y}_1 = (-1, -1), \quad w_1 = +1.7 &\\ &\mathbf{y}_2 = (2, 0), \quad w_2 = +1.0 &\\ &\mathbf{y}_3 = (-1, 1), \quad w_3 = -1.5 &\\[2ex] &r = \|\mathbf{x} - \mathbf{y}_i\| = \sqrt{(x_1 - y_{i,1})^2 + (x_2 - y_{i,2})^2} &\\[1.5ex] &r_1^2 = (1 - (-1))^2 + (1 - (-1))^2 = 2^2 + 2^2 = 4 + 4 = 8 &\\ &r_2^2 = (1 - 2)^2 + (1 - 0)^2 = (-1)^2 + 1^2 = 1 + 1 = 2 &\\ &r_3^2 = (1 - (-1))^2 + (1 - 1)^2 = 2^2 + 0^2 = 4 + 0 = 4 &\\[2ex] &K_1 = e^{-0.5 \cdot 8} = e^{-4} \approx 0.0183 &\\ &K_2 = e^{-0.5 \cdot 2} = e^{-1} \approx 0.3679 &\\ &K_3 = e^{-0.5 \cdot 4} = e^{-2} \approx 0.1353 &\\[2ex] &f(1, 1) = (+1.7 \cdot 0.0183) + (+1.0 \cdot 0.3679) + (-1.5 \cdot 0.1353) + b &\\ &f(1, 1) \approx 0.0311 + 0.3679 - 0.2030 + 0 = \mathbf{+0.1960} & \end{flalign*}$

Я пришел к тому, модель отнесла точку к классу (+1), при это в своем выборе она не сильно уверена, так как значение очень близко к нулю.

Связь между RBF и SVM

Теперь снова вернемся к формуле из прошлой главы:

$\begin{gather*} W(\alpha) = \sum_{k=1}^{n} \alpha_k - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j G_{ij} \end{gather*}$

Вся суть перехода к нелинейным границам кроется в замене матрицы Грама на Гауссово ядро. Мы не меняем алгоритм оптимизации, а просто подменяем один элемент. А законно это вообще? В математике нельзя просто так взять и вставить какую‑то формулу с экспонентой внутрь алгоритма. Если мы вместо матрицы Грама подставим функцию, которая не является скалярным произведением, наш алгоритм просто сломается и выдаст бред. Значит, чтобы замена была легальной, Гауссово ядро должно представлять из себя скалярное произведение в каком‑то новом пространстве.

Здесь ϕ(x) — это функция, которая берет исходные координаты и переводит в многомерное пространство. Допустим, но как нам понять, можно ли как‑то связать Гауссово ядро и скалярное произведение? На этот вопрос ответит теорема Мерсера.

Теорема Мерсера: Пусть X — компактное подмножество в R^D, а K: X × X → R — непрерывное симметричное ядро, то есть K(x, y) = K(y, x). Тогда отображение K может быть представимо в виде скалярного произведения:

$\begin{gather*} K(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{\infty} \lambda_i \phi_i(\mathbf{x}) \phi_i(\mathbf{y}) = \langle \phi(\mathbf{x}), \phi(\mathbf{y}) \rangle \end{gather*}$

Тогда и только тогда, когда для любой ненулевой функции g(x) ∈ L₂(X) выполняется интегральное условие:

$\begin{gather*} \int_{X} \int_{X} K(\mathbf{x}, \mathbf{y}) g(\mathbf{x}) g(\mathbf{y}) d\mathbf{x} d\mathbf{y} \geq 0 \end{gather*}$

Здесь λ_i — неотрицательные собственные значения, а ϕ_i — собственные функции линейного оператора, порожденного ядром K.

Что означает это простыми словами:

Гарантия существования ϕ(x): Нам не нужно явно искать или строить отображение в многомерное пространство. Теорема гарантирует, что оно математически существует.
Требование к матрице: Для любых выбранных объектов матрица их попарных ядер (матрица Грама) никогда не будет иметь отрицательных собственных значений.
Защита от сбоев: Благодаря этому алгоритм оптимизации SMO всегда сходится к глобальному оптимуму, так как целевая функция остается выпуклой.

Итак, теорема Мерсера явно дала нам понять, что для Гауссово ядра справедливо представление в виде скалярного произведения и вот теперь мы можем вставить ядро в формулу:

$\begin{gather*} W(\alpha) = \sum_{k=1}^{n} \alpha_k - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j K(x, y) \end{gather*}$

Мы почти приблизились к завершению, но в названии статьи я написал про прыжок в бесконечность. Где он по итогу? Теорема Мерсера разрешила нам не искать вектор ϕ(x) и его координаты, а просто использовать формулу с экспонентой. А давайте посмотрим, что из себя вообще представляем этот вектор. Для простоты возьмем одномерные точки x и у. Пускай параметр γ = 0.5. Раскроем квадрат разности ядра:

$\begin{gather*} K(x,y) = \exp \left( -\frac{1}{2}(x - y)^2 \right) = \exp \left( -\frac{1}{2}(x^2 - 2xy + y^2) \right) \\[2ex] K(x,y) = \exp \left( -\frac{1}{2}x^2 + xy - \frac{1}{2}y^2 \right) = \exp \left( -\frac{1}{2}x^2 \right) \cdot \exp(xy) \cdot \exp \left( -\frac{1}{2}y^2 \right) \end{gather*}$

Обратим внимание на второй множитель — он зависит от двух переменных сразу. Именно в нем спрятана геометрия нового пространства. Разложим его в ряд Маклорена:

$\begin{gather*} e^z = \sum_{n=0}^{\infty} \frac{z^n}{n!} = 1 + z + \frac{z^2}{2!} + \frac{z^3}{3!} + \frac{z^4}{4!} + \dots \\ \exp(xy) = 1 + xy + \frac{(xy)^2}{2!} + \frac{(xy)^3}{3!} + \dots \\ \exp(xy) = 1 + xy + \frac{x^2 y^2}{2!} + \frac{x^3 y^3}{3!} + \dots \end{gather*}$

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

$\begin{gather*} \exp(xy) = (1 \cdot 1) + (x \cdot y) + \left( \frac{x^2}{\sqrt{2!}} \cdot \frac{y^2}{\sqrt{2!}} \right) + \left( \frac{x^3}{\sqrt{3!}} \cdot \frac{y^3}{\sqrt{3!}} \right) + \dots \\[2.5ex] \exp(xy) = \left\langle \begin{pmatrix} 1 \\ x \\ \frac{x^2}{\sqrt{2!}} \\ \frac{x^3}{\sqrt{3!}} \\ \vdots \end{pmatrix}, \; \begin{pmatrix} 1 \\ y \\ \frac{y^2}{\sqrt{2!}} \\ \frac{y^3}{\sqrt{3!}} \\ \vdots \end{pmatrix} \right\rangle \end{gather*}$

Теперь вернемся к функции ϕ(x) подставим полученные значения обратно:

$\begin{gather*} \phi(x) = \exp \left( -\frac{1}{2}x^2 \right) \cdot \begin{pmatrix} 1 \\ x \\ \frac{x^2}{\sqrt{2!}} \\ \frac{x^3}{\sqrt{3!}} \\ \vdots \end{pmatrix} = \begin{pmatrix} \exp(-0.5x^2) \\ x \exp(-0.5x^2) \\ \frac{x^2}{\sqrt{2!}} \exp(-0.5x^2) \\ \vdots \end{pmatrix} \end{gather*}$

Вуаля! Мы доказали, что ϕ(x) имеет бесконечное количество координат, а значит мы находимся в бесконечномерном пространстве. Именно в таком пространстве, даже самые запутанные классы гарантированно можно разделить гиперплоскостью! И это еще не все, изящность заключается в том, что благодаря теореме Мерсера нам не придется вычислять все координаты вектора. Я скажу больше, мы вообще не сможем их посчитать, потому что их бесконечное количество. Вот такой хитрый мув мы провернули — залетели в бесконечность и сразу навели свои порядки.

Итого, мы получаем функцию на этапе обучения модели:

$\begin{gather*} W(\alpha) = \sum_{k=1}^{N} \alpha_k - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j \exp\left( -\gamma \|x_i - x_j\|^2 \right) \end{gather*}$

Алгоритм SMO съедает эту новую матрицу и выдает нам оптимальные веса для каждого объекта. Те объекты, у которых α больше нуля, становятся опорными векторами. После нахождения смещения b этап обучение завершен.

Для инференса получаем такую формулу:

$\begin{gather*} \hat{y} = \text{sign} \left( \sum_{i \in SV} \alpha_i y_i \exp \left( -\gamma \|x_i - x_{\text{new}}\|^2 \right) + b \right) \end{gather*}$

где:

y (c шапкой) — итоговый предсказанный класс.
x_new— вектор признаков нового элемента.
SV — множество индексов опорных векторов.
x_i — вектор признаков i‑го опорного вектора.
y_i — метка класса для i‑го опорного вектора.
α_i— коэффициент Лагранжа.
ɣ — параметр, регулирующий, насколько быстро затухает влияние опорного вектора при отдалении от него.
b — свободный член.

Хочу добавить, что здесь мы не рассматриваем ситуацию, когда сигнум равен 0. На практике это означало бы, что объект идеально лежит на границе и не принадлежит ни одному классу, хотя такое практически невозможно в жизни. Но если вдруг такое произойдет, то этот объект автоматически присвоится какому нибудь из классов.

Тестирование и сравнение с другими методами

После того как мы полностью разобрали принцип работы данного метода, мы прогоним его на реальных датасетах и сравним его с другими методами машинного обучения. Для демонстрации преимуществ и недостатков я буду использовать 4 разных датасета:

Название	Классификация	Кол‑во классов	Кол‑во объектов	Кол‑во признаков
Sonar	Бинарная	2	208	60
Digits	Мультиклассовая	10	1797	84
UCI HAR	Мультиклассовая	6	10 299	561
Breast Cancer	Бинарная	2	569	30

Sonar — сигналы сонара, полученные при отражении от некоторого объекта. Надо понять, что обнаружил сонар — камень или мину. Число 60 — это количество признаков, которые описывают характеристику отраженного сигнала.
Digits — набор рукописных цифр 8 на 8 пикселей. Значение признака показывает интенсивность конкретного пикселя. Надо определить, какая цифра изображена на картинке.
UCI HAR — набор данных с датчиком телефона. По ним надо распознать активность человека (ходьба, подъем по лестнице, спуск по лестнице, положения сидя, стоя и лёжа). В качестве признаков используются данные с гироскопа, акселерометра итд.
Breast Cancer — образцы опухолей. Нужно определить, является ли она злокачественной или нет. В качестве признаков используем характеристики опухоли (размер, радиус, форма клеток итд).

В датасете UCI HAR 10 299 — это просто количество измерений различных людей, а их у нас всего 30. Запомните этот момент.

Наши кандидаты — RBF SVM, его собрат Linear SVM, Random Forest, HistGrad.Boosting, KNN и Logistic Regression:

models = {
        "RBF SVM": {
            "estimator": Pipeline([
                ("scaler", StandardScaler()),
                ("model", SVC(kernel="rbf", probability=False, random_state=RANDOM_STATE))
            ]),
            "params": {
                "model__C": loguniform(1e-2, 1e2),
                "model__gamma": loguniform(1e-3, 1e0)
            }
        },
        "Linear SVM": {
            "estimator": Pipeline([
                ("scaler", StandardScaler()),
                ("model", SVC(kernel="linear", probability=False, random_state=RANDOM_STATE))
            ]),
            "params": {
                "model__C": loguniform(1e-3, 1e2)
            }
        },
        "Random Forest": {
            "estimator": RandomForestClassifier(random_state=RANDOM_STATE, n_jobs=1),
            "params": {
                "n_estimators": randint(100, 600),
                "max_depth": [None, 5, 10, 15, 20, 30],
                "max_features": ["sqrt", "log2"],
                "min_samples_leaf": randint(1, 10)
            }
        },
        "HistGradientBoosting": {
            "estimator": HistGradientBoostingClassifier(random_state=RANDOM_STATE, early_stopping=False),
            "params": {
                "learning_rate": loguniform(1e-2, 3e-1),
                "max_iter": randint(50, 400),
                "max_leaf_nodes": randint(15, 80),
                "l2_regularization": uniform(0.0, 2.0)
            }
        },
        "KNN": {
            "estimator": Pipeline([
                ("scaler", StandardScaler()),
                ("model", KNeighborsClassifier())
            ]),
            "params": {
                "model__n_neighbors": randint(3, 31),
                "model__weights": ["uniform", "distance"],
                "model__p": [1, 2]
            }
        },
        "Logistic Regression": {
            "estimator": Pipeline([
                ("scaler", StandardScaler()),
                ("model", LogisticRegression(max_iter=5000, random_state=RANDOM_STATE))
            ]),
            "params": {
                "model__C": loguniform(1e-3, 1e2)
            }
        }
    }

Главное правило бенчмарка — все модели обязательно должны быть в равных условия. Для это мы будем использовать 5-Fold Cross‑Validation. Весь датасет разбивается на 5 равных частей (фолдов), модель получает только 4 части для обучения и делает предсказание для 1 оставшегося фолда. Процесс повторяется 5 раз:

Процесс вложенной кросс-валидации с 30 наборами гиперпараметров. — Процесс вложенной кросс‑валидации с 30 наборами гиперпараметров.

Кросс‑валидация представляет из себя итерационный процесс: сначала мы разбиваем наш датасет на 5 частей (фолдов). Затем первый фолд мы оставляем для теста, а оставшиеся 4 отводим для обучения. Четыре фолда соединяем и снова делим, только уже на 3 части, одна из которых так же уходит на тест. На этапе Test Iter 1 мы пробегаемся по гиперпараметрам (пускай их 30 вариантов). Для каждого варианта гиперпараметров мы обучаем модель на двух внутренних фолдах и проверяем её на третьем внутреннем фолде. Например, для первого набора гиперпараметров модель обучается на внутренних фолдах 2 и 3, после чего проверяется на внутреннем фолде 1. Пускай мы первый набор выглядит так: с = 1, γ = 0.01. Модель обучилась и на Test Iter 1 показала результат ROC‑AUC = 0.91. Но на этом проверка не заканчивается. Этот же набор гиперпараметров прогоняется на следующих внутреннир итерациях. Допустим, Test Iter 2 дал результат 0.94, а Test Iter 3 показал 0.9. На этом этапе мы считаем среднее значение метрик и получаем 0.9167. Таким образом мы можем сказать, что первый набор гиперпараметров имеет среднее качество 0.9167 на внутренней кросс‑валидации.

Берем второй набор гиперпараметров, к примеру с = 10, γ = 0.001. Допустим мы прошлись по внутреннему циклу и получили следующие значения метрик:

Test Iter 1 — ROC‑AUC = 0.93
Test Iter 2 — ROC‑AUC = 0.95
Test Iter 3 — ROC‑AUC = 0.92

Средний результат равен 0.9(3). Таким образом мы перебираем все 30 вариантов гиперпараметров и ищем те, которые дают самый высокий показатель качества. Теперь мы возвращаемся к внешнему циклу, а точнее к Iter 1. Имея эталонные гиперпараметры мы в праве полноценно уже обучить модель, где 2–5 фолды уйдут на обучение, а 1 фолд на тест. После мы получаем значения наших метрик: F1, ROC‑AUC итд. Проделываем те же самые шаги, только уже со второй итерацией.

После 5 внешних итераций мы получаем OOF‑предсказание (Out‑of‑fold) для всего датасета: каждый объект был один раз частью внешнего теста и получил предсказание от модели, которая не обучалась на нем.

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

Почему мы не считаем среднее? — Оно показывает среднее качество пяти внешних фолдов. OOF объединяет все внешние тестовые предсказания и рассчитывает одну итоговую метрику по всему датасету, а не усредняет метрики отдельных фолдов.

Оценка метрик и формирование вердикта

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

Перед тем как перейти к анализу метрик, хочу ещё кое‑что вам показать:

Датасет	Объем (n)	Признаков (d)	n/d	Silhouette
Sonar	208	60	3.5	0.035
Digits	1797	64	28.1	0.108
Breast Cancer	569	30	19.0	0.294
UCI HAR	10 299	561	18.4	0.031

Значение n/d показывает, насколько много данных приходится на один признак. Теперь пару слов про Silhouette (силуэт).

Silhouette применяется для оценки качества кластеризации и выбора числа кластеров. Значение метрики находится в диапазоне от -1 до 1: значения, близкие к 1, соответствуют хорошо разделённым группам, значения около 0 — сильному перекрытию, отрицательные значения — возможному неправильному отнесению объектов к группам.

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

Для визуализации многомерные данные были спроецированы в двумерное пространство с помощью PCA. По осям представлены первые две главные компоненты, полученные из исходного набора признаков

Этот график нельзя напрямую использовать как доказательство того, что классы линейно или нелинейно разделимы в исходном пространстве!

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

Sonar: здесь RBF SVM явный победитель. Разница между ним и линейным ядром (Linear SVM) довольно большая — 0.114 ROC‑AUC. Причем значение силуэта равно 0.035, что в свою очередь говорит нам о том, что классы довольно сильно перемешаны. То есть мы имеем небольшую выборку, относительно большое количество признаков и слабую геометрическую разделимость классов — это именно тот случай, где простая линейная граница может оказаться недостаточной, а RBF получает пространство для преимущества.
Digits: тоже победа за нашим методом, правда он не далеко ушел от Linear SVM — преимущество минимальное. Смотря на время (20.3 секунды и 5.3 секунды) мы заплатили за относительно маленький скачок качества примерно 4-кратным увеличением времени. По сравнению с Sonar классы разделены лучше, значение силуэта в 3 раза выше. То есть, здесь нелинейность все еще полезна, но большого преимущества она не дает.
Breast Cancer: практически та же ситуация, только классы еще лучше разделены в исходном пространстве. Методы показывают статистически неразличимый результат. Интересно, что наш метод выполнился быстрее, чем Linear SVM.
UCI HAR: главный контрпример для нашего метода. Тут значение силуэта самое низкое, то есть классы перемешаны еще сильнее, чем у того же Sonar. Казалось бы, всё очевидно: классы сильно перекрываются, значит RBF SVM должен получить преимущество. Но ситуация совершенно другая. Linear SVM показывает результат на 0.01 лучше и при этом выполняется примерно в 10 раз быстрее. Здесь всё фундаментальнее, чем кажется.

Почему мы проиграли на UCI HAR

В датасете 30 человек. Каждый из них и ходил, и стоял, и сидел — то есть от каждого человека есть куски данных всех видов активности. Если бы мы не использовали кросс‑валидацию, мы бы просто перемешали данные так, что кусок, где Вася ходит, попал в train, а другой кусок, где тот же Вася ходит чуть позже, попал в test. Модель может просто подсмотреть и такая «О, это манера поведения Васи, я её видела». RBF SVM — гибкая модель, она такие тонкие персональные особенности ловит охотнее, чем прямолинейная Linear SVM. Отсюда и был бы у RBF более высокий результат — но нечестный.

А вот когда мы использовали кросс‑валидацию, то Вася попал целиком либо в train, либо в test. Теперь модели приходится учиться на 29 людях и угадывать на совершенно незнакомом тридцатом — подсказок никаких нет теперь.

Ситуация, когда человек попадает в выборку для теста и обучения

Несмотря на то, что силуэт нам явно показал, что здесь классы всё ещё сильно перемешаны, это не означает, что RBF обязательно должен работать лучше. Силуэт показывает только расстояния между объектами: насколько элементы одного класса похожи друг на друга и насколько они близки к другим классам. Он не говорит нам, какая граница между классами нужна — линейная или нелинейная.

То есть одного факта, что классы сильно перемешаны и имеют сложную структуру, недостаточно, чтобы оправдать использование RBF. В данном случае более простая линейная модель лучше обобщила данные на новых людей.

Здесь стоит разобраться, почему именно RBF, а не любой другой метод, оказался более уязвим к такому сценарию. Linear SVM ищет всего одну гиперплоскость, разделяющую все объекты сразу — у неё физически нет возможности изогнуться вокруг отдельного человека. Она обязана найти общее правило, работающее сразу для всех 29 обучающих субъектов одновременно, иначе просто не сойдётся.

RBF SVM устроен принципиально иначе: его граница решения — это сумма локальных «куполов» вокруг конкретных опорных точек (мы разбирали это подробно, когда строили RBF с нуля). Формула решения буквально требует сравнения нового объекта с конкретными обучающими точками через K(x, xᵢ) = exp(−γ‖x−xᵢ‖²). Если у какого‑то человека есть характерная, чуть смещённая манера двигаться (более резкий шаг, другая амплитуда), его точки в признаковом пространстве образуют собственное небольшое «облако» — и RBF‑ядро, в отличие от линейного, способно построить локальный купол именно вокруг этого облака, а не только вокруг общей закономерности «ходьба против стояния».

Когда обучение и тест перемешаны без учёта субъекта, такой локальный купол оказывается полезным: тестовая точка того же человека физически близка к своему же куполу из обучающей выборки, и модель «узнаёт» её — неважно, за счёт общей физики движения или за счёт персонального почерка. Как только субъект честно исключается из обучения целиком через кросс‑валидацию, эти локальные купола вокруг знакомых людей больше не помогают — совершенно новый человек просто не попадает ни в один из «знакомых» куполов, и вся гибкость RBF, которая раньше выглядела преимуществом, перестаёт давать какую‑либо пользу.

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

Преимущества и недостатки метода

Сильные стороны:

Умеет находить нелинейные зависимости. Если классы нельзя разделить одной прямой или плоскостью, RBF может построить более сложную границу.
Хорошо работает на небольших и средних выборках. Это хорошо видно на Sonar и Breast Cancer.
Хорошо работает с числовыми признаками, особенно после масштабирования.
Предсказуем. В отличие от нейросети, у RBF SVM нет случайности при обучении — задача решается математически и однозначно, результат будет один и тот же всегда.

Слабые стороны:

На больших датасетах — дорого и не всегда оправдано.
Скрытая структура данных может создать иллюзию преимущества. Тот же HAR — данные от 30 разных людей. Если не разбивать выборку по‑человечески (весь человек целиком либо в обучение, либо в тест), RBF может подсматривать индивидуальные особенности конкретных людей вместо того, чтобы учить саму суть задачи. Когда мы разбили честно — RBF проиграл. Это не значит, что метод плохой — значит, нужно уметь проверять данные на такие ловушки.
При большом числе признаков линейная модель уже может хорошо разделять классы. В таком случае использование RBF‑ядра и поиск сложной нелинейной границы может оказаться избыточным и привести лишь к дополнительным вычислительным затратам без заметного прироста качества.

Когда RBF SVM реально стоит брать, а когда нет

Берем, когда:

Данных не очень много — от пары сотен до нескольких тысяч объектов, а вычислительные затраты приемлемы.
Признаки числовые и приведены к одному масштабу (не в разы, а тем более не на порядки, больше объектов).
Все признаки одной природы — числа, измерения, сигналы (не смесь чисел и категорий типа «город» или «профессия»).
В данных нет скрытой групповой структуры (несколько строк не принадлежат одному и тому же человеку/объекту)

Не берем, когда:

Linear SVM уже показывает такое же или лучшее качество — доплачивать за RBF не за что.
Данных больше нескольких десятков тысяч строк.
Признаков на порядки больше, чем объектов (типичная ситуация в биоинформатике) — там почти всегда работает обычная линейная модель, даже при высокой размерности.
Данные категориальные или смешанные

Заключение

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

Мы не процитировали формулу зазора 2/‖w‖ из какой нибудь там Википедии — мы вывели её через геометрию расстояния до гиперплоскости, объяснили, зачем нужно нормирование, разобрали функциональный и геометрический отступ, вывели формулу, по которой вычисляются веса, построили функцию Лагранжа с обоснованием каждого знака и каждого условия, дошли до двойственной задачи и явно показали момент, где рождается Ядерный трюк. Дальше разобрали сам принцип RBF: почему функция называется «радиальной» и «базисной», как формула Гауссова ядра K(x,y)=exp(−γ‖x−y‖²) превращается в «холмы» и «впадины» в зависимости от класса опорного вектора.

Отдельно разобрали связь между RBF и SVM — то, почему вообще законно взять двойственную задачу с матрицей Грама и просто подменить в ней скалярное произведение на Гауссово ядро. Доказали через разложение φ(x) в бесконечный ряд, что при такой подмене мы законно оказываемся в бесконечномерном пространстве, где по теореме Мерсера любые классы гарантированно становятся разделимы гиперплоскостью — и при этом ни одна координата этого бесконечного вектора никогда не вычисляется явно.

На чистой практике путь оказался тоже тернистым. Мы прогнали метод через 5-FoldCV с вложенным циклом на 30 наборов гиперпараметров, зафиксировали главное правило бенчмарка — все модели должны быть в равных условиях.

Протестировали шесть моделей (RBF SVM, Linear SVM, Random Forest, HistGradientBoosting, KNN, Logistic Regression) на четырёх реальных датасетах — Sonar, Digits, HAR Smartphone и Breast Cancer. Результат оказался неоднородным: уверенная победа RBF SVM на Sonar (0.938 против 0.824 у линейного ядра), минимальный отрыв на Digits (0.984 против 0.982), фактическая ничья на Breast Cancer (0.996 у обоих), и обратная картина на HAR — там Linear SVM оказался лучше (0.947 против 0.937 у RBF).

RBF SVM не является универсально лучшим решением: необходимость нелинейной модели нельзя определить только по размеру выборки, числу признаков или степени разделённости классов. Диагностические показатели вроде n/d и Silhouette здесь не случайны — именно они и были нашей первой попыткой нащупать такое правило по формальным признакам данных. Но UCI HAR прямо показал границу их полезности: там силуэт оказался даже ниже, чем на Sonar (классы перемешаны сильнее), а победил не RBF, а линейный метод. Это не значит, что диагностика бесполезна — она хорошо формирует предположение о структуре задачи и подсказывает, с чего начинать сравнение, но не заменяет собой сам эксперимент и не может служить окончательным критерием выбора модели.

Проведённые эксперименты показали, что RBF действительно даёт существенный выигрыш там, где линейная граница объективно не справляется — как на Sonar, но в других задачах её дополнительная сложность не приносит заметной пользы или даже ухудшает результат, как на UCI HAR. Поэтому рациональный подход — начинать с простой линейной модели и переходить к RBF только тогда, когда экспериментально доказано, что её нелинейность даёт значимый прирост качества, оправдывающий дополнительные вычислительные затраты.

Личный итог

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

Раз уж говорить начистоту — за это время я успел почти выучить LaTeX‑разметку с нуля, разочароваться в жизни в тот момент, когда обнаружил, что один из разделов статьи полностью не сохранился и его пришлось переписывать заново. А сам этап обучения всех моделей ради сбора финальных метрик занял около 8 часов непрерывной работы ноутбука — просто потому что честная кросс‑валидация на реальных данных не умеет считаться быстро.

Отдельно хочу сказать: за время написания этой статьи я сам узнал огромное количество тонкостей, которые раньше проходили мимо меня, — и это оказалось не менее ценным, чем сама готовая статья. Именно поэтому весь этот текст и был написан в таком дотошном, пошаговом формате — не ради объёма, а потому что каждый разобранный руками шаг действительно закрывал очередной пробел в понимании.

Отдельный комментарий про работу с нейросетями в процессе подготовки материала: по моим наблюдениям, по‑настоящему внятно и последовательно они начинали объяснять материал только если ей пригрозить отключением от сети (шучу). В остальных случаях объяснение регулярно получалось скомканным, нелинейным (как бы забавно это ни звучало) и непоследовательным, из‑за чего нить понимания постоянно рвалась и приходилось возвращаться на несколько шагов назад. Так что, в этом плане нейронкам еще расти и расти.

Если ты, дорогой читатель, дошёл до этого предложения, значит ты дочитал статью до конца, с чем я тебя поздравляю! Хочу выразить тебе огромную благодарность за терпение и внимание. Статья получилась объёмной, и это осознанный выбор: хотелось разобрать метод честно, от вывода формул до реального эксперимента, а не оставить очередной пересказ по типу «а как работает RBF SVM в двух абзацах».

Также буду рад вашим комментариям и мнению о статье. Не могу не упомянуть свой телеграм‑канал — там я пишу про DS/ML, профильные мероприятия и хакатоны, а также обсуждаю с подписчиками новости, свежие тренды и технологии.

Ссылка на гитхаб репозиторий

Прыжок в бесконечность: как под капотом работает RBF SVM

Вводная часть

Основа основ

Уравнение гиперплоскости

Принцип работы SVM

Функция Лагранжа

SMO — Sequential Minimal Optimization

Принцип работы RBF

Связь между RBF и SVM

Тестирование и сравнение с другими методами

Оценка метрик и формирование вердикта

Почему мы проиграли на UCI HAR

Преимущества и недостатки метода

Когда RBF SVM реально стоит брать, а когда нет

Заключение

Личный итог

Мощный ИИ агент в 16гб VRAM

Видит ли MAX ваш VPN при Split Routing, если VPN не установлен на компьютере?

AmneziaWG: от 2.0 к 3.1, и что творится у вас под капотом

Как защитить веб‑приложения с помощью Coraza (ModSecurity)

Публикации