ММО3 (2015 Учебное пособие ММО (Сенько)), страница 2

Однако согласно|z|системе (2)z (x1t  xt2 ) 2.|z||z|удалённых друг от другаСледовательно задачапоискадвух максимальнопараллельных гиперплоскостей, каждая из которых отделяетобъекты одного из классов, может быть сведена к оптимизационной задаче сограничениями.2 max|z|(3)zxtj  b  1 при s j  St  K1zxtj  b  1 при s j  St  K 2 , j  1,,m.При этом оптимизация производится по компонентам направляющего вектораz  ( z1 ,, zn )и параметру сдвига b .Введём обозначение: j  1 при s j  St  K1 и2монотонно возрастает с уменьшением|z|s j  St  K 2 .

Учитывая, функцияnzi 12i, переходим от задачи (3) к задаче1 n 2 zi  min2 i 1(4) j (zxtj  b)  1 , j  1, , m .Задача(4)относитсяпрограммирования.кхорошоизученномуклассузадачквадратичногоРешениезадачиквадратичногопрограммирования.Важныминструментомисследования экстремальных значений оптимизируемых функций при ограниченияхявляется функция Лагранжа или лагранжиан, который для задачи (4) записывается в видеL(z, b, λ ) где(1 ,12nmi 1j 1 zi2    j [ j (zxtj  b)  1] ,, m ) являются неотрицательными вещественными, которые называютсямножителями Лагранжа.Из известной теоремы Каруша-Куна-Такера (ККТ) следует, что для точкикоторой функция1 n 2 zi2 i 1(z* , b* ) , вдостигает своего минимума при ограничениях задачи (4), инекоторого вектора значений неотрицательных множителей Лагранжа λ *  (1* ,, m* )соблюдаются условия стационарности лагранжиана L(z, b, λ ) по переменным ( z , b) .Также из теоремы ККТ следует необходимость выполненияm равенств, которые носятназвание условий дополняющей нежёсткости *j [ j (z*xtj  b)  1]  0 , j  1, , mУсловия стационарности заключаются в выполненииmL(z, b, λ ) zi*    *j  j x ji  0 , i  1,zij 1( z* ,b* , λ* )n равенств,n(5)В векторной форме система (5) принимает видmz    *j  j x j  0 .*j 1Из условия стационарности также следует выполнение равенстваmL(z, b, λ )   *j  j  0bj 1( z* ,b* ,λ* )(6)Условия стационарности (5,6) для лагранжиана L(z, b, λ ) являются необходимымиусловиями экстремума при ограничениях задачи (4).Поиск оптимальных значений множителей Лагранжа.

Предположим, чтоявляется некоторой точкой, в которой(z, b, λ )соблюдаются условия стационарности исоблюдаются ограничения задачи (4).Нетрудно показать, воспользовавшись уравнениями (5,6), что лагранжиан в точке(z, b, λ ) можетбытьзаписанmmj 1j 1 j 1ввидеmL(z, b, λ )  g ( λ )    j  12   j j j j ( x jxtj ) .Отметим, что в силу соблюдения ограничений задачи (4) и неотрицательностимножителей Лагранжа в точке (z, b, λ ) выполняется неравенствоnni 1i 1g (λ )   ( zi) 2  12  ( zi* )212Из условий дополняющей нежёсткости следует, что в точке ( z*, b*, λ*) справедливоравенствоL ( z * , b* , λ * ) n12m ( zi* )2    *j [ j (z*xtj  b* )  1] i 1j 1Таким образом максимум g ( λ ) равенТаким образом,(1* ,, m* )оптимальныеn12(z )i 1* 2in12(z )i 1* 2iи достигается при λ  λ .*значения неотрицательных множителей Лагранжамогут быть найдены как решение оптимизационной задачи, котораяназывается квадратичного программирования, двойственной по отношению к задаче (4):mj 1jm12m  j 1 j 1j j j (x j xtj )  maxj m j 1jj j  0, j  1,0,m(7)Пусть(ˆ1 ,разделяющей, ˆm )- решение задачи (7)Направляющий вектор оптимальнойгиперплоскости находится по формуле z* m ˆ  xjj 1То есть направляющий вектор разделяющей гиперплоскостиjj.является линейнойкомбинацией векторных описаний объектов обучающей выборки, для которых значениясоответствующих оптимальных множителей Лагранжа отличны от 0.

Такие векторныеописания принято называть опорными векторами. Пусть, m [ j (z*xtj  b)  1]  0}J 0  { j  1,Из условий дополняющей нежёсткости видно, приj  J0выполняться равенство ˆ j  0 . Поэтому векторное описаниеобязательно должноx j соответствующегообъекта обучающей выборки является опорным вектором, если j не принадлежит J 0 .Оценкапараметра сдвигаb̂находится из ограничения, соответствующегопроизвольному опорному вектору.Распознавание новых объектов. Классификация нового распознаваемого объекта sописанием x вычисляется согласно знаку выраженияmg ( x)   ˆ j j ( x j xt )  bˆj 1Объект s относится к классу K1 , если g ( x)  0 и объект s относится к классу K 2 впротивном случае.4.7.2 Случай отсутствия линейной разделимостиСущественным недостатком рассмотренного варианта метода опорных векторов являетсятребование линейной разделимости классов.

Однако данный недостаток может бытьлегко преодолён с помощью следующей модификации, основанной на использованиидополнительного вектора неотрицательных переменных ( 1 ,, m ) .Требования об отделимости классов из задачи (3) заменяются более мягкими требованиями:zxtj  b  1   j при s j  St  K1сzxtj  b  1   jпри s j  St  K 2 ,j  1,,m.mПри этом выдвигается требование минимальности суммыj 1j. Поиск оптимальныхпараметров разделяющей гиперплоскости при отсутствии линейной разделимости такимобразом сводится к решению задачи квадратично программированияm1 n 2 j  min zi  C 2 i 1j 1 j (zxtj  b)  1   j ,  j  0, , j  1, , m ,Положительная константа C является открытым параметром алгоритма.

Инымисловами оптимальное значение C подбирается пользователем.Пусть λ *  (1* ,, m* ) - вектор множителей Лагранжа, соответствующих ограничениям j (zxtj  b)  1   j ;η*  (1* ,,m* ) - вектор множителей Лагранжа, соответствующих ограничениям j  0, , j  1, , m ;Изтеоремы ККТ следует, что для точкиm1 n 2j zi  C 2 i 1j 1некоторых(z* , b* , ζ* ) , в которойдостигает своего минимума привекторовограничениях задачизначений неотрицательных множителей Лагранжасоблюдаются условия стационарности лагранжианаL(z, ζ, b, λ , η) 12nmmmi 1j 1j 1j 1 zi2  C   j    j [ j (zxtj  b)  1   j ]   j jпо переменным (z, η, b) .Данные условия записываются в видеmL(z, ζ, b, λ , η) zi*    *j  j x ji  0, i  1,zij 1( z* ,b* ,ζ* ), n;функция(4), иλ * и η*mL(z, b, λ )   *j  j  0;bj 1( z* ,b* ,λ* )L(z, b, λ ) j C   j   j  0,**j  1,,m*( z ,b , λ )Также из теоремы ККТ следует необходимость выполненияm равенств, которые носятназвание условий дополняющей нежёсткости *j [ j (z*xtj  b)  1   j ]  0,  j j , j  1, , m.

, j  1, , mОптимальные значения множителей (1* ,, m* ) могут быть найдены как решениедвойственной задачи квадратичного программирования.mmj 1j 1 j 1m  j  12   j j j j (x jxtj )  maxm j 1jj(7)0C   j  0, j  1,,mКак и в случае линейной разделимости направляющий вектор оптимальной разделяющейгиперплоскости находится по формуле z * m  xj 1*jjj.

Из условий C   j   j  0 и j j  0 следует что  j  0 и  j  0 при 0   j  C .Также как и в случае существования линейной разделимости параметра сдвигаb̂находится из ограничения, соответствующего произвольному опорному вектору x j .Действительно, из условий дополняющей нежёсткости и и следующего из них равенства j  0 следует выполнение равенства  j (z*xtj  bˆ)  1  0 , эквивалентного равенствуbˆ  z*xtj   j .Распознавание нового объектаs производится по его описанию x также как и вслучае линейно разделимых классовраспознающей функции g ( x) .с помощью решающего правила (8) по величине4.7.3 Построение оптимальных нелинейных разделяющих поверхностейс помощью метода опорных векторов.Предположим что в исходном признаковом пространствеэффективное линейноеразделение отсутствует.

Однако может существовать такое евклидово пространство H yи такое отображение из области пространстваR n содержащей описанияраспознаваемых объектов, в пространство H y , что образы объектов обучающей выборкииз классов K1 и K 2 оказываются разделимыми с помощью некоторой гиперплоскостиPy . Пусть {y1 ,, y m } -образы в пространстве H y векторов описаний объектовобучающей выборки {y1 ,, y m}.Линейная разделимость означает существованиеквадратичного программирования(4)решенияаналогазадачидля пространства H y , которое сводится крешению двойственной задачиmmj 1j 1 j 1m  j  12   j j j j (y jy tj )  maxm j 1jj0 j  0, j  1,,mОтметим, что необходимость полного восстановления преобразования  ( x) для поискавсехкоэффициентовзадачиквадратичногоДостаточно найти функцию, связывающуюпрограммирования(13)отсутствует.tскалярное произведение (y j y j ) cвекторами x j и x j , где y j  (x j ) и y j  (x j ) .Такую функцию мы далее будем называть потенциальной и обозначать K (x j ў, x j ўў).

Можно подобрать потенциальную функцию таким образом, чтобы решение (13) былооптимальным. При этом поиск оптимальной потенциальной функции может производитсявнутри некоторого заранее заданного семейства.можно задать с помощью простого сдвигаНапример, потенциальную функциюK (x j ў,x j ўў)=x j ўxtj ўў + θ . Решение,полученное путём замены скалярных произведений на потенциальные функции, можетрассматриватьсякакпостроениилинейнойразделяющейповерхностивтрансформированном пространстве, если удаётся доказать существование отображения ( x) , для которого при произвольных x и x из R n выполняется равенствоK (xў, xўў)=F (xў)F t (xўў)\Существование преобразования  ( x) , для которого выполняется равенство (15), былопоказано для неотрицательных симметричных потенциальных функций видаK (xў, xўў)=[xў(xўў)t ]d + q,где d -целое число, q -вещественная константа.Существование преобразования  ( x) с выполнением равенство (15) доказано такжедля ядровых функции типа гауссианы1K ( xў, xўў)=e2p d( x ў- x ўў) 22d 2,где  - вещественная неотрицательная константа (размер ядра).

Поскольку вобщем случае преобразованиеявляется нелинейным, то прообразом в пространствеR n линейной разделяющей гиперплоскости, существующей в пространстве H y , можетоказаться нелинейная поверхность.Для большого числа прикладных задач линейная разделимость является недостижимой.Поэтому выбор ядровой функции может производиться из требования о минимальностичисла ошибок в смысле задачи квадратичного програмирования (9). На практике подборядровых функций и их параметров производится исходя из требования достижениямаксимальной обобщающей способности, которая оценивается с помощью скользящегоконтроля или оценок на контрольной выборке. Опыт решения прикладных задачпоказывает, что высокая эффективность распознавания достигается при выборе в качествеядровой функции гауссианы.Прототипом метода опорных векторов явился метод «Обобщенный портрет»,разработанный В.Н.Вапником и А.Я.Червоненкисом [1] .