_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (1185333), страница 8
Текст из файла (страница 8)
рис. 4.8). Значение b∗ может быть полученоРис. 4.8. Оптимальная разделяющая гиперплоскость. Объекты, определяющие положение гиперплоскости, называются опорными (обозначены черным цветом). Они располагаются ближе всего к гиперплоскости.из условия дополняющей нежесткости для любого опорного вектора. При этом с вычислительной точкизрения более устойчивой процедурой является усреднение по всем таким объектам.Разреженность решенияРешающее правилоÃt̂(x) = signnX!wi ti hxi , xi + bi=1В решающее правило входят только те объекты обучения, для которых wi > 0 (опорные векторы). Такоеправило называется разреженным (sparse model). Разреженные модели обладают высокой скоростьюраспознавания в больших объемах данных, а также «проливают свет» на структуру обучающей совокупности, выделяя наиболее релевантные с точки зрения классификации объекты.Глава 4.
Метод опорных векторов и беспризнаковое распознавание образов4.2.345Случай линейно неразделимых данныхОслабляющие коэффициентыНа практике данные не являются, как правило, линейно разделимыми. Кроме того, даже линейноразделимые выборки могут содержать помехи, ошибочные метки классов и проч. Практический методраспознавания должен учитывать подобные ситуации.Предположим, что ∀(z, b) ∃xi : ρ(z,b) (xi , ti ) < 0. Позволим некоторым из ограничений не выполнятьсяпутем введения ослабляющих коэффициентов:½ti (hz, xi i + b) ≥ 1 − ξiti (hz, xi i + b) ≥ 1 ∀i = 1, . .
. , n −→ξi ≥ 0, ∀i = 1, . . . , nПри этом потребуем, чтобы количество нарушений (количество ошибок на обучении) было бы какможно меньшим:nX1kzk2 + Cξi → minz,b,ξ2i=1Постановка задачи оптимизацииnX1kzk2 + Cξi → minz,b2i=1ti (hz, xi i + b) ≥ 1 − ξi ∀i = 1, . . . , nξi ≥ 0Здесь C ≥ 0 — некоторый действительный параметр, играющий роль параметра регуляризацииФункция ЛагранжаВыпишем функцию ЛагранжаL(z, b, ξ, w, v) =nnnXXX1kzk2 + Cξi −wi [ti (hz, xi i + b) − 1 + ξi ] −vi ξi → min maxz,b,ξ w,v2i=1i=1i=1Коэффициенты Лагранжа wi ≥ 0, vi ≥ 0.nX∂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=1nXwi ti = 0i=1Глава 4. Метод опорных векторов и беспризнаковое распознавание образов46Двойственная задача оптимизацииnXnwi −i=1nXn1 XXwi wj ti tj hxi , xj i → maxw2 i=1 j=1wi ti = 0i=10 ≤ wi ≤ CРешающее правило остается без изменений:t̂(x) = sign (hz ∗ , xi + b∗ ) = signà nX!wi∗ ti hxi , xi∗+bi=14.2.4Ядровой переходЯдровой переход• На практике часто встречается ситуация, когда данные порождаются нелинейной разделяющей поверхностью.• Для обобщения метода на нелинейный случай заметим, что объекты обучающей выборки входят вдвойственную задачу оптимизации только в виде попарных скалярных произведений hxi , xj i.110.80.90.60.80.40.70.20.6X22X2• Предположим, что исходное признаковое пространство было подвергнуто некоторому нелинейномупреобразованию (см.
рис. 4.9):Φ : Rd → H0−0.20.4−0.40.3−→−0.6−0.8−1−10.50.20.1−0.8−0.6−0.4−0.20X0.20.40.60.81000.10.20.30.40.51X21(a)(b)0.60.70.80.91Рис. 4.9. Пример преобразования признакового пространства. На рис. (a) данные разделяются нелинейной поверхностью —эллипсом. Переход из пространства (x1 , x2 ) к новому пространству (x21 , x22 ) делает данные линейно разделимыми.Глава 4. Метод опорных векторов и беспризнаковое распознавание образов47Ядровой переход• Для того, чтобы построить гиперплоскость с максимальным зазором в новом пространстве H необходимо знать лишь hΦ(xi ), Φ(xj )iH .• Допустим, что существует некоторая «ядровая функция» K : Rd × Rd → R, такая чтоK(x, y) = hΦ(x), Φ(y)iH• Для построения гиперплоскости с максимальным зазором в пространстве H нет необходимости задавать преобразование Φ в явном виде, достаточно лишь знать K!• Задача оптимизации зависит только от попарных скалярных произведений, а решающее правиломожет быть представлено какt̂(x) = signà nX!wi ti hΦ(xi ), Φ(x)iH + bÃ= signi=1nX!wi ti K(xi , x) + bi=1Требования к ядровой функцииОчевидно, что не для любой функции двух переменных K найдутся такие (H, Φ), для которых K будетопределять скалярное произведение.
Необходимыми и достаточными требованиями являются:• СимметричностьK(x, y) = K(y, x)• Неотрицательная определенность (условие Мерсера)Z∀g(x) :g 2 (x)dx < ∞ZK(x, y)g(x)g(y)dxdy ≥ 0Для фиксированной функции K евклидово пространство H и преобразование Φ определено не однозначно.Примеры ядровых функций• Линейная ядровая функцияK(x, y) = hx, yi + θ, θ ≥ 0• Полиномиальная ядровая функцияK(x, y) = (hx, yi + θ)d , θ ≥ 0, d ∈ N• Гауссиан൶kx − yk2K(x, y) = exp −, σ>02σ 2• Сигмоидная ядровая функцияK(x, y) = tanh(hx, yi + r), r ∈ RЭто семейство не удовлетворяет условию Мерсера!Глава 4. Метод опорных векторов и беспризнаковое распознавание образов4.2.548Заключительные замечанияПример использования метода опорных векторовЗависимость от ширины гауссианы (см.
рис. 4.10)2.52.5222.521.51.51.51110.50.50.5000−0.5−0.5−0.5−1−1−1−1.5−1.5−1.5−2−3−2−101234−2−3−2−10(a)1234−2−3−2−10(b)1234(c)Рис. 4.10. Примеры решения двухклассовой задачи классификации с помощью метода опорных векторов. На рисунке (a)показана разделяющая поверхность для случая использования в качестве ядровой функции гауссианы с параметрами C =1, σ 2 = 0.1, (b) соответствует C = 1, σ 2 = 2, (c) — C = 1, σ 2 = 1000Зависимость от штрафного коэффициента (см. рис.
4.11)(a)(b)(c)Рис. 4.11. Примеры решения двухклассовой задачи классификации с помощью метода опорных векторов. На рисунке (a)показана разделяющая поверхность для случая C = 10−2 , (b) соответствует C = 1, (c) — C = 105Глобальность и единственность решения• Задача обучения SVM — задача квадратичного программирования• Известно, что для любой задачи выпуклого программирования (в частности, квадратичного) любой локальный максимум является и глобальным. Кроме того, решение будет единственным, еслицелевая функция строго вогнута (гессиан отрицательно определен).• Для обучения SVM можно воспользоваться любым стандартным методом решения задачи квадратичного программирования, однако лучше использовать специальные алгоритмы, учитывающиеособенности задачи квадратичного программирования в SVM (например, SM O или SV M light ).• Подробнее см.
http://www.kernel-machines.orgЗадача обучения SVM как задача максимума регуляризованного правдоподобияГлава 4. Метод опорных векторов и беспризнаковое распознавание образов49nX1kzk2 + Cξi → minz,b,ξ2i=1ti (hz, xi i + b) ≥ 1 − ξiξi ≥ 0Если ti y(xi ) ≥ 1, то ξi = 0. Для остальных точек ξi = 1 − ti y(xi ). Следовательно, оптимизируемуюфункцию можно переписать в видеnXESV (ti y(xi )) + λkzk2i=1−1Здесь λ = (2C), а ESV (·) — функция потерь, определенная какESV (s) = [1 − s]+SVM vs.
Логистическая регрессия43.532.521.510.50−2.5−2−1.5−1−0.500.511.522.5Рис. 4.12. Различные функции ошибок. Черная кривая соответствует индикаторной функции ошибки, серая кривая — функция ошибки в методе опорных векторов, пунктирная линия — функция ошибок в логистической регрессииЗадача оптимизации в логистической регрессии:nXi=1Здесь ELR (s) = log(1 + exp(−s)).Задача оптимизации в SVM:nXi=1ELR (ti y(xi )) + λkwk2 → minwESV (ti y(xi )) + λkzk2 → minzДостоинства и недостатки SVM+ Высокое качество распознавания за счет построения нелинейных разделяющих поверхностей, максимизирующих зазор+ Глобальность и в ряде случаев единственность получаемого решения— Низкая скорость обучения и большие требования к памяти для задач больших размерностей— Необходимость грамотного выбора штрафного коэффициента C и параметров ядровой функцииГлава 4. Метод опорных векторов и беспризнаковое распознавание образов4.350Метод опорных векторов для задачи регрессииЛинейная регрессия vs.
SVR32.521.510.50−3−2−10123Рис. 4.13. Различные функции ошибок. Черная кривая — квадратичная функция ошибок линейной регрессии, пунктирнаялиния — функция ошибок в методе опорных векторов для регрессииЗадача оптимизации в линейной регрессииn1X1(ti − y(xi ))2 + kwk2 → minw2 i=12Для того, чтобы добиться разреженного решения, заменим квадратичную функцию потерь на εнечувствительную:½0,если |t − y(x)| < εEε (t − y(x)) =|t − y(x)| − ε, иначеТогда мы приходим к следующей оптимизационной задаче:CnX1Eε (y(xi ) − ti ) + kzk2 → minz2i=1Ослабляющие коэффициентыexx*Рис.
4.14. Иллюстрация к введению ослабляющих коэффициентов. Объекты, лежащие выше ε-трубки, имеют положительноезначение ξi , а объекты, лежащие ниже ε-трубки, имеют положительное значение ξi∗Глава 4. Метод опорных векторов и беспризнаковое распознавание образовC51nX1(ξi + ξi∗ ) + kzk2 → min ∗2z,b,ξ,ξi=1ti ≤ y(xi ) + ε + ξiti ≥ y(xi ) − ε − ξi∗ξi , ξi∗ ≥ 0X Упр.Двойственная задача−nnnXX1 X(wi − wi∗ )(wj − wj∗ )K(xi , xj ) − ε(wi + wi∗ ) +ti (wi − wi∗ ) → max∗w,w2 i,j=1i=1i=1nX(wi − wi∗ ) = 0i=10 ≤ wi , wi∗ ≤ CФункция регрессииy(x) =nX(wi − wi∗ )K(x, xi ) + bi=1Условия дополняющей нежесткостиwi=Cw*i=00< wi<Cw*i=0eewi=0w*i=0wi =00< w*i <Cwi=0w*i=CРис. 4.15.
Иллюстрация к опорным объектам в задаче регрессииЗапишем условия дополняющей нежесткостиwi (ε + ξi − ti + hz, xi i + b) = 0wi (ε + ξi∗ + ti − hz, xi i − b) = 0(C − wi )ξi = 0,(C − wi∗ )ξi∗ = 0Из них следует, что опорные объекты лежат за пределами или на границе ε-трубки, определяемой функцией hz, xi + bГлава 4. Метод опорных векторов и беспризнаковое распознавание образов4.452Беспризнаковое распознавание образов4.4.1Основная методика беспризнакового распознавания образовЗадачи беспризнакового распознавания образовСуществует ряд задач распознавания образов, в которых трудно выбрать признаковое пространство,однако, относительно легко ввести меру сходства или несходства между парами объектов.
Примеры:• Задача распознавания личности по фотопортрету• Задача идентификации личности по подписи в процессе ее формирования• Задача распознавания классов пространственной структуры белков по последовательностям составляющих их аминокислотБеспризнаковое распознавание образов: основная идея• Предположим, что объекты выборки ω1 , . . . , ωn ∈ Ω• Пространство Ω является гильбертовым, т.е. на нем определены операции суммы и произведения начисло∀α1 , α2 ∈ Ω ∃α = α1 + α2 ∈ Ω∀α1 ∈ Ω, c ∈ R ∃α = cα1 ∈ Ω,удовлетворяющие аксиомам линейного пространства:1.2.3.4.5.6.7.8.α1 + α2 = α2 + α1α1 + (α2 + α3 ) = (α1 + α2 ) + α3∃φ ∈ Ω : α + φ = φ + α = α∀α ∃(−α) : α + (−α) = φc(α1 + α2 ) = cα1 + cα2(c + d)α = cα + dα(cd)α = c(dα)1α = α• Существует функция K : Ω × Ω → R, определяющая скалярное произведение в пространстве Ω:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
