Лекция 7. Ядерные методы. Метод опорных векторов (2015 Лекции (Сенько))

Лекция 7Ядерные методы,метод опорных векторовЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 61 / 35Содержание лекции1Ядерные методы2Метод опорных векторов2Метод опорных векторов. Регрессия.Сенько Олег Валентинович ()МОТП, лекция 62 / 35Ядерные методыНапомним, что байесовское решающее правило или оптимальноерешающее правило в смысле леммы Неймана-Пирсона могут бытьлегко восстановлены, если для каждого из распознаваемых классовK1 , . . .

, KL известны соответствующие плотности вероятностиp1 (x), . . . , pL (x) . Ранее нами рассматривался методы восстановленияплотностей p1 (x), . . . , pL (x) , основанные на гипотезе о независимостипеременных X1 , . . . , Xn , а также на гипотезе о нормальностисоответствующих распределений. Альтернативным подходом являетсяиспользование ядерных методов восстановления плотности. Плотностьвероятностей для каждого из классов K1 , . . . , KL в точкахпространства Rn оценивается по объектам стандартной обучающейвыборки Set = {s1 = (α1 , x1 ), .

. . , sm = (αm , xm )} c использованиемядровых функций.Сенько Олег Валентинович ()МОТП, лекция 63 / 35Ядерные методыПлотность вероятности для класса Ki в точке x ∈ Rn вычисляется поформуле1 XK(x, xj ),pi (x) =misj ∈Kiгде mi - число объектов в обучающей выборки из класса Ki ,K(x0 , x00 )является неотрицательной вещественнозначной функцией заданной,заданной на декартовом произведении Rn × Rn .

При этомK обладает свойством симметричности, то естьK(x0 , x00 ) = K(x00 , x0 );K достигает максимума при x0 = x00 ;K убывает или по крайней мере не возрастает по мере увеличениярасстояния между точками x0 и x00 .Сенько Олег Валентинович ()МОТП, лекция 64 / 35Ядерные методыВ одномерном случае, когда оценка плотности вероятностипроизводится в точках интервала допустимых значений одногопризнака X по обучающей выборке {(α1 , x1 ), . . . , (αm , xm )}, вx−xкачестве ядровых используются функции от x вида K( h j ), где h параметр сглаживания, характеризующий подробностьаппроксимации. Для одномерных ядровых функций предполагаетсявыполнение требований:максимальное значение K(u) должно достигаться в точке 0;должно выполняться свойство симметричности K(u) = K(−u);K(u) монотонно убывающая или не возрастающая по мереудаления u от 0 функция;R∞требуется выполнение равенства −∞ K(u)du = 1.Очевидно, что такими свойствами обладают:прямоугольное ядро K(u) = 21 при | u |≤ 1 и K(u) = 0 при| u |> 1;2гауссиана K(u) =Сенько Олег Валентинович ()u√1 e− 22π.МОТП, лекция 65 / 35Ядерные методыПеречисленными свойствами обладает также ядро ЕпанечниковаK(u) = 34 (1 − u2 ) при | u |≤ 1 и K(u) = 0 при | u |> 1.

Параметрмасштаба h характеризует подробность аппроксимации. При h → 0ядерный аппроксиматор подробно описывает детали эмпирическогораспределения объектов обучающей выборки. Однако устойчивостьаппроксимации при этом теряется. При увеличении h возрастаетустойчивость аппроксимации, но теряется способность улавливатьдетали.Многомерные ядра размерности n могут задаваться в видепроизведения одномерных ядер:nx∗i − xji1 YK().K(x∗ , xj ) = nhhi=1Сенько Олег Валентинович ()МОТП, лекция 66 / 35Ядерные методыИспользуются также ядровые функции, где связь между точкамизадаётся через расстояние между ними. Например, могутиспользоваться ядровые функции типа гауссианыK(x∗ , xj ) =√2πσ n e−(x∗ −xj )22σ 2.Согласно формуле Байеса распознаваемый объект относится в класс,для которого величина pi (x)P (Ki ) максимальна . Параметрсглаживания h может подбираться таким образом, чтобы точностьраспознавания была максимальной.

Например, можетмаксимизироваться оценка точности на контрольной выборке или воценкой скользящего контроля.Сенько Олег Валентинович ()МОТП, лекция 67 / 35метод опорных векторовМетод опорных векторов является универсальным методомраспознавания, позволяющим наряду с линейными реализовыватьтакже нелинейные решающие правила. Исходный вариант метода былпредложен для задач с двумя распознаваемыми классами K1 и K2 . Вслучаях, когда объекты разных классов в обучающей выборке линейноразделимы, обычно существует целая совокупность линейныхповерхностей, осуществляющих такое разделение.

На рисункепредставлены двумерные данные, где объекты двух классов могутбыть раделены с помощью прямых A, B, C, D. Однако наша интуиция,подсказывает что наилучшей обобщающей способностью должнаобладать разделяющая прямая F, одинаково удалённая от группобъектов из разных классов.Сенько Олег Валентинович ()МОТП, лекция 68 / 35Метод опорных векторовРис.1Интуитивные представления об оптимальной разделимостиформализует проведение разделяющей гиперплоскости посерединемежду двумя параллельными гиперплоскостями, каждая из которыхотделяет объекты одного из классов.Сенько Олег Валентинович ()МОТП, лекция 69 / 35метод опорных векторовРис.2При этом две плоскости строятся таким образом, чтобы расстояние«зазор» между ними был бы максимальным.

Из рисунка видно, чтонаибольшим является «зазор» между двумя параллеь ными прямымиF и F’.Сенько Олег Валентинович ()МОТП, лекция 610 / 35Метод опорных векторовНапомним, что пара параллельных гиперплоскостей P1 и P2 вмногомерном пространстве Rn описывается с помощью уравненийP1 → wxt = b1(1)P2 → wxt = b2От системы (1) нетрудно перейти к эквивалентной системеzxt = b + 1(2)zxt = b − 1,описывающей те же самые гиперплоскости. Расстояние (величина2.зазора) δ между гиперплоскостями P1 и P2 равно |z|Сенько Олег Валентинович ()МОТП, лекция 611 / 35Метод опорных векторовСледовательно задача поиска двух максимально удалённых друг отдруга параллельных гиперплоскостей, каждая из которых отделяетобъекты одного из классов, может быть сведена к оптимизационнойзадаче с ограничениямиδ=2→ max|z|(3)Tzxtj ≥ b + 1 при sj ∈ K1 Set ,Tzxtj ≤ b − 1 при sj ∈ K2 Set .При этом оптимизация производится по компонентам направляющеговектора z = (z1 , .

. . , zn ) и параметру сдвига b. Введём обозначениеαj = 1 при sj ∈ K1 иαj = −1 при sj ∈ K2Сенько Олег Валентинович ()МОТП, лекция 612 / 35Метод опорных векторовТогда задача (3) оказывается эквивалентна задачеn1X 2zi → min2(4)i=1αj (zxtj − b) ≥ 1, j = 1, . . . , mИз известной теоремы Каруша-Куна-Такераследует, что дляPn (ККТ)∗∗2произвольной точки (z , b ) , в которой i=1 zi достигает своегоминимума при ограничениях задачи (4), и некоторого векторанеотрицательных множителей Лагранжа λ = (λ1 , . .

. , λm )соблюдаются условия стационарности лагранжианаnmi=1j=11X 2 XL(z, b, λ) =zi −λj [αj (zxtj − b) − 1]2Сенько Олег Валентинович ()МОТП, лекция 613 / 35Метод опорных векторовТакже из теоремы ККТ следует необходимость выполнения mравенств, которые носят название условий дополняющей нежёсткостиλj [αj (z ∗ xtj − b∗ ) − 1] = 0, j = 1, . . . , mИз условия стационарности следует, чтоmX∂L(z, b, λ) ∗ ∗|( z , b ) = zi∗ −λj αj xji = 0∂zi(5)j=1В векторной форме система (5) принимает видz∗ =mXλj αj xjj=1,Из условия стационарности следует выполнение равенстваm∂L(z, b, λ) X=λj αj = 0∂b(6)j=1Сенько Олег Валентинович ()МОТП, лекция 614 / 35метод опорных векторовТаким образом для получения решения задачи (4) достаточно найтитребуемый вектор значений неотрицательных множителей Лагранжаλ∗ = (λ∗1 , .

. . , λ∗m ).Поиск оптимальных значений множителей Лагранжа.Нетрудно показать, что лагранжиан в произвольной точке (z, b, λ),для которой соблюдаются условия (5,6), может быть записан в видеL(z, b, λ) = g(λ) =mXj=1λj −mm1X Xλj 0 λj 00 αj 0 αj 00 (xj 0 xtj 00 ).2 000j =1 j =1Отметим, что в силу соблюдения ограничений задачи (4) инеотрицательности множителей Лагранжа выполняется неравенствоg(λ) ≤nXzi2 .i=1Сенько Олег Валентинович ()МОТП, лекция 615 / 35метод опорных векторовИз теории оптимизации с ограничениями следует, что при соблюденииряда условий, которые справедливы для задачи (4), максимум g(λ) повектору множителей ЛагранжаиP при условии их неотрицательности1 Pn∗ )2 . Однако(zпри соблюдении равенства mλα=0равенi=1 ij=1 j j2в силу соблюдения условий стационарности и условий дополняющейнежёсткости справедливо равенствоnL(z ∗ , b∗ , λ) = g(λ∗ ) =1X ∗ 2(zi ) .2i=1То есть точка λ∗ является точкой максимума g(λ) при условиинеотрицательности (λ1 , .

. . , λm ) и при соблюдении равенстваPmj=1 λj αj = 0 .Сенько Олег Валентинович ()МОТП, лекция 616 / 35метод опорных векторовТаким образом оказывается, что оптимальные значения множителеймножителей Лагранжа (λ1 , . . . , λ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, .