3 Метод опорных векторов (1162171), страница 2
Текст из файла (страница 2)
для объекта обучения (x, t)тестовый объект может быть представлен как(x + Δx, t), причем Δx ≤ r.• Гиперплоскость с величиной зазора ρ > r корректноклассифицирует выборку.Оптимальная разделяющая гиперплоскость.Пример 2.Лекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразовgg+DgrRЕсли объекты располагаются на достаточном расстоянииот гиперплоскости, то небольшое изменение параметров(z, b) не меняет корректного разделения данных.Оптимальная разделяющая гиперплоскость.Стат.
теория Вапника-Червоненкиса, [2]Лекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов• Пусть имеется некоторое объективное распределениеp(x, t). Обучающая и тестовая совокупности являютсян.о.р.
выборками из этого распределения.• Пусть имеется семейство классификаторов{f (x, w) : Rd → T |w ∈ Ω} и функция потерьL : T × T → R+ .• Средним риском называется мат.ожидание функциипотерь:R(w) = Ep(x,t) L(·) =L(t, f (x, w))p(x, t)dxdt• Эмпирическим риском называется следующаявеличина:1L(ti , f (xi , w))nnR(w) =i=1Оптимальная разделяющая гиперплоскость.Стат. теория Вапника-Червоненкиса, [2]Лекция 3.
МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовТеорема (Vapnik, 1995)С вероятностью 0 < η ≤ 1 выполняется следующее неравенство:h(ln(2m/h) + 1) − ln(η/4)R(w) ≤ R(w) +mЗдесь h — положительная величина, называемаяВЧ-размерностью.Теорема (Vapnik, 1995)Допустим, что вектора x ∈ Rd принадлежат сфере радиуса R.Тогда для семейства разделяющих гиперплоскостей с величинойзазора ρ верно следующее: 2 Rh ≤ min,d + 1ρ2Постановка задачи оптимизацииЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов• Предположим, что в выборке присутствуют объектыдвух классов, т.е.
∃i, j : ti = 1, tj = −1.• Для построения канонической гиперплоскости смаксимальной величиной зазора, корректноразделяющей данные, необходимо решить следующуюзадачу оптимизации:1z2 → minz,b2ti (z, xi + b) ≥ 1, ∀i = 1, . . . , nФункция ЛагранжаЛекция 3. МетодопорныхвекторовВетров,ЖуравлевФункция Лагранжа1wi (ti (z, xi + b) − 1) → min maxL(z, b, w) = z2 −wz,b2ni=1ЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовКоэффициенты Лагранжа wi ≥ 0, ∀i = 1, .
. . , n.∂L(z, b, w) = 0 ⇒ z∗ =wi ti xi∂zni=1∂L(z, b, w) = 0 ⇒∂b+wi ti = 0i=11 wi wj ti tj xi , xj −wi wj ti tj xi , xj +2nL(z∗ , b∗ , w) =nni=1ni=1 j=1nwi =i=1nni=1 j=1wi −nn1 2i=1 j=1wi wj ti tj xi , xj → maxwДвойственная задача оптимизацииЛекция 3. МетодопорныхвекторовВетров,ЖуравлевnЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразовi=1n1 wi wj ti tj xi , xj → maxw2nwi −ni=1 j=1ti wi = 0i=1wi ≥ 0, ∀i = 1, . .
. , nРешениеt̂(x) = sign (z∗ , x + b∗ ) = sign ni=1w∗i ti xi , x + b∗Опорные вектораЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Условие дополняющей нежесткости:w∗i (ti (z∗ , xi + b∗ ) − 1) = 0(4)Из (4) следует, что объекты обучающей выборки, длякоторых w∗i > 0, лежат точно на границе гиперплоскости.Они называются опорными векторами.МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовЗначение b∗ может быть получено из (4) для любогоопорного вектора. При этом с вычислительной точкизрения более устойчивой процедурой является усреднениепо всем таким объектам.Разреженность решенияЛекция 3.
МетодопорныхвекторовВетров,ЖуравлевРешающее правилоЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразовt̂(x) = signnwi ti xi , x + bi=1В решающее правило входят только те объекты обучения,для которых wi > 0 (опорные векторы).
Такое правилоназывается разреженным (sparse model). Разреженныемодели обладают высокой скоростью распознавания вбольших объемах данных, а также «проливают свет» наструктуру обучающей совокупности, выделяя наиболеерелевантные с точки зрения классификации объекты.План лекцииЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов1 Ликбез2 Метод опорных векторов для задачи классификации, [2]Метод потенциальных функцийСлучай линейно разделимых данныхСлучай линейно неразделимых данныхЯдровой переходЗаключительные замечания3 Метод опорных векторов для задачи регрессии, [2]4 Беспризнаковое распознавание образовОсновная методика беспризнакового распознавания образоПостроение функции, задающей скалярное произведениеОслабляющие коэффициентыЛекция 3.
МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовНа практике данные не являются, как правило, линейноразделимыми. Кроме того, даже линейно разделимыевыборки могут содержать помехи, ошибочные меткиклассов и проч.
Практический метод распознаваниядолжен учитывать подобные ситуации.Предположим, что ∀(z, b) ∃xi : ρ(z,b) (xi , ti ) < 0. Позволимнекоторым из ограничений не выполняться путем введенияослабляющих коэффициентов:ti (z, xi + b) ≥ 1 − ξiti (z, xi + b) ≥ 1 ∀i = 1, . . . , n −→ξi ≥ 0, ∀i = 1, . . . , nПри этом потребуем, чтобы количество нарушений(количество ошибок на обучении) было бы как можноменьшим:n1z2 + Cξi → minz,b,ξ2i=1Постановка задачи оптимизацииЛекция 3.
МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов1z2 + Cξi → minz,b2ni=1ti (z, xi + b) ≥ 1 − ξi ∀i = 1, . . . , nξi ≥ 0Здесь C ≥ 0 — некоторый действительный параметр,играющий роль параметра регуляризацииФункция ЛагранжаЛекция 3. МетодопорныхвекторовВетров,ЖуравлевФункция ЛагранжаL(z, b, ξ, w, v) =1z2 +Cξi −wi [ti (z, xi +b)−1+ξi]−2Ликбезnni=1i=1Метод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов−nvi ξi → min maxz,b,ξ w,vi=1Коэффициенты Лагранжа wi ≥ 0, vi ≥ 0.n∂L(z, b, ξ, w, v) = 0∂z⇒ z∗ =∂L(z, b, ξ, w, v) = 0∂b⇒∂L(z, b, ξ, w, v) = 0∂ξi⇒ wi + vi = Cwi ti xii=1nwi ti = 0i=1Двойственная задача оптимизацииЛекция 3.
МетодопорныхвекторовВетров,ЖуравлевnЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразовi=1n1 wi wj ti tj xi , xj → maxw2nwi −ni=1 j=1wi ti = 0i=10 ≤ wi ≤ CРешающее правило остается без изменений: n∗∗t̂(x) = sign (z∗ , x + b∗ ) = signwi ti xi , x + bi=1План лекцииЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов1 Ликбез2 Метод опорных векторов для задачи классификации, [2]Метод потенциальных функцийСлучай линейно разделимых данныхСлучай линейно неразделимых данныхЯдровой переходЗаключительные замечания3 Метод опорных векторов для задачи регрессии, [2]4 Беспризнаковое распознавание образовОсновная методика беспризнакового распознавания образоПостроение функции, задающей скалярное произведениеЯдровой переходЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразовпорождаются нелинейной разделяющей поверхностью.• Для обобщения метода на нелинейный случай заметим,что объекты обучающей выборки входят вдвойственную задачу оптимизации только в видепопарных скалярных произведений xi , xj .• Предположим, что исходное признаковое пространствобыло подвергнуто некоторому нелинейномупреобразованию:Φ : Rd → H110.80.90.60.80.40.70.20.6−→0−0.2−0.40.50.40.3−0.60.2−0.8−1−1X22Ветров,Журавлев• На практике часто встречается ситуация, когда данныеX2Лекция 3.
Методопорныхвекторов0.1−0.8−0.6−0.4−0.20X10.20.40.60.81000.10.20.30.40.5X120.60.70.80.91Ядровой переходЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов• Для того, чтобы построить гиперплоскость смаксимальным зазором в новом пространстве Hнеобходимо знать лишь Φ(xi ), Φ(xj )H .• Допустим, что существует некоторая «ядроваяфункция» K : Rd × Rd → R, такая чтоK(x, y) = Φ(x), Φ(y)H• Для построения гиперплоскости с максимальнымзазором в пространстве H нет необходимости задаватьпреобразование Φ в явном виде, достаточно лишьзнать K!• Задача оптимизации зависит только от попарныхскалярных произведений, а решающее правило можетбыть представлено какt̂(x) = signni=1wi ti Φ(xi ), Φ(x)H + b= signni=1wi ti K(xi , x) + bТребования к ядровой функцииЛекция 3.
МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОчевидно, что не для любой функции двух переменных Kнайдутся такие (H, Φ), для которых K будет определятьскалярное произведение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
