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

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

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

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

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

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

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

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

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

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

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

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

Возможные миры Формул а Логическое означивание true false true false true false truefalsetruefalsetruefalsetruefalse

Допустимые миры ФормулаДопустимое логическое означивание (допустимый мир) Вероятност ь истинности формулы true false 0,5 truefalsetruefalse0,6 truefalse 0,2 Вероятност ь допустимог о мира 0,20,30,40,1

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

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

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

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

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

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

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

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

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

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

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

БСД: FEEDBACK CYCLES

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Интересный контрпример Рассмотрим два «расширенных» идеала: один --- над u, v, w, x, а другой --- над v, w, x, y.Рассмотрим два «расширенных» идеала: один --- над u, v, w, x, а другой --- над v, w, x, y. Пусть заданы в каждом идеале соттветсвенно заданы ограничения:Пусть заданы в каждом идеале соттветсвенно заданы ограничения: –p(v)+p(w)+p(x)>= 1.6; –p(v)+p(w)+p(x)

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

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

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

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

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

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

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

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

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

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

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

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

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

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