Байесовы сети Вероятностное моделирование в Байесовых сетях ООО «НейрОК» Терехов Сергей Александрович sta@neurok.ru@neurok.ru. - презентация

1 Байесовы сети Вероятностное моделирование в Байесовых сетях ООО «НейрОК» Терехов Сергей Александрович

2 Вероятностная трактовка данных Процесс измерения сопряжен с экспериментальными погрешностями; Изучаемая система является сложной, т.е. несводимой к сумме свойств отдельных компонент, и наблюдаемое многообразие данных может быть равновероятно объяснено великим множеством структурных описаний, при этом нельзя достоверно предпочесть ни одно из них; Объем измерений конечен и не может считаться исчерпывающим описанием системы. Как согласовать субъективные неопределенности в ожиданиях исследователей (beliefs) и объективные факты о статистике экспериментальных наблюдений (probabilities)?

3 Частотные (экспериментальные) вероятности Предельный результат «бесконечного» числа испытаний в повторяющихся условиях; Пример: «Вероятность выпадения орла при бросании этой монеты равна 0.52»; Вычисляется как доля «орлов» в пределе неограниченного числа попыток. Повторяющиеся условия? Неограниченное число попыток? Как экспериментально установить вероятность ?

4 Байесовы вероятности (ожидания) Количественное выражение степени ожиданий; Пример: «Вероятность того, что завтра будет дождь есть 0.3»; «Завтра» нельзя повторить; Ожидания субъективны и зависят от (индивидуальной) априорной информации; Частотные распределения наблюдений являются частным случаем. Все вероятности являются условными (обусловленными имеющейся информацией и опытом эксперта). Для получения «объективной» картины предполагается усреднение.

5 Субъективные ожидания Требуется оценить вероятность положительного исхода в каждой из трех ситуаций: 1. Знатная леди утверждает, что она может отличить на вкус, был ли чай налит в сливки или наоборот – сливки в чай. Ей удалось это проделать 10 раз в течение бала; 2. Азартный игрок утверждает, что он может предсказать, орлом или решкой выпадет монета (которую вы ему дадите). Он смог выиграть такое пари уже 10 раз за этот вечер, ни разу не проиграв; 3. Эксперт в классической музыке декларирует, что он в состоянии различить творения Гайдна и Моцарта лишь по одной странице партитуры. Он уверенно проделал это 10 раз в музыкальной библиотеке. Наши субъективные оценки вероятности этих трех ситуаций весьма отличаются, хотя мы имеем дело с повторяющимися событиями!

6 О повторяемости условий случайных событий Серия экспериментов с бросанием кубика, сделанного из сахара, на влажную поверхность стола. Вероятности исходов последующих испытаний зависят от относительной частоты исходов предыдущих испытаний, при этом исследуемая система каждый раз необратимо изменяется в результате каждого эксперимента. Такими свойствами обладают многие биологические, экономические и социальные системы.

7 Графы и вероятности: Байесовы сети Случайные переменные – узлы ориентированного графа Отношения прямой зависимости – ребра графа Каждая переменная может зависеть только от некоторого множества своих соседей Плотность совместной вероятности значений всех переменных редуцируется до произведения локальных условных плотностей Применения Байесовых сетей: медицина, социология, стратегическое планирование, риски, управление, финансы и экономика Вероятности и случайные события Теория графов Байесовы сети

8 Преподобный Томас Байес Преп. Томас Байес, математик, впервые использовавший вероятность в индуктивном смысле, и установивший основы вероятностного рассуждения и вывода. Какова вероятность события в будущих испытаниях, основываясь на числе предыдущих испытаний, в которых это событие не произошло? Теорема Байеса связывает априорные и апостериорные вероятности причин после наблюдения следствий. Труд «Essay Towards Solving a Problem in the Doctrine of Chances», Philosophical Transactions of the Royal Society of London (1763). Томас Байес похоронен на Bunhill Fields в центре Лондона (сейчас это парк). Bayes, Thomas (b. 1702, London – d. 1761, Tunbridge Wells, Kent),

9 Эксперты и экспертные системы «Логика» действий эксперта: Получение информации о состоянии окружающего мира Принятие решения, выбор действий, по поводу которых имеются определенные ожидания последствий Приобретение опыта путем сопоставления результатов действий и ожиданий и возврат к первому этапу. Развитие экспертных систем: От моделирования эксперта к моделированию предметной области От попыток учета неопределенности в правилах к использованию классической теории вероятностей и теории принятия решений От попыток замены эксперта – к оказанию ему помощи. Новый опыт и информация о мире позволяют эксперту сообразно действовать в будущем

10 Особенности вывода суждений в условиях неопределенности Байесова логика: суждение базируется на предыдущем опыте, уточняемом имеющимся объемом оперативной информации. Суть приобретаемого знания в условиях неопределенности состоит в понимании, влияет ли полученная информация на наши ожидания относительно других событий. Основная причина трудностей при использовании систем, основанных на правилах, состоит в учете "сторонних", "косвенных" последствий наблюдаемых событий; Сложности с интуитивным пониманием независимости: условная независимость, индуцированная зависимость, «попутное» объяснение.

11 Задача о траве Шерлока Холмса Шерлок Холмс вышел из дома утром и заметил, что трава вокруг влажная. Он рассудил: «Я думаю, что ночью был дождь. Следовательно, трава возле дома моего соседа, доктора Ватсона, вероятно, также влажная». Таким образом, информация о состоянии травы у дома Холмса повлияла на его ожидания относительно влажности травы у дома Ватсона. Холмс проверил состояние сборника дождевой воды и обнаружил, что тот - сухой. В результате Холмс вынужден изменить ход своих рассуждений, и состояние травы возле его дома перестает влиять на ожидания по поводу травы у соседа. Помимо дождя, Холмс мог просто забыть выключить поливальную установку накануне. Допустим, на следующее утро Холмс снова обнаруживает, что трава влажная. Это повышает его субъективные вероятности и для прошедшего дождя, и по поводу забытой дождевальной установки. Затем Холмс замечает, что трава у дома Ватсона также влажная, и заключает, что ночью был дождь.

12 Попутное объяснение (редукция причины, explaining away) Этот шаг рассуждений практически невозможно воспроизвести в машинных системах, основанных на правилах, однако он абсолютно естественен для человека. Влажность травы у дома Холмса объясняется дождем, и следовательно нет оснований продолжать ожидать, что была забыта включенной поливальная машина. Следовательно, возросшая, было, субъективная вероятность относительно забытой поливальной машины уменьшается до (практически) исходного значения, имевшего место до выхода Холмса из дома.

13 Задача о траве Шерлока Холмса Задача описывается Байесовой сетью с 4 переменными; Причины влажности травы у дома Холмса – дождь и/или поливальная установка; Как меняются вероятности этих причин после поступления информации о сборнике дождевой воды и о влажности травы возле дома Ватсона? Explaining Away: Как возникает попутное объяснение? (R) Дождь? (S) Полив? (W) Трава у дома Ватсона? (C) Трава у дома Холмса?

14 Отношения между переменными в Байесовых сетях Последовательное соединение (a) Влияние может распространяться от A к C и обратно, пока B не конкретизировано. Дивергентное соединение (b) Влияние может распространяться между потомками узла A, пока его значение не конкретизировано. Конвергентное соединение (c) Если об A ничего не известно, кроме того, что может быть выведено из информации о его предках B,C,…,E, то эти переменные предки являются разделенными. При уточнении A открывается канал взаимного влияния между его предками.

15 Индуцированная зависимость в конвергентных соединениях Две переменные соответствуют независимым подбрасываниям двух разных монет; Эти две переменные являются причинами для 3-й переменной- индикатора; Если известно значение 3-й переменной, то первые две переменные становятся зависимыми: знание одной полностью определяет другую. 1-я монета упала «орлом» Монеты в одинаковом состоянии? 2-я монета упала «орлом»

16 Сложности с интуитивным пониманием независимости Индуцированная зависимость в конвергентных соединениях. Explaining away – попутное объяснение. Условная зависимость – мысленное выделение группы фактов, для которых значение обуславливающей переменной определено. «Парадоксы»: Доход, пол и возраст в обществе Умственные и физические способности студентов колледжа

17 Формализация понятия независимости: d-разделимость Определение (d-разделимость). Две переменные A и B в Байесовой сети являются d-разделенными, если на каждом пути, соединяющем эти две вершины на графе, найдется промежуточная переменная V, такая что: Соединение с V последовательное или дивергентное, и значение V известно, либо Соединение конвергентное, и нет свидетельств ни о значении V, ни о каждом из ее потомков. В задаче Холмса переменные «Полив» и «Влажная трава у дома Ватсона» d-разделены, если известно, что был дождь (дивергентное соединение на графе).

18 Вероятности отдельных переменных Условная вероятность – вероятность появления A при условии B («после» B) Формула полной вероятности Теорема Байеса Теорема Байеса дает решение обратной задачи - какова вероятность наступления более раннего события B, если известно что более позднее событие A наступило?

19 Пример рассуждений на основе теоремы Байеса Факт: в водоеме обнаружено загрязнение с превышением ПДК. Потенциальные источники - два предприятия, причем выбросы на первом происходят в 9 раз чаще, чем на втором. Только 15% сбросов первого предприятия превышают ПДК. Для второго предприятия эта вероятность равна 92% Кто виноват?!

20 Байесова сеть Байесова сеть состоит из следующих понятий и компонент: Множество случайных переменных и направленных связей между переменными; Каждая переменная может принимать одно из конечного множества взаимоисключающих значений; Переменные вместе со связями образуют ориентированный граф без циклов; К каждой переменной-потомку A с переменными-предками B 1,…,B n приписывается таблица условных вероятностей P(A| B 1,…,B n )

21 Редукция совместной вероятности распределения нескольких случайных переменных в Байесовой сети: - состояния всех переменных – предков для переменной A j. Это выражение носит название цепного правила для полной вероятности. Пример редукции вероятности в задаче Холмса: 4D 2D Редукция полной вероятности в Байесовой сети

22 Вычисления в задаче Холмса Переменные, не имеющие предков описываются безусловными вероятностями, а их потомки на графе - условными (R) Дождь? (S) Полив? (W) Трава у дома Ватсона? (C) Трава у дома Холмса? Граф Байесовой сети Таблицы вероятностей R P(R) S P(S) R P(W=t|R) P(W=f|R) =-==== =-==== =-========-======== t 0.3 t 0.2 t f 0.7 f 0.8 f R S P(C=t|R,S) P(C=f|R,S) =-=-==========-========== t t t f f t f f

23 Полные вероятности событий: 1) трава у дома Холмса оказалась влажной, 2) у дома Ватсона наблюдается то же самое. Вычисления в задаче Холмса (продолжение) Вычисления вероятностей отдельных переменных проводятся путем маргинализации полной вероятности

24 Если известно, что был дождь, то вероятность наблюдения влажной травы повышается: Вычисления в задаче Холмса (продолжение) Условные вероятности вычисляются суммированием по всем возможным значениям переменных, значения которых не определены

25 Если Холмс выяснил, что трава у дома влажная, то каковы вероятности причин – дождя и поливальной установки? полученные вероятности выше априорных (0.3 и 0.2, соответственно): Вычисления в задаче Холмса (продолжение) Условные вероятности причин вычисляются на основе формулы для полной вероятности

26 Когда Холмс обнаружил, что трава у дома Ватсона также влажная, то вероятности причин изменились! Вычисления в задаче Холмса (продолжение) Вероятность не выключенной поливальной установки снизилась почти до первоначального (априорного) значения автоматически.

27 Точные и приближенные вычисления в полномасштабных приложениях Некоторые методы позволяют оценить законы распределения, другие обеспечивают только случайные выборки из распределений При росте числа переменных и набора значений отдельных переменных сложность точных вычислений растет комбинаторно. На практике широко используются приближенные алгоритмы: Метод Монте-Карло (различные вариации, MCMC, …) Вариационные методы Belief propagation

28 Байесова сеть ASIA Учебный пример Байесовой сети в области постановки диагноза (туберкулез, рак легких или бронхит), в зависимости от данных медицинской диагностики (X-ray, удушье, посещение Азии, курение). Lauritzen, Steffen L. and David J. Spiegelhalter (1988) "Local computations with probabilities on graphical structures and their application to expert systems" in J. Royal Statistics Society B, 50(2),

29 Метод выборок из латинских гиперкубов Выборки из значений многомерных латинских гиперкубов (Latin Hypercube Sampling ) – прямое обобщение решения задачи ладей на плоскости. LHS позволяют моделировать многомерное распределение при фиксированном объеме выборки.

30 Приближенные вычисления при помощи LHS Простейшая сеть Таблицы вероятностей Фрагмент гиперкуба Как при заданных распределения A и B распределена C? Для каждой строки гиперкуба используем значение в столбце для получения выборочного значения соответствующей переменной: {47,32,56} ->{a2,b1,c2} Распределение C дается гистограммой значений для каждой строки

31 Приближенные вычисления при помощи LHS В сложных сетях вычисления проводятся по цепочкам, от предков к потомкам. К розыгрышу очередной переменной можно приступать, когда значения всех ее предков в данном примере выборки уже установлены. Сложность вычислений пропорциональна числу переменных и размеру выборки, т.е. определяется размером гиперкуба. Результат представляется в форме выборочных гистрограмм распределения интересующих переменных. Метод латинского гиперкуба применим и для моделирования непрерывных распределений. В этом случае для розыгрыша безусловных вероятностей используется известный метод обратных функций распределения.

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

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

34 Байесово обучение параметров модели по экспериментальным данным Если структура связей в сети зафиксирована, то обучение состоит в выборе свободных параметров распределений условных вероятностей. Пример: Однопараметрическая задача бросания монеты. Параметр θ – вероятность выпадения «орла». Пусть в N экспериментах «орел» выпал ровно h раз. Классическая оценка параметра равна выборочной частоте h/N. Это также является классическим прогнозом исхода следующего эксперимента. В Байесовом подходе значение параметра само является случайной величиной, распределение которой используется при прогнозировании исхода следующего бросания монеты.

35 Байесово обучение параметров модели по экспериментальным данным Функция правдоподобия данных - биномиальное распределение: Априорная плотность распределения θ – бета-распределение: Апостериорное распределение параметра дается теоремой Байеса:

36 Прогноз исхода будущего эксперимента по Байесу Вероятность выпадения «орла» в будущем эксперименте: Вычисления для биномиального и бета-распределения: «Физический смысл» результата: использование априорного распределения эквивалентно добавлению искусственных (полученных в гипотетических предыдущих экспериментах) отсчетов «орлов» и «решек» в экспериментальную серию.

37 Обучение параметров Байесовой сети Пусть задано множество обучающих примеров D, каждый элемент множества – вектор значений для всех переменных Байесовой сети. Классическая схема – поиск максимума правдоподобия: Байесов вариант –априорные вклады в матрицы вероятностей. Переменные сети могут могут обучаться на отдельных наборах примеров, учитывающих значения только тех переменных, которые влияют на данную. Условные вероятности в Баейсовой сети могут быть представлены нейронной сетью или другими удачными аппроксимациями плотности вероятности.

38 Представление распределений в Байесовых сетях вероятностными деревьями Пусть имеется одна зависимая переменная и задано множество обучающих примеров. Выберем дискретизацию переменной y так, что в каждый отрезок попадает одинаковое число наблюдений. Априорная заселенность всех интервалов одинакова, что соответствует максимуму энтропии:

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

40 Правила в узлах энтропийного дерева Простейший класс правил – пороговый выбор по значению одного из аргументов. Наилучший аргумент определяется путем решения серии задач одномерной оптимизации. Иерархический процесс далее продолжается для подмножеств каждого узла. Процесс формально завершается по достижении нулевой энтропии для каждого узла самого нижнего уровня. Рис. Зависимость энтропии (в долях к исходному значению) от уровня иерархии дерева

41 Структура энтропийного дерева В итоге, каждому узлу полученного дерева приписывается: Эмпирическая оценка плотности условного распределения дискретизованной зависимой переменной (при условии отнесения примера к данному узлу); Оценка выборочной энтропии распределения в этом узле; Решающее правило, позволяющее выбрать дочернюю ветвь с дальнейшим уменьшением энтропии условного распределения.

42 Плотность распределения в иерархиях энтропийного дерева Представлена плотность вероятности распределения зависимой переменной при условии отнесения примера к данному узлу дерева При обучении может использоваться регуляризирующий критерий останова по предельной сложности дерева

43 Свойства энтропийных деревьев При дроблении множества данных до нуля энтропии полученное дерево является, очевидно, переобученным, т.к. в нем полностью запомнен весь шум, содержавшийся в данных. На практике для оценок обобщающей способности можно воспользоваться методикой кросс-валидации на основе бутстрэп-выборок. Метод всегда сходится, по крайней мере, за (N-1) шагов. Вычислительная сложность метода невысока и ограничивается решением задач одномерной оптимизации на отрезке.

44 Информационная значимость факторов Информационный вклад различных входных переменных в снижение энтропии весьма неоднороден. Все факторы (независимые переменные) можно упорядочить по степени уменьшения суммарной энтропии зависимой переменной, возникшей при использовании фактора в решающих правилах. Переменные, не использованные ни в одном из правил малозначимы. Рис. Относительная значимость факторов в задаче Boston Housing

45 Примеры приложений Байесовых сетей Естественной областью использования Байсовых сетей являются экспертные системы, которые нуждаются в средствах оперирования с вероятностями. Медицина Система PathFinder (Heckerman, 1990) разработана для диагностики заболеваний лимфатических узлов. PathFinder включает 60 различных вариантов диагноза и 130 переменных, значения которых могут наблюдаться при изучении клинических случаев. Система смогла приблизиться к уровню экспертов, и ее версия PathFinder-4 получила коммерческое распространение. Множество других разработок (Child, MUNIN, Painulim, SWAN и пр.) успешно применяются в различных медицинских приложениях [Jensen96].

46 Байесова сеть ALARM в области медицинской диагностики Диагностическая система ALARM (A Logical Alarm Reduction Mechanism) в области диагностики и мониторинга состояния пациента. BeinlichSCC89: Beinlich, Ingo, H. J. Suermondt, R. M. Chavez, and G. F. Cooper (1989) "The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks" in Proc. of the Second European Conf. on Artificial Intelligence in Medicine (London, Aug.), 38, Also Tech. Report KSL-88-84, Knowledge Systems Laboratory, Medical Computer Science, Stanford Univ., CA.

47 Логическая архитектура Байесовой сети в полномасштабном приложении ALARM (медицина)

48 Описание переменных сети ALARM

49 Примеры приложений Байесовых сетей Космические и военные применения Система поддержки принятия решений Vista (Eric Horvitz) применяется в Центре управления полетами NASA (NASA Mission Control Center) в Хьюстоне. Система анализирует телеметрические данные и в реальном времени идентифицирует, какую информацию нужно выделить на диагностических дисплеях. В исследовательской лаборатории МО Австралии Байесовы сетиприменяются в тактических задачах исследования операций. Учебная модель «Operation Dardanelles» охраны территориальной зоны с моря включает в себя различные тактические сценарии поведения конфликтующих сторон, данные о передвижении судов, данные разведнаблюдений, и другие переменные. Последовательное поступление информации о действиях противников позволяет синхронно прогнозировать вероятности различных действий в течение конфликта.

50 Anti-Air Treat Identification Problem Переменные задачи Связи между переменными

51 Anti-Air Treat Identification Problem

52

53 Примеры приложений Байесовых сетей Компьютеры и системное программное обеспечение Microsoft: управление интерфейсными агентами в системе Office, в диагностике проблем работы принтеров и других справочных и wizard-подсистемах. Обработка изображений и видео Восстановление 3D сцен из динамической 2D информации, синтез статических изображений высокой четкости из видеосигнала. Финансы и экономика Оценка риска и прогноз доходности портфелей финансовых инструментов. Основные достоинства Байесовых сетей: возможность совместного учета количественных и качественных рыночных показателей, динамическое поступление новой информации, а также явные зависимости между существенными факторами, влияющими на финансовые показатели, наглядное игровое моделирование.

54 Компьтерный пакет Netica Netica - мощная, удобная в работе программа для работы с графовыми вероятностными моделями. Коммерчески доступна с 1995 г. В настоящее время Netica является одним из наиболее широко используемых инструментов для разработки Байсовых сетей. Рис. Пример интерфейса системы NETICA

55 Ресурсы Интернет по Байесовым сетям - Ассоциация Анализа Неопределенности в Искусственном Интеллекте (Association for Uncertainty in Artificial Intelligence - AUAI) - Norsys Software Corp (NETICA) - Компания Knowledge Industries - Data Digest Corporation - Компания HUGIN Expert - Компания BayesWare, Ltd - Персональные страницы специалистов по Байесовым методам

56 Итоги Байесовы вероятностные методы обучения машин являются существенным шагом вперед, в сравнении с популярными моделями "черных ящиков". Они дают понятное объяснение своих выводов, допускают логическую интерпретацию и модификацию структуры отношений между переменными задачи, а также позволяют в явной форме учесть априорный опыт экспертов. Благодаря удачному представлению в виде графов, Байесовы сети весьма удобны в пользовательских приложениях. Байесовы сети базируются на фундаментальных положениях и результатах теории вероятностей, разрабатываемых в течение нескольких сотен лет, что и лежит в основе их успеха в практической плоскости. Редукция совместного распределения вероятностей в виде произведения условных вероятностей, зависящих от малого числа переменных, позволяет избежать комбинаторных взрывов при моделировании.

57 Перспективы Байесова методология, в действительности, шире, чем семейство способов оперирования с условными вероятностями в ориентированных графах. Она включает в себя также модели с симметричными связями (случайные поля и решетки), модели динамических процессов (Марковские цепи), а также широкий класс моделей со скрытыми переменными, позволяющих решать вероятностные задачи классификации, распознавания образов и прогнозирования. Новые области применений: Динамические процессы и динамическое программирование Оптимальное управление стохастическими системами Принятие решений в автономных интеллектуальных системах