машинное обучение. А. М. Миронов Московский Государственный Университет Механикоматематический факультет Кафедра математической теории интеллектуальных систем Введение Книга
 Скачать 1.05 Mb.
|
|
∀ 𝑗 = 1, . . . , 𝑛 + 1 𝜕𝑄 𝜕 ˜ 𝑤 𝑗 = 0. (2.91) Учитывая определение функции 𝑄, перепишем (2.91) в виде ∀ 𝑗 = 1, . . . , 𝑛 + 1 𝜕𝑄 𝜕 ˜ 𝑤 𝑗 = 𝑙 ∑︁ 𝑖=1 2(⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩ − 𝑦 𝑖 )(˜ 𝑥 𝑖 ) 𝑗 = 0 (2.92) Поскольку ∀ 𝑖 = 1, . . . , 𝑙, ∀ 𝑗 = 1, . . . , 𝑛 + 1 (˜ 𝑥 𝑖 ) 𝑗 есть элемент 𝑋 𝑖𝑗 матрицы 𝑋, то соотношения (2.92) можно переписать в виде ∀ 𝑗 = 1, . . . , 𝑛 + 1 𝑙 ∑︁ 𝑖=1 ⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩𝑋 𝑖𝑗 = 𝑙 ∑︁ 𝑖=1 𝑦 𝑖 𝑋 𝑖𝑗 (2.93) Обозначим записью 𝑋 ⊤ матрицу, транспонированную к 𝑋, т.е. ∀ 𝑗 = 1, . . . , 𝑛 + 1, ∀ 𝑖 = 1, . . . , 𝑙 𝑋 ⊤ 𝑗𝑖 = 𝑋 𝑖𝑗 , и перепишем (2.93) в виде ∀ 𝑗 = 1, . . . , 𝑛 + 1 𝑙 ∑︁ 𝑖=1 𝑋 ⊤ 𝑗𝑖 ⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩ = 𝑙 ∑︁ 𝑖=1 𝑋 ⊤ 𝑗𝑖 𝑦 𝑖 (2.94) ∀ 𝑖 = 1, . . . , 𝑙 ⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩ есть 𝑖–й элемент столбца 𝑋 ˜ 𝑤, обозначим его записью (𝑋 ˜ 𝑤) 𝑖 . Нетрудно видеть, что ∀ 𝑗 = 1, . . . , 𝑛 + 1 ∙ левая сумма в (2.94), т.е. 𝑙 ∑︀ 𝑖=1 𝑋 ⊤ 𝑗𝑖 (𝑋 ˜ 𝑤) 𝑖 , есть 𝑗–й элемент столбца 𝑋 ⊤ (𝑋 ˜ 𝑤), и ∙ правая сумма в (2.94) есть 𝑗–й элемент столбца 𝑋 ⊤ 𝑌 . 61 Таким образом, столбцы 𝑋 ⊤ 𝑋 ˜ 𝑤 и 𝑋 ⊤ 𝑌 совпадают, т.е. искомый век- тор ˜ 𝑤 является решением уравнения 𝑋 ⊤ 𝑋 ˜ 𝑤 = 𝑋 ⊤ 𝑌. (2.95) Нетрудно доказать, что данное уравнение всегда имеет решение. Если матрица 𝑋 ⊤ 𝑋 невырождена, то уравнение (2.95) имеет един- ственное решение ˜ 𝑤 = (𝑋 ⊤ 𝑋) −1 𝑋 ⊤ 𝑌, а если она вырождена, то решение уравнения (2.95) м.б. неединственным. Так может произойти, например, если число 𝑙 пар в обучающей выборке 𝑆 меньше 𝑛. В этом случае вместо задачи (2.90) разумнее решать задачу 𝑄( ˜ 𝑤) = ||𝑋 ˜ 𝑤 − 𝑌 || 2 + 𝑐|| ˜ 𝑤|| 2 → min, (2.96) где 𝑐 – параметр, выражающий штраф за большую || ˜ 𝑤||. Данная задача называется задачей гребневой (ridge) регрессии. Поскольку минимизируемая функция 𝑄 в (2.96) является выпуклой и дифференцируемой, то искомое решение должно обращать в 0 все част- ные производные функции 𝑄: ∀ 𝑗 = 1, . . . , 𝑛 + 1 𝜕𝑄 𝜕 ˜ 𝑤 𝑗 = 𝑙 ∑︁ 𝑖=1 2(⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩ − 𝑦 𝑖 )(˜ 𝑥 𝑖 ) 𝑗 + 2𝑐 ˜ 𝑤 𝑗 = 0. Это соотношение можно переписать в виде ∀ 𝑗 = 1, . . . , 𝑛 + 1 𝑙 ∑︁ 𝑖=1 (⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩ − 𝑦 𝑖 )𝑋 𝑖𝑗 + 𝑐 ˜ 𝑤 𝑗 = 0. (2.97) Нетрудно доказать, что ∀ 𝑗 = 1, . . . , 𝑛 + 1 ∙ первое слагаемое в (2.97), т.е. 𝑙 ∑︀ 𝑖=1 (⟨˜ 𝑥 𝑖 , ˜ 𝑤⟩ − 𝑦 𝑖 )𝑋 𝑖𝑗 , есть 𝑗–й элемент столбца 𝑋 ⊤ 𝑋 ˜ 𝑤 − 𝑋 ⊤ 𝑌 , и ∙ слагаемое 𝑐 ˜ 𝑤 𝑗 в (2.97) есть 𝑗–й элемент столбца 𝑐 ˜ 𝑤. Поэтому искомый вектор ˜ 𝑤 является решением уравнения 𝑋 ⊤ 𝑋 ˜ 𝑤 − 𝑋 ⊤ 𝑌 + 𝑐 ˜ 𝑤 = 0 ↓ (где 0 ↓ – нулевой столбец порядка 𝑛 + 1), которое можно переписать в виде (𝑋 ⊤ 𝑋 + 𝑐𝐸) ˜ 𝑤 = 𝑋 ⊤ 𝑌 (где 𝐸 – единичная матрица порядка 𝑛 + 1). Нетрудно доказать, что матрица 𝑋 ⊤ 𝑋 + 𝑐𝐸 невырождена ∀ 𝑐 > 0. Таким образом, решение задачи гребневой регрессии имеет вид ˜ 𝑤 = (𝑋 ⊤ 𝑋 + 𝑐𝐸) −1 𝑋 ⊤ 𝑌. 62 2.8 Метрическая модель обучения Метрическая модель обучения связана с использованием некоторой меры близости 𝜌 на множестве объектов 𝑋, которую называют метрикой. Метрика 𝜌 должна быть подобрана так, чтобы зависимость 𝑓 : 𝑋 → 𝑌 между объектами и ответами (которую аппроксимирует АФ 𝑎 𝑆 ) была согласована с 𝜌, т.е. если объекты 𝑥 и 𝑥 ′ близки по этой метрике, то ответы 𝑓 (𝑥) и 𝑓 (𝑥 ′ ) были бы примерно одинаковы. Во многих задачах метрический подход существенно проще, чем рас- смотренный выше подход, основанный на описании объектов в виде век- торов значений признаков. Применение метрической модели более пред- почтительно по сравнению с другими моделями в тех случаях, когда объекты имеют сложную структуру (например, это м.б. изображения, временные ряды, структуры белков, и т.п.). 2.8.1 Понятие метрики Метрикой на множестве 𝑋 называется функция 𝜌 : 𝑋 × 𝑋 → R ≥0 , удовлетворяющая условию: ∀ 𝑥, 𝑥 ′ ∈ 𝑋 {︂ 𝜌(𝑥, 𝑥 ′ ) = 0 ⇔ 𝑥 = 𝑦 ′ , 𝜌(𝑥, 𝑥 ′ ) = 𝜌(𝑥 ′ , 𝑥). В некоторых случаях 𝜌 может также удовлетворять условию ∀ 𝑥, 𝑥 ′ , 𝑥 ′′ ∈ 𝑋 𝜌(𝑥, 𝑥 ′′ ) ≤ 𝜌(𝑥, 𝑥 ′ ) + 𝜌(𝑥 ′ , 𝑥 ′′ ) (которое называется неравенством треугольника). Примеры метрики: ∙ евклидова метрика на 𝑋 = R 𝑛 : ∀ 𝑥, 𝑥 ′ ∈ R 𝑛 𝜌(𝑥, 𝑥 ′ ) = ⎯ ⎸ ⎸ ⎷ 𝑛 ∑︁ 𝑖=1 (𝑥 𝑖 − 𝑥 ′ 𝑖 ) 2 , где 𝑥 = (𝑥 1 , . . . , 𝑥 𝑛 ), 𝑥 ′ = (𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ), ∙ взвешенная метрика на 𝑋 = R 𝑛 : предполагается, что заданы веса 𝑤 1 , . . . , 𝑤 𝑛 ∈ R ≥0 и действительное число 𝑝 ≥ 1, ∀ 𝑥, 𝑥 ′ ∈ R 𝑛 𝜌(𝑥, 𝑥 ′ ) = (︁ 𝑛 ∑︁ 𝑖=1 𝑤 𝑖 |𝑥 𝑖 − 𝑥 ′ 𝑖 | 𝑝 )︁ 1 𝑝 , 63 где 𝑥 = (𝑥 1 , . . . , 𝑥 𝑛 ), 𝑥 ′ = (𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ), (евклидова метрика является частным случаем взвешенной метри- ки: в ней 𝑝 = 2 и ∀ 𝑖 = 1, . . . , 𝑛 𝑤 𝑖 = 1), ∙ метрика на множестве символьных строк 𝐶 * , где 𝐶 – конечное мно- жество, элементы которого называются символами: ∀ 𝑥, 𝑥 ′ ∈ 𝐶 * 𝜌(𝑥, 𝑥 ′ ) равно наименьшему числу элементарных операций, кото- рые надо выполнить чтобы получить 𝑥 ′ из 𝑥, где под элементар- ной операцией понимается – удаление какого-либо символа из строки, или – вставка какого-либо символа в произвольное место строки. 2.8.2 Метод ближайших соседей Пусть задана обучающая выборка 𝑆 ⊆ 𝑋 × 𝑌 . Напомним, что 𝑋 𝑆 обозначает множество объектов, входящих в 𝑆: 𝑋 𝑆 def = {𝑥 ∈ 𝑋 | ∃ 𝑦 𝑥 ∈ 𝑌 : (𝑥, 𝑦 𝑥 ) ∈ 𝑆}. Если на множестве 𝑋 объектов задана метрика 𝜌, то ∀ 𝑥 ∈ 𝑋 объекты из множества 𝑋 𝑆 можно упорядочить в соответствии с их близостью к 𝑥, т.е. расположить в последовательность 𝑥 1 , . . . , 𝑥 |𝑆| , (2.98) удовлетворяющую условию: 𝜌(𝑥, 𝑥 1 ) ≤ . . . ≤ 𝜌(𝑥, 𝑥 |𝑆| ) (2.99) т.е. первым в (2.98) расположен ближайший к 𝑥 объект, затем – следую- щий по близости к 𝑥 объект, и т.д. ∀ 𝑖 = 1, . . . , 𝑙 объект 𝑥 𝑖 из последова- тельности (2.98) называется 𝑖–м ближайшим соседом к 𝑥. Метод ближайших соседей для построения АФ 𝑎 𝑆 заключается в том, что выбираются ∙ натуральное число 𝑘 ≥ 1 (число ближайших к 𝑥 объектов, ответы на которых учитываются при вычислении ответа 𝑎 𝑆 (𝑥)), ∙ действительные числа 𝑤 1 ≥ . . . ≥ 𝑤 𝑘 > 0, которые имеют смысл ве- сов, определяющих вклад ближайших 𝑘 соседей объекта 𝑥 из обу- чающей выборки 𝑆 в вычисление ответа для объекта 𝑥, например, ∀ 𝑖 = 1, . . . , 𝑘 𝑤 𝑖 = 𝑘 + 1 − 𝑖 𝑘 или 𝑤 𝑖 = 𝑞 𝑖 , где 0 < 𝑞 < 1 – заданный параметр, 64 ∀ 𝑥 ∈ 𝑋 значение 𝑎 𝑆 (𝑥) определяется как такой ответ 𝑦 ∈ 𝑌 , который максимизирует значение выражения 𝑘 ∑︁ 𝑖=1 [[𝑦 𝑥 𝑖 = 𝑦]]𝑤 𝑖 , (2.100) т.е. как такой ответ 𝑦, который наиболее характерен среди ответов на 𝑘 ближайших соседей 𝑥 из обучающей выборки 𝑆. АФ, построенную в соответствии с приведенным выше определени- ем, будем обозначать записью 𝑎 𝑘 𝑆 , явно указывая число 𝑘 ближайших соседей. Оптимальным является такое 𝑘, которое минимизирует риск ∑︁ (𝑥,𝑦 𝑥 )∈𝑆 [[𝑎 𝑘 𝑆∖{(𝑥,𝑦 𝑥 )} (𝑥) ̸= 𝑦 𝑥 ]]. 2.8.3 Метод окна Парзена В методе окна Парзена (МОП) используется ∙ параметр ℎ > 0, называемый шириной окна, и ∙ невозрастающая функция 𝐾(𝑟) : R ≥0 → R ≥0 , называемая ядром. Примеры ядер, используемых в МОП: [[𝑟 ≤ 1]], (1 − 𝑟 2 )[[𝑟 ≤ 1]], 𝑒 −𝑟 2 АФ 𝑎 𝑆 , построенная по МОП, определяется почти так же, как в преды- дущем пункте, со следующем отличием: вместо выражения (2.100) ис- пользуется выражение |𝑆| ∑︁ 𝑖=1 [[𝑦 𝑥 𝑖 = 𝑦]]𝐾 (︁ 𝜌(𝑥, 𝑥 𝑖 ) ℎ )︁ АФ, построенную в соответствии с приведенным выше определением, будем обозначать записью 𝑎 ℎ 𝑆 , явно указывая ширину окна ℎ. Оптималь- ным является такое ℎ, которое минимизирует риск ∑︁ (𝑥,𝑦 𝑥 )∈𝑆 [[𝑎 ℎ 𝑆∖{(𝑥,𝑦 𝑥 )} (𝑥) ̸= 𝑦 𝑥 ]]. Ширина окна ℎ может быть не константой, а функцией, зависящей от количества объектов из 𝑋 𝑆 , находящихся вблизи 𝑥. 65 2.8.4 Метод потенциалов В методе потенциалов используются следующие параметры: ∙ размеры окон ℎ 1 , . . . , ℎ |𝑆| > 0, ∙ порог ошибки 𝛿 ≥ 0, и ∙ ядро 𝐾(𝑟). АФ 𝑎 𝑆 , построенная по методу потенциалов, определяется почти так же, как в пункте 2.8.2, со следующем отличием: вместо выражения (2.100) используется выражение |𝑆| ∑︁ 𝑖=1 [[𝑦 𝑥 𝑖 = 𝑦]]𝛾 𝑖 𝐾 (︁ 𝜌(𝑥, 𝑥 𝑖 ) ℎ 𝑖 )︁ , в котором 𝛾 𝑖 ≥ 0 – веса, настраиваемые по следующему алгоритму: ∙ - 𝛾 := ¯ 0 - ? ' & $ % |𝑆| ∑︀ 𝑖=1 [[𝑎 𝑆 (𝑥 𝑖 ) ̸= 𝑦 𝑥 𝑖 ]] > 𝛿 - ? 0 1 𝛾 𝑖 := 𝛾 𝑖 + [[𝑎 𝑆 (𝑥 𝑖 ) ̸= 𝑦 𝑥 𝑖 ]] @ @ где ∙ 𝛾 = (𝛾 1 , . . . , 𝛾 |𝑆| ), ∙ ¯ 0 – вектор размерности |𝑆|, все компоненты которого равны 0, и ∙ при каждом выполнении оператора в правом прямоугольнике ин- декс 𝑖 выбирается равновероятно из множества {1, . . . , |𝑆|}. При 𝑌 = {−1, +1} можно понимать ∙ объекты из 𝑋 𝑆 как положительные и отрицательные заряды, ∙ коэффициенты 𝛾 𝑖 как абсолютные величины этих зарядов, ∙ 𝐾(𝑟) как зависимость потенциала от расстояния до заряда, ∙ значение 𝑎 𝑆 (𝑥) как знак потенциала в точке 𝑥. 66 2.8.5 Метод эталонов В этом пункте рассматривается задача построения по обучающей выбор- ке 𝑆 АФ 𝑎 𝑆 по следующему принципу: ∙ ∀ 𝑥 ∈ 𝑋 элементы множества 𝑋 𝑆 располагаются в последователь- ность 𝑥 1 , . . . , 𝑥 |𝑆| , удовлетворяющую условию (2.99), и ∙ значение 𝑎 𝑆 (𝑥) определяется как такой ответ 𝑦 ∈ 𝑌 , который мак- симизирует значение выражения (𝑥 ↦→ 𝑆 𝑦) = |𝑆| ∑︁ 𝑖=1 [[𝑦 𝑥 𝑖 = 𝑦]] 𝑤(𝑖, 𝑥), (2.101) где ∀ 𝑖 = 1, . . . , |𝑆| 𝑤(𝑖, 𝑥) – заданное число, выражающее степень важности 𝑖–го ближайшего соседа 𝑥 (т.е. 𝑥 𝑖 ) для вычисления 𝑎 𝑆 (𝑥). Значение (2.101) можно интерпретировать как ∙ меру уверенности в том, что АФ 𝑎 𝑆 отображает 𝑥 именно в 𝑦, или ∙ меру близости 𝑎 𝑆 (𝑥) к 𝑦. ∀ 𝑥 ∈ 𝑋 𝑆 сопоставим объекту 𝑥 число 𝑀 𝑆 (𝑥), называемое типично- стью объекта 𝑥, и определяемое следующим образом: 𝑀 𝑆 (𝑥) = (𝑥 ↦→ 𝑆 𝑦 𝑥 ) − max 𝑦∈𝑌 ∖𝑦 𝑥 (𝑥 ↦→ 𝑆 𝑦). Говоря неформально, 𝑀 𝑆 (𝑥) выражает меру правдоподобия утвер- ждения о том, что значением 𝑎 𝑆 (𝑥) является именно 𝑦 𝑥 Каждому объекту 𝑥 ∈ 𝑋 𝑆 можно сопоставить один из четырех пере- числяемых ниже типов, в соответствии со значением 𝑀 𝑆 (𝑥): ∙ 𝑥 – эталон, если значение 𝑀 𝑆 (𝑥) – большое положительное, ∙ 𝑥 – периферийный (или неинформативный) объект, если 𝑀 𝑆 (𝑥) – положительное, но не такое большое, как у эталонов, ∙ 𝑥 – пограничный объект, если 𝑀 𝑆 (𝑥) близко к 0, ∙ 𝑥 – выброс (т.е. зашумленный, или ошибочно размеченный объ- ект), если 𝑀 𝑆 (𝑥) < 0. Для нахождения оптимальной АФ 𝑎 𝑆 рекомендуется строить её не по всей выборке 𝑆, а по ее подвыборке ˆ 𝑆, содержащей только эталоны. ˆ 𝑆 строится при помощи излагаемого ниже алгоритма, в котором ис- пользуются следующие параметры: 67 ∙ 𝛿 – порог фильтрации выбросов, ∙ 𝑙 0 – допустимая доля ошибок. Алгоритм состоит из перечисляемых ниже действий. ∙ Из 𝑆 удаляются все пары (𝑥, 𝑦 𝑥 ), такие, что 𝑀 𝑆 (𝑥) < 𝛿. Ниже под 𝑆 понимается не исходная выборка, а результат этого удаления. ∙ ∀ 𝑦 ∈ 𝑌 в ˆ 𝑆 зачисляется такая пара (𝑥 * , 𝑦) ∈ 𝑆, что значение 𝑀 𝑆 (𝑥 * ) максимально среди {𝑀 𝑆 (𝑥) | 𝑥 ∈ 𝑋 𝑆 , (𝑥, 𝑦) ∈ 𝑆}. ∙ Далее выполняются итерации, состоящие из перечисляемых ниже действий. Итерации заканчиваются, если ˆ 𝑆 станет равно 𝑆. – 𝐸 := {(𝑥, 𝑦) ∈ 𝑆 ∖ ˆ 𝑆 : 𝑀 ^ 𝑆 (𝑥) < 0}, – если |𝐸| < 𝑙 0 то выход, – иначе ˆ 𝑆 := ˆ 𝑆 ∪ {(𝑥 * , 𝑦)}, где (𝑥 * , 𝑦) ∈ 𝐸, и значение 𝑀 ^ 𝑆 (𝑥 * ) минимально среди {𝑀 ^ 𝑆 (𝑥) | (𝑥, 𝑦) ∈ 𝐸}. 2.9 Вероятностные модели обучения 2.9.1 Дискретная вероятностная модель обучения В дискретной вероятностной модели обучения (ДВМО) предпо- лагается, что множество 𝑋 является конечным или счетным, на множе- стве 𝑋 ×𝑌 задано вероятностное распределение (обычно называемое просто распределением), т.е. функция 𝑝 вида 𝑝 : 𝑋 × 𝑌 → [0, 1], (2.102) удовлетворяющая условию ∑︀ (𝑥,𝑦)∈𝑋×𝑌 𝑝(𝑥, 𝑦) = 1. Будем предполагать, что ∀ 𝑦 ∈ 𝑌 ∃ 𝑥 ∈ 𝑋 : 𝑝(𝑥, 𝑦) > 0. ∀ (𝑥, 𝑦) ∈ 𝑋 × 𝑌 значение 𝑝(𝑥, 𝑦) называется вероятностью появле- ния пары (𝑥, 𝑦) в обучающей выборке 𝑆. Мы предполагаем, что все пары в 𝑆 появляются независимо друг от друга. Если выборка 𝑆 большая, то число 𝑝(𝑥, 𝑦) можно понимать как при- близительную ∙ долю тех пар в 𝑆, которые равны (𝑥, 𝑦), или 68 ∙ частоту появления пары (𝑥, 𝑦) в 𝑆. ∀ 𝑋 ′ ⊆ 𝑋, ∀ 𝑦 ∈ 𝑌 будем обозначать записью 𝑝(𝑋 ′ , 𝑦) значение 𝑝(𝑋 ′ , 𝑦) def = ∑︁ 𝑥∈𝑋 ′ 𝑝(𝑥, 𝑦). (2.103) Это значение можно понимать как приблизительную частоту появле- ния в обучающей выборке объекта из 𝑋 ′ с ответом 𝑦. Если 𝑋 ′ = 𝑋, то значение (2.103) обозначается записью 𝑝(𝑦), и по- нимается как приблизительная частота появления в обучающей выборке объекта с ответом 𝑦. Отметим, что ДВМО концептуально отличается от рассмотренных выше моделей обучения: ∙ в рассмотренных выше моделях обучения ∀ 𝑥 ∈ 𝑋 обучающая вы- борка не может содержать пар вида (𝑥, 𝑦) и (𝑥, 𝑦 ′ ), где 𝑦 ̸= 𝑦 ′ , т.к. вторая компонента пары (𝑥, 𝑦) – это истинный ответ на объект 𝑥, который определяется однозначно по 𝑥, ∙ а в ДВМО нет понятия истинного ответа на объект, в ней любой ответ на объект может появиться с некоторой вероятностью. Одной из компонентов ДВМО является функция потерь 𝜆 : 𝑌 × 𝑌 → R ≥0 , (2.104) которая сопоставляет каждой паре (𝑦, 𝑦 ′ ) ∈ 𝑌 × 𝑌 потерю 𝜆 𝑦𝑦 ′ ≥ 0, возникающую в том случае, когда на какой-либо объект дается ответ 𝑦 ′ , в то время когда правильным ответом на этот объект был бы 𝑦. 2.9.2 Оптимальные аппроксимирующие функции Пусть 𝑎 – функция вида 𝑎 : 𝑋 → 𝑌 . ∀ 𝑦 ∈ 𝑌 запись 𝑎 −1 (𝑦) обозначает прообраз 𝑦 относительно 𝑎: 𝑎 −1 (𝑦) = {𝑥 ∈ 𝑋 | 𝑎(𝑥) = 𝑦}. Риск, соответствующий функции 𝑎 : 𝑋 → 𝑌 определяется как сред- нее значение потери при использовании 𝑎 в качестве АФ: 𝑅(𝑎) = ∑︁ 𝑦,𝑦 ′ ∈𝑌 𝜆 𝑦𝑦 ′ 𝑝(𝑎 −1 (𝑦 ′ ), 𝑦). (2.105) 69 Если 𝜆 𝑦𝑦 ′ = [[𝑦 ̸= 𝑦 ′ ]], то 𝑅(𝑎) можно интерпретировать как вероят- ность ошибки при использовании 𝑎 в качестве АФ. Теорема 6. Пусть заданы распределение (2.102) и функция потерь (2.104). Минимальное значение риска (2.105) достигается на функции 𝑎, сопо- ставляющей каждому 𝑥 ∈ 𝑋 такой ответ 𝑦 𝑥 ∈ 𝑌 , который минимизирует значение выражения ∑︁ 𝑦∈𝑌 𝜆 𝑦𝑦 𝑥 𝑝(𝑥, 𝑦). Доказательство. Согласно определению значения 𝑝(𝑎 −1 (𝑦 ′ ), 𝑦), 𝑅(𝑎) = ∑︁ 𝑦,𝑦 ′ ∈𝑌 𝜆 𝑦𝑦 ′ ∑︁ 𝑥∈𝑎 −1 (𝑦 ′ ) 𝑝(𝑥, 𝑦) = ∑︁ 𝑦 ′ ∈𝑌 ∑︁ 𝑥∈𝑎 −1 (𝑦 ′ ) ∑︁ 𝑦∈𝑌 𝜆 𝑦𝑦 ′ 𝑝(𝑥, 𝑦). (2.106) Заметим, что сумма вида ∑︀ 𝑦 ′ ∈𝑌 ∑︀ 𝑥∈𝑎 −1 (𝑦 ′ ) . . . – это сумма вида ∑︀ 𝑥∈𝑋 . . ., где выражение, изображаемое многоточием во второй сумме, получается из выражения, изображаемого многоточием в первой сумме заменой всех вхождений 𝑦 ′ на 𝑎(𝑥). Поэтому (2.106) можно переписать в виде 𝑅(𝑎) = ∑︁ 𝑥∈𝑋 ∑︁ 𝑦∈𝑌 𝜆 𝑦,𝑎(𝑥) 𝑝(𝑥, 𝑦), откуда видно, что 𝑅(𝑎) достигает минимального значения в том и только в том случае, когда ∀ 𝑥 ∈ 𝑋 сумма ∑︀ 𝑦∈𝑌 𝜆 𝑦,𝑎(𝑥) 𝑝(𝑥, 𝑦) достигает минималь- ного значения, что по определению 𝑦 𝑥 возможно при 𝑎(𝑥) = 𝑦 𝑥 Теорема 7. Пусть заданы распределение (2.102) и функция потерь (2.104), при- чем ∙ ∀ 𝑦 ∈ 𝑌 𝜆 𝑦𝑦 = 0, и ∙ ∀ 𝑦, 𝑦 ′ ∈ 𝑌 , если 𝑦 ̸= 𝑦 ′ , то значение 𝜆 𝑦𝑦 ′ не зависит от 𝑦 ′ (обозначим это значение 𝜆 𝑦 ). Минимальное значение риска (2.105) достигается на функции 𝑎, сопо- ставляющей каждому 𝑥 ∈ 𝑋 такой ответ 𝑦 𝑥 ∈ 𝑌 , который максимизирует значение выражения 𝜆 𝑦 𝑥 𝑝(𝑥, 𝑦 𝑥 ), т.е. 𝑎(𝑥) = arg max 𝑦∈𝑌 𝜆 𝑦 𝑝(𝑥, 𝑦). (2.107) 70 Доказательство. Согласно определению риска (2.105) и условиям теоремы, 𝑅(𝑎) = ∑︀ 𝑦,𝑦 ′ ∈𝑌 𝜆 𝑦𝑦 ′ 𝑝(𝑎 −1 (𝑦 ′ ), 𝑦) = ∑︀ 𝑦,𝑦 ′ ∈𝑌,𝑦̸=𝑦 ′ 𝜆 𝑦 𝑝(𝑎 −1 (𝑦 ′ ), 𝑦) = = ∑︀ 𝑦,𝑦 ′ ∈𝑌 𝜆 𝑦 𝑝(𝑎 −1 (𝑦 ′ ), 𝑦) − ∑︀ 𝑦∈𝑌 𝜆 𝑦 𝑝(𝑎 −1 (𝑦), 𝑦) = = ∑︀ 𝑦∈𝑌 ∑︀ 𝑦 ′ ∈𝑌 ∑︀ 𝑥∈𝑎 −1 (𝑦 ′ ) 𝜆 𝑦 𝑝(𝑥, 𝑦) − ∑︀ 𝑦∈𝑌 ∑︀ 𝑥∈𝑎 −1 (𝑦) 𝜆 𝑦 𝑝(𝑥, 𝑦). (2.108) Нетрудно видеть, что ∙ сумму ∑︀ 𝑦 ′ ∈𝑌 ∑︀ 𝑥∈𝑎 −1 (𝑦 ′ ) 𝜆 𝑦 𝑝(𝑥, 𝑦) можно заменить на ∑︀ 𝑥∈𝑋 𝜆 𝑦 𝑝(𝑥, 𝑦), и ∙ сумму ∑︀ 𝑦∈𝑌 ∑︀ 𝑥∈𝑎 −1 (𝑦) 𝜆 𝑦 𝑝(𝑥, 𝑦) можно заменить на ∑︀ 𝑥∈𝑋 𝜆 𝑎(𝑥) 𝑝(𝑥, 𝑎(𝑥)), поэтому (2.108) можно переписать в виде 𝑅(𝑎) = ∑︀ 𝑦∈𝑌 ∑︀ 𝑥∈𝑋 𝜆 𝑦 𝑝(𝑥, 𝑦) − ∑︀ 𝑥∈𝑋 𝜆 𝑎(𝑥) 𝑝(𝑥, 𝑎(𝑥)) = = ∑︀ 𝑦∈𝑌 𝜆 𝑦 𝑝(𝑦) − ∑︀ 𝑥∈𝑋 𝜆 𝑎(𝑥) 𝑝(𝑥, 𝑎(𝑥)), откуда видно, что 𝑅(𝑎) достигает минимального значения в том и только в том случае, когда ∀ 𝑥 ∈ 𝑋 выражение 𝜆 |