3 Метод опорных векторов (1162171), страница 4
Текст из файла (страница 4)
[3]Лекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение• Рассмотрим задачу распознавания личности пофотопортрету.• Пусть два изображения заданы векторами яркости вточках растра: y = y(ω ) = (yt , t ∈ T) иy = y(ω ) = (yt , t ∈ T), T = {t = (t1 , t2 ), t1 = 1, n1 , t2 = 1, n2 }• Потенциальная функция может быть задана как: • K(y , y ) = y , y =t∈T yt yt α• K(y , y ) = [y , y + 1]• K(y , y ) = exp −αy − y 2 = exp (−α[y , y + y , y − 2y , y ])• Пусть задана эластичная деформация растра t → t + xt .Эластичная потенциальная функция: yt yt+xtK(y , y ) =t∈TПостроение функции K с использованиемметрикиЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение• Пусть задано метрическое пространство A с метрикойρ : A × A → R:1.
ρ(α1 , α2 ) ≥ 0, = 0 ⇔ α1 = α23. ρ(α1 , α3 ) ≤ ρ(α1 , α2 ) + ρ(α2 , α3 )2. ρ(α1 , α2 ) = ρ(α2 , α1 )• Общностью двух элементов из A относительно некоторогоцентра φ ∈ A назовем следующую величину:1 2ρ (α1 , φ) + ρ2 (α2 , φ) − ρ2 (α1 , α2 )μφ (α1 , α2 ) =2• Свойства общности1.2.3.4.5.6.7.8.μφ (α1 , α2 ) = μφ (α2 , α1 )μφ (α, α) ≥ 0 = 0 ⇔ α = φ∀α ∈ A μφ (α, φ) = 0μφ (α, α) = ρ2 (α, φ)ρ(α1 , α2 ) = (μφ (α1 , α1 ) + μφ (α2 , α2 ) − 2μφ (α1 , α2 ))1/2μφ (α1 , α2 ) ≤ 12 [μφ (α1 , α1 ) + μφ (α2 , α2 )]|μφ (α1 , α2 )| ≤ μφ (α1 , α1 ) μφ (α2 , α2 )μφ̃ (α1 , α2 ) = μφ (α1 , α2 ) − μφ (α1 , φ̃) − μφ (α2 , φ̃) + μφ (φ, φ̃)• По своим свойствам общность очень похожа на скалярноепроизведение!Матрица общностейЛекция 3. МетодопорныхвекторовВетров,Журавлев• Пусть {α1 , . .
. , αq } ⊂ A — конечная совокупностьэлементов метрического пространства с центром φ ∈ A.Cоставим матрицу общностей этих элементов:Mφ = (μφ (αi , αj ), i, j = 1, . . . , q)ЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение• Матрица общностей является симметричной,диагональные элементы неотрицательны.• В отличие от матрицы скалярных произведений,которая всегда неотрицательно определена, матрицаобщностей может иметь собственные значения любогознакаТеоремаЕсли Mφ является неотрицательно определенной для любойконечной совокупности элементов, то матрица Mφ̃относительно другого центра φ̃ также являетсянеотрицательно определенной.Соосность элементовЛекция 3.
МетодопорныхвекторовВетров,ЖуравлевЛикбезЭлемент α ∈ A называется соосным элементом дляупорядоченной пары [α1 , α2 ] с коэффициентом c ∈ R иобозначается α = coax([α1 , α2 ]; , c), еслиρ(α1 , α) = |c|ρ(α1 , α2 ),Метод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведениеρ(α2 , α) = |c − 1|ρ(α1 , α2 )c>1a0<c<1c<0aa1a2aОчевидно, что α1 = coax([α1 , α2 ]; 0), α2 = coax([α1 , α2 ]; 1).Если α = coax([α1 , α2 ]; c), то α = coax([α2 , α1 ]; 1 − c).
Дляэлементов [α1 , α2 ] и α = coax([α1 , α2 ]; c) неравентсвотреугольника переходит в равенство:ρ(α1 , α2 ) + ρ(α2 , α) = ρ(α1 , α), если c > 1ρ(α1 , α) + ρ(α, α2 ) = ρ(α1 , α2 ), если 0 < c ≤ 1ρ(α, α1 ) + ρ(α1 , α2 ) = ρ(α, α2 ), если c ≤ 0Введение линейных операцийЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]Метрическое пространство A называется евклидовымметрическим пространством, если ∀[α1 , α2 ], α1 , α2 ∈ A и∀c ∈ R ∃α ∈ A : α = coax([α1 , α2 ]; c) и матрица общностивсякой конечной совокупности элементов из A являетсянеотрицательно определенной.Введем операции суммы и умножения на число:1cα coax([φ, α]; c) α1 + α2 = 2 coax [α1 , α2 ];2БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведениеca1a1+a2a1a=coax([a1,a2];1/2)fa2Свойства введенных операцийЛекция 3.
МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведениеТеоремаВ евклидовом метрическом пространстве введенныеоперации сложения и умножения на число, а такжескалярное произведение понимаемое как общностьэлементов α1 , α2 = μφ (α1 , α2 ) удовлетворяют всемтребованиям гильбертова пространства:•••••••α1 + α2 = α2 + α1 , (α1 + α2 ) + α3 = α1 + (α2 + α3 )••α, α ≥ 0, = 0 ⇔ α = φα1 − α2 = α1 − α2 , α1 − α2 = ρ(α1 , α2 )α + φ = α, cφ = φ∀α∃(−α) : (−α) + α = φc1 (c2 α) = (c1 c2 )α1α = α(c1 + c2 )α = c1 α + c2 α, c(α1 + α2 ) = cα1 + cα2α1 , α2 = α2 , α1 , α1 + α2 , α3 = α1 , α3 + α2 , α3 ,cα1 , α2 = cα1 , α2 Полезная литератураЛекция 3. МетодопорныхвекторовВетров,ЖуравлевПриложениеПолезнаялитератураМ.
А. Айзерман, Э. М. Браверман, Л. И. РозоноэрМетод потенциальных функций в теории обучениямашинМ.: Наука, 1970V. N. VapnikThe Nature of Statistical Learning TheorySpringer, 1995О. С. СерединМетоды и алгоритмы беспризнакового распознаванияобразовДисс. к.ф.-м.н., Тульский гос. университет, 2001.