Презентация ВВЕДЕНИЕ В БАЙЕСОВСКИЕ СЕТИ Алгоритмы для Интернета, ИТМО & СПбГУ С. -Петербург, 26 октября 2006 Рук. семинара Ю. М. Лифшиц онлайн

На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему ВВЕДЕНИЕ В БАЙЕСОВСКИЕ СЕТИ Алгоритмы для Интернета, ИТМО & СПбГУ С. -Петербург, 26 октября 2006 Рук. семинара Ю. М. Лифшиц абсолютно бесплатно. Урок-презентация на эту тему содержит всего 184 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Авто/мото » ВВЕДЕНИЕ В БАЙЕСОВСКИЕ СЕТИ Алгоритмы для Интернета, ИТМО & СПбГУ С. -Петербург, 26 октября 2006 Рук. семинара Ю. М. Лифшиц



Оцените!
Оцените презентацию от 1 до 5 баллов!
  • Тип файла:
    ppt / pptx (powerpoint)
  • Всего слайдов:
    184 слайда
  • Для класса:
    1,2,3,4,5,6,7,8,9,10,11
  • Размер файла:
    6.44 MB
  • Просмотров:
    122
  • Скачиваний:
    0
  • Автор:
    неизвестен



Слайды и текст к этой презентации:

№1 слайд
ВВЕДЕНИЕ В БАЙЕСОВСКИЕ СЕТИ
Содержание слайда: ВВЕДЕНИЕ В БАЙЕСОВСКИЕ СЕТИ Алгоритмы для Интернета, ИТМО & СПбГУ С.-Петербург, 26 октября 2006 Рук. семинара Ю.М. Лифшиц

№2 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№3 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№4 слайд
Идеологическое определение
Содержание слайда: Идеологическое определение Байесовские сети --- это графические структуры для представления вероятностных отношений между большим количеством переменных и для осуществления вероятностного вывода на основе этих переменных.

№5 слайд
Уточнение- Предположение,
Содержание слайда: Уточнение-1 Предположение, лежащее в основе любой вероятностной сети, заключается в том, что, в то время как общая проблема чересчур сложна для применения наивных методов вычисления и обновления вероятностей…, отдельные клики… имеют приемлемый, разумный размер…

№6 слайд
Уточнение- В частности, мы
Содержание слайда: Уточнение-2 …В частности, мы предполагаем, что можем производить (пользуясь, например, «грубой силой», т.е. подходом по определению) любые желаемые операции, такие, как маргинализацию или нормировку, внутри любой клики, но необязательно непосредственно для всей сети сразу…

№7 слайд
Уточнение- Наша цель ---
Содержание слайда: Уточнение-3 Наша цель --- использовать структуру сети для того, чтобы распространить такие вычисления на полный набор переменных.

№8 слайд
Цель --- представить
Содержание слайда: Цель --- представить распределение вероятностей (или их семейство) над (большим числом) переменных, в общем виде выглядящее как

№9 слайд
И допускающее декомпозицию
Содержание слайда: И допускающее декомпозицию

№10 слайд
Байесовские сети доверия
Содержание слайда: Байесовские сети доверия

№11 слайд
Алгебраические байесовские
Содержание слайда: Алгебраические байесовские сети

№12 слайд
АБС графы и деревья смежности
Содержание слайда: АБС (графы и деревья смежности)

№13 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№14 слайд
Почему БС востребованы ИИ МВ
Содержание слайда: Почему БС востребованы ИИ (МВ): знания с неопределенностью, фрагменты знаний, базы фрагментов знаний Статистика: много переменных, связи всех со всеми неописуемые и неоцениваемые, зато отдельные скопления можно неплохо охарактеризовать Техника: декомпозируемость систем, знание свойств элементов и связей между ними

№15 слайд
Что предшествовало Анализ
Содержание слайда: Что предшествовало Анализ родословных для поиска источника и путей передачи генетических аномалий. Представление результатов статистических наблюдений, когда наблюдаемых переменных очень много, но их удается разбить на условно независимые наборы.

№16 слайд
БС применяются в медицине Для
Содержание слайда: БС применяются в медицине Для быстрой постановки диагноза, чтобы выбрать правильное учреждение для госпитализации Для дифференциальной диагностики заболеваний, симптоматические проявления которых сходны [но не совпадают полностью]

№17 слайд
БС применяются в
Содержание слайда: БС применяются в технологических процессах Для диагностики отказов и дефектов В драйверах принтеров Для анализа результатов тестирования ПО Для оптимизации запросов в БД Для представления результатов data mining

№18 слайд
БС применяются в научных
Содержание слайда: БС применяются в научных исследованиях Диагностика концентрации уровня кислорода в озере (PhD Thesis!) Геномика и биоинформатика Все то же представление результатов статистической обработки

№19 слайд
Потенциальная применимость БС
Содержание слайда: Потенциальная применимость БС Теория надежности структурно сложных систем (ЛВМ --- адм. И.А. Рябинин)

№20 слайд
БС в учебном процессе
Содержание слайда: БС в учебном процессе Подробнее --- немного позже. Основное Комбинирование и актуализация знаний из нескольких дисциплин; Все объекты и предметы исследования «под рукой»; Полигон для применения программных технологий.

№21 слайд
Немного об истории Логика от
Содержание слайда: Немного об истории Логика (от Аристотеля и раньше); Вероятностная логика (от Дж. Буля и позже); в ИИ удачно ввел Н. Нильссон в 1986; различные формализации, мы пользуемся Хальперном, Фагином и Меггиддо; Байесовские сети (БСД – Дж. Пиэрл, АБС – В.И. Городецкий), еще и марковские сети (???); история этим не исчерпывается; смежные дисциплины...

№22 слайд
Немного об особенностях Очень
Содержание слайда: Немного об особенностях Очень большой упор на графическое представление отношений независимости и условной независимости. Стремление избежать обсуждения тех проблем, решения которых они не знают (подмена циклов последовательностью фрагментов знаний, …) А нам бы о представлении данных хотелось бы поговорить побольше, непротиворечивость посмотреть, алгоритмы вывода выписать и сделать понятными, на доступные программные технологии опереться.

№23 слайд
БСД литература Статьи Pearl
Содержание слайда: БСД: литература Статьи Pearl J. (1985). How to Do with Probabilities what People Say You Can't. Artificial Intelligence Applications. Ed. Weisbin C.R., IEEE, North Holland, pp. 6--12. Pearl J. (1986). Fusion, Propagation, and Structuring in Belief Networks. Artificial Intelligence, vol. 29. Elsevier Science Publishers B.V., North Holland, pp. 241--288. Pearl J. (1986a). Constraint-Propagation Approach to Probabilistic Reasoning. Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). Eds. Kanal L.N., Lemmer J.F. Vol. 4, Elsevier Science Publishers B.V., North Holland, pp. 357--369. Pearl J. (1986b). On Evidentional Reasoning in Hierarchy of Hypotheses. Artificial Intelligence, vol. 28. Elsevier Science Publishers B.V., North Holland, pp. 9--15. Pearl J. (1986c). Distributed Revision of Composite Beliefs. Artificial Intelligence, vol. 33. Elsevier Science Publishers B.V., North Holland, pp. 173--215. Монографии Pearl J. (1988). Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann Publishers, 552 pp. Pearl J. (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press, 386 pp. Jensen F.V.(2001). Bayesian Networks and Decision Graphs. Springer-Verlag, NY. 268 pp. Korb K.B., Nicholson A.E. (2004). Bayesian Artificial Intelligence. Chapman and Hall/CRC, 364 pp. Kyburg H.E. Jr. (2001). Uncertain Inference. Cambridge University Press, 298 pp. Lauritzen, S. L. (1996). Graphical Models, Oxford University Press, Oxford, 1996. Neapolitan R.E. (2004). Learning Bayesian Networks. Pearson Prentice Hall, 674 pp. Nilsson N.J. (1998). Artificial Intelligence: A New Synthesis. Morgan Kaufmann Publishers, 514 pp.

№24 слайд
АБС литература Gorodetsky
Содержание слайда: АБС: литература Gorodetsky V.I., Drozdgin V.V., Jusupov R.M. Application of Attributed Grammar and Algorithmic Sensitivity Model for Knowledge Representation and Estimation // Artificial Intelligence and Information, Control Systems of ROBOTSA. North Holland, Elsevier Science Publ., 1984. pp. 232--237. Городецкий В.И. Байесовский вывод. АН СССР, ЛИИАН, Препринт № 149. Л., 1991. Городецкий В.И. Алгебраические байесовские сети --- новая парадигма экспертных систем // Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации Российской Академии наук, т. 2. М., РАН, 1993. с. 120--141. Городецкий В.И., Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью // Известия РАН. Серия "Теория и системы управления». 1997. №5. Тулупьев А.Л. Алгебраические байесовские сети. Теоретические основы и непротиворечивость. СПб.: СПИИРАН, 1995. 76 с. Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 292 с. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.

№25 слайд
Веб-сайты БСД стоит начинать
Содержание слайда: Веб-сайты БСД: стоит начинать с www.auai.org АБС: сайт в разработке, можно периодически проверять www.spiiras.nw.ru (а пока пользоваться Зеленой книгой)

№26 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№27 слайд
БА пропозициональных формул
Содержание слайда: БА пропозициональных формул

№28 слайд
Аргументное место литерал
Содержание слайда: Аргументное место (литерал)

№29 слайд
Логические операции
Содержание слайда: Логические операции

№30 слайд
Кванты
Содержание слайда: Кванты

№31 слайд
Конъюнкты
Содержание слайда: Конъюнкты

№32 слайд
Теорема о СДНФ
Содержание слайда: Теорема о СДНФ

№33 слайд
Идеал конъюнктов
Содержание слайда: Идеал конъюнктов

№34 слайд
Особенности идеала Множество
Содержание слайда: Особенности идеала Множество всех непустых конъюнктов над заданным набором атомов --- идеал; Множество всех (все непустые и один пустой) конъюнктов над заданным набором атомов --- идеал; Непустое пересечение идеалов --- идеал.

№35 слайд
Идеал конъюнктов -го порядка
Содержание слайда: Идеал конъюнктов 4-го порядка

№36 слайд
ПРИМЕР
Содержание слайда: ПРИМЕР (1)

№37 слайд
ПРИМЕР
Содержание слайда: ПРИМЕР (2)

№38 слайд
Вероятность истинности Подход
Содержание слайда: Вероятность истинности Подход по Н. Нильссону (1986 г.) Более глубокая формализация дана в работах коллектива Фагина, Хальперна, Миггидо (пригодна для рассуждений об оценках сложности) Другие глубокие формализации Спор о приоритетах (de Finetti…) Дж. Буль --- тоже писал о вероятности пропозиции

№39 слайд
НАБОР ПРОПОЗИЦИЙ
Содержание слайда: НАБОР ПРОПОЗИЦИЙ

№40 слайд
Возможные миры
Содержание слайда: Возможные миры

№41 слайд
Допустимые миры
Содержание слайда: Допустимые миры

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

№43 слайд
Теорема о СДНФ
Содержание слайда: Теорема о СДНФ

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

№45 слайд
ВЕРОЯТНОСТЬ ПРОПОЗИЦИИ
Содержание слайда: ВЕРОЯТНОСТЬ ПРОПОЗИЦИИ

№46 слайд
Индексация конъюнктов
Содержание слайда: Индексация конъюнктов (дизъюнктов) и квантов

№47 слайд
Случайные бинарные
Содержание слайда: Случайные бинарные последовательности

№48 слайд
Базовые понятия ТВ на языке
Содержание слайда: Базовые понятия ТВ на языке СБП

№49 слайд
Кванты и вероятность
Содержание слайда: Кванты и вероятность истинности

№50 слайд
Конъюнкты и вероятность
Содержание слайда: Конъюнкты и вероятность истинности

№51 слайд
Вероятности квантов и
Содержание слайда: Вероятности квантов и конъюнктов

№52 слайд
Интервальная вероятность
Содержание слайда: Интервальная вероятность конъюнкции

№53 слайд
Modus ponens
Содержание слайда: Modus ponens

№54 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№55 слайд
Фрагмент знаний определение
Содержание слайда: Фрагмент знаний (определение) Математическая модель Идеал конъюнктов Оценки вероятностей элементов идеала (точечные и интервальные)

№56 слайд
ФЗ Brute Force Calculations
Содержание слайда: ФЗ: Brute Force Calculations Поддержание непротиворечивости Априорный вывод Апостериорный вывод Вывод оценок чувствительности Объемлющая непротиворечивость Линейные комбинации ФЗ ...

№57 слайд
Точечная непротиворечивость p
Содержание слайда: «Точечная» непротиворечивость p(x)=0.4 p(x)=0.6 непротиворечиво (согласовано, совместно)

№58 слайд
Интервальная
Содержание слайда: «Интервальная» непротиворечивость p(x)=[0.4;0.5] p(x)=[0.5;0.6] непротиворечиво (согласовано, совместно)

№59 слайд
Непротиворечивость ФЗ .
Содержание слайда: Непротиворечивость ФЗ (.) Преобразовать вероятности на конъюнктах в вероятности на квантах; Проверить соответствие вероятностной аксиоматике получившихся оценок на квантах

№60 слайд
Матрицы In и Jn Матрицы
Содержание слайда: Матрицы In и Jn Матрицы преобразования вектора вероятностей конъюнктов в вектор вероятностей квантов и наоборот строятся как прямое произведение матриц Кронекера.

№61 слайд
Матрицы I , , ,
Содержание слайда: Матрицы I (2, 3, 4, 5)

№62 слайд
Множество ограничений E n
Содержание слайда: Множество ограничений E(n) Обозначим множество ограничений, вытекающих из вероятностной аксиоматики, как E(n). В матрично-векторном виде они записываются как

№63 слайд
ФЗ с , -ми оценками Задан
Содержание слайда: ФЗ с [,]-ми оценками Задан набор интервальных оценок, который мы обозначим как D(n).

№64 слайд
Непротиворечивость ФЗ Пусть
Содержание слайда: Непротиворечивость ФЗ ([]) Пусть задан набор интервальных оценок. Этот набор непротиворечив (согласован), если для произвольного элемента при выборе произвольной точки из интервальной оценки в остальных интервалах можно выбрать точки так, что получившийся набор точечных оценок непротиворечив.

№65 слайд
Поддержание
Содержание слайда: Поддержание непротиворечивости ФЗ в [,]-ом случае

№66 слайд
Априорный вывод
Содержание слайда: Априорный вывод

№67 слайд
Апостериорный вывод в ФЗ АБС
Содержание слайда: Апостериорный вывод в ФЗ АБС Мы что-то узнали: поступило свидетельство; Как оно повлияет на наши оценки вероятностей утверждений из нашей базы знаний; [Как распространить влияние свидетельства] Несколько вычислительно разных ситуаций...

№68 слайд
Детерминированное
Содержание слайда: Детерминированное свидетельство Атомарные <x> или <x> и кортежи <x1x8>, <x1x2>, <x1x2x3>... Кратко

№69 слайд
Недетерминированное
Содержание слайда: Недетерминированное свидетельство Атомарные <p[a](x)> и < p[a]( x)> Кортежи < p[a](x1x8), p[a](x1x8), p[a](x1x8), p[a](x1x8)> В краткой записи:

№70 слайд
Свидетельство с
Содержание слайда: Свидетельство с неопределенностью

№71 слайд
Апостериорный вывод . и , Вид
Содержание слайда: Апостериорный вывод: (.) и [,] Вид оценок в ФЗ, куда поступает свидетельство, также создают особый вычислительный аспект: точечные оценки --- «прямые» вычисления по определению условной вероятности; интервальные оценки --- задачи гиперболического программирования.

№72 слайд
Апостериорный вывод по
Содержание слайда: Апостериорный вывод «по определению» условной вероятности («+»)

№73 слайд
Апостериорный вывод по
Содержание слайда: Апостериорный вывод «по определению» условной вероятности («-»)

№74 слайд
Апостериорный вывод, ФЗ с ,
Содержание слайда: Апостериорный вывод, ФЗ с [,] Сведение:

№75 слайд
Апостериорный вывод, ФЗ с ,
Содержание слайда: Апостериорный вывод, ФЗ с [,] Сведение:

№76 слайд
Апостериорный вывод, ФЗ с ,
Содержание слайда: Апостериорный вывод, ФЗ с [,] Сведение:

№77 слайд
Апостериорный вывод, ФЗ с ,
Содержание слайда: Апостериорный вывод, ФЗ с [,] Сведение:

№78 слайд
Апостериорный вывод, ФЗ с ,
Содержание слайда: Апостериорный вывод, ФЗ с [,] Сведение:

№79 слайд
Несовместимость со
Содержание слайда: Несовместимость со свидетельством

№80 слайд
Апостериорный вывод при
Содержание слайда: Апостериорный вывод при недетерм-ом свидетельстве

№81 слайд
Примеры формул для рассчетов
Содержание слайда: Примеры формул для рассчетов

№82 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№83 слайд
Алгебраическая байесовская
Содержание слайда: Алгебраическая байесовская сеть Это множество фрагментов знаний, как правило, связанных между собой (имеющих общие конъюнкты), которые рассматриваются как единое целое.

№84 слайд
Граф и дерево смежности -
Содержание слайда: Граф и дерево смежности - веса Узлу графа смежности ставится в соответствие фрагмент знаний; весом же узла является идеал конъюнктов, лежащий в основе этого ФЗ.

№85 слайд
Граф смежности ---
Содержание слайда: Граф смежности --- определение Графом смежности называется ненаправленный граф, в котором между каждой парой узлов, веса которых содержат общие элементы, существует путь; в веса каждого из узлов любого пути (в графе) входят все элементы, общие для начального и конечного узлов этого пути; вес одного узла не входит полностью в вес никакого другого узла.

№86 слайд
Сепараторы Каждому ребру в
Содержание слайда: Сепараторы Каждому ребру в графе смежности также удобно приписать вес – пересечение весов, приписанных тем двум узлам, которые соединяются рассматриваемым ребром. Вес на ребре --- сепаратор (или разделитель). Непустое пересечение идеалов конъюнктов --- идеал конъюнктов.

№87 слайд
Дерево смежности Деревом
Содержание слайда: Дерево смежности Деревом смежности называется ациклический граф смежности --– такой граф, что в нем нет ни одного цикла, то есть пути (без повторяющихся узлов), начало и конец которого бы совпали.

№88 слайд
АБС --- определение
Содержание слайда: АБС --- определение Алгебраическая байесовская сеть (АБС) определяется как граф смежности с фрагментами знаний в узлах. АБС, представимая в виде дерева смежности, называется ациклической (ААБС). АБС является одной из логико-вероятностных моделей БФЗ с неопределенностью.

№89 слайд
АБС --- графическое
Содержание слайда: АБС --- графическое представление

№90 слайд
Ациклические АБС
Содержание слайда: Ациклические АБС

№91 слайд
Степени непротиворечивости
Содержание слайда: Степени непротиворечивости АБС Локальная, Экстернальная, Интернальная, Глобальная

№92 слайд
Степени непротиворечивости
Содержание слайда: Степени непротиворечивости АБС Локальная: непротиворечив каждый фрагмент знаний по отдельности.

№93 слайд
Степени непротиворечивости
Содержание слайда: Степени непротиворечивости АБС Экстернальная: совпадают оценки пересекающихся фрагментов.

№94 слайд
Степени непротиворечивости
Содержание слайда: Степени непротиворечивости АБС Интернальная: распределения вероятностей совпадают на конъюнктах, общих для двух или более ФЗ.

№95 слайд
Степени непротиворечивости
Содержание слайда: Степени непротиворечивости АБС Глобальная: непротиворечив объемлющий фрагмент знаний.

№96 слайд
АБС интернальная и глобальная
Содержание слайда: АБС: интернальная и глобальная непротиворечивость

№97 слайд
ААБС интернальная и
Содержание слайда: ААБС: интернальная и глобальная непротиворечивость Ациклическая АБС, непротиворечивая интернально, глобально непротиворечива.

№98 слайд
ААБС интернальная и
Содержание слайда: ААБС: интернальная и экстернальная непротиворечивость Экстернально непротиворечивая ациклическая АБС может быть интернально противоречивой. Есть класс ациклических сетей, у которых из экстернальной непротиворечивости следует интернальная.

№99 слайд
Апостериорный вывод
Содержание слайда: Апостериорный вывод: свидетельства Детерминированное свидетельство (и кортеж ДС); Недетерминированное свидетельство (и кортеж НДС); Недетерминированное свидетельство (и кортеж НДСН).

№100 слайд
Апостериорный вывод два ФЗ
Содержание слайда: Апостериорный вывод: два ФЗ

№101 слайд
Передача виртуального
Содержание слайда: Передача виртуального свидетельства между ФЗ

№102 слайд
Апостериорный вывод в ААБС
Содержание слайда: Апостериорный вывод в ААБС

№103 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№104 слайд
Байесовские сети доверия
Содержание слайда: Байесовские сети доверия

№105 слайд
Простейшие БСД
Содержание слайда: Простейшие БСД

№106 слайд
БСД односвязная
Содержание слайда: БСД односвязная

№107 слайд
БСД с допустимыми циклами
Содержание слайда: БСД с допустимыми циклами

№108 слайд
БСД с недопустимым циклом
Содержание слайда: БСД с недопустимым циклом

№109 слайд
Пример БСД
Содержание слайда: Пример БСД

№110 слайд
Типы связей в БСД
Содержание слайда: Типы связей в БСД

№111 слайд
Понятие d-разделимости Два
Содержание слайда: Понятие d-разделимости Два узла называются d-разделимыми, если любой путь между ними содержит последовательную или сходящуюся связь, в центральный узел которой поступило свидетельство, или расходящуюся связь, в центральный узел (и его потомки) которой не поступило свидетельство.

№112 слайд
Основное предположение
Содержание слайда: Основное предположение d-разделенные узлы независимы. Это предположение позволяет однозначно восстановить распределение вероятностей над всеми переменными.

№113 слайд
Несколько условий формально
Содержание слайда: Несколько условий формально на примере нашей сети p(u|t) × p(v|t) = p(uv|t) p(t|uv) × p(w|uv) = p(tw|uv) … В такой форме эти предположения уже не кажутся столь очевидными

№114 слайд
Что нам дают такие
Содержание слайда: Что нам дают такие предположения Независимость d-разделимых [переменных в узлах] позволяет выделить единственное распределение из всех, для которых подходят заданные условные вероятности. Это единственное распределение -- произведение всех вероятностей, заданных в БСД (chain rule).

№115 слайд
Chain rule для нашего примера
Содержание слайда: Chain rule для нашего примера

№116 слайд
Но все же Несмотря на
Содержание слайда: Но все же… Несмотря на указанную выше формализацию, методы работы с БСД позволяют использовать chain rule неявно.

№117 слайд
Первичная пропагация
Содержание слайда: Первичная пропагация Вычисление вероятностей всех переменных (по отдельности), входящих в нашу сеть.

№118 слайд
Простейший в лоб алгоритм
Содержание слайда: Простейший (в лоб) алгоритм первичной пропагации По определению условной вероятности: Аналогично хочется поступить с остальными вероятностями.

№119 слайд
Алгоритм первичной пропагации
Содержание слайда: Алгоритм первичной пропагации для ациклических направленных графов Очевидно, что в описанном выше примере нам в ходе вычисления p(w) потребуются вероятности именно в такой ситуации и требуется chain rule и понятие d-разделимости. В частности получаем, что p(uv|t) = p(u|t) × p(v|t), аналогично для отрицания t и суммируем.

№120 слайд
Первичная пропагация,
Содержание слайда: Первичная пропагация, обобщенный алгоритм «на пальцах» Если мы хотим вычислить вероятность какого либо узла, то мы должны просуммировать совместное распределение по означиванию всех остальных переменных (маргинализовать). Но, так как все наше распределение разбивается на произведение достаточно простых, можно проводить суммирование по очереди по одной (иногда по нескольким) переменным за раз, при этом большая часть сомножителей не будет от них зависеть.

№121 слайд
Первичная пропагация связь
Содержание слайда: Первичная пропагация связь простого и обобщенного алгоритмов Простой алгоритм — это всего лишь удачный порядок суммирования для обобщенного алгоритма. Обобщенный алгоритм понадобится при появлении свидетельств. Для обобщенного алгоритма удобно определить на БСД структуру дерева смежности.

№122 слайд
Моральный граф Моральным
Содержание слайда: Моральный граф Моральным графом для БСД называется ненаправленный граф, в котором вершины те же, и две вершины соединены ребром, если они либо соседствуют, либо имеют общего сына в исходной БСД.

№123 слайд
Пример морального графа
Содержание слайда: Пример морального графа

№124 слайд
Если моральный граф
Содержание слайда: Если моральный граф триангулярен То его можно разбить на клики, которые затем можно объединить в дерево смежностей (разными вариантами). Каждая максимальная клика попадает в отдельный [соответствующий ей] узел дерева смежности.

№125 слайд
Если не триангулярен То
Содержание слайда: Если не триангулярен То придется его триангулировать. Это требуется сделать, добавив, по возможности, «минимум» ребер.

№126 слайд
Дерево сочленений
Содержание слайда: Дерево сочленений

№127 слайд
Пропагация свидетельств Но
Содержание слайда: Пропагация свидетельств Но главная задача БСД — это все-таки пропагация свидетельств (апостериорный вывод). Иными словами, мы знаем апостериорные означивания нескольких узлов и хотим получить условную вероятность остальных.

№128 слайд
Переход к пропагации
Содержание слайда: Переход к пропагации свидетельств Мы умеем вычислять маргинальные вероятности. Давайте в процессе вычисления в нужном месте «заменим» «настоящую» вероятность единицей или нулем в зависимости от свидетельства. Это гарантирует, что мы получим правильные вероятности в тех узлах, что ниже. Как же учесть влияние на предшествующие узлы?

№129 слайд
Алгоритм пропагации
Содержание слайда: Алгоритм пропагации свидетельств, «на пальцах» Мы поступим как в обобщенном алгоритме первичной пропагации Для переменной, условную вероятность которой мы хотим получить, нам придется придумать хороший порядок маргинализации из совместного распределения.

№130 слайд
Дерево сочленений
Содержание слайда: Дерево сочленений обеспечивает хороший порядок обхода (суммирования)

№131 слайд
Для нашего примера
Содержание слайда: Для нашего примера

№132 слайд
Выгода считать все сразу
Содержание слайда: Выгода считать все сразу Двукратный проход по дереву смежности дает нам все искомые вероятности. Для вычисления одной вероятности можно пройти один раз (искомая помещается в вершину).

№133 слайд
Проблема направленного цикла
Содержание слайда: Проблема направленного цикла Наличие направленного цикла в байесовской сети доверия приводит к тому, что chain rule не работает. Но часто можно построить распределение, удовлетворяющее заданным условным вероятностям. Такое распределение может быть не единственным: исходным данным может отвечать семейство распределений.

№134 слайд
Изолированный цикл с
Содержание слайда: Изолированный цикл с бинарными переременными Условные вероятности задают ограничения на маргинальные вероятности. Эти ограничения можно представить в виде системы линейных уравнений.

№135 слайд
Линейные уравнения,
Содержание слайда: Линейные уравнения, задаваемые изолированным циклом

№136 слайд
Линейные уравнения,
Содержание слайда: Линейные уравнения, задаваемые изолированным циклом, в матричном представлении

№137 слайд
Погружение во фрагмент знаний
Содержание слайда: Погружение во фрагмент знаний алгебраической байесовской сети

№138 слайд
Результат погружения Мы можем
Содержание слайда: Результат погружения Мы можем получить оценки (возможно интервальные) на всевозможные конъюнкции положительно означенных элементов. Мы можем выяснить, что имеющиеся оценки не соответствуют аксиоматике вероятностной логики.

№139 слайд
Направленный цикл с потомками
Содержание слайда: Направленный цикл с потомками Потомок имеет одного родителя из цикла; Потомок является сыном двух соседних узлов; Потомок является сыном двух не соседних узлов; Потомок является сыном трех и более узлов.

№140 слайд
Потомок имеет одного родителя
Содержание слайда: Потомок имеет одного родителя из цикла Мы уже получили точечные значения маргинальных вероятностей всех элементов цикла. Маргинальная вероятность родителя, может быть рассмотрена как заданная изначально и обрабатываться традиционным для БСД способом.

№141 слайд
Потомок является сыном двух
Содержание слайда: Потомок является сыном двух соседних узлов Для двух соседних узлов нам полностью известно совместное распределение. Данное распределение можно использовать для дальнейшей пропагации традиционным образом.

№142 слайд
Потомок является сыном двух
Содержание слайда: Потомок является сыном двух несоседних узлов Распределение над родительскими узлами можно найти с точностью до одного параметра. Если зафиксировать этот параметр, то можно проводить обычную пропагацию.

№143 слайд
Потомок является сыном трех и
Содержание слайда: Потомок является сыном трех и более узлов Сложности связаны с большим количеством параметров. Параметры связаны друг с другом и не все их сочетания возможны. Пропагация проводится с учетом этих параметров. Может требовать решения ЗЛП.

№144 слайд
Учет влияния предков Главная
Содержание слайда: Учет влияния предков Главная проблема – нельзя выписать систему линейных уравнений. Причина – нельзя зная условную вероятность относительно двух узлов, редуцировать ее до условной вероятности одного из них.

№145 слайд
Путь решения Можно
Содержание слайда: Путь решения Можно зафиксировать все возможные означивания родителей. Для каждого означивания мы получаем изолированный цикл. Проводим обработку цикла и производим суммирование с учетом вероятности каждого конкретного означивания родителей.

№146 слайд
Проблема Возможна ситуация,
Содержание слайда: Проблема Возможна ситуация, когда при одних означиваниях цикл непротиворечив, а при других противоречив.

№147 слайд
Возможное решение Исключить
Содержание слайда: Возможное решение Исключить «плохие» означивания родителей. Пересчитать байесовскую сеть доверия с учетом «невозможных» состояний.

№148 слайд
Погружение БСД в АБС
Содержание слайда: Погружение БСД в АБС

№149 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№150 слайд
Базовые дисциплины
Содержание слайда: Базовые дисциплины Математические Математическая логика Теория вероятностей Экстремальные задачи Информатика Теория графов Представление данных Базы данных Искусственный интеллект Представление неопределенности Логико-вероятностный вывод Мягкие вычисления

№151 слайд
Особенности материала Части
Содержание слайда: Особенности материала Части материала «масштабируются» под нужды конкретного курса и конкретной аудитории; В возникающих экстремальных задачах используются объекты, знакомые математикам (а не насильно заимствованные из экономики); Много задач для программирования, удобно для организации семинаров и практикумов; «Неисчерпаемая тематика» для курсовых и дипломных работ

№152 слайд
Полезные навыки Для изучения
Содержание слайда: Полезные навыки Для изучения математической статистики (и способов ее применения на практике); Для дальнейшего овладения теорией надежности (структурно сложных систем в рамках ЛВМ и родственных ему) Для освоения аппаратов небайесовских мер истинности

№153 слайд
ПЛАН БС что это БС праксис и
Содержание слайда: ПЛАН БС — что это БС — праксис и генезис Вероятностная логика Фрагменты знаний (ФЗ) Алгебраические байесовские сети Байесовские сети доверия БС — дидактическое применение БС — монография

№154 слайд
Монография Тулупьев А.Л.,
Содержание слайда: Монография Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход СПб.: Наука, 2006 607 стр. ISBN 5-02-025107-0 Изд. грант РФФИ 06-01-14108

№155 слайд
Обложка
Содержание слайда: Обложка

№156 слайд
Разворот обложки
Содержание слайда: Разворот обложки

№157 слайд
Дополнительный материал
Содержание слайда: Дополнительный материал

№158 слайд
Мягкие вычисления SC
Содержание слайда: Мягкие вычисления (SC) Консорциум вычислительных методологий, которые коллективно обеспечивают основы для понимания, конструирования и развития интеллектуальных систем

№159 слайд
Мягкие вычисления отрасли
Содержание слайда: Мягкие вычисления: отрасли Нечеткая логика (FL) Нейровычисления (NC) Генетические вычисления (GC) Вероятностные вычисления (PC) Рассуждения на базе свидетельств (ER) [Байесовские сети] (BN) Хаотические системы (ChS) Машинное обучение (ML)

№160 слайд
Цель и задачи исследования
Содержание слайда: Цель и задачи исследования

№161 слайд
Декомпозируемость знаний
Содержание слайда: Декомпозируемость знаний Эксперт не мыслит о закономерностях предметной области как о «связи всего со всеми» Выделяются фрагменты знаний (Knowledge patterns), которые содержат достаточно подробные сведения о небольшом числе объектов (или утверждений) о предметной области, а также о связях между ними

№162 слайд
Модель утверждения Атомарная
Содержание слайда: Модель утверждения Атомарная пропозициональная формула (булевская переменная, пропозициональная переменная, атомарная пропозиция) --- модель «атомарного» утверждения о предметной области Пропозициональные формулы --- модели утверждений, возможно сложных, о предметной области

№163 слайд
Неопределенность Почему
Содержание слайда: Неопределенность Почему возникает Пропущенные наблюдения Неточность средств измерения Экспертные высказывания Неудачные регистрационные формы Частично незаполненное поле (только год в дате рождения) … Как проявляется Нужно ли обрабатывать

№164 слайд
Виды неопределенности
Содержание слайда: Виды неопределенности Существует много видов, например неоднозначность и многозначность слов; возможность двух или более интерпретаций записи даже на формальном языке; недетерминированность; нечёткость (в т.ч. лингвистическая); неточность (интервальные оценки); недоопределённость...

№165 слайд
Неопределенность утверждения
Содержание слайда: Неопределенность утверждения Истинностное означивание и мера истинности Мера истинности как степень доверия к утверждению Мера истинности как степень тесноты связи между частями составной пропозициональной формулы Возможные значения и оценки меры истинности

№166 слайд
Объект исследования
Содержание слайда: Объект исследования Высказывания, суждения, утверждения, представимые пропозициональными формулами над булевскими переменными; Мера истинности которых характеризуется количественно с помощью вероятностных и/или небайесовских оценок; Которые могут быть как точечные, так и интервальные [а в перспективе – твинные].

№167 слайд
Предмет исследования Базы
Содержание слайда: Предмет исследования Базы фрагментов знаний с неопределённостью; Фрагмент знаний – некоторая [математическая] структура, состоящая из небольшого набора «тесно связанных» пропозициональных формул; Мера истинности которых и теснота связи охарактеризована: тензором условных вероятностей – БСД; представлением тензора совместных вероятностей, допускающим точечные и интервальные оценки --- АБС; [обобщение последнего на небайесовские меры истинности: нечёткую, доверия-правдоподобия, необходимости-возможности...]

№168 слайд
Логико-вероятностный подход
Содержание слайда: Логико-вероятностный подход (ЛВП) Вероятностная мера как мера истинности Точечные оценки значений вероятностной меры Интервальные оценки значений вероятностной меры (как следствие неопределенности) «Интервальная вероятность» и интервальная оценка вероятности Единственность распределения и семейство распределений вероятности

№169 слайд
ЛВП --- богатая история G.
Содержание слайда: ЛВП --- богатая история G. Boole, “An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities” (1854) N. Nilsson, Probabilistic Logic (AI, 1986) N. Nilsson, Probabilistic Logic Revisited (AI, 1993) De Finetti, Whaley, Ramsay, … Школа логико-вероятностных методов в теории надежности (рук. адм. И. А. Рябинин) --- важнейшие приложения ЛВП.

№170 слайд
Непротиворечивость
Содержание слайда: Непротиворечивость Согласованность, согласуемость, программный код

№171 слайд
Пример ограничений
Содержание слайда: Пример ограничений:

№172 слайд
Программный код на C for i i
Содержание слайда: Программный код на C++ for (i = 0; i < pow2(N); i++) { c.add(IloRange(env, 0.0, IloInfinity )); for(j = 0; j < pow2(N); j++) if (i & j = i) { //Проверка на четность количества 1 в i xor j. if (parity(i ^ j)) {c[i].setCoef(x[j], 1)}; else {c[i].setCoef(x[j], -1)}; } }

№173 слайд
Непротиворечивое распределение
Содержание слайда: Непротиворечивое распределение

№174 слайд
Фрагмент знаний
Содержание слайда: Фрагмент знаний

№175 слайд
Графическое представление ФЗ
Содержание слайда: Графическое представление ФЗ

№176 слайд
Непротиворечивость
Содержание слайда: Непротиворечивость (согласованность) ФЗ

№177 слайд
Согласуемость ФЗ
Содержание слайда: Согласуемость ФЗ

№178 слайд
Поддержание непротиворечивости
Содержание слайда: Поддержание непротиворечивости

№179 слайд
Байесовские сети доверия
Содержание слайда: Байесовские сети доверия Дополнительные сведения

№180 слайд
Фрагменты знаний первого
Содержание слайда: Фрагменты знаний первого порядка

№181 слайд
Фрагменты знаний второго
Содержание слайда: Фрагменты знаний второго порядка

№182 слайд
Фрагменты знаний третьего
Содержание слайда: Фрагменты знаний третьего порядка

№183 слайд
Линейная цепь ФЗ
Содержание слайда: Линейная цепь ФЗ (1)

№184 слайд
Линейная цепь ФЗ
Содержание слайда: Линейная цепь ФЗ (2)

Скачать все slide презентации ВВЕДЕНИЕ В БАЙЕСОВСКИЕ СЕТИ Алгоритмы для Интернета, ИТМО & СПбГУ С. -Петербург, 26 октября 2006 Рук. семинара Ю. М. Лифшиц одним архивом: