машинное обучение. А. М. Миронов Московский Государственный Университет Механикоматематический факультет Кафедра математической теории интеллектуальных систем Введение Книга
 Скачать 1.05 Mb.
|
|
𝑎(𝑥) 𝑝(𝑥, 𝑎(𝑥)) достигает макси- мального значения, что по определению 𝑦 𝑥 возможно при 𝑎(𝑥) = 𝑦 𝑥 Отметим, что функция (2.107), совпадает с функцией 𝑎(𝑥) = arg max 𝑦∈𝑌 𝜆 𝑦 𝑝(𝑦)𝑝(𝑥|𝑦), (2.109) где 𝑝(𝑥|𝑦) = 𝑝(𝑥,𝑦) 𝑝(𝑦) – вероятность появления объекта 𝑥 в обучащей выбор- ке, при условии, что ответом на этот объект является 𝑦. Значение 𝑝(𝑥|𝑦) можно понимать как приблизительную долю (или частоту появления) пары (𝑥, 𝑦) в подвыборке 𝑆 𝑦 , где 𝑆 𝑦 = {(𝑥, 𝑦 𝑥 ) ∈ 𝑆 | 𝑦 𝑥 = 𝑦}. (2.110) В ряде случаев вместо (2.109) более удобно использовать формулу 𝑎(𝑥) = arg max 𝑦∈𝑌 ln (︁ 𝜆 𝑦 𝑝(𝑦)𝑝(𝑥|𝑦) )︁ , (2.111) которая, как нетрудно видеть, определяет ту же функцию, что и (2.109). 71 2.9.3 Построение АФ по обучающей выборке Пусть задана некоторая ДВМО, причем ∙ распределение (2.102) неизвестно, и ∙ функция потерь (2.104) известна и удовлетворяет условиям теоре- мы 7. Также задана некоторая обучающая выборка 𝑆 ⊆ 𝑋 ×𝑌 , построенная в соответствии с этой ДВМО. Требуется построить 𝑎 𝑆 вида (2.109), где вместо неизвестных истин- ных значений вероятностей 𝑝(𝑦) и 𝑝(𝑥|𝑦) должны быть использованы оценки ˆ 𝑝(𝑦) и ˆ 𝑝(𝑥|𝑦) этих вероятностей, вычисленные по 𝑆. В качестве оценки ˆ 𝑝(𝑦) можно взять, например, |𝑆 𝑦 | |𝑆| Для вычисления оценки ˆ 𝑝(𝑥|𝑦) обозначим записью 𝑥 1 , . . . , 𝑥 𝑚 после- довательность первых компонентов пар, входящих в 𝑆 𝑦 , и полагаем ˆ 𝑝(𝑥|𝑦) def = 1 𝑚 𝑚 ∑︁ 𝑖=1 [[𝑥 𝑖 = 𝑥]]. 2.9.4 Непрерывная вероятностная модель обучения Во многих задачах машинного обучения множеством объектов 𝑋 яв- ляется R или R 𝑛 . Для данного случая можно определить аналог рас- смотренного выше понятия ДВМО, который называется непрерывной вероятностной моделью обучения (НВМО). В НВМО вместо по- нятия вероятностного распределения используется понятие плотности вероятности (обычно называемой просто плотностью), которая пред- ставляет собой функцию 𝑝 вида 𝑝 : 𝑋 × 𝑌 → [0, 1], имеющую излагаемый ниже смысл. Для каждой пары (𝑥, 𝑦) ∈ 𝑋 × 𝑌 значение 𝑝 на паре (𝑥, 𝑦) будем обозначать записью 𝑝(𝑥|𝑦). Предполагается, что ∙ на множестве 𝑋 задана мера Лебега 𝜇, ∙ ∀ 𝑦 ∈ 𝑌 функция вида 𝑋 → R ≥0 , отображающая каждый 𝑥 ∈ 𝑋 в 𝑝(𝑥|𝑦), предполагается интегрируемой по Лебегу, и ∫︁ 𝑋 𝑝(𝑥|𝑦)𝑑𝜇 = 1. (2.112) 72 Для каждого измеримого подмножества 𝑋 ′ ⊆ 𝑋 и каждого 𝑦 ∈ 𝑌 ин- теграл ∫︀ 𝑋 ′ 𝑝(𝑥|𝑦)𝑑𝜇 интерпретируется как вероятность появления в обу- чающей выборке 𝑆 пары с первой компонентой из множества 𝑋 ′ , при условии, что вторая компонента этой пары равна 𝑦. Так же, как и в ДВМО, мы предполагаем, что все пары в 𝑆 появляются независимо друг от друга. Если выборка 𝑆 большая, то число ∫︀ 𝑋 ′ 𝑝(𝑥|𝑦)𝑑𝜇 можно пони- мать как приблизительную ∙ долю тех пар (𝑥, 𝑦) в 𝑆 𝑦 (см. (2.110)), у которых 𝑥 ∈ 𝑋 ′ , или ∙ частоту появления в 𝑆 𝑦 пар с первой компонентой из 𝑋 ′ Множество 𝑌 ответов предполагается конечным или счетным. Одной из компонентов НВМО является распределение (обозначаемое тем же символом 𝑝) на 𝑌 . ∀ 𝑦 ∈ 𝑌 число 𝑝(𝑦) имеет тот же смысл, что и в ДВМО. Как и выше, в НВМО можно ∙ определить понятие риска, соответствующего функции 𝑎 : 𝑋 → 𝑌 , ∙ и доказать, что если функция потерь (2.104) известна и удовлетво- ряет условиям теоремы 7, то оптимальная АФ имеет вид (2.109), где 𝑝(𝑥|𝑦) понимается как плотность в точке 𝑥. Таким образом, если ∙ задана некоторая НВМО, причем – плотность 𝑝(𝑥|𝑦) либо неизвестна, либо известна лишь частич- но (например, известно, что она имеет вид 𝜙(𝑥, 𝜃), где функция 𝜙 известна, а 𝜃 – неизвестный параметр), и – функция потерь (2.104) известна и удовлетворяет условиям теоремы 7, ∙ и задана некоторая обучающая выборка 𝑆 ⊆ 𝑋 × 𝑌 , построенная в соответствии с этой НВМО, то оптимальную АФ 𝑎 𝑆 можно искать в виде (2.109), где вместо неизвест- ных истинных значений вероятностей 𝑝(𝑦) и 𝑝(𝑥|𝑦) используются оценки ˆ 𝑝(𝑦) и ˆ 𝑝(𝑥|𝑦) этих вероятностей, вычисленные по 𝑆, Как и выше, в качестве оценки ˆ 𝑝(𝑦) можно взять |𝑆 𝑦 | |𝑆| Ниже излагаются различные варианты вычисления оценки ˆ 𝑝(𝑥|𝑦), в зависимости от вида множества объектов 𝑋 и предположений о классе функций, в котором содержится функция 𝑝(𝑥|𝑦) : 𝑋 → [0, 1]. 73 Обозначим записью 𝑋 𝑆 𝑦 множество первых компонентов пар, входя- щих в 𝑆 𝑦 . Элементы 𝑋 𝑆 𝑦 будем обозначать записями 𝑥 1 , . . ., 𝑥 𝑚 Рассмотрим различные виды, которые может иметь множество 𝑋. 1. 𝑋 = R. ∙ Согласно определению плотности, при небольшом числе ℎ > 0 произведение 𝑝(𝑥) · 2ℎ приблизительно равно количеству точек из 𝑋 𝑆 𝑦 , попавших в отрезок [𝑥 − ℎ, 𝑥 + ℎ]. Поэтому ˆ 𝑝(𝑥|𝑦) можно определить как долю точек из 𝑋 𝑆 𝑦 , ле- жащих внутри отрезка [𝑥 − ℎ, 𝑥 + ℎ]: ˆ 𝑝(𝑥|𝑦) = 1 2𝑚ℎ 𝑚 ∑︁ 𝑖=1 [[|𝑥 − 𝑥 𝑖 | < ℎ]]. (2.113) ∙ Другой вид оценки 𝑝(𝑥|𝑦) – оценка Парзена-Розенблатта: ˆ 𝑝(𝑥|𝑦) = 1 𝑚ℎ 𝑚 ∑︁ 𝑖=1 𝐾 (︁ 𝑥 − 𝑥 𝑖 ℎ )︁ (2.114) где 𝐾(𝑧) – четная функция, называемая ядром, такая, что ∫︁ +∞ −∞ 𝐾(𝑧) 𝑑𝑧 = 1, и ℎ – параметр, называемый шириной окна, небольшое по- ложительное число. АФ, построенную в соответствии с приведенным выше определени- ем, будем обозначать записью 𝑎 ℎ 𝑆 , явно указывая ширину окна ℎ. Оптимальным является такое ℎ, которое минимизирует риск ∑︁ (𝑥,𝑦 𝑥 )∈𝑆 [[𝑎 ℎ 𝑆∖{(𝑥,𝑦 𝑥 )} (𝑥) ̸= 𝑦 𝑥 ]]. (2.115) 2. 𝑋 – метрическое пространство, т.е. на 𝑋 задана метрика 𝜌. В этом случае м.б. использована следующая оценка ˆ 𝑝(𝑥|𝑦): ˆ 𝑝(𝑥|𝑦) = 1 𝑚𝑉 (ℎ) 𝑚 ∑︁ 𝑖=1 𝐾 (︁ 𝜌(𝑥, 𝑥 𝑖 ) ℎ )︁ (2.116) где 𝐾, ℎ – параметры, имеющие тот же смысл, что и аналогичные параметры выше (ядро и ширина окна, соответственно), и 𝑉 (ℎ) – 74 нормирующий множитель, предназначенный для того, чтобы (2.116) было плотностью, т.е. удовлетворяло условию (2.112). Если распределение объектов в пространстве 𝑋 сильно неравно- мерно, то лучше использовать переменную ширину окна, опреде- ляемую в каждой точке 𝑥 ∈ 𝑋 как расстояние от 𝑥 до (𝑘 + 1)-го соседа, где оптимальное значение 𝑘 м.б. найдено из условия, ана- логичного условию (2.115). 3. 𝑋 = R 𝑛 ∙ Если нет никаких предположений о том, какой вид может иметь плотность 𝑝(𝑥|𝑦), то можно использовать оценку ˆ 𝑝(𝑥|𝑦) = 1 𝑚 𝑚 ∑︁ 𝑖=1 𝑛 ∏︁ 𝑗=1 1 ℎ 𝑗 𝐾 (︁ 𝑥 0𝑗 − 𝑥 𝑖𝑗 ℎ 𝑗 )︁ , где – ∀ 𝑖 = 1, . . . , 𝑚 𝑥 𝑖 = (𝑥 𝑖1 , . . . , 𝑥 𝑖𝑛 ), 𝑥 = (𝑥 01 , . . . , 𝑥 0𝑛 ), и – 𝐾, ℎ 1 , . . . , ℎ 𝑛 – параметры, имеющие тот же смысл, что и аналогичные параметры в предыдущем пункте (т.е. 𝐾 – ядро, и ℎ 1 , . . . , ℎ 𝑛 – ширины окон, соответствующих каж- дому из признаков). ∙ Если известно, что 𝑝(𝑥|𝑦) имеет гауссов вид 𝒩 (𝑥; 𝜇, Σ) = (2𝜋) − 𝑛 2 |Σ| − 1 2 𝑒 − 1 2 (𝑥−𝜇) ⊤ Σ −1 (𝑥−𝜇) (⊤ обозначает транспонирование), (2.117) где 𝜇 и Σ – неизвестные параметры: – 𝜇 ∈ R 𝑛 , – Σ – симметричная, невырожденная, положительно опреде- ленная матрица порядка 𝑛, называемая ковариационной матрицей, то нахождение оценки ˆ 𝑝(𝑥|𝑦) сводится к нахождению оценок ˆ 𝜇 и ˆ Σ, которые м.б. вычислены по правилам ˆ 𝜇 = 1 𝑚 𝑚 ∑︁ 𝑖=1 𝑥 𝑖 ; ˆ Σ = 1 𝑚 − 1 𝑚 ∑︁ 𝑖=1 (𝑥 𝑖 − ˆ 𝜇)(𝑥 𝑖 − ˆ 𝜇) ⊤ Некоторое обоснование данных правил заключается в том, что 75 – 𝜇 совпадает с мат. ожиданием 𝐸𝑥 случайной величины 𝑥 с плотностью (2.117), т.е. с интегралом ∫︀ R 𝑛 𝑥𝒩 (𝑥; 𝜇, Σ)𝑑𝑥, – Σ совпадает с мат. ожиданием 𝐸(𝑥 − 𝜇)(𝑥 − 𝜇) ⊤ ∙ Если ∀ 𝑦 ∈ 𝑌 𝑝(𝑥|𝑦) имеет вид (2.117), и известно, что кова- риационные матрицы в (2.117) одинаковы для всех 𝑦 ∈ 𝑌 , то оценка ˆ Σ этих матриц м.б. вычислена по формуле ˆ Σ = 1 |𝑆| − |𝑌 | ∑︁ (𝑥,𝑦 𝑥 )∈𝑆 (𝑥 − ˆ 𝜇 𝑦 𝑥 )(𝑥 − ˆ 𝜇 𝑦 𝑥 ) ⊤ В данном случае АФ, вычисленную по формуле (2.111), можно записать (опуская сложение с константой в arg max 𝑦∈𝑌 (. . .)) в виде 𝑎(𝑥) = arg max 𝑦∈𝑌 (︁ ln(𝜆 𝑦 𝑝(𝑦)) − 1 2 (𝑥 − ˆ 𝜇 𝑦 ) ⊤ ˆ Σ −1 (𝑥 − ˆ 𝜇 𝑦 ) )︁ = = arg max 𝑦∈𝑌 (︁ ln(𝜆 𝑦 𝑝(𝑦)) − 1 2 ˆ 𝜇 ⊤ 𝑦 ˆ Σ −1 ˆ 𝜇 𝑦 + 𝑥 ⊤ ˆ Σ −1 ˆ 𝜇 𝑦 )︁ = = arg max 𝑦∈𝑌 (𝑥 ⊤ 𝛼 𝑦 + 𝛽 𝑦 ), (2.118) где 𝛼 𝑦 = ˆ Σ −1 ˆ 𝜇 𝑦 , 𝛽 𝑦 = ln(𝜆 𝑦 𝑝(𝑦)) − 1 2 ˆ 𝜇 ⊤ 𝑦 ˆ Σ −1 ˆ 𝜇 𝑦 АФ (2.118) называется линейным дискриминантом Фишера. После вычисления оценки ˆ 𝑝(𝑥|𝑦) ∙ те объекты из 𝑆 𝑦 , для которых значение ˆ 𝑝(𝑥|𝑦) мало, рассматрива- ются как выбросы, ∙ соответствующие пары (𝑥, 𝑦 𝑥 ) удаляются из 𝑆, ∙ после чего оценка ˆ 𝑝(𝑥|𝑦) перевычисляется. 2.9.5 EM-алгоритм EM-алгоритм предназначен для вычисления оценки ˆ 𝑝(𝑥|𝑦), в предполо- жении, что плотность 𝑝(𝑥|𝑦) является смесью плотностей вида 𝜙(𝑥, 𝜃 𝑗 ), где 𝑗 = 1, . . . , 𝑘, и функция 𝜙 предполагается известной, т.е. 𝑝(𝑥|𝑦) = 𝑘 ∑︁ 𝑗=1 𝑤 𝑗 𝜙(𝑥, 𝜃 𝑗 ), (2.119) 76 где 𝑤 1 , . . . , 𝑤 𝑘 , 𝜃 1 , . . . , 𝜃 𝑘 – неизвестные параметры, причем ∀ 𝑗 = 1, . . . , 𝑘 𝑤 𝑗 ∈ R ≥0 , 𝑘 ∑︁ 𝑗=1 𝑤 𝑗 = 1. (2.120) Обозначим символом Θ вектор параметров, входящих в (2.119), т.е. Θ = (𝑤 1 , . . . , 𝑤 𝑘 , 𝜃 1 , . . . , 𝜃 𝑘 ). Нахождение оценки ˆ 𝑝(𝑥|𝑦) сводится к нахождению вектора ˆ Θ оценок всех параметров, входящих в Θ. Для решения данной задачи раздельно рассматриваются случаи, ко- гда число 𝑘 компонентов смеси известно, и когда это число неизвестно. Число 𝑘 компонентов смеси известно В данном случае строится последовательность ˆ Θ (1) , ˆ Θ (2) , . . . приближе- ний к искомому вектору оценок параметров ˆ Θ. Алгоритм ∙ использует матрицу 𝐺 = (𝑔 𝑖𝑗 ) 𝑚×𝑘 скрытых (hidden) переменных, и ∙ заключается в итерационном повторении двух шагов: – E-шаг: вычисление 𝐺 по текущему приближению ˆ Θ (𝑠) , – М-шаг: вычисление следующего приближения ˆ Θ (𝑠+1) по теку- щим матрице 𝐺 и вектору ˆ Θ (𝑠) Одним из входных данных алгоритма является небольшое положи- тельное число 𝛿, используемое в критерии остановки. Первое приближение ˆ Θ (1) выбирается произвольно (или исходя из каких-либо соображений), с условием (2.120). 𝑠–я итерация (где 𝑠 ≥ 1) имеет вид: E-шаг (expectation) : ∀ 𝑖 = 1, . . . , 𝑚, ∀ 𝑗 = 1, . . . , 𝑘 𝑔 𝑖𝑗 = 𝑤 𝑗 𝜙(𝑥 𝑖 ,𝜃 𝑗 ) 𝑝(𝑥 𝑖 ) , где ∙ 𝑤 𝑗 и 𝜃 𝑗 – компоненты текущего приближения ˆ Θ (𝑠) , ∙ 𝑝(𝑥 𝑖 ) = 𝑘 ∑︀ 𝑗=1 𝑤 𝑗 𝜙(𝑥 𝑖 , 𝜃 𝑗 ). Если 𝑠 ≥ 2, и max 𝑖,𝑗 |𝑔 𝑖𝑗 −𝑔 ′ 𝑖𝑗 | < 𝛿, где 𝑔 ′ 𝑖𝑗 – соответствующая компонен- та матрицы 𝐺, вычисленной на предыдущей итерации, то алгоритм заканчивает свою работу, его результатом является ˆ Θ (𝑠) 77 M-шаг (maximization) : Целью данного шага является решение оптимизационной задачи 𝑚 ∏︁ 𝑖=1 𝑝(𝑥 𝑖 ) → max Θ , (где 𝑝(𝑥 𝑖 ) = 𝑘 ∑︀ 𝑗=1 𝑤 𝑗 𝜙(𝑥 𝑖 , 𝜃 𝑗 )) при ограничении 𝑘 ∑︀ 𝑗=1 𝑤 𝑗 = 1 (данная за- дача называется задачей максимизации правдоподобия), ко- торая эквивалентна оптимизационной задаче ln 𝑚 ∏︁ 𝑖=1 𝑝(𝑥 𝑖 ) = 𝑚 ∑︁ 𝑖=1 ln 𝑝(𝑥 𝑖 ) → max Θ при указанном выше ограничении. Функция Лагранжа этой оптимизационной задачи имеет вид 𝐿 = 𝑚 ∑︁ 𝑖=1 ln 𝑝(𝑥 𝑖 ) − 𝜆 (︁ 𝑘 ∑︁ 𝑗=1 𝑤 𝑗 − 1 )︁ Одним из необходимых условий оптимальности является соотно- шение 𝜕𝐿 𝜕𝑤 𝑗 = 𝑚 ∑︁ 𝑖=1 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) 𝑝(𝑥 𝑖 ) − 𝜆 = 0, ∀ 𝑗 = 1, . . . , 𝑘. (2.121) Из (2.121) следуют равенства 𝑤 𝑗 𝑚 ∑︁ 𝑖=1 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) 𝑝(𝑥 𝑖 ) = 𝑤 𝑗 𝜆 (∀ 𝑗 = 1, . . . , 𝑘), (2.122) просуммировав которые по 𝑗, получаем равенство 𝑘 ∑︁ 𝑗=1 𝑤 𝑗 𝑚 ∑︁ 𝑖=1 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) 𝑝(𝑥 𝑖 ) = 𝑘 ∑︁ 𝑗=1 𝑤 𝑗 𝜆, из которого следует равенство 𝑚 ∑︁ 𝑖=1 𝑘 ∑︁ 𝑗=1 𝑤 𝑗 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) 𝑝(𝑥 𝑖 ) = 𝜆 𝑘 ∑︁ 𝑗=1 𝑤 𝑗 = 𝜆. (2.123) 78 Левая часть (2.123) равна сумме 𝑚 единиц, т.е. 𝑚, поэтому 𝜆 = 𝑚. Подставляя в (2.122) 𝜆 = 𝑚, и вспоминая определение 𝑔 𝑖𝑗 , получаем равенства 𝑚 ∑︀ 𝑖=1 𝑔 𝑖𝑗 = 𝑤 𝑗 𝑚 (∀ 𝑗 = 1, . . . , 𝑘), т.е. 𝑤 𝑗 = 1 𝑚 𝑚 ∑︁ 𝑖=1 𝑔 𝑖𝑗 , ∀ 𝑗 = 1, . . . , 𝑘. (2.124) Неравенства 𝑤 𝑗 ≥ 0 будут выполнены на каждой итерации, т.к. они выполнены для ˆ Θ (1) Другие необходимые условия оптимальности имеют вид 𝜕𝐿 𝜕𝜃 𝑗 = 𝑚 ∑︀ 𝑖=1 𝑤 𝑗 𝑝(𝑥 𝑖 ) 𝜕 𝜕𝜃 𝑗 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) = = 𝑚 ∑︀ 𝑖=1 𝑤 𝑗 𝜙(𝑥 𝑖 ,𝜃 𝑗 ) 𝑝(𝑥 𝑖 ) 𝜕 𝜕𝜃 𝑗 ln 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) = = 𝑚 ∑︀ 𝑖=1 𝑔 𝑖𝑗 𝜕 𝜕𝜃 𝑗 ln 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) = = 𝜕 𝜕𝜃 𝑗 𝑚 ∑︀ 𝑖=1 𝑔 𝑖𝑗 ln 𝜙(𝑥 𝑖 , 𝜃 𝑗 ) = 0 (∀ 𝑗 = 1, . . . , 𝑘). (2.125) Последнее равенство в (2.125) эквивалентно соотношению 𝜃 𝑗 = arg max 𝜃 𝑚 ∑︁ 𝑖=1 𝑔 𝑖𝑗 ln 𝜙(𝑥 𝑖 , 𝜃) (∀ 𝑗 = 1, . . . , 𝑘). (2.126) Соотношения (2.124) и (2.126) являются теми правилами, в соответ- ствии с которыми вычисляются соответствующие компоненты вектора ˆ Θ (𝑠+1) Если 𝜙(𝑥, 𝜃 𝑗 ) имеет гауссов вид, т.е. 𝜙(𝑥, 𝜃 𝑗 ) = 𝒩 (𝑥, 𝜇 𝑗 , Σ 𝑗 ), то значе- ние параметра 𝜃 𝑗 = (𝜇 𝑗 , Σ 𝑗 ), удовлетворяющее условию (2.126), можно выразить в явном виде: 𝜇 𝑗 = 1 𝑚𝑤 𝑗 𝑚 ∑︀ 𝑖=1 𝑔 𝑖𝑗 𝑥 𝑖 , Σ 𝑗 = 1 𝑚𝑤 𝑗 𝑚 ∑︀ 𝑖=1 𝑔 𝑖𝑗 (𝑥 𝑖 − 𝜇 𝑗 )(𝑥 𝑖 − 𝜇 𝑗 ) ⊤ Число компонентов смеси неизвестно В данном случае компоненты смеси строятся в процессе обучения. Параметры алгоритма: ∙ 𝑅 – максимально допустимый разброс значений 𝑝(𝑥 𝑖 ), 79 ∙ 𝑚 0 – минимальная длина выборки, по которой можно восстановить плотность, ∙ 𝛿 – параметр критерия остановки. Сначала строится первая компонента: 𝑘 := 1, 𝑤 1 := 1, и 𝜃 1 := arg max 𝜃 𝑚 ∑︁ 𝑖=1 ln 𝜙(𝑥 𝑖 , 𝜃). Затем выполняется цикл по 𝑘 (начиная с 𝑘 = 2), тело этого цикла состоит из следующих действий: 1. Строится множество 𝑈 := {𝑥 𝑖 ∈ 𝑆 𝑦 : 𝑝(𝑥 𝑖 ) < 1 𝑅 max 𝑗 𝑝(𝑥 𝑗 )}, (𝑈 = объекты, не подходящие ни к одной из компонентов). 2. Если |𝑈 | < 𝑚 0 , то работа алгоритма завершается. (В данном случае объекты из 𝑈 рассматриваются как выбросы.) 3. Иначе добавляется новая (𝑘-я) компонента с параметрами 𝑤 𝑘 := 1 𝑚 |𝑈 |, 𝜃 𝑘 := arg max 𝜃 ∑︀ 𝑥 𝑖 ∈𝑈 ln 𝜙(𝑥 𝑖 , 𝜃), ∀ 𝑗 = 1, . . . , 𝑘 − 1 𝑤 𝑗 := 𝑤 𝑗 (1 − 𝑤 𝑘 ). 4. Для уточнения построенного в предыдущем действии вектора пара- метров Θ запускается EM-алгоритм на 𝑆 𝑦 c 𝑘 компонентами смеси и параметром остановки 𝛿. 80 Литература [1] Вьюгин В.В. Математические основы машинного обучения и про- гнозирования. Москва, издательство МЦНМО, 2018. 384 с. [2] Ветров Д.П., Кропотов Д.А. Алгоритмы выбора моделей и построе- ния коллективных решений в задачах классификации, основанные на принципе устойчивости. Москва, URSS, 2006. 112 с. [3] Информационно-аналитический ресурс по машинному обучению http://www.machinelearning.ru/ [4] Воронцов К. В., Математические методы обучения по прецедентам (теория обучения машин). http://www.machinelearning.ru/wiki/images/6/6d/ Voron-ML-1.pdf [5] F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386. (1958) [6] A. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, volume 12, pages 615–622. (1962) [7] M. Mohri and A. Rostamizadeh. Perceptron Mistake Bounds. (2013) https://arxiv.org/pdf/1305.0208.pdf [8] В. Н. Вапник, А. Я. Червоненкис. Теория распознавания образов. Статистические проблемы обучения. М., Наука. (1974) [9] Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потен- циальных функций в теории обучения машин. - М.: Наука, 1970. - 320 с. [10] Головко В. А. Нейронные сети: обучение, организация и примене- ние. - М.: ИПР- ЖР, 2001. 81 [11] Загоруйко Н. Г. Прикладные методы анализа данных и знаний. - Новосибирск: ИМ СО РАН, 1999. [12] Лапко А. В., Ченцов С. В., Крохов С. И., Фельдман Л. А. Обу- чающиеся системы обработки информации и принятия решений. Непараметрический подход. - Новосибирск: Наука, 1996. [13] Нейроинформатика / А. Н. Горбань, В. Л. Дунин-Барковский, А. Н. Кирдин, Е. М. Миркес, А. Ю. Новоходько, Д. А. Россиев, С. А. Терехов и др. - Новосибирск: Наука, 1998. - 296 с. [14] Хардле В. Прикладная непараметрическая регрессия. - М.: Мир, 1993. [15] Bishop C. M. Pattern Recognition and Machine Learning. - Springer, Series: Information Science and Statistics, 2006. - 740 pp. [16] Burges C. J. C. A tutorial on support vector machines for pattern recognition // Data Mining and Knowledge Discovery. - 1998. - Vol. 2, no. 2. - Pp. 121–167. http://citeseer.ist.psu.edu/burges98tutorial.html [17] Murphy Kevin P. Machine Learning: A Probabilistic Perspective. The MIT Press, 2012, 1104 с. [18] Хайкин С. Нейронные сети. Полный курс. Вильямс, 2018, 1104 с. [19] Николенко С., Кадурин А., Архангельская Е. Глубокое обучение. Погружение в мир нейронных сетей, Питер, 2018. 480 с. [20] Гудфеллоу Я., Бенджио И., Курвилль А. Глубокое обучение. ДМК Пресс, 2017, 652 с. [21] Лесковец Ю., Раджараман А., Ульман Д. Анализ больших наборов данных. ДМК Пресс, 2016, 498 с. [22] Kung S.Y. Kernel Methods and Machine Learning, Cambridge University Press, 2014, 578 с. [23] Skansi S. Introduction to Deep Learning: From Logical Calculus to Artificial Intelligence. Springer, 2018. 191 c. [24] Smith J. Machine Learning Systems. Manning Publications Co., 2018. 253 c. 82 [25] Мюллер А., Гвидо С. Введение в машинное обучение с помощью Python, Москва, 2017. 393 с. [26] Флах П. Машинное обучение. Наука и искусство построения алго- ритмов, которые извлекают знания из данных. ДМК Пресс, 2015. 402 с. [27] Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2014. 739 p. [28] Мерков А. Б. Распознавание образов. Введение в методы статисти- ческого обучения. 2011. 256 с. [29] Мерков А. Б. Распознавание образов. Построение и обучение веро- ятностных моделей. 2014. 238 с. [30] Коэльо Л.П., Ричарт В. Построение систем машинного обучения на языке Python. 2016. 302 с. [31] Barber D. Bayesian Reasoning and Machine Learning. Cambridge University Press, 2012. [32] Mackay D.J.C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003. [33] Wainwright M.J., Jordan M.I. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning, NOWPress, 2008. [34] Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009. 83 |