2010 Лекции МОТП (Ветров) (1185317), страница 7
Текст из файла (страница 7)
p(an−1 |an )p(an )• Можно показать (Jaynes, 1995), что правиласуммирования и произведения вероятностей являютсяединственными возможными операциями,позволяющими рассматривать вероятности какпромежуточную ступень между истиной и ложьюАприорные и апостериорные сужденияЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети• Предположим, мы пытаемся изучить некотороеявление• У нас имеются некоторые знания, полученные до (лат.a priori) наблюдений/эксперимента.
Это может бытьопыт прошлых наблюдений, какие-то модельныегипотезы, ожидания• В процессе наблюдений эти знания подвергаютсяпостепенному уточнению. После (лат. a posteriori)наблюдений/эксперимента у нас формируются новыезнания о явлении• Будем считать, что мы пытаемся оценить неизвестноезначение величины θ посредством наблюденийнекоторых ее косвенных характеристик x|θФормула БайесаЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети• Знаменитая формула Байеса (1763 г.) устанавливаетправила, по которым происходит преобразованиезнаний в процессе наблюдений• Обозначим априорные знания о величине θ за p(θ)• В процессе наблюдений мы получаем серию значенийx = (x1 , . . . , xn ). При разных θ наблюдение выборки xболее или менее вероятно и определяется значениемправдоподобия p(x|θ)• За счет наблюдений наши представления о значении θменяются согласно формуле Байесаp(θ|x) =p(x|θ)p(θ)p(x|θ)p(θ)=Rp(x)p(x|θ)p(θ)dθ• Заметим, что знаменатель не зависит от θ и нуженисключительно для нормировки апостериорнойплотностиПланЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделей3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиУсловная независимость случайных величинЛекция 2.Графическиемодели.
Общеепредставление• Случайные величины x и y называются условнонезависимыми от z, еслиВетровp(x, y|z) = p(x|z)p(y|z)ЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети• Другими словами вся информация овзаимозависимостях между x и y содержится в z• Заметим, что из безусловной независимости не следуетусловная и наоборот• Основное свойство условно независимых случайныхвеличинp(z|x, y) =p(x|z)p(y|z)p(z)p(x, 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)ПримерЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети• Рассмотрим следующую гипотетическую ситуацию: римскиелегионы во главе с императором атакуют вторгшихся варваров• События «гибель императора» и «уничтожение Рима» неявляются независимыми• Однако, если нам дополнительно известен исход битвы сварварами, эти два события становятся независимыми• В самом деле, если легионы битву проиграли, то судьба Римамало зависит от того, был ли император убит в сраженииПланЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделей3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиКлассическая задача машинного обученияЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сети• Задачу машинного обучения можно трактовать каквосстановление неизвестных зависимостей междунаблюдаемымми переменными X и скрытыми(латентными) переменными T. В случае обучения сучителем такое восстановление производится пообучающей выборке Y• В классических задачах машинного обученияпредполагается, что обучающая выборкасформирована из однородных и независимых объектовY = {(xi , ti )}ni=1• До недавнего времени вероятностные методыобработки данных ограничивались только такимпростейшим случаем, а изложение каждого методаначиналось со слов «Предположим, что нам данавыборка из независимых одинаково распределенныхслучайных величин...»Задачи со структурными ограничениямиЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сети• Во многих задачах взаимосвязи между наблюдаемымии скрытыми переменными носят сложный характер• В частности, между отдельными переменнымисуществуют вероятностные зависимости• Факт зависимости переменных друг от друга удобноотображать с помощью неориентированного графа(марковской сети)• Если связи между переменнымипричинно-следственные, то их удобно отображать ввиде ориентированных графов (байесовских сетей)• Основным средством работы с графическимимоделями служит аппарат теории вероятностей, в еебайесовской интерпретацииПростой примерЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сетиЗадача о раскраске областей на плоскости так, чтобыникакие соседние не были окрашены в одинаковый цветПростой примерЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сетиЗадача о раскраске областей на плоскости так, чтобыникакие соседние не были окрашены в одинаковый цветПростой примерЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровТакая задача легко формулируется в терминахграфической модели, в которой каждая вершина графаможет находиться в одном из четырех состоянийЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сетиВопрос залу: почему четырех?Примеры задач со структурными связямиЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбез• Обработка изображений, сигналовГрафическиемодели• Анализ социальных сетейЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сети• Поиск залежей полезных ископаемых• Анализ естественных языков• Биомедицина и биоинформатика• Веб-поиск• и др.ПланЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделей3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиГрафические моделиЛекция 2.Графическиемодели.
ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сети• Графическая модель представляет собойориентированный или неориентированный граф• Вершины графа соответствуют переменным• Ребра графа соответствуют вероятностнымотношениям, определяющим непосредственныезависимостиГлавные задачи в анализе графическихмоделейЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиЗадачи соструктурнымиограничениямиОсновныепроблемы ванализеграфическихмоделейБайесовские сетиМарковские сетиОбозначим совокупность наблюдаемых переменных X, аненаблюдаемых переменных T. Основными задачами ванализе графических моделей являются• Подсчет условного распределения на значенияотдельной скрытой переменной p(ti |X)−?• Нахождение наиболее вероятной конфигурациискрытых переменных p(T|X) → maxT• Оценка адекватности выбранной графической моделиданным p(X)−?Трудности, возникающие при использованииграфических моделейЛекция 2.Графическиемодели.