Разбираемся в ML без воды: от базы до Attention. Часть 8: Kernel Trick

В предыдущей части мы затронули концептуальную идею Kernel Trick (ядерного трюка). Если говорить кратко: когда у нас нет возможности линейно разделить данные в текущем пространстве признаков, мы можем отобразить их в пространство более высокой размерности, где классы станут легко разделимы обычной гиперплоскостью.

В этой части мы глубоко изучим математическое устройство этого метода и разберемся, почему и как именно он работает «под капотом».

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

Перед основной работой поговорим немного о теории.

Первым делом введем Лагранжиан (функцию Лагранжа).

Пусть дана функция , которую нужно минимизировать при условиях , где $i=1,\dots,m$ и $g_i(x) \le 0$ , при $j=1,\dots,k$ .

Лагранжиан $\mathcal{L}(x, \lambda, \alpha)$ строится следующим образом:

$\mathcal{L}(x, \lambda, \alpha) = f(x) + \sum_{i=1}^{m}\lambda_ih_i(x) + \sum_{j=1}^{k}\alpha_ig_i(x),$

где $\lambda_i$ — множители Лагранжа (двойственные переменные) для ограничений-равенств,
а $\alpha_i \ge 0$ — для ограничений-неравенств.

Вот три главных принципа, на которых строится этот процесс:

Поиск седловой точки: Решение исходной задачи часто сводится к поиску седловой точки функции Лагранжа — точки, являющейся минимумом по одному направлению и максимумом по другому. Для её нахождения частные производные приравнивают к нулю.
Условия Каруша-Куна-Таккера (KKT): Для задач с ограничениями-неравенствами лагранжиан служит основой условий KKT. Они представляют собой систему необходимых (а в случае выпуклости — и достаточных) условий для оптимального решения.
Двойственность: Построение лагранжиана позволяет перейти от исходной задачи к двойственной. Это часто упрощает вычисления и дает нижние оценки для минимума.

Условия Каруша-Куна-Таккера

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

Стационарность (Stationarity): Градиент лагранжиана по исходным переменным в точке
минимума должен быть равен нулю:

$\nabla_x \mathcal{L}(x^*, \lambda^*, \alpha^*) = \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^{k} \alpha_j^* \nabla g_j(x^*) = 0$
Допустимость прямой задачи (Primal Feasibility): Точка должна удовлетворять всем исходным ограничениям: $h_i(x^*) = 0, \forall i = 1, \dots,m$ для условий-равенств, а также $g_j(x^*) \le 0, \forall j = 1, \dots, k$ , для условий-неравенств
Допустимость двойственной задачи (Dual Feasibility): Множители Лагранжа при ограничениях-неравенствах не могут быть отрицательными: $\alpha_j^* \ge 0, \forall j = 1, \dots, k$
Дополняющая нежесткость (Complementary Slackness): Произведение каждого множителя Лагранжа на соответствующее ограничение-неравенство должно быть строго равно нулю: $\alpha_j^* g_j(x^*) = 0, \forall j = 1, \dots, k$ .

Именно условие дополняющей нежесткости играет ключевую роль. Оно означает, что если ограничение выполняется с запасом (), то штраф за него обнуляется ( $\alpha_j^* = 0$ ). И наоборот: если коэффициент активен $(\alpha_j^* > 0$ ), то ограничение должно выполняться строго на границе ().

Кстати говоря, во многих источниках (особенно в советских учебниках) данное условие встречается как «условие Куна-Таккера». Говорят, что Каруш раньше дошел до этого, но его труды остались незамеченными, а потом каким-то образом мир узнал об этом. В общем, мы не обидим Каруша и оставим его фамилию.

Двойственная задача SVM

Как говорится, вернемся к нашим баранам. Вспомним постановку задачи для SVM:

$\min_\omega\frac{1}{2}||\omega||^2: \ y_i\langle \omega, x_i \rangle \ge 1$

Перепишем ограничение в стандартной форме ( $g_i(\omega) \le 0$ ):

$g_i(\omega) = 1 - y_i\langle \omega, x_i \rangle \le 0.$

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

$\mathcal{L}(\omega, \alpha) = \frac{1}{2}||\omega||^2 + \sum_{i=1}^{n}\alpha_i(1 - y_i\langle \omega, x_i \rangle)$

Применим условие стационарности (приравняв градиент к нулю):

$\nabla_\omega\mathcal{L}(\omega,\alpha) = \omega - \sum_{i=1}^{n}\alpha_iy_ix_i = 0$

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

$\omega = \sum_{i=1}^{n}\alpha_iy_ix_i$

Подставим это выражение обратно в лагранжиан и избавимся от весов:

$\mathcal{L}(\alpha) = \frac{1}{2}||\sum_{i=1}^{n}\alpha_iy_ix_i ||^2 + \sum_{i=1}^{n}\alpha_i(1 - y_i\langle \sum_{j=1}^{n}\alpha_jy_jx_j , x_i \rangle)$

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

$\mathcal{L}(\alpha) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle \to \max_\alpha$

При ограничении $\alpha_i \ge 0$ . Кроме того, если мы вспомним про (bias), который мы удобно

спрятали в $\omega$ , то в лагранжиане появится слагаемое $-\sum_i a_iy_ib_i$ . Придется честно взять

производную по , откуда получим ещё одно ограничение: $\sum_{i=1}^{n}\alpha_iy_i = 0$ .

Что мы получили? В формуле никаких $\omega$ , а мы строим модель машинного обучения. Хоть и выглядит это (как минимум) странно, на самом деле, всё более чем в порядке. На секунду представим, что мы уже решили задачу и нашли подходящее $\alpha$ .

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

$\hat{y} = \text{sign}(\langle\omega,x\rangle) = \text{sign}\left(\left\langle\sum_{i=1}^{n}\alpha_iy_ix_i, x\right\rangle\right) = \text{sign}\left(\sum_{i=1}^{n}a_iy_i\langle x_i,x\rangle\right)$

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

Ядро (Kernel)

Включим наш внутренний геометрический интепретатор и зададим себе вопрос: а что вообще такое скалярное произведение \langle x_i, x \rangle в формуле предсказания?

Вспоминая геометрию, скалярное произведение — это величина, показывающая схожесть двух объектов. Если новый объект $x$ похож на обучающий вектор $x_{i}$ (они сонаправлены), значение будет большим. Если они абсолютно разные (перпендикулярны), то произведение зануляется.

Выходит, что и обучение SVM, и предсказание для новых точек зависят исключительно от попарной схожести объектов.

И тут возникает следующая идея: а почему мы обязаны измерять схожесть только стандартным скалярным произведением?

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

Итак. Ядро (Kernel) — это функция , которая принимает на вход два вектора из исходного пространства и возвращает число, равное их скалярному произведению в некотором Гильбертовом пространстве. Простыми словами, Гильбертово пространство — это линейное пространство (конечномерное или бесконечномерное), в котором строго определено скалярное произведение.

Выражаясь на языке формул: $K(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle$

Но можно ли взять вообще любую хитрую математическую формулу и назвать её ядром? Конечно, нет. Функция должна честно гарантировать, что где-то действительно существует то самое Гильбертово пространство, в котором её результат равен скалярному произведению. И критерий этой «честности» задает теорема Мерсера.

Функция является ядром тогда и только тогда, когда выполняются два условия:

Симметричность:

Положительная полуопределенность (дискретный аналог): Для любого конечного набора точек $x_1, \dots, x_n$ и любых вещественных чисел $c_1, \dots, c_n$ выполняется неравенство:

$\sum_{i=1}^{n}\sum_{j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})\ge 0$

Внимательно посмотрим на левую часть последнего неравенства: $\sum_{i=1}^{n}\sum_{j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})\ge 0.$

На первый взгляд эта двойная сумма выглядит не очень, но её можно легко переписать на языке линейной алгебры. Для этого введем два объекта:

Вектор коэффициентов , составленный из всех чисел $c_1, \dots, c_n$ :

$c=\left(\begin{matrix}c_{1}\\ c_{2}\\ \vdots \\ c_{n}\end{matrix}\right)$

Квадратную матрицу размером $n \times n$ , элементами которой являются попарные значения ядра для всех наших объектов. Эту матрицу называют матрицей ядра или матрицей Грама:

$G=\left(\begin{matrix}K(x_{1},x_{1})&K(x_{1},x_{2})&\dots &K(x_{1},x_{n})\\ K(x_{2},x_{1})&K(x_{2},x_{2})&\dots &K(x_{2},x_{n})\\ \vdots &\vdots &\ddots &\vdots \\ K(x_{n},x_{1})&K(x_{n},x_{2})&\dots &K(x_{n},x_{n})\end{matrix}\right)$

Теперь заметим, что выражение под двойной суммой — это не что иное, как покоординатное расписание квадратичной формы. В матричном виде эта двойная сумма сворачивается в короткое произведение:

$c^TGc \ge 0$

Такое требование для любого ненулевого вектора — это каноническое определение положительно полуопределенной матрицы (Positive Semi-Definite).

Таким образом, теорема Мерсера на практике сводится к очень понятному правилу: ядро должно быть таким, чтобы для любой выборки объектов, которая нам попадется, её матрица Грама окажется положительно полуопределенной.

Зачем это алгоритму?

У положительно полуопределенной матрицы все собственные значения неотрицательны. Для SVM это имеет критическое значение. Благодаря положительной полуопределенности матрицы Грама функция потерь в двойственной задаче гарантированно будет строго выпуклой. У неё будет только один глобальный оптимум, который наш алгоритм оптимизации найдет без риска застрять в локальных минимумах.

Несколько типов ядер

Несмотря на то, что можно взять ручку и бумагу и за час придумать 100500 ядер, на практике в 99% случаев инженеры выбирают один из четырех проверенных вариантов, которые зашиты в библиотеки по умолчанию (например, в scikit-learn).

1. Линейное ядро (Linear Kernel)

Это тривиальное ядро вида

$K(x_i, x_j) = \langle x_i, x_j \rangle$

Грубо говоря то, что у нас было ещё до обсуждения ядер

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

2. Полиномиальное ядро (Polynomial Kernel)

Это «режим бармена»: данное ядро смешивает признаки между собой, добавляя степени и перекрестные произведения:

$K(x_{i},x_{j})=(\gamma \cdot \langle x_{i},x_{j}\rangle +c)^{d}.$

Здесь у нас три гиперпараметра: $\gamma, c, d$ . Разберем их по очереди

1. Степень полинома — (degree)

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

2. Свободный член — (coef0)

Что делает: Контролирует баланс и влияние между членами высших и низших степеней при раскрытии скобок.
Если (такое ядро называют однородным), модель полностью теряет возможность проводить обычные прямые линии. Она будет строить только кривые той степени сложности, на которую настроен параметр . Добавление константы позволяет алгоритму мягко учитывать как сложные нелинейные комбинации, так и простые линейные зависимости одновременно.

К слову, это тот самый из предыдущей части (для slack variables). На самом деле он никуда не пропал, а просто поменял свое место: если честно расписать концепцию Soft-Margin SVM для двойственной задачи, то этот параметр возникнет в виде верхнего ограничения для множителей Лагранжа: $0 \le \alpha_i \le C$ .

3. Масштабирующий коэффициент — $\gamma$ (gamma)

Что делает: Регулирует, насколько агрессивно модель реагирует на скалярное произведение (сходство) объектов.
По сути, это масштабирующий множитель для пространства признаков. Если параметр $\gamma$ очень большой, то даже небольшое сходство точек превратится в огромные значения после возведения в степень , и граница начнет резко подстраиваться под отдельные точки. Это может привести к переобучению.

3. Сигмоидальное ядро (Sigmoid Kernel)

Пришло в SVM прямиком из мира глубокого обучения:

$K(x_{i},x_{j})=\tanh (\gamma \langle x_{i},x_{j}\rangle +c)$

Функция гиперболического тангенса ( $\tanh$ ) используется как классическая функция активации в нейросетях. Использование этого ядра превращает SVM в архитектуру, математически похожую двухслойному перцептрону. Подробнее это обсудим в будущем.

Параметры $\gamma$ и в выполняют точно такие же роли, как и в полиномиальном.

4. Радиально-базисная функция или Гауссово ядро (RBF Kernel)

Наверное, самый популярный выбор на практике. Формула выглядит так:

$K(x_{i},x_{j})=\exp (-\gamma \|x_{i}-x_{j}\|{}^{2}).$

Идея: Это чистый «измеритель сходства», основанный на евклидовом расстоянии между точками в обертке экспоненты. Посмотрим, как работает экспонента:

Если два объекта $x_{i}$ и $x_{j}$ находятся в одной точке, расстояние между ними равно нулю, а . Сходство максимальное.
Если объекты начинают отдаляться друг от друга, расстояние растёт, а экспонента с отрицательным знаком стремительно падает. На большом удалении $K(x_i, x_j) \to 0$ .

Гиперпараметр $\gamma$ регулирует «радиус влияния» каждой отдельной точки обучающей выборки. Маленькая $\gamma$ дает большой радиус, и модель строит плавные, красивые границы. Но если выкрутить $\gamma$ на максимум, радиус сожмется: сходство будет фиксироваться только на экстремально близких расстояниях, и вокруг каждой тренировочной точки образуются «изолированные островки безопасности» её класса. Это приводит к переобучению.

Особенность RBF-ядра заключается в том, что если разложить эту экспоненту в бесконечный ряд Тейлора:

$K(x_{i},x_{j})= 1 -\gamma \|x_{i}-x_{j}\|{}^{2} + \frac{\gamma^2 \|x_{i}-x_{j}\|{}^{4}}{2!} - \frac{\gamma^3 \|x_{i}-x_{j}\|{}^{6}}{3!}+ ...$

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

**Визуализация разделяющих границ SVM при использовании различных ядер (Kernels) на одном и том же наборе данных.**

Мультиклассовая классификация: когда классов больше двух

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

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

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

Стратегия One-vs-Rest (OvR) или One-vs-All

Самый популярный подход (в scikit-learn для SVM он включается по умолчанию).

Идея: Если у нас есть 3 класса (A, B, C), мы обучаем 3 независимые модели SVM:
1. Первая модель: A (класс +1) против всех остальных (класс -1).
2. Вторая модель: B (класс +1) против всех остальных (класс -1).
3. Третья модель: C (класс +1) против всех остальных (класс -1).
Как делается предсказание: Мы прогоняем новый объект через все 3 модели. Каждая модель выдает свое расстояние до разделяющей полосы (уверенность алгоритма). Победителем объявляется тот класс, чья модель выдала максимальный отступ.

Стратегия One-vs-One (OvO)

Более тяжелый, но иногда более точный подход.

Идея: Мы обучаем бинарный SVM для каждой отдельной пары классов. Для 3 классов нам понадобится 3 модели (A vs B, B vs C, Av s C). Если бы классов было 10, пришлось бы обучить целых 45 моделей.
Как делается предсказание: Каждая модель голосует за свой класс-победитель в паре. Новый объект получает ту метку, которая набрала больше всего «голосов» в этом тотализаторе.

Сравнение SVM vs LogReg на практике

Пора переходить от абстрактных Гильбертовых пространств к реальному коду. Вернемся к нашему датасету автомобилей, с которым мы работали ещё в третьей части. Возьмем то, что назвали final_df (где не осталось текстовых категориальных признаков). На этот раз мы попытаемся предсказать мультиклассовый таргет owner (количество бывших владельцев: один, два, три, четыре и больше).

На ринг выходят три бойца: классическая логистическая регрессия (которая решает мультикласс через Softmax из коробки), линейный SVM и ядерный SVM с RBF-ядром (оба используют обертку One-vs-Rest). Мы не будем подбирать гиперпараметры, танцевать с бубнами и заниматься оверфиттингом. Запустим всё на стандартных настройках (разве что, от греха переобучения подальше, возьмем gamma=0.5) , чтобы соревнование оказалось максимально честным. Посмотрим на код:

import matplotlib.pyplot as pltimport numpy as npimport pandas as pdfrom sklearn.linear_model import LogisticRegressionfrom sklearn.model_selection import train_test_splitfrom sklearn.preprocessing import StandardScalerfrom sklearn.svm import SVC# Выбираем фичи и мультиклассовый таргетX = final_df.drop('owner', axis=1) # признаки (все столбцы кроме 'owner')y = final_df['owner'] # целевая переменная (столбец 'owner')# 2. Делим данные и обязательно масштабируем X_train, X_test, y_train, y_test = train_test_split(    X, y, test_size=0.2, random_state=42)scaler = StandardScaler()X_train_scaled = scaler.fit_transform(X_train)X_test_scaled = scaler.transform(X_test)# 3. Инициализируем моделиmodels = {    "Логистическая регрессия": LogisticRegression(solver="lbfgs"),    "Линейный SVM (OvR)": SVC(kernel="linear", decision_function_shape="ovr"),    "Ядерный SVM (RBF, OvR)": SVC(kernel="rbf", gamma=0.5 decision_function_shape="ovr")}# 4. Обучаем и сравниваем точность (Accuracy)print("--- Результаты ---\n")for name, model in models.items():    model.fit(X_train_scaled, y_train)    y_pred = model.predict(X_test_scaled)    acc = accuracy_score(y_test, y_pred)    prec = precision_score(y_test, y_pred, average='macro', zero_division=0)    rec = recall_score(y_test, y_pred, average='macro', zero_division=0)        print(f"{name}:")    print(f"  Accuracy:  {acc:.4f}")    print(f"  Precision: {prec:.4f}")    print(f"  Recall:    {rec:.4f}\n")>>> Логистическая регрессия -> accuracy на тесте: 0.6786 >>> Линейный SVM (OvR) -> Точность на тесте: 0.6647

Результаты:

--- Результаты ---Логистическая регрессия:  Accuracy:  0.6786  Precision: 0.4705  Recall:    0.4501Линейный SVM (OvR):  Accuracy:  0.6647  Precision: 0.3293  Recall:    0.4370Ядерный SVM (RBF, OvR):  Accuracy:  0.6993  Precision: 0.3661  Recall:    0.2715

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

Что произошло с метриками?

Ядерный SVM (RBF) выдал самый высокий Accuracy (0.6993), но его Recall рухнул до 0.2715. Что это значит? Модель поймала жесткую ловушку дисбаланса классов. Чтобы максимизировать общую точность (Accuracy), RBF-ядро просто начало массово раздавать всем машинам самый популярный класс, полностью игнорируя редкие классы. То есть модель нашла «чит» для Accuracy, но стала бесполезной для поиска редких владельцев.
Логистическая регрессия оказалась настоящим сбалансированным героем. У неё не сильно хуже accuracy (0.6786), и при этом Precision (0.4705) и Recall (0.4501) значительно выше. За счет Log Loss она честно пыталась учесть каждый редкий объект, не скатываясь в банальное угадывание большинства.

Заключение

На этом наш разбор метода опорных векторов официально завершен. Мы изучали линейный SVM, вывели двойственную задачу, разобрались в условии Каруша-Куна-Таккера, рассмотрели теорему Мерсера и матрицу Грама и на практике посмотрели, как Kernel Trick ведет себя в условиях сурового мультикласса.

В следующей части мы перейдем из классических линейных моделей в мир абсолютно нелинейного «из коробки» семейства алгоритмов. Мы начнем разбираться с Деревьями решений (Decision Trees) и узнаем, как строить логические ветки без всяких Лагранжианов и почему они станут фундаментом для мощнейших ансамблей.

ссылка на оригинал статьи https://habr.com/ru/articles/1042260/