2010 Лекции МОТП (Ветров) (1185317), страница 9
Текст из файла (страница 9)
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сети• При использовании ориентированных графовопределение условной независимости не очень просто• В марковских сетях это проще. На рисунке A и Bнезависимы при условии C• Ребра графа связывают переменные, между которымисуществуют непосредственные (а не опосредованные)зависимостиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетямиCBAФакторизация в марковских сетяхЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• Пусть yi и yj независимы при условии, что всеостальные переменные нам известны, т.е.p(yi , yj |Y{i,j} ) = p(yi |Y{i,j} )p(yj |Y{i,j} )• Это означает, что yi и yj не соединены ребром (иначе небыло бы условной независимости)• Запишем совместное распределение и применимправило умножения вероятностейp(Y) = p(yi , yj |Y{i,j} )p(Y{i,j} ) = p(yi |Y{i,j} )p(yj |Y{i,j} )p(Y{i,j} )• Таким образом, переменные, не соединенные ребрами,входят в разные множители совместногораспределенияПотенциалы марковской сетиЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• В общем виде совместное распределение значений элементовсети записывается с помощью неотрицательных потенциальныхфункций, определенных на максимальных кликахXY1YψC (YC ), Z =ψC (YC ), ψC (YC ) ≥ 0p(Y) =Z CYC• На рисунке синяя клика является максимальной, а зеленая —нет. Совместное распределение имеет вид1p(Y) = ψ1 (y1 , y2 , y3 )ψ2 (y2 , y3 , y4 )Zy1y2y3y4Потенциальная функция не обязана иметь вероятностную природу, ночем она больше, тем более вероятны соответствующие значенияпеременных. Обычно потенциальные функции задаютсяпользователем исходя из априорных предпочтений тех или иныхконфигураций переменных.
Реже — настраиваются по даннымЭнергетическая нотацияЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• Иногда удобно ввести обозначениеψC (YC ) = exp(−EC (YC )), где EC (YC ) имеет смысл энергии• Тогда задача нахождения наиболее вероятногосостояния системы сводится к задаче минимизацииполной энергии системы1YψC (YC ) =Z C!ÃXXarg max exp −EC (YC ) = arg minEC (YC )arg max p(Y) = arg maxCC• Заметим, что в отличие от байесовских сетей дляполного задания графической модели необходимознать (или конструктивно уметь подсчитывать)нормировочную константу ZПланЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделейМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиФильтрация изображенийЛекция 2.Графическиемодели. ОбщеепредставлениеxjВетровtjЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• Рассмотрим задачу фильтрации изображения.
Пусть xi ∈ {−1, 1}— наблюдаемые пиксели бинарного изображения, а ti ∈ {−1, 1} —истинные значения пикселей• Введем энергию системыE(X, T) = hXiti − βXi,jti tj − ηXt i xi ,iгде h ∈ R позволяет отразить априорные предпочтения в пользутого или иного цвета (например, указать, что желтый цветвстречается чаще, чем синий), β > 0 выражает степеньзависимости между соседними пикселями, а η > 0 показываетинтенсивность шумаРазметка областей IЛекция 2.Графическиемодели. ОбщеепредставлениеВернемся к примеру со странамиВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетямиСовместная плотность задается формулойp(X) =1ψ1 (F, G, W)ψ2 (G, O, W)ψ3 (W, O, L, I)ψ4 (I, S, O)×Z× ψ5 (S, I, A)ψ6 (S, C)ψ7 (M, I)Разметка областей IIЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• Предположим, что переменные могут принимать одно изчетырех значений {red, yellow, blue, green}• Требование несовпадающих цветов областей эквивалентноусловию равенства нулю потенциала, если хотя бы два егоаргумента имеют одинаковое значение, напримерψ5 (red, blue, red) = 0Разметка областей IIIЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетямиМы можем снизить число нежелаемых цветовых переходов(например, из желтого в красный) снизив соответствующие значенияпотенциалов ψ7 (red, yellow), ψ7 (yellow, red), ψ6 (red, yellow) и ψ6 (yellow, red)Разметка областей IVЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетямиМы можем искусственно способствовать окраске отдельных регионовв выбранные цвета, вводя индивидуальные множители, напримерψ1 (F, G, W) = φ1 (F, G, W)φ2 (F)φ3 (W).Теперь можно увеличить значение φ2 (blue) и φ3 (green), чтобыполучить политическую карту, привычную российскому глазуПримеры марковских сетейЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• Изображения• Социальные сети• Случайные поля• Карты сайтов• Условные случайные поля• и др.ПланЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделейМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиМарковские vs.
Байесовские сетиЛекция 2.Графическиемодели. ОбщеепредставлениеВетровСходства и различия двух типов графических моделейЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетямиСвойствоМарковские сетиБайесовские сетиФормаПроизв. потенциалов Произв. потенциаловПотенциалыПроизвольныеУсл. вероятностиЦиклыРазрешеныЗапрещеныНормировкаZ =?Z=1Условная нез-ть Легко проверяемаСложнееПолнотанетнетАнализMCMC, BP, и т.д.. Сводить к марковскимСуществующее положение делЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• На сегодняшний день существуют эффективныеалгоритмы (sum-product, max-product) анализаациклических графов (деревьев), решающие все триосновные задачи анализа графических моделей• Частным случаем деревьев являются графы-цепочки,характеризующие, например, сигналы во времени• В случае наличия циклов сложность точныхалгоритмов резко возрастает• Для анализа графов с циклами в основномиспользуются приближенные методы (loopy BP, EP,MCMC)• В некоторых частных случаях для анализациклических сетей существуют эффективные точныеалгоритмы, например, разрезы графовСведение байесовских сетей к марковскимЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями• Наиболее разработаны в настоящее время методыанализа марковских сетей• Байесовскую сеть можно легко свести к марковской спотерей информации, переженив всех родителей(морализация)• Заметим, что в приведенном примере все полезныесвойства оказались потеряны, и мы получилибанальную клику, в которой все зависят от всехy1y2y2y1y3y3y4y4Лекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбезОсновыпримененияСММЛекция 3. Скрытые марковские модели.Часть 1ЕМ-алгоритмЮ. И. Журавлев1 , Д. П.
Ветров11МГУ, ВМиК, каф. ММПКурс «Математические основы теориипрогнозирования»ПланЛекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритм1 ЛикбезМетод динамического программирования2 Основы применения СММОпределение СММОбучение СММ с учителемАлгоритм Витерби3 ЕМ-алгоритмГрафические модели с неполными даннымиРазделение гауссовской смесиПланЛекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбезМетоддинамическогопрограммированияОсновыпримененияСММЕМ-алгоритм1 ЛикбезМетод динамического программирования2 Основы применения СММОпределение СММОбучение СММ с учителемАлгоритм Витерби3 ЕМ-алгоритмГрафические модели с неполными даннымиРазделение гауссовской смесиЗадача объезда странЛекция 3.Скрытыемарковскиемодели.
Часть 1x11x12x1kx21x22x2kВетровЛикбезМетоддинамическогопрограммированияОсновыпримененияСММxfxsЕМ-алгоритмxn1xn2Страна 1 Страна 2xnkСтрана k• Рассмотрим такую задачу: необходимо в определеннойпоследовательности объехать k стран, в каждой из которыхпровести одну ночь в отеле, потратив минимум денег• Если в каждой стране имеется n городов, то задача сводится кперебору nk вариантовФункция БеллманаЛекция 3.Скрытыемарковскиемодели.
Часть 1x11x12x1kВетровx21x22x2kЛикбезМетоддинамическогопрограммированияxfxsОсновыпримененияСММЕМ-алгоритмxn1xn2Страна 1 Страна 2xnkСтрана k• Пусть цена билета между городами xij и xi+1,l задается функциейf (xij , xi+1,l ), а цена ночлега в городе — функцией h(xij )• Подсчитаем функцию Беллмана V(x), определяемуюрекуррентно: V(xs ) = 0£¤V(xi+1,l ) = min V(xij ) + f (xij , xi+1,l ) + h(xi+1,l )j• Физический смысл функции Беллмана это наименьшая суммаденег, которую нужно потратить, чтобы добраться из города xs вгород xi+1,l (легко показать по индукции)Динамическое программированиеЛекция 3.Скрытыемарковскиемодели. Часть 1Ветровx11x12x1kx21x22x2kЛикбезМетоддинамическогопрограммированияxfxsОсновыпримененияСММЕМ-алгоритмxn1xn2xnkСтрана 1 Страна 2Страна k• Определим также функцию S(x), возвращающую город, откудамы приехали в город x: S(xs ) = ∅£¤S(xi+1,l ) = arg min V(xij ) + f (xij , xi+1,l ) + h(xi+1,l )j• Тогда оптимальный путь (x1∗ , x2∗ , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
