Лекция 7. Ядерные методы_ метод опорных векторов (1185284), страница 2
Текст из файла (страница 2)
, λm ) могут быть найдены как решениедвойственной задачи квадратичного программирования:mXj=1mm1X Xλj −λj 0 λj 00 αj 0 αj 00 (xj 0 xtj 00 ) → max2 000(7)j =1 j =1mXλj αj = 0j=1λj ≥ 0, j = 1, . . . , mСенько Олег Валентинович ()МОТП, лекция 617 / 35Метод опорных векторовПусть (λ̂1 , . . . , λ̂m ) - решение задачи (7) . Направляющий вектороптимальнойразделяющей гиперплоскости находится по формулеPmλ̂αxj=1 j j j То есть направляющий вектор разделяющейгиперплоскости является линейной комбинацией векторных описанийобъектов обучающей выборки, для которых значения соответствующихоптимальных множителей Лагранжа отличны от 0.
Такие векторныеописания принято называть опорными векторами. ПустьJ0 = {j = 1, . . . , m | [αj (zxtj − b) − 1] 6= 0}Из условий дополняющей нежёсткости видно, при j ∈ J0 обязательнодолжно выполняться равенство λ̂j = 0. Поэтому векторное описаниеxj соответствующего объекта обучающей выборки является опорнымвектором, если j не принадлежит J0 . Оценка параметра сдвига b̂находится из ограничения, соответствующего произвольному опорномувектору.Сенько Олег Валентинович ()МОТП, лекция 618 / 35Метод опорных векторовДействительно, из условий дополняющей нежёсткости следует, чтопри произвольном j, когда λj > 0, обязательно должно выполнятьсяравенство αj (zxtj − b) − 1 = 0, эквивалентное равенству b = zxtj − αj .Классификация нового распознаваемого объекта s с описанием xвычисляется согласно знаку выраженияg(x) =mXλ̂j αj (xj xt ) − b̂.(8)j=1Объект s относится к классу K1 , если g(x) и объект s относится кклассу K2 в противном случае.Существенным недостатком рассмотренного варианта метода опорныхвекторов является требование линейной разделимости классов.Однако данный недостаток может быть легко преодолён с помощьюследующей модификации, основанной на использованиидополнительного вектора неотрицательных переменныхξ = (ξ1 , .
. . , ξm ) .Сенько Олег Валентинович ()МОТП, лекция 619 / 35Метод опорных векторов. Случай отсутствия линейнойразделимости.Требования об отделимости классов (3) заменяются более мягкимитребованиями:Tzxtj ≥ b + 1 − ξj при sj ∈ K1 Set ,Tzxtj ≤ b − 1 + ξj при sj ∈ K2 Set . PВыдвигается также требование минимальности суммы mj=1 ξj . Поископтимальных параметров разделяющей гиперплоскости приотсутствии линейной разделимости таким образом сводится крешению задачи квадратично программированияnmX1X 2zi + Cξj → min2i=1αj (zxtj(9)j=1− b) ≥ 1 − ξj , ξj ≥ 0, j = 1, . . .
, mгде - некоторая положительная константа, являющаяся открытымпараметром алгоритма. Иными словами оптимальное значение Cподбирается пользователем.Сенько Олег Валентинович ()МОТП, лекция 620 / 35метод опорных векторов. Случай отсутствия линейнойразделимости.Из теоремы ККТ следует, что для произвольной точки (z ∗ , b∗ , ξ ∗ ) , вкоторой достигается минимум функционалаnmi=1j=1X1X 2zi + Cξj2при справедливости ограничений (9) , и некоторых векторовнеотрицательных множителей Лагранжа λ = (λ1 , .
. . , λn ) иη = (η1 , . . . , ηm ) соблюдаются условия стационарности лагранжианаL(z, b, λ, ξ, η) =Сенько Олег Валентинович ()nmmi=1j=1j=1X1X 2 Xηj ξjλj [αj (zxtj − b) − 1 + ξj ] −zi −2МОТП, лекция 621 / 35Метод опорных векторов. Случай отсутствия линейнойразделимости.Данные условия записываются в видеmX∂L(z, b, λ, ξ, η)|zi∗ = zi∗ −λj αj xji = 0∂zi(10)j=1i = 1, . . . , nm∂L(z, b, λ, ξ, η) X=λj αj = 0,∂bj=1∂L(z, b, λ, ξ, η)= C − λj − ηj = 0,∂ξjj = 1, . . . , m.Сенько Олег Валентинович ()МОТП, лекция 622 / 35Метод опорных векторов. Случай отсутствия линейнойразделимости.Также выполняются условия дополняющей нежёсткостиλj [αj (zxtj − b) − 1 + ξj ] = 0,(11)ηj ξj = 0,j = 1, .
. . , mОптимальные значения множителей (λ1 , . . . , λm ) могут быть найденыкак решение двойственной задачи квадратичного программированияmXλj −j=1mm1X Xλj 0 λj 00 αj 0 αj 00 (xj 0 xtj 00 ) → max2 000(12)j =1 j =1mXλj αj = 0j=1C ≥ λj ≥ 0, j = 1, . . . , mСенько Олег Валентинович ()МОТП, лекция 623 / 35Метод опорных векторов. Случай отсутствия линейнойразделимости.Как и в случае линейной разделимости направляющий вектороптимальнойразделяющей гиперплоскости находится по формулеPẑ = mλ̂αi=1 j j xj .
Из условий C − λj − ηj и ηj ξj = 0 следует чтоηj > 0 и ξj = 0 при 0 < λj < C. Также как и в случае существованиялинейной разделимости параметра сдвига b̂ находится из ограничения,соответствующего произвольному опорному вектору. Действительно,из условий дополняющей нежёсткости и и следующего из нихравенства ξj = 0 следует выполнение равенства αj (zxtj − b) − 1 = 0,эквивалентного равенству b = zxtj − αj . Распознавание нового объектаs производится по его описанию x также как и в случае линейноразделимых классов с помощью решающего правила (8) по величинераспознающей функции g(x) .Сенько Олег Валентинович ()МОТП, лекция 624 / 35Метод опорных векторов.
Построение нелинейных разделяющихповерхностейТаким образом построение оптимального решающего правиласводится к решению двойственных задач квадратичногопрограммирования (7) или (12). Следует отметить, что вектораописаний объектов обучающей выборки {xj | j = 1, . . . , m} входят взадачи (7),(12) только через свои скалярные произведения xj 0 xtj 00 приλj 0 > 0 и λj 00 > 0. Аналогично при вычислении значенияраспознающей функции (8) по описанию распознаваемого объекта xна самом деле используются только скалярные произведения xxtj 00 .Предположим что в исходном признаковом пространстве эффективноелинейное разделение отсутствует. Однако может существовать такоеевклидово пространство Hy и такое отображение Φ из областипространства Rn , содержащей описания распознаваемых объектов, впространство Hy , что образы объектов обучающей выборки изклассов K1 и K2 оказываются разделимыми с помощью некоторойгиперплоскости Py .
Пусть {y 1 , . . . , y m } -образы в пространстве Hyвекторов описаний объектов обучающей выборки {x1 , . . . , xm }.Сенько Олег Валентинович ()МОТП, лекция 625 / 35Метод опорных векторов. Построение нелинейных разделяющихповерхностейЛинейная разделимость означает существование решения аналогазадачи квадратичного программирования (4) для пространства Hy ,которое сводится к решению двойственной задачиmXλj −j=1mm1X Xλj 0 λj 00 αj 0 αj 00 (y j 0 y tj 00 ) → max2 000(13)j =1 j =1mXλj αj = 0j=1λj ≥ 0, j = 1, .
. . , mОтметим, что необходимость полного восстановления преобразованияΦ(x) для поиска всех коэффициентов задачи квадратичногопрограммирования (13) отсутствует. Достаточно найти функцию,связывающую скалярное произведение y j 0 y tj 00 c векторами xj 0 и xj 00 ,где y j 0 = Φ(xj 0 ) и y j 0 = Φ(xj 00 ) .Сенько Олег Валентинович ()МОТП, лекция 626 / 35Метод опорных векторо. Построение нелинейных разделяющихповерхностейТакую функцию мы далее будем называть потенциальной иобозначать K(x0 , x00 ). Можно подобрать потенциальную функциютаким образом, чтобы решение (13) было оптимальным. При этомпоиск оптимальной потенциальной функции может производитсявнутри некоторого заранее заданного семейства. Например,потенциальную функцию можно задать с помощью простого сдвигаK(x0 , x00 ) = x0 (x00 )t + θ,(14)Решение, полученное путём замены скалярных произведений напотенциальные функции, может рассматриваться как построениилинейной разделяющей поверхности в трансформированномпространстве, если удаётся доказать существование отображения Φ,для которого при произвольных x0 и x00 из Rn выполняется равенствоK(x0 , x00 ) = Φ(x0 )Φt (x00 ).Сенько Олег Валентинович ()МОТП, лекция 6(15)27 / 35Метод опорных векторов.
Построение нелинейных разделяющихповерхностейСуществование преобразования Φ , для которого выполняетсяравенство (15), было показано для неотрицательных симметричныхпотенциальных функций видаK(x0 , x00 ) = (x0 (x00 )t + θ)2 ,,где d ≥ 1-целое число а также ядровых функции типа гауссианыK(x0 , x00 ) =√2πσ n e−(x0 −x00 )22σ 2,где σ - вещественная неотрицательная константа (размер ядра).Поскольку в общем случае преобразование является нелинейным, топрообразом в пространстве Rn линейной разделяющейгиперплоскости, существующей в пространстве Hy , может оказатьсянелинейная поверхность.Сенько Олег Валентинович ()МОТП, лекция 628 / 35Метод опорных векторо.
Построение нелинейных разделяющихповерхностейДля большого числа прикладных задач линейная разделимостьявляется недостижимой. Поэтому выбор ядровой функции можетпроизводиться из требования о минимальности числа ошибок всмысле задачи квадратичного програмирования (9). На практикеподбор ядровых функций и их параметров производится исходя изтребования достижения максимальной обобщающей способности,которая оценивается с помощью скользящего контроля или оценок наконтрольной выборке.Сенько Олег Валентинович ()МОТП, лекция 629 / 35Метод опорных векторов.
Регрессия.Методика улучшения обобщающей способности, лежащая в основеМетода опорных векторов (МОВ) может быть распространена такжена задачи регрессии, то есть на задачи прогнозирования некоторойпеременной Y , принимающей значения из интервала вещественнойоси по значениями вещественных переменных X1 , . . . , Xn . Вместотребования максимизации величины «зазора» междураспознаваемыми классами для задач распознавания в случае задачрегрессии выдвигается требование минимизации вариацииe из которой принимаютпрогнозирующей функции на области X,значения переменные X1 , . . . , Xn Уменьшение вариациипрогнозирующей функции очевидно позволяет снизить вариационнуюсоставляющую обобщённой ошибки прогнозирования и уменьшитьэффект переобучения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
