[МУЗЫКА]

Всем привет!

Сейчас мы рассмотрим такой популярный метод, как метод опорных векторов.

Данный алгоритм был предложен Вапником в 90-х годах

как модификация алгоритма обобщенного портрета.

[НЕРАЗБОРЧИВО] был разработан Червоненкисом и Вапником.

Основная идея обобщенного портрета заключается в том,

как правильно отделить точки, расположенные на единичной

сфере при помощи решающего правила, линейного решающего правила.

Теперь давайте постараемся дать определение

методу опорных векторов и более детально рассмотреть данный алгоритм.

Идея метода опорных векторов основана на построение

оптимальной разделющей гиперплоскости.

Конкретно можно посмотреть на следующих примерах, как этот алгоритм работает.

Допустим, наша выборка состоит из двух линейно разделимых классов.

Пример приведен на рисунке A.

Далее мы строим максимальную полосу между классами и

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

В этом случае мы получаем конкретно максимальное расстояние от крайних

объектов класса до разделяющей гиперплоскости.

Именно объекты, которые объединены кружочками на данном рисунке,

они и показывают, что мы построили оптимальную полосу.

В случае если мы не получаем крайних объектов, которые размещены

на границе полосы, значит наша полоса неоптимальная и мы можем ее перестроить,

пока не упремся в крайние объекты.

По факту наш алгоритм называется опорным,

потому что на таких объектах он и обучается.

Давайте теперь формализуем пример, рассмотренный выше.

Поскольку наша выборка, рассматриваемая в конкретном примере,

является линейно разделимой, то мы можем ввести такое определение,

как вектор нормали w и константу w0,

такая что все отступы от данной константы будут положительными.

Но для начала оптимизации и более детального определения данного алгоритма,

нам надо нормализовать отступ и сказать, что его минимальное значение = 1.

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

В случае если разделяющая полоса является оптимальной,

то мы получаем хотя бы один объект положительного класса,

лежащий прямо на границе данной полосы, и один объект отрицательного класса,

лежащий с другой стороны на границе данной полосы.

В противном случае, если у нас нет таких граничных опорных объектов,

полоса построена неоптимально и мы должны заново перестроить

данную полосу и найти новое положение гиперплоскости.

Основываясь на уравнении опорных объектов, получаем сокращение констант в числителе.

Из этого можно видеть, что для максимизации ширины разделяющей

полосы необходимо минимизировать нормы вектора нормали.

Можно заметить, что при посроении оптимальной гиперплоскости

в задаче разделимой, линейно разделимой выборки нам

необходимо минимизировать норму вектора нормали при условии, что отступ у нас ≥ 1.

В результате мы получаем задачу минимизации с ограничениями.

Однако в условиях линейно неразделимой выборки наша система

неравенств считается неразрешимой.

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

Давайте теперь обобщим нашу задачу,

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

Для этого мы можем ввести возможность объекта ошибаться

и заходить за разделяющую полосу.

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

При этом с учетом ξi система наших неравенств уже становится совместной,

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

А поскольку мы хотим минимизировать сумму ошибок на объектах

мы можем внести параметр ξi в функционал,

который минимизирует норму вектора w с конкретными гиперпараметром c.

Необходимо заметить, что данный гиперпараметр влияет на

количество объект, которые могут зайти за полосу.

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

ограничениями неравенства.

Линейный SVM. Часть 1

Введение в науку о данных (An Introduction to Data Science)

Meet the Instructors