Главная » Просмотр файлов » 3 Метод опорных векторов

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

Файл №1162171 3 Метод опорных векторов (Д.П. Веторв, Ю.И. Журавлёв - Лекции) 3 страница3 Метод опорных векторов (1162171) страница 32019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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. Пример.

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

Тип файла
PDF-файл
Размер
393,38 Kb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6510
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее