Лекция 7 (2012 Лекции МОТП (Сенько))

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 7Ядерные методыНапомним, что байесовское решающее правило или оптимальноерешающее правило в смысле леммы Неймана-Пирсона могутбыть легко восстановлены, если для каждого из распознаваемыхклассов K1, , K L известны соответствующие плотностивероятностиf1 (x),, f L (x) . Ранее нами рассматривался методвосстановления плотностей f1 (x), , f L (x), основанный нагипотезе о нормальности соответствующих распределений.Альтернативным подходом является использование ядерныхметодов восстановления плотности.Ядерные методыЯдерные методы восстановления плотности в многомерномпространстве основаны на использовании так называемыхядровых функций.

Ядровая функция с центром в точке x j  R nx  xj1K()обычно записывается в форме hn. При этомhx  xj1выдвигается требование Rn [ hn K ( h )]dx  1 , где h - параметрсглаживания. В качестве ядровых функции может бытьиспользовано многомерное ядро ГауссаKN (x  xjh)1(2 )n / 2 |  |exp{11t(xx)(xx)jj }22hЯдерные методыПлотность вероятности для классаобъектам обучающей выборкипо формулеKiможет быть вычислена поSt  {s1  ( y1, x1 ),, sm  ( ym , xm )}x  xj1 mif i ( x) K()n mi h s j KihСогласно формуле Байеса распознаваемый объект относится вкласс, для котороговеличина mi fi (x)h nmis j KiK(x  xjh)максимальна .Параметр сглаживания находится с помощью метода скользящийконтроль.Метод опорных векторовМетод опорных векторов является универсальным методомраспознавания, позволяющим наряду с линейнымиреализовывать также нелинейные решающие правила.Исходный вариант метода был предложен для задач с двумяраспознаваемыми классами.Метод опорных векторовВ случаях, когда объекты разныхклассоввлинейносуществуетобучающейразделимы,целаялинейныхвыборкеобычносовокупностьповерхностей,осуществляющих такое разделение.На рисунке представлены двумерныеданные, где объекты двух классовмогут быть раделены с помощьюпрямых A, B, C, D.Метод опорных векторов• Однако наша интуиция, подсказывает что наилучшейобобщающей способностью должна обладатьразделяющая прямая F, одинаково удалённая от группобъектов из разных классов.

Интуитивные представленияоб оптимальной разделимости формализует проведениеразделяющей гиперплоскости посередине между двумяпараллельными гиперплоскостями, каждая из которыхотделяет объекты одного из классов.Метод опорных векторовПри этом две плоскости строятсятаким образом, чтобы расстояние«зазор» между ними был бымаксимальным. Из рисункавидно, что наибольшим является«зазор» между двумя параллеьными прямыми F и F’.Метод опорных векторовНапомним, что пара параллельных гиперплоскостей 1 и  2многомерном пространстве R n описывается спомощью уравненийwxt  b1(1 )wxt  b2(2 )(1)От системы (1) нетрудно перейти к эквивалентной системеzxt  b  1(1 )zxt  b  1(2 )(2),описывающей те же самые гиперплоскости.Метод опорных векторовРасстояние (величина зазора)  между гиперплоскостями 1 и22равна | z | . Следовательно задача поиска двухпараллельными гиперплоскостями, каждая из которыхотделяет объекты одного из классов, может быть сведена коптимизационной задаче с ограничениями2 max|z|zxtj  b  1 приs j  K1zxtj  b  1 приs j  K2(3)Метод опорных векторовПри этом оптимизация производится по компонентамнаправляющего вектора z  ( z1,Введём обозначение, zn ) и параметру сдвига b j  1, если s j  K1, и  j  1, если s j  K1Тогда задача (3) оказывается эквивалентна задаче1 n 2zi  min2 i 1 j (zxtj  b)  1j  1,,m(4)Метод опорных векторовИз известной теоремы Каруша-Куна-Такера следует,что дляn2**zпроизвольной точки (z , b ) , в которой  i достигает своегоi 1минимума при ограничениях задачи (4), и некоторого векторанеотрицательных множителей Лагранжа λ  (1,, m )соблюдаются условия стационарности лагранжиана,1 n 2 mL(z, b, λ )   zi    j [ j (zxtj  b)  1]2 i 1j 1а также условие дополняющей нежёсткости j [ j (z*xtj - b* )  1]  0j  1,,mМетод опорных векторовИз условия стационарности следует, чтоmL(z, b, λ )*|z*  zi    j j xi  0zij 1i  1,mилиz    j j x j*,j 1mL(z, b, λ )   j j  0а такжеbj 1(5),nМетод опорных векторовОптимальные значения множителей(1 ,, m )Могут быть найдены как решение двойственной задачиквадратичного программированияmmmt1xx j 2  j j j j j j  maxj 1 j 1i 1m i 1jj  0j(6)0j  1,,mМетод опорных векторовПусть (ˆ1 ,, ˆm ) - решение задачи (6) .Направляющий вектор оптимальной разделяющейmгиперплоскости находится по формуле zˆ   ˆ j j x jj 1То есть направляющий вектор разделяющей гиперплоскостиявляется линейной комбинацией векторных описаний объектовобучающей выборки, для которых значения соответствующихоптимальных множителей Лагранжа отличны от 0 ..Метод опорных векторовТакие векторные описания принято называть опорнымивекторами.

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

Однако данный недостаток может быть легкопреодолён с помощью следующей модификации, основаннойна использовании дополнительного вектора неотрицательныхпеременныхξ  (1,, m ) . Требования об отделимостиклассов (3) заменяются требованиями более мягкимитребованиямиzxtj  b  1   jzxtj  b  1   jприприs j  K1s j  K1j  1,,mМетод опорных векторовСлучай отсутствия линейной разделимостиВыдвигается также требование минимальности суммыmj 1.j. Поиск оптимальных параметров разделяющейгиперплоскости при отсутствии линейной разделимости такимобразом сводится к решению задачи квадратичноm1 n 2программирования  zi  C  j  min2 i 1j 1 j (zxtj  b)  1   j ,  j  0 j  1, , m (8)где С - некоторая положительная константа, являющаясяоткрытым параметром алгоритма.Метод опорных векторовСлучай отсутствия линейной разделимости***Из теоремы ККТ следует, что для произвольной точки (z , b , ξ ) ,m1 n 2в которой достигается минимум функционала  zi  C   j2 i 1j 1при справедливости ограничений (8) , и некоторых векторовнеотрицательных множителей Лагранжа λ  (1,η  (1,,m ), m )соблюдаются условия стационарностилагранжиана,mmm1 n 2tL(z, b, λ )   zi  C  j    j [ j (zx j  b)  1   j ]   j j2 i 1j 1j 1j 1Метод опорных векторовСлучай отсутствия линейной разделимостиДанные условия записываются в видеmL(z, b, λ, ξ, )*|z*  zi    j j xi  0zij 1i  1,,nmL(z, b, λ, ξ, )   j j  0bj 1L(z, b, λ , ξ, ) C   j  j  0 j(9)j  1,,mМетод опорных векторовСлучай отсутствия линейной разделимостиТакже выполняются условия дополняющей нежёсткости j j  0j  1, j [ j (zx  b)  1   j ]  0tj,mj  1,,m(10)Метод опорных векторовСлучай отсутствия линейной разделимостиОптимальные значения множителей(ˆ1 ,, ˆm )Могут быть найдены как решение двойственной задачиквадратичного программированияmmmt1xx j 2  j j j j j j  maxj 1 j 1i 1m j 1jj(11)00  j  Cj  1,,mМетод опорных векторовСлучай отсутствия линейной разделимостиКак и в случае линейной разделимости направляющий вектороптимальной разделяющей гиперплоскости находится поmzˆ   ˆ j j x.j Из условий (10) и (11) следует чтоформулеˆ j  0j 1ˆи  j  0 при 0   j  C .

Следовательно Оценкапараметра сдвиганаходится из ограничения,соответствующего произвольному опорному векторуˆ j  CИными словамиˆ tj   jbˆ  zxj  J s где J s  { j {1,, m}| C   j  0}Метод опорных векторовСлучай отсутствия линейной разделимостиРаспознавание нового объектаsпроизводится по егоописанию x также как и в случае линейно разделимыхклассов по с помощью решающего правила (7) повеличине распознающей функции g (x) .Метод опорных векторовСледует отметить, что вектора описаний объектов обучающей выборкиxjj  1,,mвходят в задачу (9) только через свои скалярныеtпроизведения x j x j . Аналогично при вычислении значенияраспознающей функции (10) по описанию распознаваемого объектаx на самом деле используются только скалярные произведенияxxtjпри  j  0Предположим что в исходном признаковом пространствелинейное разделение отсутствуетэффективноеМетод опорных векторовНелинейная разделяющая поверхностьОднако такое разделение может существовать в пространствеRкоторое может быть получено из исходного признаковогопространства R nx с помощью преобразования  , ставящегоnnпроизвольному вектору из x  R x вектор из y  R yy .Линейная разделимость означает существование решения.Задачи квадратичного программированияmj i 1m j 1jjm12mtyy j j j j j j  maxj1 j100   j , y j  (x j ), j  1, , m(12)nyyМетод опорных векторовНелинейная разделяющая поверхностьОтметим, что необходимость полного восстановленияпреобразования для поиска всех коэффициентов задачиквадратичного программирования (12) отсутствует.