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

Методы оценки обоснованности119Марковская цепь• Методы Монте Карло, использующие Марковские цепи (Monte Carlo Markov chain, MCMC) являютсяболее эффективными средствами получения выборки из заданного распределения• При использовании МСМС каждая очередная точка выборки xi зависит некоторым образом отпредыдущей точки xi−1• Методы этой группы позволяют «нащупать» области с высоким значением плотности и проводитьвыборку из них• Полученная выборка (x1 , .

. . , xn ) не является выборкой независимых одинаково распределенныхслучайных величин, но вполне подходит для взятия интегралаАлгоритм 6: Схема ГиббсаВход: Многомерное распределение p(x);Выход: Выборка из распределения (x1 , . . . , xn )1: Инициализация x0 = (x01 , . . . , x0d );2: для i = 1, . . . , ni−1i−13:Сгенерировать xi1 из распределения p(x1 |xi−12 , x3 , . . . , xd );i−1i−14:Сгенерировать xi2 из распределения p(x2 |xi1 , x3 , . .

. , xd );...5:Сгенерировать xid из распределения p(xd |xi2 , xi3 , . . . , xid−1 );6:xi := (xi1 , . . . , xid );11.3.3Гибридный метод Монте-Карло• Гибридные методы используют информацию не только о значении плотности p(x), но и о градиентеее логарифма ∂ log∂xp(x)• Для этого используются аналогии с аналитической механикойАналитическая механика была разработана в первой половине 19 в.

ирландским математиком Гамильтоном. В ееоснове лежит идея замены одного дифференциального уравнения второго порядка во втором законе Ньютона насистему двух дифференциальных уравнений первого порядка• Считая x переменными состояния, введем потенциальную энергию системыE(x) = − log p(x) + C• Здесь используется принцип минимальной потенциальной энергии, гласящий, что состояние системытем более вероятно, чем меньше ее потенциальная энергияАналитическая механика• Введем дополнительные переменные, называемые моментамиr=dxdt• Кинетическая энергия системы является функцией моментов K(r) = 0.5krk2 , а полная энергиясистемы (гамильтониан) равнаH(x, r) = E(x) + K(r)Глава 11. Методы оценки обоснованности120• Уравнения Гамильтона являются записью второго закона Ньютона через переменные состояния имоментыdx∂H=dt∂rdr∂H=−dt∂xИнтегрирование уравнений Гамильтона• При динамическом изменении замкнутой системы гамильтониан H является постоянным по времени(закон сохранения энергии)• Изменение системы описывается функциями x(t) и r(t), связанными уравнениями Гамильтона• При численном решении уравнений получаемr(t + ε/2) = r(t) −ε ∂E(x(t))2 ∂xx(t + ε) = x(t) + εr(t + ε/2)r(t + ε) = r(t + ε/2) −ε ∂E(x(t + ε))2 ∂x• Полученные решения приблизительно описывают одну из линий уровня функции ГамильтонаРис.

11.4. Исходное распределение (вверху) и линии уровня соответствующего ему гамильтониана. Численное решение уравнений Гамильтона приводит к получению последовательности точек, находящихся на одной линии уровняСхема генерации выборки• Точки (x(t1 ), . . . , x(tn )) представляют собой равномерную выборку из множества {x|p(x) ≥ C0 }• Чтобы получить выборку из распределения p(x) через каждые m ¿ n итераций значение моментовберется из распределения p(r) = Z1r exp(−K(r)) = N (r|0, I)• Такая схема генерации выборки позволяет быстро найти области с большим значением p(x) и получить репрезентативную выборку из этих областейГлава 12Графические модели. Гауссовскиепроцессы в машинном обученииВ первой части главы описываются графические модели, являющиеся основным средством анализа структурированной информации методами машинного обучения.

Кратко описаны понятия условной независимости, ориентированных (байесовские сети) и неориентированных (марковские сети) графических моделей. Вторая часть главы посвящена гауссовским случайным процессам (полям) и их применению длярешения задачи восстановления регрессии и классификации. Отдельное внимание уделено автоматическому подбору наиболее обоснованной ковариационной функции случайного поля по конечному множествунаблюдений.121Глава 12. Графические модели.

Гауссовские процессы в машинном обучении12.112.1.1122Ликбез: Случайные процессы и условная независимостьСлучайные процессыСлучайные процессы• Случайным процессом будем называть индексированное множество случайных величин ξ(ω) ={ξt (ω)|t ∈ T }• Иногда используется нотация ξ(ω, t)• Первоначально T ⊂ R, а переменная t ассоциировалась со временемСлучайный процесс в этом случае удобно представлять как некоторую случайную величину, меняющуюся во времени• Если T ⊂ Rd , то случайный процесс обычно называют случайным полемСлучайный процесс в этом случае удобно представлять как некоторую случайную величину, меняющуюся в пространствеДвойственная природа случайного процесса• При фиксированном времени t = t0 процесс представляет собой обычную случайную величинуX(ω) = ξ(ω, t0 )• При фиксированном элементарном событии ω = ω0 процесс представляет собой функцию, называемую реализацией случайного процессаf (t) = ξ(ω0 , t)• Таким образом, случайный процесс обладает как вероятностными, так и функциональными характеристиками• В частности, можно говорить о математическом ожидании, дисперсии процесса в фиксированныймомент времени, а также рассматривать производные и интегралы от реализаций процессаВероятностные характеристики случайного процесса• Среднее значение процессаm(t) = Eξ(ω, t)• Ковариационная функция процессаC(t1 , t2 ) = Cov(ξ(ω, t1 ), ξ(ω, t2 )),обладающая следующими свойствамиC(t, t) = Dξ(ω, t) ≥ 0,C(t1 , t2 ) ≤pC(t1 , t1 )C(t2 , t2 )• Процесс называется стационарным, если его вероятностные характеристики не зависят от времени,в частностиC(t, t + τ ) = C(0, τ ) = C(τ ), ∀tБольшинство теорем в теории случайных процессов доказано для стационарных процессовГлава 12.

Графические модели. Гауссовские процессы в машинном обучении12.1.2123Условная независимостьУсловная независимость случайных величин• Случайные величины x и y называются условно независимыми от z, еслиp(x, y|z) = p(x|z)p(y|z)• Другими словами вся информация о взаимозависимостях между x и y содержится в z• Заметим, что из безусловной независимости не следует условная и наоборот• Основное свойство условно независимых случайных величинp(z|x, y) =p(x, y|z)p(z)p(x|z)p(y|z)p(z)==p(x, y)p(x, y)p(x|z)p(z)p(y|z)p(z)p(z|x)p(z|y)1 p(z|x)p(z|y)==p(x, y)p(z)p(z)p(x)p(y)p(x, y)Zp(z)Пример• Рассмотрим следующую гипотетическую ситуацию: римские легионы во главе с императором атакуют вторгшихся варваров• Легионы могут победить варваров, а могут быть разгромлены (Рим в этом случае весьма вероятнобудет уничтожен).

В свою очередь император может уцелеть, а может погибнуть в сражении• События «гибель императора» и «уничтожение Рима» не являются независимыми• Однако, если нам дополнительно известен исход битвы с варварами, эти два события становятсянезависимыми• В самом деле, если легионы битву проиграли, то судьба Рима мало зависит от того, был ли императорубит в сражении12.212.2.1Графические моделиОриентированные графыБайесовские сетиTДВРЗРис. 12.1.

Графическая модель, соответствующая примеру про Джона и колокольчик для воров (см. главу 6)• Во многих задачах взаимосвязи между наблюдаемыми и скрытыми переменными носят сложныйхарактерГлава 12. Графические модели. Гауссовские процессы в машинном обученииИ124РБРис. 12.2. Графическая модель «Варвары и Рим времен заката»• В частности, между отдельными переменными существуют вероятностные зависимости• Если удается выделить причинно-следственные связи между переменными, то такие взаимосвязиудобно изображать в виде ориентированных графов• Ориентированные графы также часто называются байесовскими сетямиСовместное распределение переменныхx1x2x3x4x5x6x7Рис.

12.3.Рассмотрим графическую модель, изображенную на рис. 12.3. Совместное распределение системыпеременных задается выражениемp(x1 , x2 , x3 , x4 , x5 , x6 , x7 ) =p(x1 )p(x2 )p(x3 )p(x4 |x1 , x2 , x3 )p(x5 |x1 , x3 )p(x6 |x4 )p(x7 |x4 , x5 ).Совместное и условные распределения• В общем случае, совместное распределение для графа с n вершинамиp(x) =nYi=1p(xi |pai ),Глава 12. Графические модели. Гауссовские процессы в машинном обучении125где pai — множество вершин-родителей xi• Основной задачей, возникающей при работе с графическими моделями, является подсчет условныхвероятностейp(unobs(x)|obs(x)),где obs(x) — множество наблюдаемых переменных, а unobs(x) — множество скрытых переменных• При работе с графическими моделями широко используются sum- и product- ruleВычисление условных распределений I• Вернемся к иллюстрации графической модели из семи переменных• Пусть нам необходимо найти распределение (x5 , x7 ) при заданных значениях x1 , x2 , x4 и неизвестныхx3 , x6 (см.

рис. 12.4)x1x2x3x4x5?x6?x7Рис. 12.4.Вычисление условных распределений II• По определению условной вероятностиp(x5 , x7 |x1 , x2 , x4 ) =p(x1 , x2 , x4 , x5 , x7 )p(x1 , x2 , x4 )• Расписываем знаменательp(x1 , x2 , x4 ) = p(x1 )p(x2 )p(x4 |x1 , x2 ) = {Sum rule}Zp(x1 )p(x2 ) p(x4 |x1 , x2 , x3 )p(x3 )dx3Глава 12. Графические модели. Гауссовские процессы в машинном обучении126• Аналогично числительp(x1 , x2 , x4 , x5 , x7 ) = p(x1 )p(x2 )p(x4 |x1 , x2 )p(x5 |x1 )p(x7 |x5 , x4 ) =µZ¶ µZ¶p(x4 |x1 , x2 , x3 )p(x3 )dx3p(x5 |x1 , x3 )p(x3 )dx3 p(x7 |x5 , x4 )p(x1 )p(x2 )• Для взятия возникающих интегралов обычно пользуются методами Монте Карло• Таким образом, условное распределение выражено через известные атомарные распределения видаp(xi |pai )12.2.2Три элементарных графаГраф 1cabРис.

12.5.• Аналогия: Рим, император и варвары• Переменные a и b условно независимы от c (см. рис. 12.5)• Возможна маргинализация (исключение переменной)Zp(a, b) = p(a|c)p(b|c)p(c)dc 6= p(a)p(b)Граф 2acbРис. 12.6.• Аналогия: данные t, параметры алгоритма w, параметры модели (гиперпараметры) α в байесовскомобучении• Переменные a и b условно независимы от c (см. рис. 12.6)• Возможна маргинализация (исключение переменной)Zp(a, b) = p(a) p(b|c)p(c|a)dc 6= p(a)p(b)Глава 12. Графические модели. Гауссовские процессы в машинном обученииa127bcРис. 12.7.Граф 3• Аналогия: Вор, землятрясение и сигнализация• Переменные a и b независимы, т.е. p(a, b) = p(a)p(b), но не условно независимы (см. рис.

12.7)!• Зависимость p(c|a, b) не может быть выражена через p(c|a) и p(c|b), хотя обратное верноZp(c|a) = p(c|a, b)p(b)db12.2.3Неориентированные графыМарковские поля• Неориентированные графические модели также называются Марковскими полями• Ребра между узлами графа иллюстрируют взаимозависимость между переменными• Обычно используются для анализа массива данных, имеющего структуру, например сигнала, изображения, сложного объектаСкрытые марковские поля• Наиболее известным примером неориентированной графической модели являются скрытые марковские поля, используемые, в частности, для анализа речевых сигналов (рис.