Это вторая часть моей серии заметок по CS M146.

Оглавление

СВМ: мотивация

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

Алгоритм персептрона может привести к любой границе решения, но интуитивно граница решения справа выглядит лучше. В то время как персептрон дает нам одну границу решения, SVM – это контролируемый алгоритм машинного обучения, который дает нам границу решения. В частности, это даст нам лучший.

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

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

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

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

SVM: формулировка проблемы

Давайте формализуем то, что мы видели в предыдущем разделе. Мы хотим найти математическое выражение для маржи.

Пусть 𝑥 будет одной из точек данных, а 𝑃 будет точкой на границе решения 𝑤𝑥+𝑏﹦0. Тогда маржа следующая.

Поскольку 𝑃 находится на границе решения, 𝑤𝘱+𝑏﹦0. Следовательно,

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

Мы знаем, что позже возьмем производную от этой целевой функции, поэтому мы не хотим иметь дело с абсолютным значением, поскольку оно не дифференцируемо. Обратите внимание на правильно классифицированные примеры, когда 𝑤𝑥+𝑏 положительно, y положительно. Когда 𝑤𝑥+𝑏 отрицательно, y также отрицательно. Следовательно, мы можем переписать нашу цель следующим образом.

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

Визуально это то, что происходит при добавлении этого ограничения.

Теперь у нас есть следующая цель.

Это то же самое, что сказать

Обратите внимание, что по крайней мере одна из точек данных будет удовлетворять 𝑦(𝑤𝑥＋𝑏)﹦0, потому что мы будем уменьшать 𝑤 и 𝑏 до тех пор, пока одна из точек данных не достигнет ограничения. Причина, по которой мы хотим уменьшить их, состоит в том, чтобы максимизировать 1/abs(𝑤). В задачах оптимизации мы часто хотим минимизировать нашу цель по соглашению. Таким образом, мы можем записать нашу цель следующим образом.

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

До сих пор мы предполагали, что набор данных линейно разделим. Это называется жесткая маржа. Но на практике набор данных обычно не является линейно разделимым. Сейчас мы избавимся от этого предположения. Чтобы позволить некоторым точкам данных попасть внутрь поля, мы введем резервную переменную ξ.

Ограничение теперь позволяет 𝑦(𝑤𝑥＋𝑏) быть меньше 1. Это называется мягкая маржа. Но мы не хотим, чтобы ξ было слишком большим. Нам также необходимо ограничить ξ.

Гиперпараметр 𝐶 определяет, насколько мы должны наказывать нашу целевую функцию за большие резервные переменные.

SVM: потеря шарнира

Итак, какая функция затрат достигает целевой функции, которую мы вывели из предыдущего раздела? Оказывается, функция стоимости, которую мы минимизируем в SVM, выглядит следующим образом.

Почему это то же самое, что и целевая функция, которую мы нашли? Проверь это.

Действительно, функция затрат такая же, как и целевая функция! Вот визуальная интерпретация функции потерь, которую мы минимизируем.

SVM: трюк с ядром

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

Оптимизация

Рассмотрим следующую задачу оптимизации.

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

Тогда решение задачи оптимизации такое же, как решение задачи ниже.

Давайте подумаем, почему это правда. Представьте, что 𝑥 не удовлетворяет ограничениям равенства. Другими словами, h(x)≠0 для некоторого 𝑗. Мы можем настроить β𝑗 на бесконечность, и цель также станет бесконечной. Точно так же предположим, что 𝑥 не удовлетворяет ограничениям неравенства. Другими словами, f(x)＞0 для некоторого 𝑖. Мы можем настроить 𝛼ᵢ так, чтобы цель приближалась к бесконечности. Если 𝑥 не удовлетворяет ни одному из ограничений, то цель уходит в бесконечность. В противном случае 𝛼ᵢ - все нули, а h (x) - все нули. То есть исчезают второй и третий члены лагранжиана. Преимущество использования лагранжиана заключается в том, что нам больше не нужно беспокоиться об ограничениях.

Двойная формулировка

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

В общем случае p* и d* будут разными значениями. Однако p* и d* будут одинаковыми, если выполняется сильная двойственность. Чтобы соблюдалась сильная двойственность, L должен удовлетворять так называемым условиям ККТ. Честно говоря, я вообще не знаю, что это за вещи. Но важно то, что задача оптимизации SVM удовлетворяет этим условиям. Другими словами, d* совпадает с p*.

Ядро SVM

Теперь давайте применим те вещи из предыдущих разделов к SVM. Напомним, вот целевая функция.

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

Теперь вычисляем лагранжиан.

Цель оптимизации для primal:

Цель оптимизации для двойного режима:

Начнем с минимизации.

Берем производную по каждой переменной.

В оптимуме эти градиенты равны нулю.

Теперь мы можем заменить их обратно на L.

Вот проблема оптимизации, которая у нас есть прямо сейчас.

Мы можем объединить три ограничения в одно.

Вот наша новая задача оптимизации.

Теперь мы успешно выразили цель с внутренними произведениями точек данных.

SVM: опорные векторы

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

Кажется, что 𝑤 зависит только от точек данных с 𝛼＞0. Когда 𝛼＞0? Из условий KKT получается 𝛼＞0, когда точки данных находятся в пределах поля.

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