'

БАЙЕСОВСКИЕ СЕТИ:

Понравилась презентация – покажи это...





Слайд 0

БАЙЕСОВСКИЕ СЕТИ: Вероятностная семантика и оптимизационные алгоритмы в логико-вероятностном выводе 08 октября 2004 г Александр Львович Тулупьев, СПИИРАН Дмитрий Александрович Никитин, СПИИРАН Сергей Игоревич Николенко, СПбГУ


Слайд 1

ПЛАН ИЗЛОЖЕНИЯ Объект, предмет и контекст исследования Обозначения Вероятностная логика Фрагменты знаний Байесовские сети доверия (сжато) Алгебраические байесовские сети ФЗ АБС непротиворечивость, априорный и апостериорный вывод, устойчивость АБС непротиворечивость, априорный и апостериорный вывод Презентация Д.А. Никитина Презентация С.И. Николенко Применение байесовских сетей Заключение


Слайд 2

ОБЪЕКТ ИССЛЕДОВАНИЯ Распределение вероятностей (или их семейство) над пропозициональными формулами, в общем виде представимое как


Слайд 3

ПРЕДМЕТ ИССЛЕДОВАНИЯ Изучаем только распределения, которые допускают декомпозицию


Слайд 4

КОНТЕКСТ ИССЛЕДОВАНИЯ Знания хранятся и передаются фрагментами (паттернами) Атомарные высказывания о предметной области представляем пропозициональными формулами Меру их истинности и тесноту связи между ним характеризуем с помощью вероятности Фактически, мы пытаемся изучать один из возможных классов моделей баз фрагментов знаний с неопределенностью


Слайд 5

ПРАГМАТИКА Изучая свойства нашего предмета исследования и разрабатывая алгоритмы, мы опираемся на методы математики и теоретической информатики. Тем не менее, наша конечная цель --- дать спецификацию программисту, чтобы он воплотил результаты исследований в программном приложении. При этом алгоритмы и спецификации хотелось бы писать так, чтобы максимально учитывать достижения современной практической информатики: возможности сред разработки приложений, математических пакетов, алгоритмических библиотек…


Слайд 6

НЕКОТОРЫЕ ОБОЗНАЧЕНИЯ Аргументное место Цепочка конъюнкций Положит. означенная цеп. конъ. Набор атомарных пропозиций Кванты Пропоз. формулы над множеством А Идеал цепочек конъюнкций --- модель фрагмента знаний АБС


Слайд 7

ЕСЛИ БЫТЬ ЧРЕЗМЕРНО ФОРМАЛЬНЫМ


Слайд 8

ПРИМЕР (1) . , , , .


Слайд 9

ПРИМЕР (2) . , , ,


Слайд 10

ВЕРОЯТНОСТНАЯ ЛОГИКА Подход по Н. Нильссону (1986 г.) Более глубокая формализация дана в работах коллектива Фагина, Хальперна, Миггидо (пригодня для рассуждений об оценках сложности) Другие глубокие формализации Спор о приоритетах (de Finetti…) Дж. Буль --- тоже писал о вероятности пропозиции


Слайд 11

НАБОР ПРОПОЗИЦИЙ


Слайд 12

Возможные миры


Слайд 13

Допустимые миры


Слайд 14

Вероятность истинности В рамках подхода Н. Нильссона мы рассуждаем о вероятности истинности пропозиции; Для краткости говорят вероятность пропозиции


Слайд 15

Подход Н. Нильссона Формальное изложение


Слайд 16

Теорема о СДНФ


Слайд 17

КВАНТЫ: Множество элементарных событий


Слайд 18

ВЕРОЯТНОСТЬ ПРОПОЗИЦИИ


Слайд 19

ФРАГМЕНТ ЗНАНИЙ


Слайд 20

ФЗ --- ФИЛОСОФИЯ ВОПРОСА Эксперты связывают 1—2—3… пропозиции в своих рассуждениях (свойство переработки, передачи, хранения знаний человеком) В статистике мы можем с какой-то степенью уверенности рассуждать об 1—2—3… пропозициях (иначе придется делать объем выборки слишком большим) Фактически нам приходится рассуждать о наборах (базах) фрагментов знаний с неопределенностью А работаем мы с различными моделями фрагментов знаний (моделями моделей предметной области)


Слайд 21

МОДЕЛЬ ФЗ В БСД


Слайд 22

МОДЕЛЬ ФЗ В АБС


Слайд 23

БАЙЕСОВСКИЕ СЕТИ ДОВЕРИЯ В необходимом объеме (максимально сжатом)


Слайд 24

БСД: ДОПУСТИМАЯ ТОПОЛОГИЯ


Слайд 25

БСД: FEEDBACK CYCLES


Слайд 26

АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ


Слайд 27

ФЗ АБС: идеал цепочек конъюнкций


Слайд 28

ОПЕРАЦИИ В ФЗ АБС Поддержание непротиворечивости Априорный вывод Апостериорный вывод Анализ устойчивости (чувствительности)


Слайд 29

НЕПРОТИВОРЕЧИВОСТЬ ФЗ АБС


Слайд 30

ТОЧЕЧНЫЕ ОЦЕНКИ: распределение вероятностей (1)


Слайд 31

ТОЧЕЧНЫЕ ОЦЕНКИ: распределение вероятностей (2)


Слайд 32

ИНТЕРВАЛЬНЫЕ ОЦЕНКИ: семейство распределений(1)


Слайд 33

ИНТЕРВАЛЬНЫЕ ОЦЕНКИ: семейство распределений (2)


Слайд 34

ИНТЕРВАЛЬНЫЕ ОЦЕНКИ: поддержание непротиворечивости


Слайд 35

АПРИОРНЫЙ ВЫВОД В ФЗ


Слайд 36

АПРИОРНЫЙ ВЫВОД: точечные оценки Вероятность любой формулы, построенной над атомарными пропозициями из заданного ФЗ, можно линейно выразить через вероятности элементов этого ФЗ. В точечном случае, таким образом, априорный вывод сводится к прямому вычислению вероятности новой пропозиции через вероятности известных.


Слайд 37

АПРИОРНЫЙ ВЫВОД: интервальные оценки Вероятность любой формулы, построенной над атомарными пропозициями из заданного ФЗ, можно линейно выразить через вероятности элементов этого ФЗ. В интервальном случае вероятность новой формулы придется рассмотреть как целевую функцию соответствующей ЗЛП, найти максимум и минимум этой функции В результате решения оптимизационной задачи будет получена интервальная оценка вероятности истинности новой формулы.


Слайд 38

АПОСТЕРИОРНЫЙ ВЫВОД В ФЗ


Слайд 39

СВИДЕТЕЛЬСТВО Детерминированное свидетельство: Недетерминированное свидетельство


Слайд 40

КОРТЕЖ СВИДЕТЕЛЬСТВ Детерминированные свидетельства: Недетерминированные свидетельства


Слайд 41

ДВЕ ЦЕЛИ апостериорного вывода Оценка вероятности свидетельства (кортежа свидетельств) над заданным ФЗ Оценка апостериорных вероятностей элементов ФЗ при заданном свидетельстве (кортеже свидетельств)


Слайд 42

АПОСТЕРИОРНЫЙ ВЫВОД: формулы … более подробно возникающие задачи оптимизации будут рассмотрены в специальной части презентации (Д. А. Никитин)


Слайд 43

УСТОЙЧИВОСТЬ (чувствительность)


Слайд 44

УСТОЙЧИВОСТЬ ПРОЦЕССОВ: «философия» вопроса Поддержание непротиворечивости Априорный вывод Апостериорный вывода


Слайд 45

ПОДДЕРЖАНИЕ НЕПРОТИВОРЕЧИВОСТИ НЕУСТОЙЧИВО В точечном случае --- контрпример В интервальном случае --- исследуем


Слайд 46

АПРИОРНЫЙ ВЫВОД УСТОЙЧИВ Вычислительные эксперименты показывают устойчивость как в случае точечных, так и в случае интервальных оценок (относительно допустимых вариаций) Показатели, на которые мы опираемся: Изменение результата вывода (т.сл.) Изменение границ результата вывода (и. сл.) Изменение величины интервала, представляющего результат (и. сл.) Эмпирическое определение показателей сводится к решению задач линейного программирования


Слайд 47

Апостериорный вывод: поиск показателей устойчивости Относительно чего устойчивость Что можно «варьировать», «допустимо варьировать», как это формализовать Изменение каких целевых переменных отслеживать Какие (метрические) пространства выбирать (хотим получать удобные задачи оптимизации)


Слайд 48

АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ (АБС)


Слайд 49

АБС: определение Алгебраическая байесовская сеть состоит множества идеалов цепочек конъюнкций, построенных над подмножествами одного и того же множества атомарных пропозициональных формул. Идеалы могут иметь общие элементы. Как правило рассматривают только связные АБС, поскольку компоненты связности можно рассмотреть как отдельные самостоятельные АБС.


Слайд 50

АБС: изображение детализированное


Слайд 51

АБС: изображение схематическое


Слайд 52

АБС: изображение ФЗ и связей между ними


Слайд 53

АБС: степени непротиворечивости Непротиворечивость локальная Непротиворечивость внутренняя Непротиворечивость внешняя Непротиворечивость в целом k-непротиворечивость


Слайд 54

АБС: локальная непротиворечивость АБС еще и нет Непротиворечив каждый отдельный ФЗ, вошедший в АБС


Слайд 55

Внутренняя и внешняя непротиворечивость Неожиданное открытие


Слайд 56

Внутренняя непротиворечивость АБС Ранее использовавшееся определение … когда выполняется требование локальной непротиворечивости, и оценка каждого отдельного элемента, входящего в более чем один ФЗ, согласована;


Слайд 57

Внешняя непротиворечивость АБС Ранее использовавшееся определение … когда выполнено требование локальной непротиворечивости и оценки, требующие согласования, рассматриваются все вместе


Слайд 58

Формализация «согласия» А что такое --- оценки совпадают? Первый подход: для одного и того же элемента, входящего в разные идеалы цепочек конъюнкций, его оценки во всех этих идеалах, совпадают; Второй подход: для одного и того же элемента, входящего в разные идеалы цепочек конъюнкций, его оценки во всех этих идеалах, совпадают; кроме того, мы рассматриваем только те распределения вероятностей, которые совпадают на общих элементах идеалов, удовлетворяя при этом всем ограничениям, наложенным во соответствующих иделалах.


Слайд 59

Интересный контрпример Рассмотрим два «расширенных» идеала: один --- над u, v, w, x, а другой --- над v, w, x, y. Пусть заданы в каждом идеале соттветсвенно заданы ограничения: p(v)+p(w)+p(x)>= 1.6; p(v)+p(w)+p(x)<= 1.5. Тогда интервальные оценки любого элемента этих идеалов остануться [0;1]. Эти идеалы непротиворечивы по первому подходу, но противоречивы (абсолютно) по второму подходу.


Слайд 60

Интересный контрпример (*) Внешне противоречий не видно, а при совместном рассмотрении --- несовместные оценки. Но пример касается некоторого «расширения» ФЗ. Как ведет себя распределения вероятностей на идеалах цепочек конъюнкций --- исследуем.


Слайд 61

Новая «внешняя» непротиворечивость Накладываем ограничение только на «внешние признаки», т.е. так, чтобы границы интервалов совпадали


Слайд 62

Новая «внутренняя» непротиворечивость Требуется совпадение распределений, а не только границ интервалов.


Слайд 63

Непротиворечивость в целом В точечном случае В интервальном случае


Слайд 64

Ациклическая АБС Из новой «внутренней» непротиворечивости следует непротиворечивость в целом


Слайд 65

Априорный вывод в АБС


Слайд 66

Формула над ФЗ Поиск априорной оценки истинности формулы осуществляется как в отдельно взятом ФЗ


Слайд 67

Формула над несколькими ФЗ Над участвующими ФЗ надстраиваем ФЗ, их объемлющий; далее рассуждаем как для случая с отдельно взятым ФЗ; Получить оценки верхней и нижней границы формулы через уже имеющиеся переменные, не надстраивая объемлющий ФЗ; (?) Разложить формулу в СДНФ, оценить каждого кванта из СДНФ на основе апостериорного вывода; (?) Приближенные оценки (например, на основе работы с минимальными элементами); (?)


Слайд 68

Апостериорный вывод Базируется на выводе в отдельно взятом ФЗ В определенном смысле используется метод «пропагации» (т.е. распространения, продвижения) свидетельств


Слайд 69

«Идеальная» организация апостериорного вывода в ФЗ Свидетельство входит по одним переменным; Вероятности внутри ФЗ пересчитываются; Новое «свидетельство» выходит по наборам переменных, общих с другими ФЗ


Слайд 70

Схема «идеального» апостериорного вывода в цепи ФЗ Обобщается на Ациклическую АБС


Слайд 71

АБС и БСД В случае точечных оценок при соблюдении гипотезы условной независимости существует алгоритм апостериорного вывода над АБС для кортежа детерминированных свидетельств. БСД над пропозициями можно конвертировать в ациклическую АБС с точечными оценками; результаты вывода в БСД и апостериорного вывода в такой АБС будут совпадать


Слайд 72

Проблема циклов Циклы погружаются в объемлющий ФЗ Циклы разрываются, если соответствующие наборы переменных независимы Приближенные методы: степени согласованности оценок, полученных разными путями Вопросы, связанные с обработкой циклов, требуют еще очень большой работы


Слайд 73

Возможное применение байесовских сетей и их «родственников» Оценки надежности Диагностика неисправностей Прогнозирование (предсказание наиболее вероятных событий) Мониторинг производственных процессов Мониторинг показателей качества Исследование и моделирование социальных сетей в эпидемиологии как путей распространения инфекций Применение в дидактике (в области математики и информатики)


×

HTML:





Ссылка: