Разбираемся в ML без воды: от базы до Attention. Часть 7: SVM и SGD

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

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

Если логистическая регрессия отвечала на вопрос “с какой вероятностью объект принадлежит классу?”, то философия SVM звучит иначе “где провести наиболее устойчивую границу между классами?”.

Support vector machine

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

Разберем основную идею․

Сначала для простоты рассмотрим линейно разделимые множества (как на картинке). Естественно, в таких задачах у нас есть возможность разделить классы разными линиями. И нам хотелось бы найти “лучшую” из них. Если посмотрим на картинку, желтая прямая, например, пришла и говорит “Дон Классификационе, мне нужно разделение”. Но он делает это без уважения.

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

Потому, даже на интуитивном уровне, кажется выгодным провести такую прямую, которая равноудалена от двух классов.

Теперь реализуем идею математически.

Гиперплоскость зададим уравнением

Как и раньше введем фиктивный , и переименуем в .

Теперь наши векторы выглядят так:.

Тогда, уравнение гиперплоскости будет иметь следующий вид:

Чтобы дело шло легче, в SVM классы будем кодировать не как (как в логистической регрессии) а как . Это даст нам возможность использовать функцию сигнум ().

Теперь предсказание модели выглядит максимально просто:

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

Точки, которые попали ровно на эти линии, называются опорными векторами (Support Vectors). Именно на них держится вся конструкция. Если убрать из выборки любые другие точки, лежащие глубже в своих классах, наша разделяющая прямая никак не изменится.

Расстояние между этими двумя линиями называется зазором (margin). Посчитаем чему он равен.

Сначала заметим, что раз , то вектор перпендикулярен разделяющей гиперплоскости.

Теперь возьмём точку на верхней границе и точку на нижней. Они удовлетворяют уравнениям: и .

Ширина зазора — это длина проекции вектора на нормированный вектор :

Наша цель — сделать этот зазор максимальным. А максимизировать эквивалентно

минимизации ( введена для удобства взятия производной)

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

В итоге получаем полноценную задачу оптимизации для так называемого Hard-Margin SVM:

Soft-margin SVM

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

Отсюда возникает идея более мягкого Soft-Margin SVM.

Суть в том, что мы мягче относимся к границе, вместо жесткой “Берлинской стены” даём возможность кругам и треугольникам пойти чуточку туда-сюда. Делается это вводом так называемых slack variables (дополнительные/вспомогательные переменные) в условие оптимизации:

Но мы помним, что методы машинного обучения хитрые и ленивые и если оставить всё как есть, они найдут обходные пути. К примеру, модель скажет: “шеф, беру , и твоё условие выполняется”․ Потому, во избежание раздутых придется ввести штраф.

Поймем, что здесь происходит: первая часть остается неизменной — мы всё ещё минимизируем норму весов, чтобы максимизировать зазор. Во второй части уравнения гиперпараметр C, который называется параметром штрафа (penalty parameter) иногда еще называют параметром регуляризации, но я критически против такого, представляет из себя обратное от параметра регуляризации для линейных моделей. Идея в том, что размер этого коэффициента прямо пропорционален страху модели ошибиться. Если в случае линейных моделей большая уменьшает веса, то в SVM большое значение заставляет модель уменьшать , из-за чего увеличиваются веса.
Как следствие, большие значения могут привести к переобучению, а маленькие – к недообучению. На практике, например в библиотеке Scikit-Learn дефолтным значением является C = 1.0.
После коэффициента C идёт стандартный трюк, к которому мы уже привыкли — деление на размер данных.
Ну и напоследок сумма всех slack variables. Мы можем себе позволить это за счет того, что они неотрицательны.

Следующая логическая идея — это перейти из условной задачи оптимизации в “безусловную”. Для этого перепишем наши ограничения относительно :

Также, не забудем условие .

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

Функция называется Hinge Loss (шарнирная функция потерь). Работает она таким образом

• Если , то объект классифицирован верно и лежит за пределами разделяющей полосы. Соответственно, штрафа нет;

• Если , то объект классифицирован верно, но попал внутрь разделяющей полосы. Здесь раскрывается особенность SVM: он штрафует за верный ответ, если тот оказался неуверенным (слишком близким к границе);

• Если же , то модель ошиблась классом. Штраф, санкции, бьем по рукам.

Подставим данное выражение в задачу минимизации и получим окончательный вид задачи SVM.

Или же։

Решение SVM

Итак, постановка задачи есть. Можно перейти к решению.

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

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

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

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

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

Геометрически это означает, что если объект лежит правильно и далеко от границы, то loss за него равен нулю, а алгоритм занимается исключительно сжатием весов, то есть расширением margin.

Обновление весов выглядит следующим образом:

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

Значит, обновление весов происходит так:

Геометрически смысл в том, что модель не просто расширяет разделяющую полосу (margin), но и буквально берет ошибочный объект “за шиворот”, притягивая его обратно в сторону правильного класса.

Стохастический градиентный спуск

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

Версия градиентного спуска, которая применяется не сразу ко всему датасету, а к одному объекту или к небольшой группе объектов (batch), и называется стохастическим градиентным спуском (SGD).

В классическом градиентном спуске нам пришлось бы на каждой итерации считать лосс и градиенты по абсолютно всему датасету. Если у вас миллион строк данных, один шаг обучения занял бы вечность. SGD решает эту проблему радикально: мы берем несколько объектов, говорим модели: “вот возьми такой набор, считай что остальные объекты в датасете плюс-минус такие же”. Да, траектория движения к минимуму зачастую становится менее стабильной, но в среднем алгоритм движется в правильном направлении, приходя к оптимуму в разы быстрее.

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

И оказывается, что SVM и SGD буквально созданы друг для друга․ C SVM стохастический спуск раскрывает свое главное преимущество — вычислительную лень.

Вспомним, как ведет себя Hinge Loss:

• Если объект находится в безопасной зоне , то лосс равен нулю.

• Раз лосс равен нулю, то и градиент ошибки зануляется.

Для алгоритма это означает режим энергосбережения. На очередной итерации SGD выбирает случайный объект. Если этот объект “хороший” и лежит глубоко в своем классе, модель вообще не тратит силы на обработку ошибки — она лишь слегка уменьшает норму весов.

Боевой режим активируется только тогда, когда SGD натыкается на объект, который заступил внутрь разделяющей полосы или улетел на чужую территорию. Именно эта вычислительная избирательность позволяет обучать линейный SVM на гигантских датасетах практически мгновенно.

А что если данные нелинейные? Kernel trick

Все, что мы описывали до этого момента, относится к линейному SVM. Наш алгоритм идеально ищет линию (гиперплоскость). Но в реальной жизни данные часто нелинейны.

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

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

Однако у такого подхода есть огромный минус: пересчитывать координаты миллионов точек в новые, многомерные пространства — это вычислительный кошмар. И здесь на сцену выходит Kernel trick (ядерный трюк).

Математика SVM хороша тем, что в формулах оптимизации объекты всегда встречаются только в виде скалярного произведения. Ядерная функция — это хитрая математическая формула (например, популярное RBF-ядро), которая позволяет посчитать скалярное произведение объектов в новом, высокоразмерном пространстве, вообще не выполняя сам переход в это пространство.

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

Заключение

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

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