3 Метод опорных векторов (1162171), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Необходимыми и достаточнымитребованиями являются:• СимметричностьK(x, y) = K(y, x)• Неотрицательная определенность (условие Мерсера)∀g(x) :g2 (x)dx < ∞K(x, y)g(x)g(y)dxdy ≥ 0Для фиксированной функции K евклидово пространство Hи преобразование Φ определено не однозначно.Примеры ядровых функцийЛекция 3. Методопорныхвекторов• Линейная ядровая функцияВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовK(x, y) = x, y + θ, θ ≥ 0• Полиномиальная ядровая функцияK(x, y) = (x, y + θ)d , θ ≥ 0, d ∈ N• Гауссианаx − y2K(x, y) = exp −, σ>02σ 2• Сигмоидная ядровая функцияK(x, y) = tanh(x, y + r), r ∈ RЭто семейство не удовлетворяет условию Мерсера!План лекцииЛекция 3.

МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов1 Ликбез2 Метод опорных векторов для задачи классификации, [2]Метод потенциальных функцийСлучай линейно разделимых данныхСлучай линейно неразделимых данныхЯдровой переходЗаключительные замечания3 Метод опорных векторов для задачи регрессии, [2]4 Беспризнаковое распознавание образовОсновная методика беспризнакового распознавания образоПостроение функции, задающей скалярное произведениеПример использования метода опорныхвекторовЛекция 3. МетодопорныхвекторовЗависимость от ширины гауссианы2.5Ветров,Журавлев2.5221.51.5110.5ЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов2.521.510.50.5000−0.5−0.5−0.5−1−1−1−1.5−2−3−1.5−2−10123C = 1, σ = 0.124−2−3−1.5−2−10123−2−34C = 1, σ = 2−2C=1012Зависимость от штрафного коэффициентаC = 10−2−1234C = 1, σ = 10002C = 105Глобальность и единственность решенияЛекция 3.

МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов• Задача обучения SVM — задача квадратичногопрограммирования• Известно, что для любой задачи выпуклогопрограммирования (в частности, квадратичного)любой локальный максимум является и глобальным.Кроме того, решение будет единственным, еслицелевая функция строго вогнута (гессианотрицательно определен).• Для обучения SVM можно воспользоваться любымстандартным методом решения задачи квадратичногопрограммирования, однако лучше использоватьспециальные алгоритмы, учитывающие особенностизадачи квадратичного программирования в SVM(например, SMO или SVM light ).http://www.kernel-machines.orgЗадача обучения SVM как задача максимумарегуляризованного правдоподобияЛекция 3.

МетодопорныхвекторовВетров,Журавлев1z2 + Cξi → minz,b,ξ2(5)ti (z, xi + b) ≥ 1 − ξiξi ≥ 0(6)(7)ni=1ЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовЕсли ti y(xi ) ≥ 1, то ξi = 0.

Для остальных точекξi = 1 − ti y(xi ). Следовательно, функцию (5) можнопереписать в видеnESV (ti y(xi )) + λz2i=1Здесь λ = (2C)−1 , а ESV (·) — функция потерь, определеннаякакESV (s) = [1 − s]+SVM vs. Логистическая регрессияЛекция 3.

Методопорныхвекторов43.5Ветров,Журавлев32.52Ликбез1.51Метод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов0.50−2.5−2−1.5−1−0.500.511.522.5Логистическая регрессия:ni=1ELR (ti y(xi )) + λw2 → minwЗдесь ELR (s) = log(1 + exp(−s)).SVM:nESV (ti y(xi )) + λz2 → mini=1zДостоинства и недостатки SVMЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]МетодпотенциальныхфункцийСлучай линейноразделимыхданныхСлучай линейнонеразделимыхданныхЯдровой переходЗаключительныезамечанияМетод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов• Высокое качество распознавания за счет построениянелинейных разделяющих поверхностей,максимизирующих зазор• Глобальность и в ряде случаев единственностьполучаемого решения• Низкая скорость обучения и большие требования кпамяти для задач больших размерностей• Необходимость грамотного выбора штрафногокоэффициента C и параметров ядровой функцииЛинейная регрессия vs.

SVRЛекция 3. Методопорныхвекторов32.52Ветров,Журавлев1.51ЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразов0.50−3−2−10123Линейная регрессияn11(ti − y(xi ))2 + w2 → minw2 i=12Для того, чтобы добиться разреженного решения, заменимквадратичную функцию потерь на ε-нечувствительную:0,если |t − y(x)| < εEε (t − y(x)) =|t − y(x)| − ε, иначеТогда мы приходим к следующей оптимизационной задаче:n1CEε (y(xi ) − ti ) + z2 → minz2i=1Ослабляющие коэффициентыЛекция 3. МетодопорныхвекторовeВетров,ЖуравлевxxЛикбез*Метод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовCni=11(ξi + ξi∗ ) + z2 → min ∗2z,b,ξ,ξti ≤ y(xi ) + ε + ξiti ≥ y(xi ) − ε − ξi∗ξi , ξi∗ ≥ 0Двойственная задача (Упр.)Лекция 3.

МетодопорныхвекторовВетров,ЖуравлевЛикбез−nn1(wi − w∗i )(wj − w∗j )K(xi , xj ) − ε(wi + w∗i )+2i,j=1i=1Метод опорныхвекторов длязадачиклассификации,[2]+nti (wi − w∗i ) → max∗i=1Метод опорныхвекторов длязадачирегрессии, [2]nБеспризнаковоераспознаваниеобразов(wi − w∗i ) = 0i=10 ≤ wi , w∗i ≤ CФункция регрессииy(x) =ni=1(wi − w∗i )K(x, xi ) + bw,wУсловия дополняющей нежесткостиЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]Беспризнаковоераспознаваниеобразовwi=Cw*i=00< wi<Cw*i=0eewi=0w*i=0wi =00< w*i <Cwi=0w*i=CУсловия дополняющей нежесткостиwi (ε + ξi − ti + z, xi + b) = 0wi (ε + ξi∗ + ti − z, xi − b) = 0(C − w∗i )ξi∗ = 0(C − wi )ξi = 0,План лекцииЛекция 3.

МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение1 Ликбез2 Метод опорных векторов для задачи классификации, [2]Метод потенциальных функцийСлучай линейно разделимых данныхСлучай линейно неразделимых данныхЯдровой переходЗаключительные замечания3 Метод опорных векторов для задачи регрессии, [2]4 Беспризнаковое распознавание образовОсновная методика беспризнакового распознавания образоПостроение функции, задающей скалярное произведениеЗадачи беспризнакового распознаванияобразовЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведениеСуществует ряд задач распознавания образов, в которыхтрудно выбрать признаковое пространство, однако,относительно легко ввести меру сходства или несходствамежду парами объектов.

Примеры:• Задача распознавания личности по фотопортрету• Задача идентификации личности по подписи впроцессе ее формирования• Задача распознавания классов пространственнойструктуры белков по последовательностямсоставляющих их аминокислотБеспризнаковое распознавание образов:основная идеяЛекция 3.

МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение• Предположим, что объекты выборки ω1 , . . . , ωn ∈ Ω• Пространство Ω является гильбертовым, т.е. на немопределены операции суммы и произведения на число,удовлетворяющие аксиомам линейного пространства:∀α1 , α2 ∈ Ω ∃α = α1 + α2 ∈ Ω∀α1 ∈ Ω, c ∈ R ∃α = cα1 ∈ Ω1.3.5.7.α1 + α2 = α2 + α1∃φ ∈ Ω : α + φ = φ + α = αc(α1 + α2 ) = cα1 + cα2(cd)α = c(dα)2.4.6.8.α1 + (α2 + α3 ) = (α1 + α2 ) + α3∀α ∃(−α) : α + (−α) = φ(c + d)α = cα + dα1α = α• Существует функция K : Ω × Ω → R, определяющаяскалярное произведение в пространстве Ω:1. K(α1 , α2 ) = K(α2 , α1 )3.

K(α1 + α2 , α) = K(α1 , α) + K(α2 , α)2. K(α, α) ≥ 0, = 0 ⇔ α = φ4. K(cα1 , α2 ) = cK(α1 , α2 )Беспризнаковое распознавание образов:основная идеяЛекция 3. МетодопорныхвекторовРешающая функцияt̂(ω) = sign(K(ϑ, ω) + b)Ветров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение1K(ϑ, ϑ)2Задача оптимизации+Cni=1ξi → minti (K(ϑ, ωi ) + b) ≥ 1 − ξiϑ,b,ξξi ≥ 0nnДвойственная задачаоптимизации1i=1 wi − 2ni=1 ti wi = 0Решениеt̂(ω) = signi,j=1 ti tj wi wj K(ωi , ωj )→ max0 ≤ wi ≤ Cni=1 ti wi K(ωi , ω)+bwБеспризнаковое распознавание образов:основная идеяЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение• Для решения задачи нет необходимости явно задаватьлинейные операции в пространстве Ω, достаточно лишьпотребовать их существование в пространстве, гдефункция K задает скалярное произведение• Для применения данного подхода достаточно задатьфункцию K.

Эта функция может быть построенанепосредственно, либо с использованием меры сходстваПлан лекцииЛекция 3. МетодопорныхвекторовВетров,ЖуравлевЛикбезМетод опорныхвекторов длязадачиклассификации,[2]Метод опорныхвекторов длязадачирегрессии, [2]БеспризнаковоераспознаваниеобразовОсновнаяметодикабеспризнаковогораспознаванияобразовПостроениефункции,задающейскалярноепроизведение1 Ликбез2 Метод опорных векторов для задачи классификации, [2]Метод потенциальных функцийСлучай линейно разделимых данныхСлучай линейно неразделимых данныхЯдровой переходЗаключительные замечания3 Метод опорных векторов для задачи регрессии, [2]4 Беспризнаковое распознавание образовОсновная методика беспризнакового распознавания образоПостроение функции, задающей скалярное произведениеЯвное задание функции K. Пример.

Характеристики

Список файлов лекций