Глава 26. Заключение

Байесовские сети в практических задачах искусственного интеллекта: распознавание образов, распознавание речи, обнаружение дефектов, формирование прогнозов, моделирование теста последовательных разведений, элементы моделирования социальных сетей. Марковские сети, модель Изинга, изучение магнетизма и концепция потенциалов. Условные и совместные вероятности как тензоры. Тензоры совместных и условных вероятностей как потенциалы. Стохастические булевы сети; булевы сети и клеточные автоматы. Индексация одномерных клеточных автоматов. Скрытые марковские модели. Отношения между различными классами вероятностных сетей. Вариации алгоритмов обучения: метрические подходы, информационные меры, стохастический поиск. Парадигма самообучающихся систем. Деревья принятия решений. Обучение концептам. Нейронные сети. Генетические алгоритмы. Байесовское обучение и классификаторы. Алгоритмы кластеризации. Байесовское обучение с подкреплением. Вероятностные автоматы.

2. Лабораторный практикум

— не предусмотрен учебным планом

3. Перечень примерных контрольных вопросов и заданий для самостоятельной работы

— не предусмотрен учебным планом

4. Темы курсовых работ (выборочно)

Проектирование, разработка и тестирование графического пользовательского интерфейса, объектно-ориентированных библиотек и структур таблиц в реляционных базах данных

1. для представления фрагмента знаний алгебраической байесовской сети,

2. для представления одной или нескольких альтернативных модейлй фрагмента знаний;

3. для проверки и поддержания непротиворечивости локальных объектов теории байесовских сетей;

4. для локального априорного вывода;

5. для локального апостериорного вывода;

6. для глобального апостериорного вывода;

7. для локального обучения;

8. для глобального обучения (обучения структуры байесовской сети);

9. для преобразования одних объектов теории байесовских сетей в другие.

5. Темы рефератов

— не предусмотрены учебным планом

6. Примерный перечень вопросов к экзамену по всему курсу

9-й семестр

1. Декомпозируемость системы знаний. Фрагменты знаний. Базы фрагменты знаний. Математические модели фрагментов знаний. Математические модели баз фрагментов знаний. Вероятностные графические модели, логико-вероятностные графические модели. Задачи логико-вероятностного вывода и задачи автоматического обучения.

2. Пропозиции-атомы, пропозиции-кванты, пропозиции-конъюнкты, пропозиции-дизъюнкты. Индексация указанных классов пропозиций. Идеал конъюнктов, идеал дизъюнктов. Литерал (аргументное место). Теорема о совершенной нормальной дизъюнктивной форме. Факторизация пространства пропозициональных формул по отношению эквивалентности. Канонический представитель класса эквивалентности.

3. Элементы классической теории вероятностей. Вероятностное пространство, конечное пространство исходов. Алгебра событий, база алгебры событий, дискретная плотность вероятности. Вероятность. Алгебра событий — булева алгебра. Смесь распределений. Формула Мёбиуса. Неизмеримые события, внутренняя мера вероятности и внешняя мера вероятности. Условная вероятность. Независимость и условная независимость. Теорема Байеса. Формула полной вероятности.

4. Определение вероятности истинности пропозициональной формулы с помощью возможных миров.

5. Упрощенная структура вероятностной логики по Н. Нильссону.

6. Структура вероятностной логики по Хальперну, Фейгину и Меджидо.

7. Случайный бинарный (булев) элемент. Случайная бинарная (булева) последовательность. Композиция распределений случайных бинарных последовательностей. Неединственность композиции. Операция композиции и условная независимость.

8. Меры доверия. Вероятность истинности как мера доверия. Интервальные оценки меры доверия.

9. Прямое произведений и степень матриц. Определение матриц I_n и J_n, их свойства и взаимосвязь.

10. Задачи линейного и гиперболического программирования (определение, основные элементы). Библиотеки для решения задач линейного программирования.

11. Граф. Дерево. Цепь. Основные семейства узлов графа. Граф смежности, дерево смежности, цепь смежности. Максимальный и минимальный граф смежности, их свойства. Дерево клик. Дерево сочленений.

12. Построение максимального графа смежности. Алгоритмы перебора минимальных графов смежности. Визуализация графов смежности. Метрики на минимальных графах смежности.

13. Направленный граф. Ациклический направленный граф. Виды односвязных направленных графов; многосвязные ациклические направленные граф. Моральный граф. Триангуляция морального графа. Построение по моральному графу дерева смежности и дерева сочленений.

14. Библиотека JGraph (можно охарактеризовать любую другую обладающую достаточными возможностями бесплатно доступную библиотеку, реализующую представление графов, их визуализацию и операции над ними).

15. Представление в программном коде идеалов конъюнктов и наборов квантов. Представление дерева смежности в реляционной базе данных.

16. Представление в реляционной базе данных идеалов конъюнктов и наборов квантов с атрибутами. Представление дерева смежности в программном коде.

17. Фрагмент знаний алгебраической байесовской сети. Определение и возможные операции. Скалярные и интервальные оценки вероятности истинности. Диаграммы Хассе и сокращенные обозначения. Альтернативные математические модели фрагментов знаний.

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

19. Виды свидетельств в теории алгебраических байесовских сетей и их обработка. Вероятностная семантика свидетельства в теории алгебраических байесовских сетей.

20. Линейная комбинация непротиворечивых фрагментов знаний. Линейная оболочка непротиворечивых фрагментов знаний. Линейные комбинация и оболочка в задачах поддержки принятия решений. Накрывающая непротиворечивость, неединственность линейной оболочки противоречивых фрагментов знаний.

21. Локальный априорный вывод в теории алгебраических байесовских сетей и чувствительность его результатов. Соответствующие матрично-векторные уравнения. Расширенный фрагмент знаний. Алгоритм построения СДНФ пропозициональной формулы по ее записи в виде строки.

22. Непротиворечивость и локальный априорный вывод в альтернативных моделях фрагмента знаний, где носителем выступает идеал дизъюнктов и набор квантов. Соответствующие матрично-векторные уравнения.

23. Две задачи апостериорного вывода в теории алгебраических байесовских сетей. Вид свидетельств и результаты апостериорно вывода. Вероятностная семантика апостериорного вывода в случае детерминированного свидетельства, поступающего во фрагмент знаний со скалярными оценками истинности. Особые случаи.

24. Локальный апостериорный вывод в случае детерминированного свидетельства: матрично-векторные уравнения и алгоритмы.

25. Локальный апостериорный вывод в случае стохастического свидетельства: матрично-векторные уравнения и алгоритмы.

26. Локальный апостериорный вывод в случае неточного свидетельства: матрично-векторные уравнения и алгоритмы.

27. Алгоритм распространения виртуального свидетельства при исходном стохастическом свидетельстве и скалярных априорных оценках в алгебраической байесовской сети. Вероятностная семантика этого алгоритма.

28. Алгоритм распространения виртуального свидетельства при исходном неточном свидетельстве и интервальных априорных оценках в алгебраической байесовской сети. Вероятностная семантика этого алгоритма (получение накрывающих, а не точных оценок).

29. Структура алгебраической байесовской сети и апостериорный вывод.

30. Вероятностная семантика циклов смежности в алгебраических байесовских сетях. Преобразование циклов смежности. Проверка непротиворечивости и другие виды логико-вероятностного вывода в циклах смежности.

31. Степени непротиворечивости алгебраической байесовской сети. Степени непротиворечивости и структура алгебраической байесовской сети. Алгоритмы проверки и поддержания алгебраической байесовской сети.

32. Ациклические алгебраические байесовские сети: особенности структуры, вероятностной семантики и алгоритмов логико-вероятностного вывода.

33. Глобальный априорный вывод в ациклической алгебраической байесовской сети со скалярными априорными оценками и глобальный апостериорный вывод с детерминированными свидетельствами — взаимосвязь алгоритмов указанных видов логико-вероятностного вывода.

34. Непротиворечивость результатов локального апостериорного вывода. Возможности сокращения расчетов в локальном апостериорном выводе при поступлении детерминированного свидетельства. Согласованность результатов апостериорного вывода в цепи смежности из двух фрагментов знаний со скалярными априорными оценками при поступлении либо детерминированного, либо стохастического свидетельства в один из них.

35. Байесовская сеть доверия: два определения, их эквивалентность, вероятностная семантика сети. Случайные бинарные (булевы) элементы, случайные бинарные (булевы) последовательности, случайные многозначные элементы, случайные многозначные последовательности в узлах байесовской сети доверия.

36. Различные виды структуры байесовских сетей доверия. Преобразование байесовской сети доверия в дерево смежности. Марковская эквивалентность в байесовских сетях доверия.

37. Семантически эквивалентный образ байесовской сети доверия (со структурой цепи, дерева и полидерева) в виде алгебраической байесовской сети.

38. Семантически эквивалентный образ байесовской сети доверия (с многосвязной структурой) в виде алгебраической байесовской сети.

39. Алгоритм первичной пропагации в байесовской сети доверия (со структурой цепи, дерева и полидерева).

40. Алгоритм первичной пропагации в байесовской сети доверия (с многосвязной структурой)

41. Компаративный анализ вероятностной семантики ациклических алгебраических байесовских сетей и байесовских сетей доверия.

42. Направленный цикл в байесовской сети доверия. Алгоритмы его преобразования. Несущестование БСД-исчисления, допускающего обработку направленного цикла при сохранении классической вероятностной семантики байесовской сети доверия. Примеры.

43. Компаративный анализ вероятностной семантики направленного цикла в байесовской сети доверия и цикла смежности в алгебраической байесовской сети. Алгоритмы проверки непротиворечивости указных объектов.

44. Вероятностная семантика линейных и циклических паттернов в байесовских сетях.

45. Различные алгоритмы генерации случайных бинарных последовательностей в алгебраических байесовских сетях и байесовских сетях доверия. Сэмплирование (генерация выборок) по Гиббсу. Стохастические алгоритмы логико-вероятностного вывода в байесовских сетях доверия. Связь этих алгоритмов с выводом в марковских сетях и стохастических булевских сетях.

46. Задачи автоматического обучения в вероятностных графических моделях: общая характеристика, постановка и примеры.

47. Сопряженные распределения (бета-распределение и распределение Дирихле) в задаче локального автоматического обучения байесовских сетей доверия и алгебраических байесовских сетей.

48. Обучение локальной структуры в байесовских сетях доверия.

49. Обучение глобальной структуры в байесовских сетях доверия.

50. Обучение глобальной структуры в алгебраических байесовских сетях. Перебор минимальных графов смежности. Особенности соответствующих алгоритмов и результатов.

51. Алгебраические байесовские сети в синтезе непротиворечивых баз фрагментов знаний по неполным, неточным, нечисловым данным.

52. Тропинчатые модели (path models).

53. Принципы Райхенбаха. Типы причинно-следственных связей.

54. Подход Райта к причинно-следственным моделям, принципы декомпозиции Райта.

55. Примеры приложений байесовских сетей и других вероятностных и логико-вероятностных графических моделей.

56. Марковские модели, модель Изинга. Сэмплирование (генерация выборки) по Гиббсу.

57. Стохастические булевы сети; булевы сети и клеточные автоматы. Индексация одномерных клеточных автоматов.

58. Принцип условной независимости в байесовских сетях.

59. Определение потенциала и операции над потенциалами. Потенциалы, условная вероятность и совместная вероятность. Операция маргинализации. Маргинализация и композиция распределений случайных бинарных последовательностей.

60. Сложность перебора структур при автоматическом обучении байесовских сетей доверия. Функционалы, оптимум которых ищется при решении задач автоматического обучения байесовских сетей доверия.

7. Технические средства обучения и математическое обучение. Применяется компьютер с ОС MS Windows XP, проектор и микрофон. На компьютере должны быть установлены JDK 6.14 или выше, Netbeans 6.51 или выше, MS Office 2007, Adobe Acrobat Reader 8 или выше, LaTeX (MikTeX 2.7 или выше), библиотека or124.jar, lp_solve 5.5 или иной действующей версии.

8. Активные методы обучения. В данном курсе применяются как классические аудиторные методы, так и методы, ориентированные на непосредственную апробацию полученных теоретических знаний при работе с программным кодом и готовыми программами и комплексами программ. Документ с возможными темами учебно-исследовательских работ выдается студентам на первом или втором лекционном занятии; студенты обладают возможностью выбора одной или нескольких тем. Кроме того, используются деловые игры для развития профессиональных навыков математиков-исследователей, системных аналитиков, проектировщиков и разработчиков программного обеспечения; темы деловых игр совпадают с формулировками тем курсовых работ и вопросов из примерного перечня: на занятии после постановки цели деловой игры и введения необходимых определений (при необходимости — дополнительных вопросов и указаний) разрабатывается план действий, ставятся математические задачи или задачи на проектирование элементов базы данных или комплекса программ, задачи выполняются двумя или более командами, результаты обсуждаются, формируется итоговый вариант решения или проекта.

9. Материальное обеспечение дисциплины. Аудитория должна быть оборудована компьютерами с установленным программным обеспечением, перечень которого указан в п. 7.