Формальные методы вывода решений при вероятностном подходе

ЛЕКЦИЯ 17

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

Начнем с очень простого примера — с описания проблемной области студенческой жизни, когда за плохую учёбу и пропуски занятий студенту грозит исключение из института. Для описания этой проблемной области введём три булевых переменных, á студент учится плохо по предмету СИИñ, á он пропустил много занятий по предмету СИИñ, и á студента могут исключить из институтаñ. Полное совместное распределение представляет собой таблицу с размерами 2 х 2 х 2 (табл. 23.).

Таблица 23

Полное совместное распределение для мира студенческой жизни

Все возможные комбинации булевых переменных.	студент учится плохо по предмету СИИ	ù студент учится плохо по предмету СИИ
студента могут исключить из института	ù студента могут исключить из института	студента могут исключить из института	ù студента могут исключить из института
он пропустил много занятий по предмету СИИ	0,576	0,064	0,012	0,016
ù он пропустил много занятий по предмету СИИ	0,144	0,072	0,008	0,108

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

Р(студент учится плохо по предмету СИИ Ú он пропустил много занятий по предмету СИИ) = 0,576 + 0,064 + 0,012 + 0,016 + 0,144 + 0,072 = 0,884

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

Р(он пропустил много занятий по предмету СИИ) = 0,576 + 0,064 + 0,012 + 0,016 =0,668

Такой процесс называется маргинализацией, или исключением из суммы, поскольку из суммы вероятностей исключаются прочие переменные,кроме á он пропустил много занятий по предмету СИИñ. Можно записать следующее общее правило маргинализации для любых множёств переменных y и z:

Р(y) = å Р(y, z)

^z

Это означает, что распределение вероятностей по У может быть получено путем исключения из суммы вероятностей всех прочих переменных, относящихся к любому совместному распределению вероятностей, содержащему У, т.е. суммирование ведётся по всем значениям z. В одном из вариантов этого правила учитываются условные вероятности, а не совместные вероятности. С использованием правила произведения можно записать:

Р(y) = å Р(yçz)*Р(z)

^z

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

В большинстве случаев нас будет интересовать задача вычисления условных вероятностей некоторых переменных при наличии свидетельств, касающихся других переменных. Условные вероятности можно найти, вначале воспользовавшись уравнением 1 для получения выражения в терминах безусловных вероятностей, а затем рассчитать это выражение на основании полного совместного распределении. Например, можно вычислить вероятность исключения из института после получения свидетельства о том, что студент пропустил много занятий по предмету СИИ, следующим образом:

Р(АÙ В) = 0,576 + 0,12 » 0,9

Р(АçВ) = Р(В) 0,576 + 0,064 + 0,012+0,016

где: А- студента могут исключить из института; В- он пропустил много занятий по предмету СИИ;

Просто для проверки мы можем также рассчитать вероятность того, студента не исключат из института после получения свидетельства о том, что студент пропустил много занятий по предмету СИИ:

Р(СÙ В) = 0,064 + 0,16 » 0,1

Р(СçВ) = Р(В) 0,576 + 0,064 + 0,012+0,016

где: С - ù студента могут исключить из института; В- он пропустил много занятий по предмету СИИ;

Полученные значения соответствуют следствиям из аксиом вероятностей: сумма вероятностей двух взаимно исключающих событий равна 1.

Обратите внимание на то, что в этих двух примерах вычисления вероятности терм 1/ Р (В) остается постоянным, независимо от того, какое значение А или С вычисляется. фактически этот терм может рассматриваться как константа нормализации для распределения Р(А или СçВ), гарантирующая, что полученные вероятности в сумме составят 1. Для обозначения подобных констант будем использовать символ a.

Наосновании приведенного выше примера можно составить общую процедуру вероятностного вывода. Мы будем придерживаться того случая, в котором запрос касается только одной переменной. Допустим, что Х - переменная запроса (в данном примере А- студента могут исключить из института); Е — множество переменных свидетельства (в данном примере к нему относится только В- он пропустил много занятий по предмету СИИ); е — наблюдаемые значения этих переменных; У — оставшиеся ненаблюдаемые переменные (в данном примере таковой является только D- студент учится плохо по предмету СИИ). Запросом является, и ответ на него может быть вычислен следующим образом;

Р ( Х ç е ) = a ´ Р ( Х, е ) = a ´ å Р ( Х, е, y)

^у

где суммирование осуществляется по всем возможным значениям y (те. по всем возможным комбинациям значений ненаблюдаемых переменных У). Обратите внимание на то, что переменные Х,Е и У, вместе взятые, составляют полное множество переменных для данной проблемной области, поэтому Р ( Х, е, y) представляет собой подмножество вероятностей из полного совместного распределения. Упрощённую схему алгоритма вычисления ответа на запрос можно изложить следующим образом: сначала проверяются в циклах значения Х и значения У для перебора всех возможных атомарных событий с фиксированными значениями е, затемскладываются их вероятности из таблицы совместного распределения, после чего результаты нормализуются.

При наличии полного совместного распределения, с которым можно было бы рать, этот алгоритм становится полным алгоритмом получения ответов на вероятностные запросы, касающиеся дискретных переменных. Но этот алгоритм. недостаточно хорошо масштабируется, поскольку при наличии проблемной области, которая описана булевыми переменными, он требует входной таблицы с размером О (2 ⁿ), а обработка этой таблицы занимает время Т ´ 2 ⁿ где Т – время одной итерации алгоритма.

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

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

Дата добавления: 2015-06-27