2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

КАФЕДРА САПР и ПК

Применение Байесовых сетей.

ПО КУРСУ «МОДЕЛИРОВАНИЕ»

Выполнил слушатель

группы ИВТ-363

Ефанов П.А.

Проверил

Кузнецов В.В.

Волгоград 2006

Содержание.

• Содержание. 2
• Введение 3
• Основные понятия и определения 5
• • Законы теории вероятностей. 5
  • • Законы сложения вероятностей. 6
    • Условные вероятности. 6
    • Формула Байеса. 7
  • Введение в байесовские сети доверия. 7
• Моделирование в условиях неопределенности 8
• • Экспертные системы и формальная логика 8
  • Особенности вывода суждений в условиях неопределенности 9
  • Определение d-разделимости 11
• Использование Байесовых сетей. 13
• • Вероятности прогнозируемых значений отдельных переменных 13
  • Пример построения простейшей байесовской сети доверия. 13
  • Расчет в байесовской сети. 15
  • Байесовские сети доверия как одно из направлений современных экспертных систем. 16
  • Представление знаний с использованием байесовской сети доверия и условная независимость событий. 16
  • Замечание о субъективных вероятностях и ожидания. 17
  • Синтез сети на основе априорной информации. 18
• Пример использования Байесовых сетей 19
• • Медицина 19
  • Космические и военные применения 19
  • Компьютеры и системное программное обеспечение 19
  • Обработка изображений и видео 19
  • Финансы и экономика 20
• Описание прикладных программ 21
• • AUAI -- Ассоциация анализа неопределенности в искусственном интеллекте 21
  • NETICA 21
  • Knowledge Industries 22
  • Data Digest Corporation 22
  • BayesWare, Ltd 22
  • HUGIN Expert 22
• Выводы 24
• Список используемой литературы. 25

Введение

Байесовы сети представляют собой графовые модели вероятностных и причинно-следственных отношений между переменными в статистическом информационном моделировании. В байесовых сетях могут органически сочетаться эмпирические частоты появления различных значений перемен-ных, субъективные оценки «ожиданий» и теоретические представления о математических вероятностях тех или иных следствий из априорной ин-формации. Это является важным практическим преимуществом и отличает байесовы сети от других методик информационного моделирования.

Наблюдаемые события редко могут быть описаны как прямые следствия строго детерминированных причин. На практике широко применяется ве-роятностное описание явлений. Обоснований тому несколько: и наличие неустранимых погрешностей в процессе экспериментирования и наблю-дений, и невозможность полного описания структурных сложностей изу-чаемой системы, и неопределенности вследствие конечности объема наблюдений.

На пути вероятностного моделирования встречаются определенные слож-ности, которые (если отвлечься от чисто теоретических проблем) можно условно разделить на две группы:

технические (вычислительная сложность, «комбинаторные взрывы» и т.п.);

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

Для иллюстрации одной из «идейных» сложностей рассмотрим простой пример из области вероятностного прогнозирования. Требуется оценить вероятность положительного исхода в каждой из трех ситуаций:

Знатная леди утверждает, что она может отличить на вкус, был ли чай налит в сливки или наоборот -- сливки в чай. Ей удалось это проделать 10 раз в течение бала.

Азартный игрок утверждает, что он может предсказать, орлом или решкой выпадет монета (которую вы ему дадите). Он смог выиграть такое пари уже 10 раз за этот вечер, ни разу не проиграв!

Эксперт в классической музыке заявляет, что он в состоянии разли-чить творения Гайдна и Моцарта лишь по одной странице партитуры. Он уверенно проделал это 10 раз в музыкальной библиотеке.

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

Особенно затруднительно получить формулировку, понятную вычисли-тельной машине.

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

Часть из указанных проблем решается в вероятностных байесовых се-тях, которые представляют собой графовые модели причинно-следствен-ных отношений между случайными переменными. В байесовых сетях мо-гут органически сочетаться эмпирические частоты появления различных значений переменных, субъективные оценки «ожиданий» и теоретические представления о математических вероятностях тех или иных следствий из априорной информации. Это является важным практическим преиму-ществом и отличает байесовы сети от других методик информационного моделирования.

Байесовы сети широко применяются в таких областях, как медицина, стратегическое планирование, финансы и экономика.

Основные понятия и определения

Законы теории вероятностей.

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

Эксперимент может быть связан также с непрерывным пространством событий.

Если в эксперименте, состоящем из n опытов, событие Е имело место m раз, то вероятность P{E} появления события Е математически определяется соотношением

Приведенное определение означает, что если эксперимент повторяется бесконечное число раз, то, искомая вероятность представляется граничным значение дроби m/n.

По определению , где вероятность P{E} равна 0, если событие E невозможно, и 1, если оно достоверно.

Законы сложения вероятностей.

Для двух событий E и F запись E+F означает их объединение, а EF - пересечение. События E и F называются несовместными (взаимно исключающими), если они не пересекаются, т.е. наступление одного события исключает возможность реализации другого. При принятых определениях закон сложения вероятностей определяется соотношением

Первая строка системы в случае несовместности E и F, вторая - иначе.

Вероятность того, что события E и F произойдут одновременно, обозначается как P{EF}. Если эти события независимы, тогда

Условные вероятности.

Для двух события E и F условная вероятность события E при условии, что наступило событие F, обозначается как P{E|F} и определяется по формуле

Если событие E содержится в событии F (т.е. множество исходов E является подмножеством исходов F), тогда

Два события E и F являются независимыми тогда и только тогда, когда выполняется равенство P{E|F}=P{E}. В этом случае формула условной вероятности сводится к следующему

Теорема умножения, если соответствующие условные вероятности определены

Теорема умножения для большого числа событий, если соответствующие условные вероятности определены

Формула полной вероятности для группы несовместных событий Bi

Формула Байеса.

Пусть A_i - полная группа несовместных событий, тогда формула Байеса (формула перерасчета гипотез) и B некоторое событие положительной вероятности

Доказательство следует из теоремы умножения и формулы полной вероятности.

Введение в байесовские сети доверия.

Байесовские сети доверия - Bayesian Belief Network - используются в тех областях, которые характеризуются наследованной неопределённостью. Эта неопределённость может возникать вследствие:

1. неполного понимания предметной области;

2. неполных знаний;

3. когда задача характеризуется случайностью.

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

Соединения методом причин и следствий позволяют более просто оценивать вероятности событий. В реальном мире оценивание наиболее часто делается в направлении от “наблюдателя” к “наблюдению”, или от “эффекта” к “следствию”, которое в общем случае более сложно оценить, чем направление “следствие -> эффект”, то есть в направлении от следствии.

Рис.1. Пример простейшей байесовской сети доверия.

Рассмотрим пример сети (рис.1), в которой вероятность пребывания вершины «e» в различных состояниях (ek) зависит от состояний (ci , dj) вершин «c» и «d» и определяется выражением:

где p(ek|ci, dj) - вероятность пребывания в состоянии ek в зависимости от состояний ci, dj. Так как события, представленные вершинами «c» и «d» независимы, то

p(ek |ci , dj) = p(ci) *p(dj).

Рис.2. Двухуровневая БСД.

Рассмотрим пример более сложной сети (рис.2). Данный рисунок иллюстрирует условную независимость событий. Для оценки вершин «c» и «d» используются те же выражения, что и для вычисления p(e_k), тогда:

,

.

Из этих выражений видно, что вершина «e» условно не зависит от вершин A1, A2, B1, B2, так как нет стрелок непосредственно соединяющих эти вершины.

Рассмотрев эти примеры попробуем теперь более точно определить основные понятия, используемые в БСД. Байесовские сети доверия -- это направленный ациклический граф, обладающий следующими свойствами:

1. каждая вершина представляет собой событие, описываемое случайной величиной, которая может иметь несколько состояний;

2. все вершины, связанные с “родительскими” определяются таблицей условных вероятностей (ТУВ) или функцией условных вероятностей (ФУВ);

3. для вершин без “родителей” вероятности её состояний являются безусловными ( маргинальными).

Другими словами, в байесовских сетях доверия вершины представляют собой случайные переменные, а дуги - вероятностные зависимости, которые определяются через таблицы условных вероятностей. Таблица условных вероятностей каждой вершины содержит вероятности состояний этой вершины при условии состояний её “родителей”.

Моделирование в условиях неопределенности

Экспертные системы и формальная логика

Попробуем проследить за способом работы эксперта в некоторой опре-деленной области. Примерами экспертов являются врач, проводящий об-следование, финансист, изучающий условия предоставления ссуды, либо пилот, управляющий самолетом.

Действия эксперта могут условно быть представлены в виде повторя-ющейся последовательности из трех этапов:

1. получение информации о состоянии окружающего мира;

2. принятие решения относительно выбора некоторых действий, по по-воду которых у эксперта имеются определенные ожидания послед-ствий;

3. приобретение опыта путем сопоставления результатов действий и ожиданий и возврат к первому этапу.

Приобретенный новый опыт и информация о мире позволяют эксперту сообразно действовать в будущем. Попытки компьютерного моделирования действий эксперта привели в конце 60-х годов к появлению экспертных систем (ЭС) , которые ча-ще всего основывались на продукционных правилах типа «ЕСЛИ условие, ТО факт или действие». Будущее подобных систем связывалось при этом с заменой экспертов их моделями. Однако после первых успехов обнажи-лись проблемы, и первой среди них -- серьезные затруднения при попытках работы с нечеткой, недоопределенной информацией.

Следующие поколения ЭС претерпели кардинальные изменения:

1. вместо моделирования эксперта моделируется предметная область;

2. вместо попыток учета неопределенности в правилах -- использование классической теории вероятностей и теории принятия решений;

3. вместо попыток замены эксперта -- оказание ему помощи.

В конце 80-х годов были предложены обобщения ЭС в виде байесовых сетей, и была показана практическая возможность вычислений вероят-ностных выводов даже для сетей больших размеров. Вернемся к трехэтапному описанию профессиональных действий экс-перта. Сейчас нас будет интересовать вопрос, как наблюдения эксперта, т. е. получение им информации о внешнем мире, изменяют его ожидания по поводу ненаблюдаемых событий?

Особенности вывода суждений в условиях неопределенности

Суть приобретаемого знания в условиях неопределенности состоит в пони-мании, влияет ли полученная информация на наши ожидания относительно других событий. Основная причина трудностей при использовании систем, основанных на правилах, состоит в учете «сторонних», «косвенных» по-следствий наблюдаемых событий. Проиллюстрируем это на уже успевшем стать классическим примере.

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

Теперь рассмотрим две возможные причины, почему трава у дома Холмса оказалась влажной. Помимо дождя, Холмс мог просто забыть вы-ключить поливальную установку накануне. Допустим, на следующее утро Холмс снова обнаруживает, что трава влажная. Это повышает его субъек-тивные вероятности и для прошедшего дождя, и по поводу забытой дожде-вальной установки. Затем Холмс обнаруживает, что трава у дома Ватсона также влажная и заключает, что ночью был дождь.

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

Важная особенность «попутного объяснения» состоит в изменении от-ношений зависимости между событиями по мере поступления информа-ции. До выхода из дома Холмса факты дождя и работы поливальной уста-новки были независимы. После получения информации о траве у дома они стали зависимыми. Далее, когда появилась информации о влажности травы у дома Ватсона, состояние зависимости вновь изменилось.

Эту ситуацию удобно описать при помощи графа, узлы которого пред-ставляют события (или переменные), а пара узлов (A, B) связывается на-правленным ребром, если информация об A может служить причиной для B. В этом случае узел A будет родителем для B, который, в свою очередь, называется узлом-потомком по отношению к A.

История с травой у Холмса и Ватсона представлена на рис. 1.

Рисунок 1 Граф рассуждений Шерлока Холмса

Граф на рис. 1 может быть отнесен к семейству байесовых сетей. В дан-ном примере переменные в узлах могут принимать только булевы значения 1 или 0 (да/нет). Из графа на рис. 1 можно сделать несколько полезных выводов о зависимости и независимости переменных. В традиционной постановке байесовы сети не предназначены для оперирования с непрерывным набором состояний (например, с действительным числом на заданном отрез-ке). Для представления действительных чисел в некоторых приложениях можно провести разбиение отрезка на сегменты и рассматривать дискретный набор их центров.

Например, если известно, что ночью не было дождя, то информация о состоянии травы у дома Ватсона не оказывает влияния на ожидания по поводу состояния травы у дома Холмса.

В середине 80-х годов были подробно проанализированы способы, ко-торыми влияние информации распространяется между переменными в байесовой сети. Будем считать, что две переменные разделены, если но-вые сведения о значении одной из них не оказывают влияния на ожидания по поводу другой. Если состояние переменной известно, мы будем назы-вать такую переменную конкретизированной.

В байесовой сети возможны три типа отношений между переменными:

1. последовательные соединения (рис. 2a);

2. дивергентные соединения (рис. 2b),;

3. конвергентные соединения (рис. 2c).

Ситуация на рис. 2c требует, по-видимому, дополнительных поясне-ний--как возникает зависимость между предками конвергентного узла, когда становится известным значение потомка. Для простоты рассмот-рим пример, когда узел A имеет всего двух предков -B и C. Пусть эти две переменные отвечают за выпадение орла и решки при независимом броса-нии двух разных монет, а переменная A -- логический индикатор, который «загорается», когда обе монеты оказались в одинаковом состоянии (напри-мер, обе - решки). Теперь легко понять, что если значение индикаторной переменной стало известным, то значения B и C стали зависимыми -- знание одного из них полностью определяет оставшееся.

Общее свойство (условной) независимости переменных -- узлов в бай-есовой сети получило название d-разделения (d-separation).

Определение d-разделимости

Две переменные A и B в байесовой сети являются d-разделенными, если на каждом пути, соединяющем эти две вершины на графе, найдется промежуточная переменная V, такая что:

1. соединение с V последовательное или дивергентное и значение V известно, либо

2. соединение конвергентное и нет свидетельств ни о значении V, ни о каждом из ее потомков.

Так, в сети задачи Шерлока Холмса (рис. 1) переменные «Полив?» и «Трава у дома Ватсона?» являются d-разделенными. Граф содержит на пути между этими переменными конвергентное соединение с переменной «Трава у до-ма Холмса?».

(a)

(b)

(c)

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

Свойство d-разделимости соответствует особенностям логики экспер-та-человека, поэтому крайне желательно, чтобы в рассуждениях машин относительно двух d-разделенных переменных новая информация об од-ной из них не изменяла степень детерминированности второй переменной. Формально, для переменных A и C, независимых при условии B, имеет место соотношение P(A | B) = P(A | B, C).

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

Вот простой пример, поясняющий эту трудность: в некотором сообще-стве мужчины среднего возраста и молодые женщины оказались матери-ально более обеспеченными, чем остальные люди. Тогда при условии фик-сированного повышенного уровня обеспеченности пол и возраст человека оказываются условно зависимыми друг от друга!

Еще один классический пример, связанный с особенностями условных вероятностей. Рассмотрим некоторый колледж, охотно принимающий на обучение сообразительных и спортивных молодых людей (и тех, кто обла-дает обоими замечательными качествами!). Разумно считать, что среди всех молодых людей студенческого возраста спортивные и интеллектуальные показатели независимы. Теперь если вернуться к множеству зачисленных в колледж, то легко видеть, что высокая сообразительность эффективно понижает вероятность спортивности и наоборот, так как каждого из этих свойств по-отдельности достаточно для приема в колледж. Таким образом, спортивность и умственные показатели оказались зависимыми при условии обучения в колледже.

Использование Байесовых сетей.

Вероятности прогнозируемых значений отдельных переменных

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

Приведем пример точных вычислений в простой байесовой сети, мо-делирующей задачу Шерлока Холмса. Обозначения и смысл пе-ременных в сети : R --был ли дождь, S -- включена ли поливальная установка, C -- влажная ли трава у дома Холмса, и W -- влажная ли трава у дома Ватсона.

Все четыре переменные принимают булевы значения 0 -- ложь, (f) или 1 -- истина (t). Совместная вероятность P(R, S, C, W), таким образом, да-ется совокупной таблицей из 16 чисел. Таблица вероятностей нормирована, так что

Зная совместное распределение, легко найти любые интересующие нас условные и частичные распределения. Например, вероятность того, что ночью не было дождя при условии, что трава у дома Ватсона -- влажная, дается простым вычислением:

Из теоремы об умножении вероятностей полная вероятность пред-ставляется цепочкой условных вероятностей:

P(R, S, C, W) = P(R) * P(S | R) * P(C |R,S)*P(W | R, S, C).

В описанной ранее байесовой сети ориентированные ребра графа отража-ют суть вероятностей, которые реально имеют место в задаче. Поэтому формула для полной вероятности существенно упрощает-ся:

P(R, S, C, W) = P(R) *P(S) * P(C |R,S)*P(W | R).

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

Пример построения простейшей байесовской сети доверия.

Рассматриваем небольшую яблочную плантацию «яблочного Джека». Однажды Джек обнаружил, что его прекрасное яблочное дерево лишилось листвы. Теперь он хочет выяснить, почему это случилось. Он знает, что листва часто опадает, если:

дерево засыхает в результате недостатка влаги; или дерево болеет.

Данная ситуация может быть смоделирована байесовской сетью доверия, содержащей 3 вершины: «Болеет», «Засохло» и «Облетело».

Рис.1. Пример байесовской сети доверия с тремя событиями.

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

Вершина “Болеет” говорит о том, что дерево заболело, будучи в состоянии «болеет», в противном случае она находится в состоянии «нет». Аналогично для других двух вершин. Рассматриваемая байесовская сеть доверия, моделирует тот факт, что имеется причинно-следственная зависимость от события “Болеет” к событию “Облетело” и от события “Засохло” к событию “Облетело”. Это отображено стрелками на байесовской сети доверия.

Когда есть причинно-следственная зависимость от вершины А к другой вершине B, то мы ожидаем, что когда A находится в некотором определённом состоянии, это оказывает влияние на состояние B. Следует быть внимательным, когда моделируется зависимость в байесовских сетях доверия. Иногда совсем не очевидно, какое направление должна иметь стрелка.

Например, в рассматриваемом примере, мы говорим, что имеется зависимость от “Болеет” к “Облетело”, так как когда дерево болеет, это может вызывать опадание его листвы. Опадание листвы является следствием болезни, а не болезнь - следствием опадания листвы.

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

Приведенные таблицы иллюстрируют ТУВ для трёх вершин байесовской сети доверия. Заметим, что все три таблицы показывают вероятность пребывания некоторой вершины в определённом состоянии, обусловленным состоянием её родительских вершин. Но так как вершины Болеет и Засохло не имеют родительских вершин, то их вероятности являются маргинальными, т.е. не зависят (не обусловлены) ни от чего.

На данном примере мы рассмотрели, что и как описывается очень простой байесовской сетью доверия. Современные программные средства (такие как MSBN, Hugin и др.) обеспечивают инструментарий для построения таких сетей, а также возможность использования байесовских сетей доверия для введения новых свидетельств и получения решения (вывода) за счёт пересчёта новых вероятностей во всех вершинах, соответствующих вновь введенным свидетельствам.

В нашем примере пусть известно, что дерево сбросило листву. Это свидетельство вводится выбором состояния «да» в вершине “Облетело”. После этого можно узнать вероятности того, что дерево засохло. Для приведенных выше исходных данных, результаты вывода путем распространения вероятностей по БСД будут:

p( “Болеет” = «болеет» | “Облетело” = «да») = 0,47; p( “Засохло” = «засохло» | “Облетело” = «да») = 0,49.

Расчет в байесовской сети.

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

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

,

где D - объединения всех поступивших в систему данных;

Vji - композиционные высказывания, составленные из элементарных, то есть множество значений Xi составляют Vji ;

Xi - пропозиционные переменные (то есть переменные, значениями которых являются высказывания), определяющие состояние вершин БСД.

При этом процесс распространения вероятностей в БСД основывается на механизме пересчёта, в основе функционирования которого лежит следующая последовательность действий:

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

Этот процессор осуществляет пересчёт апостериорных вероятностей Bel(Vji) для всех возможных значений Vji данной переменной Xi и посылает соседим вершинам ответные сообщения.

Деятельность процессора инициируется нарушением условий согласованности с состояниями соседних процессоров и продолжается до восстановления этих условий.

В некоторых системах, реализующих байесовские сети доверия используется метод noisy or gate, позволяющий существенно упростить вычислительный процесс. Суть его заключается в том, что в ряде примеров вершина «y» может быть условно независима от целого ряда вершин «xr» , где r = 1,2,..., n. Для того, чтобы сократить оценку 2n вероятностей, которые необходимы при использовании таблиц условных вероятностей, и используется данный метод. Согласно ему вероятность «y» в зависимости от n вершин «xr» оценивается как

,

что позволяет оценить только p(y | x 1), p(y | x 2) ... p(y | x n), и на их основании определить оценку p( y | x1 x2 ... xn).

Байесовские сети доверия как одно из направлений современных экспертных систем.

Выбор байесовских сетей доверия в качестве ЭС по сравнению с другими направлениями их построения обусловлен рядом причин.

1. Логический вывод в байесовских сетях доверия является трактуемым с вычислительной точки зрения, так как теория, лежащая в его основе, имеет аксиоматическое обоснование, отработанное в течение последних десятилетий. В то время, как системы, основанные на теории нечётких множеств, на теории функций доверия, теории Демпстера - Шефера не имеет строгого математического обоснования и в большинстве случаев используют эвристические процедуры ( ЭС типа MYCIN, EMYCIN и т.д.).

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

3. Метод noisy or gate обеспечивает эффективное вычисление условных вероятностей.

4. Несмотря на то, что теорию вероятности зачастую критикуют с точки зрения её использования в «знаниях», она не нарушает общих представлений о «замкнутом мире» объектов.

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

Рассмотрим фрагмент представления медицинской БЗ, в которой можно выделить заболевания, симптомы их проявления, а также факторы риска, влияющие на возникновение заболеваний. Пусть некоторая упрощённая модель качественного описания БЗ имеет вид, приведенный на рис.2. Эта модель соответствует следующему набору медицинских знаний:

Одышка [o] может быть вследствие туберкулёза [t], рака лёгких [r] или бронхита [b], а также вследствие ни одного из перечисленных заболеваний или более, чем одного.

Визит в Азию [a] повышает шансы туберкулёза [t].

Курение [k] - фактор риска, как для рака [r], так и бронхита [b].

Результаты рентгена, определяя затемнённость в лёгких не позволяют различить рак [r] и туберкулёз [t], так же как не определяет факт наличия или отсутствия одышки [o].

Последний факт представляется в графе промежуточной переменной (событием) [tr]. Эта переменная соответствует логической функции «или» для двух родителей ([t] и [r]) и она означает наличие либо одной, либо двух болезней или их отсутствие.

Рис.2. Представление фрагмента модели медицинской БЗ в виде БСД.

Важное понятие байесовской сети доверия - это условная независимость случайных переменных, соответствующих вершинам графа. Две переменные A и B являются условно независимыми при данной третьей вершине C, если при известном значении C, значение B не увеличивает информативность о значениях A, то есть

p ( A | B, C ) = p ( A | C ) .

Если имеется факт, что пациент курит, то мы устанавливаем наши доверия относительно рака и бронхита. Однако наши доверия относительно туберкулёза не изменяются. То есть [t] условно не зависит, от [k] при данном пустом множестве переменных

p ( t | k ) = 0

Поступления положительного результата рентгена пациента повышают наши доверия относительно туберкулёза и рака, но не относительно бронхита. То есть [b] - условно не зависит от [x] при данном k

p ( b | x, k ) = p ( b | k )

Однако, если бы знали также, что у пациента учащённое дыхание [o], то рентгеновские результаты также имели бы воздействие на наше доверие относительно бронхита. То есть [b] условно зависит от [x] при данных o и k. Таким образом, логический вывод в БСД означает вычисление условных вероятностей для одних переменных при наличии информации (свидетельств) о других. При этом для распространения вероятностей используется теорема Байеса.

Замечание о субъективных вероятностях и ожидания.

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

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

Использование субъективных ожиданий в байесовых сетях является единственной альтернативой на практике, если необходим учет мнения экспертов (например, врачей или социологов) о возможности наступления события, к которому неприменимо понятие повторяемости, а также невоз-можно его описание в терминах совокупности элементарных событий.

Синтез сети на основе априорной информации.

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

Для синтеза сети необходимо выполнить следующие действия:

1. сформулировать проблему в терминах вероятностей значений целе-вых переменных;

2. выбрать понятийное пространство задачи, определить переменные,
имеющие отношение к целевым переменным, описать возможные
значения этих переменных;

3. выбрать на основе опыта и имеющейся информации априорные ве-роятности значений переменных;

4. описать отношения «причина-следствие» (как косвенные, так и пря-мые) в виде ориентированных ребер графа, разместив в узлах пере-менные задачи;

5. для каждого узла графа, имеющего входные ребра указать оценки
вероятностей различных значений переменной этого узла в зависи-мости от комбинации значений переменных-предков на графе.

Эта процедура аналогична действиям инженера по знаниям при постро-ении экспертной системы в некоторой предметной области. Отношения зависимости, априорные и условные вероятности соответствуют фактам и правилам в базе знаний ЭС.

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

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

Пример использования Байесовых сетей

Естественной областью использования байесовых сетей являются эксперт-ные системы, которые нуждаются в средствах оперирования с вероятностя-ми.

Медицина

Система PathFinder (Heckerman, 1990) разработана для диагностики забо-леваний лимфатических узлов. PathFinder включает 60 различных вариан-тов диагноза и 130 переменных, значения которых могут наблюдаться при изучении клинических случаев. Система смогла приблизиться к уровню экспертов, и ее версия PathFinder-4 получила коммерческое распростране-ние.

Множество других разработок (Child, MUNIN, Painulim, SWAN и др.) успешно применяются в различных медицинских приложениях .

Космические и военные применения

Система поддержки принятия решений Vista (Eric Horvitz) применяется в Центре управления полетами NASA (NASA Mission Control Center) в Хью-стоне. Система анализирует телеметрические данные и в реальном времени идентифицирует, какую информацию нужно выделить на диагностических дисплеях.

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

Компьютеры и системное программное обеспечение

В фирме Microsoft методики байесовых сетей применены для управления интерфейсными агентами-помощниками в системе Office (знакомая мно-гим пользователям «скрепка»), в диагностике проблем работы принтеров и других справочных и wizard-подсистемах.

Обработка изображений и видео

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

Финансы и экономика

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

Результаты моделирования представляются в форме гистограмм рас-пределений вероятностей, что позволяет провести детальный анализ соот-ношений «риск-доходность». Весьма эффективными являются также ши-рокие возможности по игровому моделированию.

Описание прикладных программ

Байесовы сети -- интенсивно развивающаяся научная область, многие результаты которой уже успели найти коммерческое применение. Приводится список популярных программ, спектр которых, отражает общую картину, возникшую в последние 10-15 лет.

AUAI -- Ассоциация анализа неопределенности в искусственном интеллекте

(URL: http://www.auai.org/)

Ассоциация анализа неопределенности в искусственном интеллекте (Association for Uncertainty in Artificial Intelligence -- AUAI) -- некоммерческая организация, главной целью которой является проведение ежегодной Конференции по неопределенности в искусственном интеллекте (UAI).

Конференция UAI-2002 прошла в начале августа 2002 года в Университете Альберты (Эдмонтон, Канада). Конференции UAI проходят ежегодно, начиная с 1985 года, обычно в совместно с другими конференциями по смежным проблемам. Труды конференций издаются в виде книг, однако многие статьи доступны в сети.

NETICA

(URL: http://www.norsys.com/index.html)

Norsys Software Corp. -- частная компания, Расположенная в Ванкувере (Канада). Norsys специализируется в разработке программного обеспечения для байесовых сетей. Программа Netica --основное достижение компании, разрабатывается с 1992 года и стала коммерчески доступной в 1995 году. В настоящее время Netica является одним из наиболее широко используемых инструментов для разработки байесовых сетей.

Версия программы с ограниченной функциональностью свободно доступна на сайте фирмы Norsys.

Рисунок 1 Пример байесовой сети в приложении Netica

Netica -- мощная, удобная в работе программа для работы с графовыми вероят-ностными моделями. Она имеет интуитивный и приятный интерфейс пользователя для ввода топологии сети. Соотношения между переменными могут быть заданы, как индивидуальные вероятности, в форме уравнений, или путем автоматического обучения из файлов данных (которые могут содержать пропуски).

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

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

Knowledge Industries

(URL: http://www.kic.com/)

Knowledge Industries --ведущий поставщик программных инструментальных средств для разработки и внедрения комплексных диагностических систем. При проектировании сложных и дорогостоящих вариантов систем диагностик в компа-нии используется байесовы сети собственной разработки.

Data Digest Corporation

(URL: http://www.data-digest.com/home.html)

Data Digest Corporation является одним из лидеров в применении методов байесовых сетей к анализу данных.

BayesWare, Ltd

(URL: http://www.bayesware.com/corporate/profile.html)

Компания BayesWare основана в 1999 году. Она производит и поддерживает про-граммное обеспечение, поставляет изготовленные на заказ решения, предоставляет программы обучения, и предлагает услуги консультирования корпоративным за-казчикам и общественным учреждениям. Одна из успешных разработок компании, Bayesware Discoverer, основана на моделях байесовых сетей.

HUGIN Expert

(URL: http://www.hugin.com/)

Компания Hugin Expert была основана в 1989 году в Ольборге, (Дания). Их основ-ной продукт Hugin начал создаваться во время работ по проекту ESPRIT, в котором системы, основанные на знаниях, использовались для проблемы диагностирова-ния нервно-мышечных заболеваний. Затем началась коммерциализация результа-тов проекта и основного инструмента -- программы Hugin. К настоящему моменту Hugin адаптирована во многих исследовательских центрах компании в 25 различ-ных странах, она используется в ряде различных областей, связанных с анализом решений, поддержкой принятия решений, предсказанием, диагностикой, управле-нием рисками и оценками безопасности технологий.

Hugin является программой реализацией системы принятия решений на основе байесовских сетей доверия. Имеет две версии Pro и Explorer. Функционирует в среде OS Windows95, Windows NT, а также имеет версию UNIX. Эта система имеет развитый интерфейс и позволяет достаточно просто создавать базы знаний и фактов. Использует два основных режима работы:

режим редактирования и построения причинно-следственной сети, а также заполнения таблиц условных вероятностей, являющихся количественным описанием БЗ.

режим расчёта вероятностных оценок для принятия решения по всем событиям, входящим в причинно-следственную сеть. Расчёты могут осуществляться как на основе классической теории Байеса, так и на основе методов теории возможностей.

“Hugin” имеет возможность связи с основными наиболее распространёнными программными средствами фирмы Microsoft. Данная ЭС имеет все основные функции любой информационной системы, включая такие как: хранение данных, вывод на принтер всех элементов ЭС, диагностика ошибок в работе.

Выводы

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

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

Байесовы сети базируются на фундаментальных положениях и резуль-татах теории вероятностей, разрабатываемых в течение нескольких сотен лет, что и лежит в основе их успеха в практической плоскости.

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

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

Список используемой литературы.

1. Таха Х.А., Введение в исследование операций, Вильямс, Киев, 2005.

2. Терехов С.А., Лекции по нейроинформатике, МИФИ, М., 2003.

3. Хабаров С., Экспертные системы, M., 2003.

4. Чернова Н.И., Математические методы и исследование операций в эк., М., 2000.

5. http://www.ai.mit.edu/? murphyk/Software/BNT/bnsoft.html. Описание программных продуктов для работы с байесовскими сетями.