Классификаторы SVC¶
Классификаторы SVC основаны на одной из наиболее популярных методологий обучения по прецедентам, которая была предложена в 70-е годы прошлого века сотрудниками Института проблем управления АН СССР В. Н. Вапником и А. Я. Червоненкисом. Данный подход называется в настоящее время "Машина опорных векторов" (SVM -Support Vector Machine).
SVM — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов с адаптацией для нелинейных классификаторов и может также рассматриваться как частный случай регуляризации по Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора, поэтому метод также известен как метод классификатора с максимальным зазором.
Основная идея метода — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с наибольшим зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей классы. Разделяющей гиперплоскостью будет гиперплоскость, создающая наибольшее расстояние до двух параллельных гиперплоскостей. Алгоритм основан на допущении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора.
a. Математические основания SVM¶
Рассматривается задача обучения по прецедентам $(X, Y, y∗,X^l)$, где $X$ - пространство объектов, $Y$ - множество ответов, $y∗ : X → Y$ - целевая зависимость,значения которой известны только на объектах обучающей выборки $X^l = \left( {x_i ,y_i } \right)_{i = 1}^l ,y_i = y^* \left( {x_i } \right)$. Требуется построить алгоритм $a: X → Y$ , аппроксимирующий целевую зависимость на всём пространстве $X$.
Метод опорных векторов в задачах бинарной классификации
Рассмотрим задачу классификации на два непересекающихся класса, в которой объекты описываются $n$-мерными вещественными векторами: $X = R^n ,Y = \left\{ { - 1, + 1} \right\}$
Будем строить линейный пороговый классификатор:
$$a\left( x \right) = sign\left( {\sum\limits_{j = 1}^n {w_j x^j - w_0 } } \right) = sign\left( {\left\langle {w,x} \right\rangle - w_0 } \right),\;\;\;(1)$$
где $x = (x^1, . . . , x^n)$ - признаковое описание объекта $x$; вектор $w = \left( {w_1 ,....,w_n } \right) \in R^n$
и скалярный порог $w_0 \in R$ являются параметрами алгоритма.
Уравнение $\left\langle {w,x} \right\rangle = w_0$ описывает гиперплоскость, разделяющую классы в пространстве $R^n$.
Хотя правило классификации в точности совпадает с моделью нейрона по МакКаллоку-Питтсу, критерий и методы настройки параметров в $SVM$ радикально отличаются от персептронных (градиентных) методов обучения.
Понятие оптимальной разделяющей гиперплоскости
Предположим, что выборка линейно разделима, то есть существуют такие значения параметров $w, w_0$, при которых функционал числа ошибок:
$$Q\left( {w,w_0 } \right) = \sum\limits_{i = 1}^l {\left[ {y_i \left( {\left\langle {w,x_i } \right\rangle - w_0 } \right) < 0} \right]}$$
принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна, поскольку существуют и другие положения разделяющей гиперплоскости, реализующие то же самое разбиение выборки. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора. Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих классов. Первоначально данный принцип классификации возник из эвристических соображений: вполне естественно полагать, что максимизация зазора (margin) между классами должна способствовать более уверенной классификации. В дальнейшем этот принцип получил мощное теоретическое обоснование.
Нормировка. Заметим, что параметры линейного порогового классификатора определены с точностью до нормировки: алгоритм a(x) не изменится, если $w$ и $w_0$ одновременно умножить на одну и ту же положительную константу. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделяющей гиперплоскости) объектов $x_i$ из $X^l$ выполнялись условия: $\left\langle {w,x_i } \right\rangle - w_0 = y_i$
Сделать это возможно, поскольку при оптимальном положении разделяющей гиперплоскости все пограничные объекты находятся от неё на одинаковом расстоянии. Остальные объекты находятся дальше. Таким образом, для всех
$$\left\langle {w,x_i } \right\rangle - w_0 = \left\{ {\begin{array}{*{20}c}
{ \le - 1,{\rm if }y_i = - 1} \\
{ \ge 1,{\rm if }y_i = + 1} \\
\end{array}} \right.\;\;\;(2)$$$$ - 1 < \left\langle {w,x} \right\rangle - w_0 < 1$$
задаёт полосу, разделяющую классы. Ни одна из точек обучающей выборки не может лежать внутри этой полосы. Границами полосы служат две параллельные гиперплоскости с направляющим вектором w. Точки, ближайшие к разделяющей гиперплоскости, лежат в точности на границах полосы. При этом сама разделяющая гиперплоскость проходит ровно по середине полосы.
Ширина разделяющей полосы. Чтобы разделяющая гиперплоскость как можно дальше отстояла от точек выборки, ширина полосы должна быть максимальной. Пусть $x_-$ и $x_+$ - две произвольные точки классов −1 и +1 соответственно, лежащие
на границе полосы. Тогда ширина полосы есть:
$$\left\langle {\left( {x_ + - x_ - } \right),\frac{w}{{\left\| w \right\|}}} \right\rangle = \frac{{\left\langle {w,x_ + } \right\rangle - \left\langle {w,x_ - } \right\rangle }}{{\left\| w \right\|}} = \frac{{\left( {w_0 + 1} \right) - \left( {w_0 - 1} \right)}}{{\left\| w \right\|}} = \frac{2}{{\left\| w \right\|}}$$
Ширина полосы максимальна, когда норма вектора w минимальна. Итак, в случае, когда выборка линейно разделима, достаточно простые геометрические соображения приводят к следующей задаче: требуется найти такие значения параметров $w$ и $w_0$, при которых норма вектора $w$ минимальна при условии (2). Это задача квадратичного программирования. Она будет подробно рас-
смотрена ниже . Затем будет сделано обобщение на тот случай, когда линейной разделимости нет
Линейно разделимая выборка.
Построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при l ограничениях-неравенствах вида (2) относительно $n + 1$ переменных $w, w_0$:
$$\left\{ {\begin{array}{*{20}c}
{\left\langle {w,w } \right\rangle \to \min } \\
{y_i \left( {\left\langle {w,x_i } \right\rangle - w_0 } \right) \ge 1,i = 1,....,l} \\
\end{array}} \right.\;\;\;(3)$$
По теореме Куна-Таккера эта задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа
$$\left\{ {\begin{array}{*{20}c}
{\Lambda \left( {w,w_0 ;\lambda } \right) = \frac{1}{2}\left\langle {w,w } \right\rangle - \sum\limits_{i = 1}^l {\lambda _i \left( {y_i \left( {\left\langle {w,x{}_i} \right\rangle - w_0 } \right) - 1} \right) \to \min _{w,w_0 } \max _\lambda } } \\
{\lambda _i \ge 0,{\rm }i = 1,...............,l{\rm }} \\
{\lambda _i = 0,{\rm } \vee {\rm }\left\langle {w,x_i } \right\rangle - w_0 = y_i ,{\rm }i = 1,.....................,l;{\rm }} \\
\end{array}} \right.$$
где $\lambda = \left( {\lambda _1 ,.......,\lambda _l } \right)$ - вектор двойственных переменных. Последнее из трёх условий называется условием дополняющей нежёсткости. Необходимым условием седловой точки является равенство нулю производных Лагранжиана. Отсюда немедленно вытекают два полезных соотношения
$$\frac{{\partial \Lambda }}{{\partial w}} = w - \sum\limits_{i = 1}^l {\lambda _i y_i x_i } = 0 \Rightarrow w = \sum\limits_{i = 1}^l {\lambda _i y_i x_i }\;\;\;(4)$$$$\frac{{\partial \Lambda }}{{\partial w_0 }} = - \sum\limits_{i = 1}^l {\lambda _i y_i } = 0 \Rightarrow \sum\limits_{i = 1}^l {\lambda _i y_i } = 0\;\;\;(5)$$
Из (4) следует, что искомый вектор весов $w$ является линейной комбинацией векторов обучающей выборки, причём только тех, для которых $\lambda _i \ne 0$. Согласно условию дополняющей нежёсткости на этих векторах $x_i$ ограничения-неравенства обращаются в равенства: $\left\langle {w,x{}_i} \right\rangle - w_0 = y_i$,следовательно, эти векторы находятся на границе разделяющей полосы. Все остальные векторы отстоят дальше от границы,для них $\lambda_i = 0$, и они не участвуют в сумме (4). Алгоритм (1) не изменился бы,если бы этих векторов вообще не было в обучающей выборке.
Опр.1. Если $\lambda _i > 0$ и $\left\langle {w,x{}_i} \right\rangle - w_0 = y_i$ , то объект обучающей выборки $x_i$ называется опорным вектором (support vector). Подставляя (4) и (5) обратно в Лагранжиан, получим эквивалентную задачу квадратичного программирования, содержащую только двойственные переменные
$$\left\{ {\begin{array}{*{20}c}
{ - \Lambda \left( \lambda \right) = - \sum\limits_{i = 1}^l {\lambda _i + \frac{1}{2}\sum\limits_{i = 1}^l {\sum\limits_{j = 1}^l {\lambda _i \lambda _j y_i y_j \left( {\left\langle {x_i ,x_j } \right\rangle } \right) \to \mathop {\min }\limits_\lambda } } } } \\
{\lambda _i \ge 0,{\rm }i = 1,............,l;{\rm }} \\
{\sum\limits_{i = 1}^l {\lambda _i y_i = 0} } \\
\end{array}} \right.\;\;\;(6)$$
Здесь минимизируется квадратичный функционал, имеющий неотрицательно определённую квадратичную форму, следовательно, выпуклый. Область, определяемая ограничениями неравенствами и одним равенством, также выпуклая. Следовательно, данная задача имеет единственное решение. Допустим, мы решили эту задачу. Тогда вектор $w$ вычисляется по формуле (4). Для определения порога $w_0$ достаточно взять произвольный опорный вектор $x_i$ и выразить $w_0$ из равенства $w_0 = \left\langle {w,x_i } \right\rangle - y_i$ . На практике для повышения численной устойчивости рекомендуется брать в качестве w0 среднее по всем опорным векторам, а ещё лучше медиану:
$$w_0 = med\left\{ {\left\langle {w,x_i } \right\rangle - y_i :\lambda _i > 0,i = 1,....,l} \right\}\;\;\;(7)$$$$a\left( x \right) = sign\left( {\sum\limits_{i = 1}^l {\lambda _i y_i \left\langle {x_i ,x} \right\rangle - w_0 } } \right)\;\;\;(8)$$
Обратим внимание, что реально суммирование идёт не по всей выборке, а только по опорным векторам, для которых $\lambda _i \ne 0$. Именно это свойство разреженности (sparsity) отличает SVM от других линейных разделителей - дискриминанта Фише
ра, логистической регрессии и однослойного персептрона.
Резюмируя, отметим, что пока остаются открытыми два вопроса: как быть, если классы линейно не разделимы, и как решить двойственную задачу (6)? Начнём с первого вопроса. Ниже рассматривается обобщение двойственной задачи на случай отсутствия линейной разделимости. После этого будет рассмотрен переход от скалярных произведений к произвольным ядрам - так
называемый 'kernel trick', позволяющий строить нелинейные разделители.
Линейно неразделимая выборка.
Чтобы обобщить SVM на случай линейной неразделимости, позволим алгоритму допускать ошибки на обучающих объектах, но при этом постараемся, чтобы ошибок было поменьше. Введём набор дополнительных переменных $\xi _i \ge 0$, характеризующих величину ошибки на объектах $x_i, i = 1, . . . , l$. Возьмём за отправную точку задачу (3); смягчим в ней ограничения-неравенства, и одновременно введём в минимизируемый функционал штраф за суммарную ошибку:
$$\left\{ {\begin{array}{*{20}c}
{\frac{1}{2}\left\langle {w,w} \right\rangle + C\sum\limits_{i = 1}^l {\xi _i \to \mathop {\min ;}\limits_{w,w_0 ,\xi } } } \\
{y_i \left( {\left\langle {w,x_i } \right\rangle - w_0 } \right) \ge 1 - \xi _i ,{\rm }i = 1,....,l;} \\
{\xi _i \ge 0,{\rm }i = 1,........,l.} \\
\end{array}} \right.\;\;\;\;(9)$$
К этой же оптимизационной задаче приводит ещё одна цепочка рассуждений.Вспомним, что в случае $Y = {−1,+1}$ отступом (margin) объекта $x_i$ от границы классов называется величина
$$m_i = y_i \left( {\left\langle {w,x_i } \right\rangle - w_0 } \right)$$
Алгоритм допускает ошибку на объекте $x_i$ тогда и только тогда, когда отступ $m_i$ отрицателен. Если $m_i ∈ (−1,+1)$, то объект $x_i$ попадает внутрь разделяющей полосы. Если $m_i > 1$, то объект $x_i$ классифицируется правильно, и находится на некотором удалении от разделяющей полосы. Запишем функционал числа ошибок алгоритма a на выборке $X^l$ в терминах отступов:
$$Q\left( {a,X^l } \right) = \sum\limits_{i = 1}^l {\left[ {m_i < 0} \right]}$$
Заменим в этом функционале пороговую функцию потерь кусочно-линейной верхней оценкой: $\left[ {m_i < 0} \right] \le \left( {1 - m_i } \right)_ +$ .Смысл этой замены в том, чтобы сделать функцию потерь чувствительной к величине ошибки и заодно ввести штраф за приближение объекта к границе классов.Кроме того, добавим к функционалу $Q$ штрафное слагаемое $\tau \left\| w \right\|^2$. В соответствии с принципом регуляризации некорректно поставленных задач по А. Н. Тихонову такая добавка означает, что среди всех векторов $w$, минимизирующих функци онал $Q$, наиболее предпочтительны векторы с минимальной нормой. Регуляризация часто применяется для настройки линейных моделей классификации и регрессии.
При наличии шумовых и/или зависимых признаков она повышает устойчивость алгоритма по отношению к составу выборки и его обобщающую способность.
С учётом обеих модификаций функционал качества принимает вид:
$$Q\left( {a,X^l } \right) = \sum\limits_{i = 1}^l {\left( {1 - m_i } \right)_ + + } \tau \left\| w \right\|^2 \to \mathop {\min }\limits_{w,w_0 }\;\;\;(10)$$
Нетрудно показать, что задача минимизации данного функционала эквивалентна оптимизационной задаче с ограничениями (9), если взять параметр регуляризации $\tau = \frac{1}{{2C}}$ . Таким образом, принцип оптимальной разделяющей гиперплоскости (или максимизации ширины разделяющей полосы) совпадает с принципом регуляризации по Тихонову. Положительная константа $C$ (или $τ$ ) является управляющим параметром метода и позволяет находить компромисс между максимизацией разделяющей полосы
и минимизацией суммарной ошибки.
Вернёмся к задаче (9) и запишем её функцию Лагранжа:
$$\Lambda \left( {w,w_0 ,\xi ;\lambda ,\eta } \right) = \frac{1}{2}\left\langle {w,w} \right\rangle - \sum\limits_{i = 1}^l {\lambda _i } \left( {y_i \left( {\left\langle {w,x_i } \right\rangle - w_0 } \right) - 1} \right) - \sum\limits_{i = 1}^l {\xi _i \left( {\lambda _i + \eta _i - C} \right)}$$
где $\eta = \left( {\eta {}_1,.....,\eta _l } \right)$ - вектор переменных, двойственных к переменным $\xi = \left( {\xi _1 ,.....,\xi _l } \right)$. Как и в прошлый раз, условия Куна-Таккера сводят задачу к поиску седловой точки функции Лагранжа:
$$\left\{ {\begin{array}{*{20}c}
{\Lambda \left( {w,w_0 ,\xi ;\lambda ,\eta } \right) \to \min _{w,w_0 ,\xi } \max _{\lambda ,\eta } } \\
\begin{array}{l}
\xi _i \ge 0,{\rm }\lambda _i \ge 0,{\rm }\eta _i \ge {\rm 0}{\rm , }i = 1,....,l{\rm } \\
\lambda _i = 0,{\rm } \vee {\rm }y_i \left( {\left\langle {w,x_i } \right\rangle - w_0 } \right) = 1 - \xi _i ,{\rm }i = 1,....,l \\
\eta _i = 0{\rm } \vee {\rm }\xi _i {\rm = 0}{\rm , }i = 1,....,l \\
\end{array} \\
\end{array}} \right.$$
В последних двух строках записаны условия дополняющей нежёсткости. Необходимым условием седловой точки является равенство нулю производных Лагранжиана. Отсюда получаются три полезных соотношения:
$$\frac{{\partial \Lambda }}{{\partial w}} = w - \sum\limits_{i = 1}^l {\lambda _i } y_i x_i = 0{\rm } \Rightarrow {\rm }w = \sum\limits_{i = 1}^l {\lambda _i } y_i x_i\;\;\;(11)$$$$\frac{{\partial \Lambda }}{{\partial w_0 }} = - \sum\limits_{i = 1}^l {\lambda _i } y_i = 0{\rm } \Rightarrow {\rm }\sum\limits_{i = 1}^l {\lambda _i } y_i = 0\;\;\;(12)$$$$\frac{{\partial \Lambda }}{{\partial \xi _i }} = - \lambda _i - \eta _i + C = 0{\rm } \Rightarrow {\rm }\lambda _i + \eta _i = C,{\rm }i = 1,....,l\;\;\;(13)$$
Первые два соотношения в точности такие же, как и в линейно разделимом случае. Из третьего соотношения и неравенства $η_i > 0$ следует ограничение $\lambda _i \le C$. Отсюда, и из условий дополняющей нежёсткости вытекает, что возможны только три допустимых сочетания значений переменных $ξ_i, λ_i, η_i$ и отступов $m_i$.
Соответственно, все объекты $x_i, i = 1, . . . , l$ делятся на следующие три типа:
- $λ_i = 0; η_i = C; ξ_i = 0; m_i > 1$.
Объект $x_i$ классифицируется правильно и находится далеко от разделяющей
полосы. Такие объекты будем называть периферийными.
- $0 < λ_i < C; 0 < η_i < C; ξ_i = 0; m_i = 1$.
Объект $x_i$ классифицируется правильно и лежит в точности на границе разде-
ляющей полосы. Такие объекты, как и раньше, будем называть опорными.
- $λ_i = C; η_i = 0; ξ_i > 0; m_i < 1$.
Объект $x_i$ либо лежит внутри разделяющей полосы, но классифицируется пра
вильно ($0 < ξ_i < 1, 0 < m_i < 1$), либо попадает на границу классов ($ξ_i = 1, m_i = 0$),
либо вообще относится к чужому классу ($ξ_i > 1, m_i < 0$). Во всех этих случаях
объект $x_i$ будем называть нарушителем
В силу соотношения (13) в Лагранжиане обнуляются все члены, содержащие переменные $ξ_i$ и $η_i$, и он принимает тот же вид, что и в случае линейной разделимости. Параметры разделяющей поверхности $w$ и $w_0$, согласно формулам (11) и (12), также выражаются только через двойственные переменные $λ_i$. Таким образом, задача снова сводится к квадратичному программированию относительно двойственных переменных $λ_i$. Единственное отличие от линейно разделимого случая состоит в появлении ограничения сверху $\lambda _i \le C$:
$$\left\{ {\begin{array}{*{20}c}
{ - \Lambda \left( \lambda \right) = - \sum\limits_{i = 1}^l {\lambda _i + \frac{1}{2}\sum\limits_{i = 1}^l {\sum\limits_{j = 1}^l {\lambda _i \lambda _j y_i y_j \left\langle {x_i ,x_j } \right\rangle \to \mathop {\min }\limits_\lambda } } } } \\
{0 \le \lambda _i \le C,{\rm }i = 1,....,l} \\
{\sum\limits_{i = 1}^l {\lambda _i y{}_i = 0{\rm }} } \\
\end{array}} \right.\;\;\;(14)$$
На практике для построения SVM решают именно эту задачу, а не (6), так как гарантировать линейную разделимость выборки в общем случае не представляется возможным. Этот вариант алгоритма называют SVM с мягким зазором (soft-margin
SVM), тогда как в линейно разделимом случае говорят об SVM с жёстким зазором (hard-margin SVM).
Для алгоритма классификации сохраняется формула (8), с той лишь разницей, что теперь ненулевыми $λ_i$ обладают не только опорные объекты, но и объекты-нарушители. В определённом смысле это недостаток SVM, поскольку нарушителями часто оказываются шумовые выбросы, и построенное на них решающее правило,по сути дела, опирается на шум.
Константу $C$ обычно выбирают по критерию скользящего контроля. Это трудоёмкий способ, так как задачу приходится решать заново при каждом значении $C$.
Если есть основания полагать, что выборка почти линейно разделима, и лишь объекты-выбросы классифицируются неверно, то можно применить фильтрацию выбросов. Сначала задача решается при некотором $C$, и из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки $ξ_i$. После этого задача решается заново по усечённой выборке. Возможно, придётся проделать несколько таких итераций, пока оставшиеся объекты не окажутся линейно разделимыми.
Ядра и спрямляющие пространства.
Существует ещё один подход к решению проблемы линейной неразделимости. Это переход от исходного пространства признаковых описаний объектов $X$ к новому пространству $H$ с помощью некоторого преобразования $\varphi: X → H$. Если пространство $H$ имеет достаточно высокую размерность, то можно надеяться, что в нём выборка окажется линейно разделимой (легко показать, что если выборка $X^l$ не противоречива, то всегда найдётся пространство размерности не более $l$, в котором она будет линейно разделима). Пространство $H$ называют спрямляющим. Если предположить, что признаковыми описаниями объектов являются векторы $\varphi(x_i)$, а не векторы $x_i$, то построение SVM проводится точно так же, как и ранее.Единственное отличие состоит в том, что скалярное произведение $\left\langle {x,x'} \right\rangle$ в пространстве $X$ всюду заменяется скалярным произведением $\left\langle {\varphi (x),\varphi (x')} \right\rangle$ в пространстве $H$. Отсюда вытекает естественное требование: пространство $H$ должно быть наделено скалярным произведением, в частности, подойдёт любое евклидово, а в общем случае и гильбертово, пространство.
Опр.2. Функция $K: X × X → R$ называется ядром (kernel function), если она представима в виде $K\left( {x,x'} \right) = \left\langle {\varphi (x),\varphi (x')} \right\rangle$ при некотором отображении $\varphi: X → H$, где $H$ - пространство со скалярным произведением.
Постановка задачи (14), и сам алгоритм классификации (8) зависят только от скалярных произведений объектов, но не от самих признаковых описаний. Это означает, что скалярное произведение $\left\langle {x,x'} \right\rangle$ можно формально заменить ядром $K(x, x′)$. Поскольку ядро в общем случае нелинейно, такая замена приводит к существенному расширению множества реализуемых алгоритмов $a: X → Y$.
Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объек-
тов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x, x′)$, удовлетворяю-
щей аксиомам скалярного произведения, то задача может решаться методом SVM. Для такого подхода был придуман термин беспризнаковое распознавание (featureless recognition), хотя многие давно известные метрические алгоритмы клас-
сификации (kNN, RBF и др.) также не требуют задания признаковых описаний.
Любая ли функция двух аргументов $K(x, x′)$ может исполнять роль ядра? Следующая теорема даёт исчерпывающий ответ на этот вопрос и показывает, что класс допустимых ядер достаточно широк
Теорема 1 (Мерсер, 1909). Функция $K(x, x′)$ является ядром тогда и только тогда, когда она симметрична, $K(x, x′) = K(x′, x)$, и неотрицательно определена: $\int\limits_X {\int\limits_X {K\left( {x,x'} \right)} } g\left( x \right)g\left( {x'} \right)dxdx' \ge 0$ для любой функции $g:X \to R$
Существует эквивалентное определение неотрицательной определённости.
Опр.3. Функция $K(x, x′)$ неотрицательно определена, если для любой конечной выборки $X^p = (x_1, . . . , x_p)$ из $X$ матрица $K = \left\| {K\left( {x_i ,x_j } \right)} \right\|$ размера $p × p$ неотрицательно определена: $z^T Kz \ge 0$ для любого $z ∈ R^p$.
Проверка неотрицательной определённости функции в практических ситуациях может оказаться делом нетривиальным. Часто ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая, как правило, по критерию скользящего контроля. Очевидно, что это не оптимальное решение. На сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.
Следующие правила порождения позволяют строить ядра в практических задачах:
- Произвольное скалярное произведение $K\left( {x,x'} \right) = \left\langle {x,x'} \right\rangle$ является ядром.
- Константа $K(x, x′) = 1$ является ядром.
- Произведение ядер $K(x, x′) = K_1(x, x′)K_2(x, x′)$ является ядром.
- Для любой функции $\varphi : X → R$ произведение $K(x, x′) = \varphi(x)\varphi(x′)$ является ядром.
- Линейная комбинация ядер с неотрицательными коэффициентами $K(x, x′) = = α_1K_1(x, x′) + α_2K_2(x, x′)$ является ядром.
- Композиция произвольной функции $\varphi : X → X$ и произвольного ядра $K_0$ является ядром: $K(x, x′) = K_0(\varphi(x), \varphi(x′))$.
- Если $s: X×X → R$ - произвольная симметричная интегрируемая функция, то $K\left( {x,x'} \right) = \int\limits_X {s\left( {x,z} \right)} s\left( {x',z} \right)dz$ является ядром.
- Функция вида $K(x, x′) = k(x − x′)$ является ядром тогда и только тогда, когда Фурье-образ $F\left[ k \right]\left( \omega \right) = \left( {2\pi } \right)^{\frac{n}{2}} \int\limits_X {e^{ - i\left( {\omega ,x} \right)} } k\left( x \right)dx$неотрицателен.
- Предел локально-равномерно сходящейся последовательности ядер является ядром.
- Композиция произвольного ядра $K_0$ и произвольной функции $f : R → R$, представимой в виде сходящегося степенного ряда с неотрицательными коэффициентами $K\left( {x,x'} \right) = f\left( {K_0 \left( {x,x'} \right)} \right)$ , является ядром. В частности, функции $f\left( z \right) = e^z$ и $f\left( z \right) = \frac{1}{{1 - z}}$ от ядра являются ядрами
Существует несколько 'стандартных' ядер, которые при ближайшем рассмотрении приводят к известным алгоритмам: полиномиальным разделяющим поверхностям, двухслойным нейронным сетям, потенциальным функциям (RBF-сетям), и другим.
Наиболее распространённые ядра:
линейное: $k(x,x')=\left\langle {x,x'} \right\rangle$
полиномиальное: $k\left( {x,x'} \right) = \left( {\gamma \left\langle {x,x'} \right\rangle + r} \right)^d$
радиальная базисная функция: $k\left( {x,x'} \right) = \exp \left( { - \gamma \left\| {x - x'} \right\|^2 } \right),\gamma > 0$
радиальная базисная функция Гаусса: $k\left( {x,x'} \right) = \exp \left( { - \frac{{\left\| {x - x'} \right\|^2 }}{{2\sigma ^2 }}} \right)$
сигмовидная : $k\left( {x,x'} \right) = \tanh \left( {\gamma \left\langle {x,x'} \right\rangle + r} \right)$, для почти всех $\gamma >0$ и $r<0$
Ядра претендуют на роль универсального языка для описания широкого класса алгоритмов обучения по прецедентам. Наблю-
дается парадоксальная ситуация. С одной стороны, ядра одно из самых красивых и плодотворных изобретений в машинном обучении. С другой стороны, до сих пор не найдено эффективного общего подхода к их подбору в конкретных задачах.
Преимущества SVM перед методом стохастического градиента.
Вместо многоэкстремальной задачи решается задача квадратичного программирования, имеющая единственное решение. Методы оптимизации в этом случае существенно более эффективны.
Автоматически определяется число нейронов скрытого слоя. Оно равно числу опорных векторов.
Принцип оптимальной разделяющей гиперплоскости приводит к максимизации ширины разделяющей полосы между классами, следовательно, к более уверенной классификации. Градиентные нейросетевые методы выбирают положение разделяющей гиперплоскости произвольным образом, 'как придётся
Недостатки SVM.
Метод опорных векторов неустойчив по отношению к шуму в исходных данных. Если обучающая выборка содержат шумовые выбросы, они будут существенным образом учтены при построении разделяющей гиперплоскости. Этого недостатка лишён метод релевантных векторов (relevance vector machine, RVM).
До сих пор не разработаны общие методы построения спрямляющих пространств или ядер, наиболее подходящих для конкретной задачи. Построение адекватного ядра является искусством и, как правило, опирается на априорные знания о предметной области. На практике 'вполне разумные' функции $K(x, x′)$, выведенные из содержательных соображений, далеко не всегда оказываются положительно определёнными.
В общем случае, когда линейная разделимость не гарантируется, приходится подбирать управляющий параметр алгоритма $C$.
Алгоритм настройки SVM.
Двойственная задача (14) является задачей квадратичного программирования. Общие методы решения таких задач известны, но довольно трудоёмки, как в смысле реализации, так и по времени выполнения. Поэтому для обучения SVM применяются алгоритмы, учитывающие специфические особенности SVM. Специфика заключается в том, что число опорных векторов $h$, как правило, невелико, $h ≪ l$,и эти векторы находятся поблизости от границы классов. Именно эти особенности и позволяют ускорить поиск опорных объектов. Специализированные алгоритмы настройки SVM успешно справляются с выборками из десятков тысяч объектов.
Здесь мы рассмотрим не самый известный, но также довольно эффективный алгоритм - последовательный метод активных ограничений (incremental active set method, INCAS).
Перепишем двойственную задачу (14) в матричных обозначениях. Введём матрицу $Q = \left( {y{}_iy_j K\left( {x_i ,x_j } \right)} \right)_{i = 1,l}^{j = 1,l}$ размера $l × l$ и три вектор-столбца длины $l$: вектор ответов $y = \left( {y_i } \right)_{i = 1,l}$ , вектор двойственных переменных $\lambda = \left( {\lambda _i } \right)_{i = 1,l}$ и вектор единиц $e = \left( 1 \right)_{i = 1,l}$ . Тогда задачу (1.14) можно переписать в виде:
$$\left\{ {\begin{array}{*{20}c}
{\frac{1}{2}\lambda ^T Q\lambda - e^T \lambda \to \mathop {\min }\limits_\lambda } \\
{y^T \lambda = 0} \\
{0 \le \lambda \le C_e } \\
\end{array}} \right.\;\;\;(15)$$
Допустим, что решение $λ$ ещё не известно, но зато известно разбиение множества объектов на три непересекающихся подмножества $\left\{ {1,....,l} \right\} = I_O \cup I_C \cup I_S$:
$I_O = \left\{ {i:\lambda {}_i = 0} \right\}$ -периферийные объекты, $m_i > 1$;
$I_S = \left\{ {i:0 < \lambda {}_i < C} \right\}$ -опорные объекты, $m_i = 1$;
$I_C = \left\{ {i:\lambda {}_i = C} \right\}$ -объекты-нарушители, $m_i < 1$;
где $m_i = y_i \left( {\left\langle {w,x_i } \right\rangle - w_0 } \right)$ отступ объекта $x_i$ от границы классов.
Ограничения-неравенства $0 \le \lambda _i \le C$ становятся активными, то есть обращаются в равенства, на периферийных объектах ($i \in I_O ,\lambda _i = 0$) и объектах - нарушителях ($i \in I_C ,\lambda _i = C$). Соответствующие значения $λ_i$ можно подставить обратно в (15) и получить оптимизационную задачу, зависящую только от части переменных $\lambda _i ,i \in I_S$. Чтобы выписать эту задачу в матричном виде, введём трёхблочные обозначения для матрицы $Q$ и векторов $y, e, λ$:
$$Q = \left( {\begin{array}{*{20}c}
{Q_{SS} } & {Q_{SO} } & {Q_{SC} } \\
{Q_{OS} } & {Q_{OO} } & {Q_{OC} } \\
{Q_{CS} } & {Q_{CO} } & {Q_{CC} } \\
\end{array}} \right); y = \left( {\begin{array}{*{20}c}
{y_S } \\
{y_O } \\
{y_C } \\
\end{array}} \right);e = \left( {\begin{array}{*{20}c}
{e_S } \\
{e_O } \\
{e_C } \\
\end{array}} \right);\lambda = \left( {\begin{array}{*{20}c}
{\lambda _S } \\
{\lambda _O } \\
{\lambda _C } \\
\end{array}} \right)$$
В этих обозначениях задача (15) принимает вид:
$$\left\{ {\begin{array}{*{20}c}
{\frac{1}{2}\lambda _S^T Q_{SS} \lambda _S + Ce_C^T Q_{CS} - e_S^T \lambda _S \to \mathop {\min }\limits_{\lambda _S } } \\
{y_S^T \lambda _S + Ce_C^T y_C = 0} \\
\end{array}} \right.\;\;\;(16)$$
Если не обращать внимания на ограничения-неравенства, то это задача минимизации квадратичного функционала от $h = |I_S|$ переменных с одним линейным ограничением типа равенства. Она легко решается стандартными методами линейной алгебры и сводится, фактически, к обращению симметричной положительно определённой матрицы $Q_{SS}$ размера $h × h$.
Решение этой задачи даёт весь вектор $\lambda$, что позволяет вычислить параметры алгоритма $w$ и $w_0$ по формулам (4) и (7). Теперь можно классифицировать объекты выборки $x_i$, вычислить отступы $m_i$, и проверить, правильно ли множество объектов было разбито на подмножества $I_O ∪ I_C ∪ I_S$. Если условия Куна-Таккера не нарушатся ни на одном объекте, значит, решение задачи (15) найдено. Если же обнаружится хотя бы одно противоречие, то соответствующий объект должен быть переведён из одного подмножества в другое.
Всего возможны четыре типа противоречий:
- Если $i ∈ I_S$ и $\lambda _i \le 0$, то объект $x_i$ переводится из $I_S$ в $I_O$.
- Если $i ∈ I_S$ и $\lambda _i \ge C$, то объект $x_i$ переводится из $I_S$ в $I_C$.
- Если $i ∈ I_O$ и $m_i \le 1$, то объект $x_i$ переводится из $I_O$ в $I_S$.
- Если $i ∈ I_C$ и $m_i \ge 1$, то объект $x_i$ переводится из $I_C$ в $I_S$.
После каждой модификации множеств $I_O, I_C, I_S$ задача (16) решается заново. Итерационный процесс перевода объектов из одного множества в другое продолжается до тех пор, пока все объекты не будут удовлетворять условиям Куна-Таккера.
Описанный процесс является частным случаем метода активных ограничений (active sets method), который применяется для решения произвольных задач математического программирования с ограничениями-неравенствами. В линейном программировании он эквивалентен симплекс-методу. Сходимость данного метода в общем случае не гарантируется, однако в задачах настройки SVM зацикливания случаются крайне редко и легко предотвращаются с помощью нескольких удачных эвристик.Неплохая эвристика заключается в том, чтобы на каждом шаге выбирать объект $i$, для которого условие Куна-Таккера нарушается сильнее всего. Это способствует увеличению скорости сходимости.
Количество итераций существенно зависит от того, насколько удачным окажется начальное приближение. На практике применяются различные приёмы, чтобы сразу поточнее 'угадать' множество опорных векторов $I_S$.
Приём 1. Выбирается произвольная точка выборки, и находится ближайшая к ней точка другого класса. Для неё, в свою очередь, находится ближайшая точка в первом классе, и т. д. Этот итерационный процесс, как правило, сходится очень
быстро к некоторой паре пограничных точек. В Алгоритме 1 эта пара принимается за начальное приближение $I_S$, но можно и продолжить процесс, построив несколько или даже все такие пары.
Приём 2. Строится несколько достаточно грубых линейных классификаторов.Для этого можно использовать однослойные персептроны, проводя небольшое число итераций методом стохастического градиента. Затем для каждой линейной разделя-
ющей поверхности находится несколько ближайших к ней точек.
Алгоритм 1. Обучение SVM: последовательный метод активных ограничений
Вход:
$X^l$ - обучающая выборка;
$C$ - параметр двойственной задачи;
Выход:
параметры линейного классификатора $w, w_0$;
- 1: начальное приближение:
$I_S =$ две ближайшие точки из разных классов;
$I_O =$ все остальные точки;
$I_C = \emptyset$;
$$\left\{ {\begin{array}{*{20}c}
{\frac{1}{2}\lambda _S^T Q_{SS} \lambda _S + Ce_C^T Q_{CS} - e_S^T \lambda _S \to \mathop {\min }\limits_{\lambda _S } } \\
{y_S^T \lambda _S + Ce_C^T y_C = 0} \\
\end{array}} \right.$$
5: если $|I_S| > 2$ и $∃i: i ∈ I_S$ и $\lambda _i \le 0$ то перевести $i$ в $I_O$;
6: если $|I_S| > 2$ и $∃i: i ∈ I_S$ и $\lambda _i \ge C$ то перевести $i$ в $I_C$;
7: пока существует $i ∈ I_S$, который необходимо перевести в $I_O$ или в $I_C$;
8: вычислить параметры алгоритма $w$ и $w_0$ по формулам (4) и (7);
9: вычислить отступы $m_i$, $i ∈ I_0 ∪ I_C$;
10: если $∃i: i ∈ I_O$ и $m_i \le 1$ то перевести $i$ в $I_S$;
11: если $∃i: i ∈ I_C$ и $m_i \ge 1$ то перевести $i$ в $I_S$;
12: пока существует $i ∈ I_O ∪ I_C$, который необходимо перевести в $I_S$;
Высокая эффективность Алгоритма 1 вытекает из двух фактов. Во-первых, оптимизационная задача, решаемая на шаге 4, зависит только от матриц $Q_{SS}$ и $Q_{CS}$. Значит, вычислять скалярные произведения $K(x, x′)$ приходится только для пар объектов типа 'опорный–опорный' и 'опорный–нарушитель'.Во-вторых, множество $I_S$ на каждом шаге изменяется только на один элемент.Это позволяет выполнять пересчёт обратной матрицы $Q_{SS}^{ - 1}$ за $O(h^2)$ операций, тогда как обычное обращение потребовало бы $O(h^3)$ операций.
Преимущества метода INCAS.
Метод позволяет решать задачи, в которых нет линейной разделимости, в том числе задачи с шумовыми выбросами.
Метод особенно эффективен, когда число опорных векторов $h = |I_S|$ невелико.
Метод хорошо приспособлен для решения таких задач, в которых обучающие объекты поступают по одному в режиме реального времени. Добавление нового объекта реализуется практически так же, как перевод объекта из одного подмножества в другое, и требует порядка $O(h^2)$ операций
Недостатки метода INCAS.
- Метод становится неэффективен, когда число опорных векторов велико. В то же время, это означает, что либо выборка существенно неразделима, либо ядро $K(x, x′)$ выбрано неудачно. В обоих случаях такую задачу, скорее всего,нет смысла решать - надо менять ядро или саму постановку
Мультиклассовые методы опорных векторов
В своем исходном виде SVM не поддерживает многоклассовую классификацию. Для этого дополнительно разработано несколько мультиклассовых методов SVM:
Метод OvR.
Самой ранней реализацией многоклассовой классификации SVM, вероятно, является метод «один против всех». Он строит k моделей SVM, где k — количество классов.M-тый SVM обучается на всех примерах с положительными метками m-го класса и на всех остальных примерах с отрицательными метками. Таким образом, учитывая $l$ данных обучения $(x_1, y_1),...., (x_l, y_l)$ где $x_i \in R^n$ ,$i = 1,....,l$ и $y_i \in \left\{ {1,....,k} \right\}$ $x_i$ относится к m-му классу, m-й SVM решает следующую задачу:
$$\left\{ {\begin{array}{*{20}c}
{\frac{1}{2}\left( {w^m } \right)^T w^m + C\sum\limits_{i = 1}^l {\xi _i^m {\rm } \to {\rm }\mathop {\min }\limits_{w^m ,b^m ,\xi ^m } } } \\
\begin{array}{l}
\left( {w^m } \right)^T \phi \left( {x_i } \right) + b^m \ge 1 - \xi _i^m ,{\rm }if{\rm }y_i = m \\
\left( {w^m } \right)^T \phi \left( {x_i } \right) + b^m \le - 1 + \xi _i^m ,{\rm }if{\rm }y_i \ne m \\
\xi _i^m \ge 0,{\rm }i = 1,....,l \\
\end{array} \\
\end{array}} \right.\;\;\;(1)$$
где обучающие данные $x_i$ отображаются в пространство более высокой размерности с помощью функции $\phi$, а $C$ — штрафной параметр.
Минимизация ${\frac{1}{2}\left( {w^m } \right)^T w^m }$ означает, что мы хотим максимизировать $2/\left\| {w^m } \right\|$, разницу между двумя группами данных. Когда данные не являются линейно разделимыми, существует штрафной член $C\sum\limits_{i = 1}^l {\xi _i^m {\rm }}$ ,который может уменьшить количество ошибок обучения. Основная концепция SVM стоит состоит в поиске баланса между членом регуляризации ${\frac{1}{2}\left( {w^m } \right)^T w^m }$ и ошибками обучения.
После решения (1) имеется k решающих функций:
$$\begin{array}{*{20}c}
{\left( {w^1 } \right)^T \phi \left( x \right) + b^1 } \\
{...} \\
{\left( {w^k } \right)^T \phi \left( x \right) + b^k } \\
\end{array}$$
Мы говорим, что $x$ находится в классе, который имеет наибольшее значение решающей функции:
$$class{\rm }\;\;of\;\;{\rm }x \equiv \mathop {\arg \max }\limits_{m = 1,....,k} \left( {\left( {w^k } \right)^T \phi \left( x \right) + b^k } \right),\;\;\;(2)$$
Практически мы решаем двойственную задачу (1), в которой количество переменных совпадает с количеством данных в (1). Таким образом, решены задачи квадратичного программирования с k l-переменными.
Метод OvO.
Другой важный метод называется методом «один против одного». Этот метод создает $k(k- 1)/2$ классификаторов, каждый из которых обучается на данных из двух классов. Для обучающих данных $i$-го и $j$-го классов мы решаем следующую задачу бинарной классификации:
$$\left\{ {\begin{array}{*{20}c}
{\frac{1}{2}\left( {w^{ij} } \right)^T w^{ij} + C\sum\limits_i {\xi _t^{ij} \to \mathop {\min }\limits_{w^{ij} ,b^{ij} ,\xi ^{ij} } } } \\
\begin{array}{l}
\left( {w^{ij} } \right)^T \phi \left( {x_t } \right) + b^{ij} \ge 1 - \xi ^{ij} {\rm , }if{\rm }y_t = i \\
\left( {w^{ij} } \right)^T \phi \left( {x_t } \right) + b^{ij} \le - 1 + \xi ^{ij} {\rm , }if{\rm }y_t = j \\
\xi ^{ij} \ge 0 \\
\end{array} \\
\end{array}} \right.\;\;\;(3)$$
Существуют разные методы проведения будущего тестирования после того, как построены все классификаторы $k(k-1)/2$. Можно использовать следующую стратегию голосования.Если $sign\left( {\left( {w^{ij} } \right)^T \phi \left( x \right) + b^{ij} } \right)$ говорит, что x принадлежит i-му классу, то добавляется голос за i-й класс. В противном случае j-ое увеличивается на единицу. Затем мы прогнозируем, что x принадлежит к классу с наибольшим количеством голосов. Подход к голосованию, описанный выше также называется стратегией «Максимум побед». В случае, если два класса имеют одинаковые голоса, хотя это может быть не очень хорошей стратегией, теперь мы просто выбираем тот, у которого меньший индекс.
Практически мы решаем двойственное уравнение (3), в котором количество переменных совпадает с количеством данных в двух классах. Следовательно, если в среднем каждый класс имеет $l/k$ точек данных, нам нужно решить $k(k-1)/2$ задач квадратичного программирования, где каждая из них имеет около $2l/k$ переменных.
Метод DAGSVM
Третий алгоритм, обсуждаемый здесь, — это машины опорных векторов направленных ациклических графов (DAGSVM). Фаза его обучения такая же, как и у метода «один против одного», путем решения $k(k-1)/2$ двоичных SVM. Однако на этапе тестирования он использует корневой бинарно-направленный ациклический граф, который имеет $k(k-1)/2$ внутренних узла и $k$ листьев. Каждый узел представляет собой двоичную SVM $i$-го и $j$-го классов. Учитывая тест выборка x, начиная с корневого узла, оценивает функцию двоичного решения. Затем он перемещается влево или вправо в зависимости от выходного значения. Следовательно, мы проходим определенный путь, прежде чем достичь листового узла, который указывает предсказанный класс.
Преимущество использования DAG заключается в том, что можно провести некоторый анализ обобщений. Аналогичных теоретических результатов для методов «один против всех» и «один против одного» пока нет. Кроме того, время его тестирования меньше, чем у метода «один против одного».
Метод Крамера и Зингера.
Краммер и Сингер предложили подход к решению многоклассовых задач путем решения одной задачи оптимизации.По сути решается следующая основная задача:
$$\left\{ {\begin{array}{*{20}c}
{\mathop {\min }\limits_{w_m ,\xi _i } \frac{1}{2}\sum\limits_{m = 1}^k {w_m^T w_m } + C\sum\limits_{i = 1}^l {\xi _i } } \\
{w_{y{}_i}^T \phi \left( {x_i } \right) - w_m^T \phi \left( {x_i } \right) \ge e_i^m - \xi _i ,i = 1,...,l} \\
\end{array}} \right.\;\;\;(4)$$
где $e_i^m \equiv 1 - \delta _{y_i ,m}$ и
$$\delta _{y_i ,m} \equiv \left\{ {\begin{array}{*{20}c}
{1{\rm }if{\rm }y_i = m} \\
{0{\rm }if{\rm }y_i \ne m} \\
\end{array}} \right.$$
Тогда решающая функция:
$$\mathop {\arg \max \left( {w_m^T \phi \left( x \right)} \right)}\limits_{m = 1,...,k}$$
В (4)
$$\xi _i = \left( {\mathop {\max \left( {w_m^T \phi \left( {x_i } \right) + e_i^m } \right) - w_y^T \phi \left( {x_i } \right)}\limits_m } \right)_ +$$
где $\left( . \right)_ + \equiv \max \left( {.,0} \right),\xi _i \ge 0$ когда $y_i = m,e_i^m = 0$
Двойственная задача (4) такова:
$$\mathop {\min }\limits_\alpha f\left( \alpha \right) = \frac{1}{2}\sum\limits_{i = 1}^l {\sum\limits_{j = 1}^l {K_{i,j} } } \bar \alpha _i^T \bar \alpha _J + \sum\limits_{i = 1}^l {\bar \alpha _i^T \bar e_i }\;\;\;(5)$$$$\sum\limits_{m = 1}^k {\alpha _i^m } = 0,i = 1,...,l\;\;\;(5a)$$$$\left\{ {\begin{array}{*{20}c}
{\alpha _i^m \le 0,{\rm }if{\rm }y_i \ne m} \\
{\alpha _i^m \le C,{\rm }if{\rm }y_i = m} \\
{i = 1,....,l,{\rm }m = 1,...k} \\
\end{array}} \right.\;\;\;(5b)$$
Где $K_{i,j} \equiv \phi \left( {x_i } \right)^T \phi \left( {x_j } \right)$ , $\bar \alpha {}_i \equiv \left[ {\alpha _i^1 ,....,\alpha _i^k } \right]^T , \wedge \bar e_i \equiv \left[ {e_i^1 ,....,e_i^k } \right]^T$
Тогда $w_m = \sum\limits_{i = 1}^l {\alpha _i^m } \phi \left( {x_i } \right)$ . Если записать $\alpha \equiv \left[ {\alpha _1^1 ,....,\alpha _1^k ,....,\alpha _l^1 ,....,\alpha _l^k } \right]^T$ и $e \equiv \left[ {e_1^1 ,....,e_1^k ,....,e_l^1 ,....,e_l^k } \right]^T$
тогда двойную целевую функцию можно записать как:
$$\frac{1}{2}\alpha ^T \left( {K \otimes I} \right)\alpha + e^T \alpha$$
где $I$ — единичная матрица размера $k$ на $k$, а $ \otimes$ — произведение Кронекера. Поскольку $K$ положительно полуопределен, $K\otimes I$, гессиан двойственной целевой функции также является положительно полуопределенным. Это еще один способ объяснить, что (5) представляет собой задачу выпуклой оптимизации.
Функция принятия решения:
$$\mathop {\arg \max }\limits_{m = 1,...,k} \sum\limits_{i = 1}^l {\alpha _i^m K\left( {x_i ,x} \right)}$$
Если выбирать в рабочем наборе $k$ переменных, связанных с одним и тем же $x_i$. То есть $\alpha _i^1 ,....,\alpha _i^k$ элементы рабочего набора, выбор индекса $i$ которого будет обсуждаться ниже. Тогда подзадача:
$$\left\{ {\begin{array}{*{20}c}
{\min \frac{1}{2}A\bar \alpha _i^T \bar \alpha _i + B^T \bar \alpha _i } \\
{\sum\limits_{i = 1}^k {\alpha _i^m = 0} } \\
{\alpha _i^m \le C_{y_i }^m ,{\rm }m = 1,....,k} \\
\end{array}} \right.\;\;\;(6)$$
Где $A = K_{i,i}$ и $B = \bar e_i + \sum\limits_{j \ne i} {K_{j,i} } \bar \alpha _j$
Кроме того, $\bar C_{y_i }^m ,m = 1,....,k$ — вектор размером k на 1, все элементы которого равны нулю, за исключением того, что $y_i$-й компонент равен $C$.
Основная причина такой постановки в том, что (6) представляет собой очень простую задачу.Для (6) был предложен алгоритм,который используется ниже.Градиент двойной целевой функции равен:
$$\left[ {\begin{array}{*{20}c}
{\sum\limits_{j = 1}^l {K_{1,j} \alpha _j^1 + e_1^1 } } \\
\begin{array}{l}
... \\
\sum\limits_{j = 1}^l {K_{1,j} \alpha _j^k + e_1^k } \\
\sum\limits_{j = 1}^l {K_{2,j} \alpha _j^1 + e_2^1 } \\
... \\
\sum\limits_{j = 1}^l {K_{2,j} \alpha _j^k + e_2^k } \\
... \\
\end{array} \\
\end{array}} \right]$$
Тогда $B$, вектор $k$ на 1, можно вычислить по информации градиента следующим образом:
$$B_m = \frac{{\partial f\left( \alpha \right)}}{{\partial \alpha _i^m }} - K_{i,i} \alpha _i^m = \frac{{\partial f\left( \alpha \right)}}{{\partial \alpha _i^m }} - A\alpha _i^m ,m = 1,....,k$$
Во время итераций важно всегда обновлять градиент. Это делается после нового $\alpha _i^1 ,....,\alpha _i^k$, который получается с помощью (6) и ,следовательно, требуется $O(kl)$ операций.
Далее мы обсудим выбор рабочего набора и условие остановки метода декомпозиции. Условие ККТ требует наличия $b_1 ,....,b_l$ и $\lambda _1^1 \ge 0,....,\lambda _l^k \ge 0$ таких, что для всех $i = 1,....,l,m = 1,....,k$,
$$\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m - b_i = - \lambda _i^m {\rm } \wedge {\rm }\lambda _i^m \left( {\bar C_{y_i }^m - \alpha _i^m } \right) = 0$$
Тогда для всех $i = 1,....,l,m = 1,....,k$,
$$\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m - b_i \left\{ {\begin{array}{*{20}c}
{ = 0{\rm }if{\rm }\alpha _i^m {\rm < \bar C}_{{\rm y}_{\rm i} }^{\rm m} {\rm }} \\
{ \le 0{\rm }if{\rm }\alpha _i^m {\rm = \bar C}_{{\rm y}_{\rm i} }^{\rm m} } \\
\end{array}} \right.$$
Мы можем переписать это как
$$\mathop {{\rm max}}\limits_{\alpha _i^m \le C_{y_i }^m } \left( {\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m } \right) \le b_i \le \mathop {{\rm min}}\limits_{\alpha _i^m \le C_{y_i }^m } \left( {\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m } \right)\;\;\;(7)$$
Затем в ходе итераций выбираем следующий рабочий набор $\left\{ {\alpha _i^1 ,....,\alpha _i^k } \right\}$ из
$$\arg \max \left( {\mathop {{\rm max}}\limits_{\alpha _i^m \le C_{y_i }^m } \left( {\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m } \right) - \mathop {{\rm min}}\limits_{\alpha _i^m \le C_{y_i }^m } \left( {\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m } \right)} \right)\;\;\;(8)$$
Другими словами, среди $lk$-компонентных групп переменных выберем ту, которая имеет наибольшее нарушение условия ККТ. Тогда решение подзадачи (6) будет гарантировать строгое уменьшение целевой функции двойственной задачи.
Следуя (7), критерием остановки может быть:
$$\mathop {\max }\limits_i \left( {\mathop {{\rm max}}\limits_{\alpha _i^m \le C_{y_i }^m } \left( {\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m } \right) - \mathop {{\rm min}}\limits_{\alpha _i^m \le C_{y_i }^m } \left( {\sum\limits_{j = 1}^l {K_{i,j} } \alpha _j^m + e_i^m } \right)} \right) < \varepsilon\;\;\;(9)$$
где $\varepsilon$ останавливающий допуск
Сходимость описанного метода декомпозиции доказана так как предел (9) стремиться к нулю при числе реализаций стремящемся к бесконечности.Следовательно, за конечное число итераций метод декомпозиции останавливается, поскольку (9) выполняется.
