_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007).pdf), страница 9

K(α1 , α2 ) = K(α2 , α1 )2. K(α, α) ≥ 0, = 0 ⇔ α = φ3. K(α1 + α2 , α) = K(α1 , α) + K(α2 , α)4. K(cα1 , α2 ) = cK(α1 , α2 )Глава 4. Метод опорных векторов и беспризнаковое распознавание образовРешающая функцияt̂(ω) = sign(K(ϑ, ω) + b)Задача оптимизацииPn+ C i=1 ξi → minϑ,b,ξti (K(ϑ, ωi ) + b) ≥ 1 − ξiξi ≥ 0Двойственная задачаоптимизацииPnPn1i=1 wi − 2i,j=1 ti tj wi wj K(ωi , ωj ) → maxwPni=1 ti wi = 00 ≤ wi ≤ CРешениеPnt̂(ω) = sign ( i=1 ti wi K(ωi , ω) + b)5312 K(ϑ, ϑ)• Для решения задачи нет необходимости явно задавать линейные операции в пространстве Ω, достаточно лишь потребовать их существование в пространстве, где функция K задает скалярноепроизведение• Для применения данного подхода достаточно задать функцию K. Эта функция может быть построена непосредственно, либо с использованием меры сходства4.4.2Построение функции, задающей скалярное произведениеЯвное задание функции K. Пример.

[Середин, 2001]Рис. 4.16. Примеры фотографий лиц в задаче идентификации личности по фотопортрету. На фотографиях также представлено эластичное преобразование растра при сравнении двух фотопортретов, получающееся в результате решения задачиминимизации искажений при условии минимального отклонения точек растра от исходного положения• Рассмотрим задачу распознавания личности по фотопортрету.• Пусть два изображения заданы векторами яркости в точках растра: y 0 = y(ω 0 ) = (yt0 , t ∈ T ) иy 00 = y(ω 00 ) = (yt00 , t ∈ T ), T = {t = (t1 , t2 ), t1 = 1, n1 , t2 = 1, n2 }• Потенциальная функция может быть задана как:P– K(y 0 , y 00 ) = hy 0 , y 00 i = t∈T yt0 yt00– K(y 0 , y 00 ) = [hy 0 , y 00 i + 1]α¡¢– K(y 0 , y 00 ) = exp −αky 0 − y 00 k2 = exp (−α[hy 0 , y 0 i + hy 00 , y 00 i − 2hy 0 , y 00 i])Глава 4.

Метод опорных векторов и беспризнаковое распознавание образов54• Пусть задана эластичная деформация растра t → t + xt (см. рис. 4.16). Эластичная потенциальнаяфункция:X0K(y 0 , y 00 ) =yt0 yt+xtt∈TПостроение функции K с использованием метрики• Пусть задано метрическое пространство A с метрикой ρ : A × A → R:1. ρ(α1 , α2 ) ≥ 0, = 0 ⇔ α1 = α22. ρ(α1 , α2 ) = ρ(α2 , α1 )3. ρ(α1 , α3 ) ≤ ρ(α1 , α2 ) + ρ(α2 , α3 )• Общностью двух элементов из A относительно некоторого центра φ ∈ A назовем следующую величину:¤1£ 2ρ (α1 , φ) + ρ2 (α2 , φ) − ρ2 (α1 , α2 )µφ (α1 , α2 ) =2• Свойства общности1. µφ (α1 , α2 ) = µφ (α2 , α1 )2. µφ (α, α) ≥ 0 = 0 ⇔ α = φ3. ∀α ∈ A µφ (α, φ) = 04. µφ (α, α) = ρ2 (α, φ)5.

ρ(α1 , α2 ) = (µφ (α1 , α1 ) + µφ (α2 , α2 ) − 2µφ (α1 , α2 ))1/26. µφ (α1 , α2 ) ≤ 12 [µφ (α1 , α1 ) + µφ (α2 , α2 )]pp7. |µφ (α1 , α2 )| ≤ µφ (α1 , α1 ) µφ (α2 , α2 )8. µφ̃ (α1 , α2 ) = µφ (α1 , α2 ) − µφ (α1 , φ̃) − µφ (α2 , φ̃) + µφ (φ, φ̃)• По своим свойствам общность очень похожа на скалярное произведение!Матрица общностей• Пусть {α1 , .

. . , αq } ⊂ A — конечная совокупность элементов метрического пространства с центромφ ∈ A. Cоставим матрицу общностей этих элементов:Mφ = (µφ (αi , αj ), i, j = 1, . . . , q)• Матрица общностей является симметричной, диагональные элементы неотрицательны.• В отличие от матрицы скалярных произведений, которая всегда неотрицательно определена, матрица общностей может иметь собственные значения любого знакаТеорема 4. Если Mφ является неотрицательно определенной для любой конечной совокупности элементов, то матрица Mφ̃ относительно другого центра φ̃ также является неотрицательно определенной.Глава 4. Метод опорных векторов и беспризнаковое распознавание образов55c>1aa20<c<1ac<0a1aРис. 4.17.

Иллюстрация к понятию соосных элементовСоосность элементовЭлемент α ∈ A называется соосным элементом для упорядоченной пары [α1 , α2 ] с коэффициентомc ∈ R и обозначается α = coax([α1 , α2 ]; , c), еслиρ(α1 , α) = |c|ρ(α1 , α2 ),ρ(α2 , α) = |c − 1|ρ(α1 , α2 )Очевидно, что α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Введение линейных операцийМетрическое пространство A называется евклидовым метрическим пространством, если∀[α1 , α2 ], α1 , α2 ∈ A и ∀c ∈ R ∃α ∈ A : α = coax([α1 , α2 ]; c) и матрица общности всякой конечной совокупности элементов из A является неотрицательно определенной.Введем операции суммы и умножения на число:µ¶1cα , coax([φ, α]; c) α1 + α2 = 2 coax [α1 , α2 ];2ca1a1+a2a1a=coax([a1,a2];1/2)a2fРис.

4.18. Введение линейных операций в евклидовом метрическом пространствеГлава 4. Метод опорных векторов и беспризнаковое распознавание образов56Свойства введенных операцийТеорема 5. В евклидовом метрическом пространстве введенные операции сложения и умножения начисло, а также скалярное произведение понимаемое как общность элементов hα1 , α2 i = µφ (α1 , α2 ) удовлетворяют всем требованиям гильбертова пространства:•••••••••α1 + α2 = α2 + α1 , (α1 + α2 ) + α3 = α1 + (α2 + α3 )α + φ = α, cφ = φ∀α∃(−α) : (−α) + α = φc1 (c2 α) = (c1 c2 )α1α = α(c1 + c2 )α = c1 α + c2 α, c(α1 + α2 ) = cα1 + cα2hα1 , α2 i = hα2 , α1 i, hc1 α1 + c2 α2 , α3 i = c1 hα1 , α3 i + c2 hα2 , α3 ihα, αi ≥ 0, =p0⇔α=φkα1 − α2 k = hα1 − α2 , α1 − α2 i = ρ(α1 , α2 )Глава 5Задачи выбора моделиВ главе рассматриваются вопросы выбора модели при обучении ЭВМ.

Изложена суть проблемы и ееметодологический характер. Приведены многочисленые примеры задач выбора модели, с которыми приходится сталкиваться при решении конкретных прикладных проблем. Рассмотрено несколько общих (независящих от эвристик) методов выбора модели, проанализированы их преимущества и недостатки.57Глава 5.

Задачи выбора модели5.158Ликбез: Оптимальное кодированиеОптимальное кодирование• Рассматривается задача кодирования алфавита A словами из алфавита B, как правило содержащегоменьше символов• Пусть каждый символ a ∈ A встречается в текстах с вероятностью p(a). Обозначим l(a) длину егокодирования в B• Задача построить схему кодирования, обеспечивающую минимальную среднюю длину кодированныхсообщений, т.е.XEA l(a) =p(a)l(a) → mina∈AТеорема Шеннона• Теорема Шеннона. Если кодируемые элементы a могут встречаться с разными вероятностями p(a),то существует оптимальное кодирование данного множества элементов и длина описания элементаa равна l(a) = − logB p(a)• Основание логарифма B — это мощность кодирующего алфавита.

Если алфавит B состоит из двухсимволов (например, ноль и единица), то логарифм двоичный, а длина описания измеряется в битахЕсли логарифм натуральный, то длина описания измеряется в натах, хотя довольно трудно представить себе алфавитиз 2.7182... символов :)• Теорема Шеннона согласуется со здравым смыслом: чем чаще встречается символ, тем короче должна быть длина его описания, и наоборотЛень Морзе дорого обошлась (и обходится) человечеству из-за того, что пропусканая способность каналов связиоказалась ниже оптимальной5.25.2.1Постановка задачи выбора моделиОбщий характер проблемы выбора моделиОпределение модели• Пусть A(w) — решающее правило, полученное в результате настройки весов w ∈ Ω в ходе обучения• Модель — это совокупность всех решающих правил, которые получаются путем присваивания весамвсех возможных допустимых значений A(Ω)• Модель определяется множеством допустимых весов Ω, априорными распределениями весов на этоммножестве P (w) и структурой решающего правила A(.)Задача выбора модели• Выбрать модель — значит определить множество Ω, указать на нем априорные вероятности весовP (w) и определить структуру (схему, по которой настраиваемые веса будут образовывать композицию с входными данными) решающего правила A• Поскольку рассмотреть всевозможные множества, распределения и структуры невозможно, их обычно ограничивают некоторым параметрическим семейством, зависящим от структурных параметров• Под задачей выбора модели будем понимать проблему автоматической настройки всех структурныхпараметров для данного алгоритма машинного обученияГлава 5.

Задачи выбора модели59Смысл проблемы выбора модели• Нетрудно придумать алгоритм, блестяще работающий на обучающей выборке (например, запомнитьдля нее правильные ответы). Вот только на новых объектах такой алгоритм, скорее всего, будетработать плохо• Возникает идея ограничить множество допустимых решающих правил, чтобы в процессе обучениямы не могли бы получить «плохие» решения• Ценой неизбежно становится ухудшение работы алгоритма на обучающей выборке• Процесс выбора модели в машинном обучении — это поиск компромисса между точностью на обучении и его «надежностью» на произвольных объектах генеральной совокупностиФилософский смысл проблемы выбора модели• Данная проблема проявляется в различных областях математики в частности, и человеческой деятельности вообще• Не будет преувеличением сказать, что она носит общенаучный и даже философский характер• Это проблема выбора средств: гайку можно выточить на старом добром станке (в котором из механизмов только электродвигатель времен Александра II), а можно использовать новейшее оборудование с ЧПУ (три микропроцессора, система калибровки, связанная со спутником и 20 кг техническойдокументации)• Гайка, сделанная на новейшем станке, будет иметь более высокое качество.