_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (1185333), страница 7
Текст из файла (страница 7)
Метод опорных векторов и беспризнаковое распознавание образов38x2**(x 1,x 2)x1g(x1,x2)=0Рис. 4.2. Пример решения задачи условной оптимизации. Черные линии обозначают линии уровня оптимизируемой функции.Серая пунктирная прямая представлет собой область поиска решения. Точка (x∗1 , x∗2 ) = (1/2, 1/2) является решением задачи.Тогда∇x L = 0∂L=0∂λ⇒ условие ортогональности ∇f + λ∇g = 0⇒ g(x) = 0Функция Лагранжа. Пример (см.
рис. 4.2)f (x1 , x2 ) = 1 − x21 − x22 → maxx1 ,x2g(x1 , x2 ) = x1 + x2 − 1 = 0Функция Лагранжа:L(x, λ) = 1 − x21 − x22 + λ(x1 + x2 − 1)Условия стационарности:− 2x1 + λ = 0− 2x2 + λ = 0x1 + x2 − 1 = 0Решение: (x∗1 , x∗2 ) = ( 12 , 12 ), λ = 1.Ограничение в виде неравенства (см. рис. 4.3)Задача условной оптимизацииf (x) → maxxg(x) ≥ 0РешениеВнутри области g(x) > 0На границе g(x) = 0ОграничениенеактивноактивноУсловие стационарности∇f (x) = 0, ∇x L = 0, λ = 0∇f (x) = −λ∇g(x), ∇x,λ L = 0, λ > 0Глава 4.
Метод опорных векторов и беспризнаковое распознавание образов39Рис. 4.3. Иллюстрация к задаче оптимизации с ограничениями в виде неравенства. В случае, если оптимальная точка лежитвне области g(x) ≥ 0, то в точке оптимума градиенты ∇f и ∇g должны быть коллинеарны и направлены в разные стороныУсловие дополняющей нежесткости:λg(x) = 0Теорема Каруша-Куна-ТаккераПусть fi : X → R, i = 0, 1, . . . , m — выпуклые функции, отображающие нормированное пространствоX в прямую, A ∈ X — выпуклое множество. Рассмотрим следующую задачу оптимизации:f0 (x) → min;fi (x) ≤ 0, i = 1, . .
. , m, x ∈ A(P )Теорема 1.1. Если x̂ ∈ absmin(P ) — решение задачи, то найдетсяPm ненулевой вектор множителей Лагранжаλ ∈ Rm+1 такой, что для функции Лагранжа L(x) = i=0 λi fi (x) выполняются условия:a) стационарности minx∈A L(x) = L(x̂)b) дополняющей нежесткости λi fi (x̂) = 0, i = 1, . . . , mc) неотрицательности λi ≥ 02. Если для допустимой точки x̂ выполняются условия a)–c) и λ0 6= 0, то x̂ ∈ absmin(P )3. Если для допустимой точки x̂ выполняются условия a)–c) и ∃x̃ ∈ A : fi (x̃) < 0, i = 0, . .
. , m(условие Слейтера), то x̂ ∈ absmin(P )4.2Метод опорных векторов для задачи классификацииЗадача классификации• Рассматривается задача классификации на два класса. Имеется обучающая выборка (X, t) ={xi , ti }ni=1 , где x ∈ Rd , а метка класса t ∈ T = {−1, 1}.• Необходимо с использованием обучающей выборки построить отображение A : Rd → T , которое длякаждого нового входного объекта x∗ выдает его метку класса t∗ .4.2.1Метод потенциальных функцийМетод потенциальных функций [Айзерман и др., 1964]Глава 4.
Метод опорных векторов и беспризнаковое распознавание образов40Рис. 4.4. Иллюстрация к методу потенциальных функций.В каждом объекте xi помещен электрический заряд ti qi . В качестве разделяющей функции используется потенциал создаваемого поля:nXf (x) =ti qi K(x, xi )i=1Функция K(x, y) называется потенциальной функцией и имеет смысл потенциала в точке y, создаваемогозарядом в точке x.
Предполагается, чтоK(x, y) → 0 при kx − yk → +∞K(x, y) → max при kx − yk → 0Алгоритм обучения: f (x) + K(x, xk ), если tk = 1 и f (xk ) ≤ 0f (x) − K(x, xk ), если tk = −1 и f (xk ) ≥ 0f new (x) =f (x),иначе4.2.2Случай линейно разделимых данныхРазделяющая гиперплоскость<z,x>+b=0z0Рис. 4.5. Разделяющая гиперплоскость для объектов двух классов. Направление гиперплоскости задается вектором нормалиzГлава 4.
Метод опорных векторов и беспризнаковое распознавание образов41• Гиперплоскость задается направляющим вектором гиперплоскости z и величиной сдвига b(см. рис. 4.5):{x ∈ Rd |hz, xi + b = 0}, z ∈ Rd , b ∈ R• Если вектор z имеет единичную длину, то величина hz, xi определяет длину проекции вектора xна направляющий вектор z. В случае произвольной длины скалярное произведение нормируется наkzk.Каноническая гиперплоскость• Если величину направляющего вектора z и величину сдвига b умножить на одно и то же число, тосоответствующая им гиперплоскость не изменится.• Пара (z, b) задает каноническую гиперплоскость для набора объектов x1 , .
. . , xn ∈ Rd , еслиmin |hz, xi i + b| = 1i=1,...,n(∗)• Условие (*) означает, что ближайший вектор к канонической гиперплоскости находится от нее нарасстоянии 1/kzk:xi : |hz, xi i + b| = 1, x : hz, xi + b = 0¯¿À¯¯ z¯1|hz, xi − xi| = 1 ⇒ ¯¯, xi − x ¯¯ =kzkkzk• Каноническая гиперплоскость определена однозначно с точностью до знака z и bКлассификатор• Будем искать классификатор в виде разделяющей гиперплоскости (см. рис.
4.6):t̂(x) = sign(y(x)) = sign(hz, xi + b)• Предположим, что исходные данные являются линейно разделимыми, т.е.∃(z, b) : t̂(xi ) = ti ∀i = 1, . . . , nОптимальная разделяющая гиперплоскость• Зазором гиперплоскости данной точки (x, t) называется величина:ρ(z,b) (x, t) =t(hz, xi + b)kzkЗазором гиперплоскости называется величина:ρ(z,b) = min ρ(z,b) (xi , ti )i=1,...,n• Для корректно распознаваемого объекта его величина зазора соответствует расстоянию от этого объекта до гиперплоскости. Отрицательная величина зазора соответствует ошибочной классификацииобъекта.• Оптимальная разделяющая гиперплоскость — гиперплоскость с максимальной величиной зазораГлава 4. Метод опорных векторов и беспризнаковое распознавание образов42Рис. 4.6. Для линейно разделимой выборки существует бесконечно большое число гиперплоскостей, корректно разделяющихданные.
Жирной линией показана оптимальная разделяющая гиперплоскость.gg+Dgr(a)R(b)Рис. 4.7. Иллюстрация к оптимальной разделяющей гиперплоскости.Оптимальная разделяющая гиперплоскость. Примеры• Предположим, что все объекты тестовой выборки получены путем небольших смещений относительно обучающих объектов, т.е. для объекта обучения (x, t) тестовый объект может быть представленкак (x + ∆x, t), причем k∆xk ≤ r.• Гиперплоскость с величиной зазора ρ > r корректно классифицирует выборку (см. рис. 4.7, a).• Если объекты располагаются на достаточном расстоянии от гиперплоскости, то небольшое изменениепараметров (z, b) не меняет корректного разделения данных (см.
рис. 4.7, b).Оптимальная разделяющая гиперплоскость. Стат. теория Вапника-Червоненкиса• Пусть имеется некоторое объективное распределение p(x, t). Обучающая и тестовая совокупностиявляются н.о.р. выборками из этого распределения.• Пусть имеется семейство классификаторов {f (x, w) : Rd → T |w ∈ Ω} и функция потерь L : T × T →R+ .• Средним риском называется мат.ожидание функции потерь:ZR(w) = Ep(x,t) L(·) = L(t, f (x, w))p(x, t)dxdt• Эмпирическим риском называется следующая величина:nRemp (w) =1XL(ti , f (xi , w))n i=1Глава 4.
Метод опорных векторов и беспризнаковое распознавание образов43Теорема 2 (Vapnik, 1995). С вероятностью 0 < η ≤ 1 выполняется следующее неравенство:rh(ln(2n/h) + 1) − ln(η/4)R(w) ≤ Remp (w) +n(∗)Здесь h — положительная величина, называемая ВЧ-размерностью.Теорема 3 (Vapnik, 1995). Допустим, что вектора x ∈ Rd принадлежат сфере радиуса R. Тогда длясемейства разделяющих гиперплоскостей с величиной зазора ρ верно следующее:µ· 2 ¸ ¶Rh ≤ min,d + 1(∗∗)ρ2Для гиперплоскости, корректно разделяющей данные, эмпирический риск равен нулю. Корень в оценке на средний риск (*) является монотонно возрастающей функцией по h.
Поэтому минимизация оценкиэквивалентна минимизации ВЦ-размерности, что согласно формуле (**) эквивалентно максимизации зазора ρ.Постановка задачи оптимизации• Предположим, что в выборке присутствуют объекты двух классов, т.е. ∃i, j : ti = 1, tj = −1.• Для построения канонической гиперплоскости с максимальной величиной зазора, корректно разделяющей данные, необходимо решить следующую задачу оптимизации:1kzk2 → minz,b2ti (hz, xi i + b) ≥ 1, ∀i = 1, . . . , nФункция ЛагранжаВыпишем функцию ЛагранжаL(z, b, w) =nX1kzk2 −wi (ti (hz, xi i + b) − 1) → min maxwz,b2i=1Коэффициенты Лагранжа wi ≥ 0, ∀i = 1, . . .
, n.nX∂L(z, b, w) = 0 ⇒ z ∗ =wi ti xi∂zi=1nX∂L(z, b, w) = 0 ⇒wi ti = 0∂bi=1L(z ∗ , b∗ , w) =nnn XnX1 XXwi wj ti tj hxi , xj i −wi wj ti tj hxi , xj i+2 i=1 j=1i=1 j=1nXnXnn1 XX+wi =wi −wi wj ti tj hxi , xj i → maxw2 i=1 j=1i=1i=1Глава 4. Метод опорных векторов и беспризнаковое распознавание образов44Двойственная задача оптимизацииnXnwi −i=1nXn1 XXwi wj ti tj hxi , xj i → maxw2 i=1 j=1ti wi = 0i=1wi ≥ 0, ∀i = 1, . . . , nРешениеt̂(x) = sign (hz ∗ , xi + b∗ ) = signà nX!wi∗ ti hxi , xi+ b∗i=1Опорные вектораУсловие дополняющей нежесткости:wi∗ (ti (hz ∗ , xi i + b∗ ) − 1) = 0Из этого условия следует, что объекты обучающей выборки, для которых wi∗ > 0, лежат точно на границегиперплоскости. Они называются опорными векторами (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
