2010 Лекции МОТП (Ветров) (1185317), страница 8
Текст из файла (страница 8)
ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сети• Не во всех случаях существуют строгие алгоритмывывода и обучения графических моделей• Даже там, где они существуют, их применение можетоказаться невозможно из-за высоких вычислительныхтребований и требований к памяти• В настоящее время в мире активно разрабатываютсяприближенные эффективные методы обучения ипринятия решения в графических моделях (MonteCarlo Markov chains, Variational bounds, Expectationpropagation, Belief propagation, и др.)ПланЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделей3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиСовместное распределение переменныхЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сетиСовместное распределение системы переменных задаетсявыражениемp(Y) = p(y1 , y2 , y3 , y4 , y5 , y6 , y7 ) =p(y1 )p(y2 )p(y3 )p(y4 |y1 , y2 , y3 )p(y5 |y1 , y3 )p(y6 |y4 )p(y7 |y4 , y5 ).Совместное и условные распределенияЛекция 2.Графическиемодели.
ОбщеепредставлениеВетров• В общем случае совместное распределение дляориентированного графа с n вершинамиЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сетиp(Y) =nYp(yi |pai ),i=1где pai — множество вершин-родителей yi• Обычно предполагается, что атомарные условныераспределения p(yi |pai ) известны• Зная атомарные распределения, мы можем рассчитать(хотя бы теоретически) любые условные вероятностиодних подмножеств переменных по другимподмножествам переменныхВычисление условных распределений IЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сети• Вернемся к иллюстрации графической модели из семипеременных• Пусть нам необходимо найти распределение (y5 , y7 ) призаданных значениях y1 , y2 , y4 и неизвестных y3 , y6Вычисление условных распределений IIЛекция 2.Графическиемодели.
Общеепредставление• По определению условной вероятностиp(y5 , y7 |y1 , y2 , y4 ) =ВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сетиp(y1 , y2 , y4 , y5 , y7 )p(y1 , y2 , y4 )• Расписываем знаменательp(y1 , y2 , y4 ) = p(y1 )p(y2 )p(y4 |y1 , y2 ) = {Sum rule}Zp(y1 )p(y2 ) p(y4 |y1 , y2 , y3 )p(y3 )dy3• Аналогично числительp(y1 , y2 , y4 , y5 , y7 ) = p(y1 )p(y2 )p(y4 |y1 , y2 )p(y5 |y1 )p(y7 |y5 , y4 ) = p(y1 )×µZ¶ µZ¶p(y2 )p(y4 |y1 , y2 , y3 )p(y3 )dy3p(y5 |y1 , y3 )p(y3 )dy3 p(y7 |y5 , y4 )• Для взятия возникающих интегралов обычно пользуютсяразличными аппроксимационными методами• Таким образом, условное распределение выражено черезизвестные атомарные распределения вида p(yi |pai )ПланЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделей3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиОсобенности использования байесовскихсетейЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сети• По смыслу построения байесовские сети не могутсодержать ориентированные циклы, т.к. это будетнарушать правило умножения вероятностей• Главным достоинством графических моделей являетсяотносительно простое выделение условно-независимыхвеличин, которое облегчает дальнейший анализ,позволяя значительно уменьшить количествофакторов, влияющих на данную переменную• В байесовских сетях сделать это несколько сложнее,чем в марковскихГраф 1Лекция 2.Графическиемодели.
ОбщеепредставлениеcВетровЛикбезГрафическиемоделиabБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сети• Аналогия: Рим (a), император (b) и варвары (c)• Переменные a и b независимы при заданном c• Возможна маргинализация (исключение переменной)Zp(a, b) =p(a|c)p(b|c)p(c)dc 6= p(a)p(b)Граф 2Лекция 2.Графическиемодели. ОбщеепредставлениеВетровacbЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользования• Аналогия: хорошая работа (a), премия (c), яхта (b)• Переменные a и b независимы при заданном c• Возможна маргинализация (исключение переменной)ZМарковские сетиp(a, b) = p(a)p(b|c)p(c|a)dc 6= p(a)p(b)Граф 3Лекция 2.Графическиемодели.
ОбщеепредставлениеabВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сетиc• Аналогия: вор (a), землетрясение (b) и сигнализация(c)• Переменные a и b независимы, т.е. p(a, b) = p(a)p(b), ноне условно независимы!• Зависимость p(c|a, b) не может быть выражена черезp(c|a) и p(c|b), хотя обратное верноZp(c|a) = p(c|a, b)p(b)dbПланЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделей3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиПример нестрогих вероятностныхрассуждений IЛекция 2.Графическиемодели.
ОбщеепредставлениеabВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сетиc• Рассмотрим последний граф подробнее. Введемобозначения событий: «сигнализация сработала/несработала» (s/¬s), «вор есть/вора нет» (v/¬v) и«землетрясение произошло/не произошло» (z/¬z)• Пусть p(s|v, ¬z) = p(s|v, z) = 1, p(s|¬v, z) = 0.1,p(s|¬v, ¬z) = 0, p(v) = 2 × 10−4 , p(z) = 10−2 .Графическая модель полностью определенаПример нестрогих вероятностныхрассуждений IIЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезДопустим, мы получили сигнал тревоги.
Необходимооценить вероятность того, что в квартире вор p(v|s)ГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сетиp(v|s) =1p(s|v)p(v)p(s|v)p(v) =Zp(s|v)p(v) + p(s|¬v)p(¬v)p(s|¬v) = p(s|¬v, z)p(z) + p(s|¬v, ¬z)p(¬z) = 10−3p(s|v) = 115p(v|s) ≈ , p(¬v|s) ≈ , Z ≈ 1.2 × 10−366Пример нестрогих вероятностныхрассуждений IIIЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сетиФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользования• Пусть теперь дополнительно стало известно, чтопроизошло землетрясение.
Как изменится вероятностьтого, что в квартире вор p(v|s, z)?1p(s|v, z)p(v|z), p(v|z) = p(v)ZZ = p(s|v, z)p(v|z) + p(s|¬v, z)p(¬v|z) =p(v|s, z) =1 × 2 × 10−4 + 0.1 × (1 − 2 × 10−4 ) = 0.1002p(v|s, z) = 0.002, p(¬v|s, z) = 0.998Марковские сети• Заметим, что события z и v перестали бытьнезависимыми, и добавление сведений о значении zменяет знания о значении v. Это называется эффектомоправдания (explaining away)Примеры байесовских сетейЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбез• Скрытые марковские моделиГрафическиемодели• Фильтр КалманаБайесовские сети• Экспертные системыФакторизациябайесовскихсетейТриэлементарныхграфаПримериспользованияМарковские сети• Вероятностный РСА• Смеси экспертов• Факторный анализ• и др.ПланЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделейМарковские сетиПотенциалы иэнергия кликПримериспользованияСвязь сбайесовскимисетями3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиНеориентированные графические моделиЛекция 2.Графическиемодели.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
