ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 113
Скачиваний: 1
Метод опорных векторов
Лекция № 7 курса
«Алгоритмы для Интернета»
Юрий Лифшиц
∗
9 ноября 2006 г.
Содержание
1. Постановка задачи классификации
1
2. Оптимальная разделяющая гиперплоскость
2
2.1. Разделение прямой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.2. Разделение полосой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.3. Случай линейной разделимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.4. Случай отсутствия линейной разделимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3. Обучение машины опорных векторов
4
4. Расширение пространства признаков
7
5. Примеры
8
Итоги
9
Источники
9
1.
Постановка задачи классификации
В этой лекции мы будем рассматривать только бинарную классификацию, то есть имеется только два
класса — принадлежит категории и не принадлежит категории (оранжевые точки/зеленые точки). Каж-
дый
объект
классификации является вектором (точкой) в
n
-мерном пространстве. Каждая координата
вектора — это некий признак, и она тем больше, чем больше этот признак выражен у данного объекта.
Чем меньше эта координата, тем меньше этот признак соответствует объекту.
Учебная коллекция
— это множество векторов
[
x
1
..x
n
]
∈
R
n
и чисел
[
y
1
..y
n
]
∈ {−
1
,
1
}
. Число
y
i
равно
1
в случае принадлежности соответствующего вектора
x
i
категории и
−
1
в противном случае, то есть уже
известно, какого цвета точки
[
x
1
..x
n
]
.
Метод опорных векторов
(SVM) — это алгоритм, обучающийся различать объекты двух классов.
Постановка задачи
: мы имеем коллекцию оранжевых и зеленых точек. Необходимо найти такое пра-
вило, по которому новую, неокрашенную точку мы могли бы покрасить в один из этих двух цветов.
∗
Законспектировал Каширин Виктор.
1
2.
Оптимальная разделяющая гиперплоскость
2.1.
Разделение прямой
Линейный классификатор — это первый способ решения поставленной задачи. Идея заключается в
следующем: найти прямую, которая отделяет все оранжевые точки от зеленых точек. Если удастся найти
такую прямую, то классифицировать каждую новую точку можно будет следующим образом: если точка
лежит выше прямой, то она оранжевая, если ниже — зеленая. Формализуем эту классификацию: необхо-
димо найти вектор
w
такой, что для некоторого граничного значения
b
и новой точки
x
i
выполняется:
w
·
x
i
> b
⇒
y
i
= 1;
w
·
x
i
< b
⇒
y
i
=
−
1
.
Уравнение
w
·
x
i
=
b
описывает гиперплоскость, разделяющую классы в пространстве
R
n
.
Если скалярное произведение вектора
w
на
x
i
больше допускающего значения
b
, то новая точка при-
надлежит первой категории, если меньше — второй. На самом деле вектор
w
перпендикулярен искомой
разделяющей прямой, а значение
b
зависит от кратчайшего расстояния между разделяющей прямой и
началом координат.
L
1
b
L
2
L
3
Рис. 1.
Пример классифицирующих разделяющих прямых
Рассмотрим пример на рисунке 1. Для прямой
L
2
граница
b
равна
0
, а для прямой
L
1
— длине пер-
пендикуляра, опущенного на
L
1
из начала координат.
2.2.
Разделение полосой
Поскольку мы свободны в выборе разделяющей гиперплоскости, то нужно этим воспользоваться для
улучшения классификации. Постараемся расположить разделяющую прямую так, чтобы она максимально
далеко отстояла от ближайших к ней точек обоих классов, то есть найдем такие вектор
w
и число
b
, что
для некоторого
ε >
0
выполняется:
w
·
x
i
>
b
+
ε
⇒
y
i
= 1;
w
·
x
i
6
b
−
ε
⇒
y
i
=
−
1
.
Алгоритм классификации не изменится, если
w
и
b
одновременно умножить на одну и ту же константу.
Можно воспользоваться этим и выбрать константу таким образом, чтобы для всех пограничных (то есть
ближайших к разделяющей гиперплоскости) точек выполнялись условия
w
·
x
i
−
b
=
y
i
.
Это возможно сделать, так как при оптимальном положении разделяющей гиперплоскости все погра-
ничные объекты находятся от нее на одинаковом расстоянии, а остальные объекты находятся дальше.
2
Домножим тогда неравенства на
1
ε
и выберем
ε
равным единице. Таким образом, для всех векторов
x
i
из
учебной коллекции:
w
·
x
i
−
b
>
1
,
если
y
i
= 1;
w
·
x
i
−
b
6
−
1
,
если
y
i
=
−
1
.
Условие
−
1
< w
·
x
i
−
b <
1
задает полосу, разделяющую классы. Ни одна из точек обучающей выборки
не может лежать внутри этой полосы. Границами полосы являются две параллельные гиперплоскости с
направляющим вектором
w
. Точки, ближайшие к разделяющей гиперплоскости, лежат точно на границах
полосы. Пример разделяющей полосы изображен на рисунке 2.
w·x
i
–
b = 1
w·x
i
–
b = 0
w·x
i
–
b =
–
1
Рис. 2.
Разделяющая полоса
Ширина полосы равна
2
k
w
k
[3]. Чем шире полоса, тем увереннее можно классифицировать документы,
соответственно, самая широкая полоса является лучшей.
2.3.
Случай линейной разделимости
Сформулируем условия задачи поиска оптимальной разделяющей полосы.
Имеются ограничения:
y
i
(
w
·
x
i
−
b
)
>
1
. Вообще здесь нужно писать два неравенства, но так как
y
i
∈ {−
1
,
1
}
, то подставляя
y
i
в формулу, автоматически получаем необходимое неравенство. При этих
ограничениях
y
i
и
x
i
константы, так как это элементы учебной коллекции,
w
и
b
являются переменными.
Мы хотим найти такие
w
и
b
, чтобы выполнялись все линейные ограничения, и при этом как можно
меньше была норма вектора
w
(следовательно, шире разделяющая полоса), то есть необходимо миними-
зировать:
k
w
k
2
=
w
·
w.
Такая задача называется задачей
квадратичной оптимизации
— при линейных ограничениях найти
минимум квадратичной функции.
2.4.
Случай отсутствия линейной разделимости
У рассматриваемого метода есть два существенных недостатка:
•
метод не работает, в случае если классы линейно не разделимы;
•
предположим, что в учебной коллекции есть ошибка — неправильно классифицирован один или
несколько элементов. Из-за этих элементов результирующая разделяющая полоса может сильно
отличаться от той, которая получилась бы в случае с корректной учебной коллекцией.
3
Позволим алгоритму допускать ошибки на обучающих документах. Введем набор дополнительных
переменных
ξ
i
>
0
, характеризующих величину ошибки на объектах
x
i
∈
[
x
1
..x
n
]
. Это позволяет смягчить
ограничения-неравенства:
y
i
(
w
·
x
i
−
b
)
>
1
−
ξ
i
.
Предполагается, что если
ξ
i
= 0
, то на документе
x
i
ошибки нет. Если
ξ
i
>
1
, то на документе
x
i
допускается ошибка. Если
0
< ξ
i
<
1
, то объект попадает внутрь разделительной полосы, но относится
алгоритмом к своему классу.
Переформулируем задачу поиска оптимальной разделяющей: при данных ограничениях минимизиро-
вать сумму
k
w
k
2
+
C
X
ξ
i
.
Коэффициент
C
— это параметр настройки метода, который позволяет регулировать отношение меж-
ду максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки. Этот параметр
выбирается вручную для каждой ситуации отдельно.
Заметим, что эта задача осталась задачей
квадратичного программирования
.
Итак, это первый полученный результат, который говорит о том, какой линейный классификатор необ-
ходимо выбирать. Мы пришли к выводу, что чем шире полоса и чем меньше штрафов, тем классификатор
лучше. Таким образом, задача обучения классификатора свелась к задаче оптимизации, поиску линей-
ного классификатора, который лучше всего подходит к тем учебным данным, которые у нас имеются.
Естественно, возникает вопрос, как решать поставленную задачу оптимизации. Мы разберемся в этом в
следующей части.
3.
Обучение машины опорных векторов
Как известно, чтобы найти минимум функции, необходимо исследовать ее производную. Однако в
нашем случае помимо функции нам заданы линейные ограничения, которые необходимо учитывать при
минимизации. Множество точек, удовлетворяющих ограничениям, в
n
-мерном пространстве представ-
ляет собой многогранник: пространство делится несколькими гиперплоскостями или полуплоскостями в
зависимости от того, стоят в линейных ограничениях соответственно знаки равенства или неравенства.
Пересечение нескольких полупространств и дает многогранник, который может также в некотором месте
продолжаться в бесконечность. В этом ограниченном пространстве и необходимо найти минимум.
Решить эту задачу можно с помощью метода Лагранжа. Лагранж попытался свести задачу поиска
условного минимума (с ограничениями) к задаче поиска безусловного минимума (без ограничений), чтобы
затем воспользоваться стандартным методом поиска минимума функции. Для этого необходимо изменить
целевую функцию, то есть ту функцию, которую необходимо минимизировать.
Метод Лагранжа при нескольких условиях-равенствах
Если условия представляют собой равенства, то множество, на котором ищется минимум, есть пере-
сечение нескольких гиперплоскостей, и является неким подпространством. Введем дополнительные пере-
менные
λ
i
, называемые множителями Лагранжа, и вместо исходной целевой функции
F
будем рассмат-
ривать такую:
F
−
X
i
λ
i
G
i
,
где
G
i
— уравнения ограничений. Лагранж доказал, что в той точке, в которой у функции
F
достигается
условный минимум, при фиксированном наборе
λ
i
у новой функции также достигается минимум, но
при этом уже по всем переменным
x
, без ограничений. Зная это, можно воспользоваться следующим
алгоритмом поиска минимума:
1. Берем все производные новой целевой функции по переменным
x
и приравниваем их к нулю.
2. С помощью получившихся уравнений выражаем переменные
x
через
λ
1
. . . λ
n
.
4
3. Так как целевая функция имеет минимум, и при этом выполнены линейные ограничения, то пе-
ременные
x
, выраженные через
λ
i
, подставляем в
n
уравнений для
G
1
. . . G
n
. Подставив, получаем
систему из
n
уравнений для
n
неизвестных. Решив систему, найдем значения
λ
i
, следовательно,
найдем значения переменных
x
при которых достигается условный минимум.
Приведем пример. Будем минимизировать
F
(
x
) =
x
1
+
x
2
при условии
G
(
x
)
:
x
2
1
+
x
2
2
= 1
. Составим
новую целевую функцию:
x
1
+
x
2
−
λ
(
x
2
1
+
x
2
2
−
1)
. Нам известно, что при некотором
λ
в той точке, в
которой минимизируется
F
(
x
)
, минимизируется и получившаяся целевая функция. Рассмотрим частные
производные по
x
1
и
x
2
, равные соответственно
1
−
2
λx
1
и
1
−
2
λx
2
. Приравняем их к нулю, и, выразив
x
1
и
x
2
через
λ
, получим, что
x
1
=
x
2
=
1
2
λ
. Подставим получившиеся значения
x
1
и
x
2
в уравнение огра-
ничения:
1
4
λ
2
+
1
4
λ
2
= 1
, и получим
λ
=
±
√
2
. Теперь необходимо исследовать оба случая и рассмотреть,
чему будет равна функция. Оказывается, что в одной точке функция достигает максимума, в другой —
минимума. Задача решена.
Метод Лагранжа при нескольких условиях-неравенствах
Будем рассматривать целевую функцию
F
−
X
i
λ
i
G
i
при условии, что все неравенства
G
i
>
0
, и все
λ
i
>
0
.
Теорема Лагранжа, в случае если ограничения являются неравенствами, звучит следующим образом.
Если в точке
x
достигается условный минимум исходной целевой функции, то при условии, что выпол-
няется равенство нулю производных по
x
новой целевой функции, существует такой набор
λ
i
, что в этой
же точке
x
достигается минимум новой целевой функции, но уже глобально по всем
x
. При этом для
каждого
λ
i
верно следующее: либо
λ
i
равно нулю, и соответствующее ограничение не активно, либо
λ
i
не
равно нулю, и соответствующее ограничение выполняется, но является при этом уже равенством.
Теперь алгоритм поиска минимума следующий:
1. Взять все производные новой целевой функции по переменным
x
и приравнять их к нулю.
2. С помощью получившихся уравнений выразить
x
через
λ
1
. . . λ
n
. Для каждого
λ
i
верно следующее:
–
или
λ
i
равно нулю, и соответствующее ограничение
G
i
оказывается неактивным, оно не участ-
вует в целевой функции;
–
или, если
λ
i
не равно нулю, то соответствующее активное ограничение
G
i
является равенством.
3. Подставить
x
в активные ограничения. Для
n
переменных решить
n
«или-уравнений».
Вернемся к исходной задаче: при ограничениях-неравенствах
y
i
(
w
·
x
i
−
b
)
>
1
−
ξ
i
, ξ
i
>
0
минимизировать квадратичную функцию
1
2
k
w
k
2
+
C
X
i
ξ
i
.
Формулируя эту задачу в терминах метода Лагранжа, получаем, что необходимо найти минимум по
w
,
b
,
ξ
i
и максимум по
λ
i
функции
1
2
w
·
w
+
C
X
i
ξ
i
−
X
i
λ
i
(
ξ
i
+
y
i
(
w
·
x
i
−
b
)
−
1)
при условиях
ξ
i
>
0
, λ
i
>
0
.
5