ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 114
Скачиваний: 1
Эта новая целевая функция называется
Лагранжианом
. Необходимым условием метода Лагранжа являет-
ся равенство нулю производных Лагранжиана по переменным
w
и
b
. Взяв производную целевой функции
по
w
, выражаем вектор
w
через множители Лагранжа:
w
=
X
i
λ
i
y
i
x
i
.
Из этого следует, что искомый вектор
w
должен быть линейной комбинацией учебных векторов, причем
только тех, для которых
λ
i
6
= 0
.
Если
λ
i
>
0
, то документ обучающей коллекции
x
i
называется
опорным вектором
(
support vector
).
Теперь уравнение разделяющей гиперплоскости выглядит так:
X
i
λ
i
y
i
x
i
·
x
−
b
= 0
,
где
x
i
— это документ, который мы хотим классифицировать.
В случае если бы не были введены штрафы, значение
b
можно было бы найти как среднее между
значениями скалярного произведения
w
на вектора первой категории и второй. Если же штрафы введены,
то необходимо найти полосу, при которой сумма штрафов минимальна.
Взяв производную целевой функции по
b
, получаем что
X
i
λ
i
y
i
= 0
.
Подставляя
w
, выраженное через
λ
i
, в Лагранжиан, получаем новую, «двойственную» задачу: реше-
нию соответствуют такие значения множителей, при которых достигается максимум
X
i
λ
i
−
1
2
X
i,j
λ
i
λ
j
y
i
y
j
(
x
i
·
x
j
)
при условиях
X
i
λ
i
y
i
= 0
,
0
6
λ
i
6
C,
где второе ограничение — это дополненное исходное ограничение на
λ
i
, так как штрафы
ξ
i
тоже выража-
ются через
λ
i
.
Полезно заметить, что матрица коэффициентов при
λ
i
λ
j
положительно определена, из чего следу-
ет, что полученная функция выпуклая, а значит любой локальный максимум (минимум) этой функции
является ее глобальным максимумом (минимумом).
В итоге, исходная задача квадратичной оптимизации была переформулирована в задачу для множи-
телей Лагранжа. Целевая функция зависит не от самих
x
i
, а от скалярных произведений между ними.
Само скалярное произведение есть некоторая метрика близости, которая, например, для векторов пока-
зывает количество совпадений признаков, и во многих практических случаях использование скалярных
произведений учебных векторов гораздо удобнее манипуляций самими учебными векторами.
Решение двойственной задачи: метод последовательных оптимизаций
Алгоритм решения двойственной задачи таков:
1. Начать с набора
λ
i
, удовлетворяющих ограничениям.
2. С помощью хитрых эвристик выбрать из набора пару улучшаемых коэффициентов
λ
i
λ
j
.
3. При фиксированных значениях остальных множителей из набора и имеющихся ограничениях
y
i
λ
i
+
y
j
λ
j
=
y
i
λ
old
i
+
y
j
λ
old
j
и
0
6
λ
i
, λ
j
6
C
выбрать оптимальную пару значений (
мини-оптимизация
).
4. Продолжать процесс, повторяя шаги 2 и 3, до наступления
стоп-условий
.
6
Таким образом, на каждом шаге мы изменяем два коэффициента так, чтобы оставались выполненными
ограничения, и при этом функция возросла. Множество таких пар
λ
i
λ
j
, удовлетворяющих ограничениям,
лежит на диагонали в прямоугольнике со сторонами равными
C
. Действительно, из ограничения следует,
что
y
i
λ
i
+
y
j
λ
j
=
const
, что в свою очередь задает уравнение прямой. Ее отрезок, лежащий в квадрате,
в котором
λ
i
и
λ
j
изменяются в пределах от
0
до
C
, и является множеством точек, удовлетворяющих
ограничениям. Среди этого множества нужно выбрать ту точку, при которой максимизируемая функция
принимает наибольшее значение. В нашем случае имеются всего две переменные, и нужно просто найти
максимум квадратичной функции.
Стоп-условие
— это некоторая эвристика. Нам известно, что на каждом шаге максимизируемая функ-
ция должна возрастать, тогда в качестве стоп-условия может быть выбрано следующее: за последние сто
шагов функция возросла менее чем на какое-нибудь число
ε
. Исследуемая функция выпуклая, и после
того, как она перестанет расти и достигнет максимума, можно быть уверенными, что этот максимум
глобальный.
4.
Расширение пространства признаков
Метод классификации разделяющей полосой имеет два недостатка:
•
в поиске разделяющей полосы существенное значение имеют только пограничные точки;
•
во многих случаях найти оптимальную разделяющую полосу невозможно.
Следовательно, необходимо как-то улучшить метод. Как мы помним, условия задачи оптимизации, сфор-
мулированной с помощью множителей Лагранжа, зависели только от скалярных произведений между
учебными документами. Поэтому для улучшения метода можно попытаться изменить скалярное произ-
ведение. Здесь на помощь приходит идея
расширенного пространства
.
Построение машины опорных векторов:
1. Выберем отображение
φ
(
x
)
векторов
x
в новое,
расширенное
пространство.
2. Автоматически получается новая функция скалярного произведения
K
(
x, y
) =
φ
(
x
)
·
φ
(
y
)
. На прак-
тике обычно выбирают не отображение
φ
(
x
)
, а сразу функцию
K
(
x, y
)
, которая могла бы быть
скалярным произведением при некотором отображении
φ
(
x
)
. Функция
K
(
x, y
)
называется
ядром
.
Эта функция есть главный параметр настройки машины опорных векторов.
3. Находим разделяющую гиперплоскость в новом пространстве: с помощью функции
K
(
x, y
)
мы со-
ставляем новую матрицу коэффициентов для задачи оптимизации, подставляя вместо
(
x
i
·
x
j
)
зна-
чение
K
(
x
i
, x
j
)
, и решаем новую задачу оптимизации.
4. Найдя
w
и
b
, получаем классифицирующую поверхность
w
·
φ
(
x
)
−
b
в новом, расширенном простран-
стве.
7
5.
Примеры
Пример 1
Рассмотрим наглядный пример перехода к расширенному пространству, изображенный на рисунке 3.
Как видно, эти оранжевые и зеленые точки не разделяются никакой полосой. Если же мы перенесем
Рис. 3.
Пример перехода к расширенному пространству
эти точки на сферу, то тогда они разделяются плоскостью, которая срезает часть сферы вместе с оран-
жевыми точками. Таким образом, выгнув пространство с помощью отображения
φ
, можно легко найти
разделяющую гиперплоскость.
Пример 2
φ
(
x
) =
φ
((
x
1
, x
2
))
→
(
x
2
1
, x
2
2
,
√
2
x
1
x
2
)
K
(
x, y
) =
x
2
1
y
2
1
+
x
2
2
y
2
2
+ 2
x
1
x
2
y
1
y
2
= (
x
·
y
)
2
Мы видим, что не обязательно считать
φ
(
x
)
и
φ
(
y
)
, чтобы сосчитать скалярное произведение. Можно
сразу сказать, что новое скалярное произведение есть старое скалярное произведение в квадрате. Это
очень полезно, так как в данном примере пространство увеличилось всего на одну координату, а в прак-
тических ядрах оно может увеличиться во много раз, и в таких случаях считать скалярное произведение
через функцию
φ
может быть очень невыгодно.
Пример 3
φ
(
x
) = (1
, c
10
...
0
x
1
, . . . , c
110
...
0
x
1
x
2
, . . . , c
0
...
0
d
x
d
k
)
В данном случае отображение делает следующее: оно берет вектор
x
, и делает столько координат,
сколько бывает мономов степени не больше
d
, добавляя некоторые коэффициенты. Моном степени
d
есть произведение некоторых координат вектора в таких степенях, что их сумма не превышает
d
. Мы
придумали это отображение, уже имея в виду, что хотим получить скалярное произведение вида:
K
(
x, y
) = (1 +
x
·
y
)
d
Раскроем скалярное произведение
x
·
y
=
x
1
y
1
+
. . .
+
x
n
y
n
и подставим в скобку
(1 +
x
·
y
)
. Возведем ее в
степень
d
и получим большую сумму, из которой можно заметить, что коэффициент при соответствующем
мономе-координате равен корню из числа слагаемых в этой сумме, в которых присутствует этот моном.
Общая формула для коэффициента координаты-монома вида
x
α
1
1
. . . x
α
k
k
такова:
C
α
1
...α
k
=
s
d
!
α
1
!
. . . α
k
!(
d
−
α
1
−
. . .
−
α
k
)!
.
8
Итак, с помощью введенного отображения мы смогли найти разделяющую гиперплоскость
w
·
φ
(
x
)
−
b
.
На самом деле это многочлен от координат исходного вектора
x
, причем
w
i
— это коэффициент этого
многочлена. В расширенном пространстве мы ищем
w
i
, для которых гиперплоскость
w
·
φ
(
x
)
−
b
будет
разделением, однако в исходном пространстве мы ищем полином, который опишет кривую разделения
первого и второго классов. Поэтому, выбрав соответствующее ядро, мы выбираем класс разделяющих
поверхностей. Ядру
K
(
x, y
) = (1 +
x
·
y
)
d
соответствуют все полиномы, то есть мы ищем
оптимальную
полиномиальную разделяющую поверхность
.
Итоги
Преимущества SVM:
•
на тестах превосходит другие методы;
•
при различных выборах ядер можно эмулировать другие подходы. Например, большой класс ней-
ронных сетей можно представить в виде SVM с определенными ядрами;
•
теоретическое обоснование: итоговое правило мы выбираем не с помощью некоторых эвристик, а
согласно оптимизации некоторой функции.
Недостатки:
•
мало параметров для настройки: после того как мы зафиксировали ядро, единственным варьируе-
мым параметром остается коэффициент ошибки
C
;
•
не очень понятно, как выбирать ядро;
•
медленное обучение.
Метод опорных векторов сводит обучение классификатора к задаче квадратичной оптимизации.
Задача квадратичной оптимизации решается эвристическими алгоритмами путем последовательного
уменьшения целевой функции.
Для построения нелинейных классификаторов используется отображение исходных объектов в расши-
ренное пространство признаков.
Источники
[1] Wikipedia, Support Vector machine
http://en.wikipedia.org/wiki/Support_vector_machine
[2] CJC Burges. A Tutorial on Support Vector Machines for Pattern Recognition
http://www.music.mcgill.ca/˜rfergu/adamTex/references/Burges98.pdf
[3] Константин Воронцов. Лекция по методу опорных векторов
http://www.ccas.ru/voron/download/SVM.pdf
[4] John Platt. Sequential Minimal Optimization
http://research.microsoft.com/users/jplatt/smo.html
[5] Страница курса
http://logic.pdmi.ras.ru/˜yura/internet.html
9