ЛОГИЧЕСКИЙ ВЫВОД С ИСПОЛЬЗОВАНИЕМ ПОЛНЫХ СОВМЕСТНЫХ РАСПРЕДЕЛЕНИЙ
В данном разделе будет описан простой метод вероятностного вывода, т.е. вычисления апостериорных вероятностей для высказываний, заданных в виде запросов, на основании наблюдаемых свидетельств. Мы будем использовать полное совместное распределение как своего рода "базу знаний", из которой могут быть выведены ответы на все вопросы. В ходе этого мы также представим несколько полезных методов манипулирования уравнениями, в которых учитываются вероятности.
Начнем с очень простого примера — с описания проблемной области, состоящей только из трех булевых переменных, Toothache, Cavity и Catch (неприятные ощущения от захвата зуба стальными клещами дантиста все еще свежи в памяти автора). Полное совместное распределение представляет собой таблицу с размерами 2x2x2
Обратите внимание на то, что вероятности в этом совместном распределении в сумме составляют 1, как и требуется согласно аксиомам вероятностей. Следует также отметить, что уравнение 13.2 предоставляет нам прямой способ вычисления вероятности любого высказывания, простого или сложного: мы должны определить те атомарные события, в которых данное высказывание является истинным, и сложить их вероятности. Например, имеется шесть атомарных событий, в которых истинным является высказывание cavi ty v toothache:
P(cavity v toothache) = 0.108 + 0.012 + 0.072 + 0.008 + 0.016 +
0.064 = 0.28
Одна из задач, которая встречается особенно часто, состоит в том, чтобы извлечь из подобной таблицы распределение вероятностей по некоторому подмножеству переменных или по одной переменной. Например, складывая элементы первого ряда табл. 13.2, получим безусловную, или маргинальную, вероятность8 события cavi ty.
P(cavity) = 0.108 + 0.012 + 0.072 + 0.008 = 0.2
Такой процесс называется маргинализацией, или исключением из суммы, поскольку из суммы вероятностей исключаются прочие переменные, кроме Cavity. Можно записать следующее общее правило маргинализации для любых множеств переменных Y и z:
Р(У) = P(Y,z) (13.4)
z
Это означает, что распределение вероятностей по Y может быть получено путем исключения из суммы вероятностей всех прочих переменных, относящихся к любому совместному распределению вероятностей, содержащему Y. В одном из вариантов этого правила учитываются условные вероятности, а не совместные вероятности с использованием правила произведения:
P(Y) = P(Y|z)P(z) (13.5)
z
Это правило называется правилом обусловливания. Как оказалось, правила маргинализации и обусловливания являются очень полезными правилами для всех видов логических выводов, в которых применяются вероятностные выражения.
В большинстве случаев нас будет интересовать задача вычисления условных вероятностей некоторых переменных при наличии свидетельств, касающихся других переменных. Условные вероятности можно найти, вначале воспользовавшись уравнением 13.1 для получения выражения в терминах безусловных вероятностей, а затем рассчитав это выражение на основании полного совместного распределения. Например, можно вычислить вероятность наличия дупла после получения свидетельства о том, что пациент страдает от зубной боли, следующим образом:
. Р(cavity л toothache)
P(cavity\toothache) = Р{toothache)
0.108 + 0.012
" 0.108 + 0.012 + 0.016 + 0.064 " °-6
Просто для проверки мы можем также рассчитать вероятность того, что у пациента нет дупла, если у него наблюдается зубная боль:
. P{—icavity л toothache)
P(-*cavity\toothache) = Р{ toothache)
0.016+0.064
= 0.4
" 0.108 + 0.012 + 0.016 + 0.064
Обратите внимание на то, что в этих двух примерах вычисления вероятности терм 1/Р( toothache) остается постоянным, независимо от того, какое значение Cavi ty вычисляется. Фактически этот терм может рассматриваться как константа .нормализации для распределения Р (Cavity \ toothache), гарантирующая, что полученные вероятности в сумме составят 1. Во всех главах этой книги, где речь идет о вероятностях, для обозначения подобных констант будем использовать символ а. С помощью такого обозначения можно записать два приведенных выше уравнения в виде одного:
Р(Cavity\ toothache) = а Р(Cavity, toothache)}
= а [Р (Cavi ty, toothache, catch) + P (Cavi ty, toothache, —icatch) ]
= а [<0.108,0.016> + <0.012,0.064>] = а <0.12,0.08> = <0.6,0.4>
Как оказалось, нормализация является полезным сокращением во многих вероятностных вычислениях.
На основании приведенного выше примера можно составить общую процедуру вероятностного вывода. Мы будем придерживаться того случая, в котором запрос касается только одной переменной. Кроме того, потребуются некоторые обозначения: допустим, что X— переменная запроса (в данном примере Cavity); Е — множество переменных свидетельства (в данном примере к нему относится только Toothache); е— наблюдаемые значения этих переменных; Y— оставшиеся ненаблюдаемые переменные (в данном примере таковой является только Catch). Запросом является р (х| е), и ответ на него может быть вычислен следующим образом:
где суммирование осуществляется по всем возможным значениям у (т.е. по всем возможным комбинациям значений ненаблюдаемых переменных Y). Обратите внимание на то, что переменные X, Е и Y, вместе взятые, составляют полное множество переменных для данной проблемной области, поэтому Р [X, е,у) представляет собой подмножество вероятностей из полного совместного распределения. Алгоритм вычисления ответа на запрос приведен в листинге 13.2. В этом алгоритме проверяются в циклах значения Хи значения Y для перебора всех возможных атомарных событий с фиксированными значениями е, складываются их вероятности из таблицы совместного распределения, после чего результаты нормализуются.
Листинг 13.2. Алгоритм вероятностного вывода путем перебора всех элементов в таблице полного совместного распределения
function Enumerate-Joint-Ask{X, е, Р) returns распределение по X inputs: X, переменная запроса
е, наблюдаемые значения переменных Е
Р, совместное распределение по переменным
{X} U Е U Y} /* Y - скрытые переменные */
Q{X) <— распределение по X, первоначально пустое for each значение xi переменной X do
Q(xi) <— Enumerate-Joint (xi, e, Y, [], P) return Normalize(Q(X))
function Enumerate-Joint(x, e, vars, values, P) returns действительное число
if Empty?(vars) then return P(x,e,values) Y <— First(vars)
При наличии полного совместного распределения, с которым можно было бы работать, алгоритм Enumerate-Joint-Ask становится полным алгоритмом получения ответов на вероятностные запросы, касающиеся дискретных переменных. Но этот алгоритм недостаточно хорошо масштабируется, поскольку при наличии проблемной области, которая описана п булевыми переменными, он требует входной таблицы с размером 0(2П), а обработка этой таблицы занимает время 0(2П). В реальных задачах может потребоваться рассмотреть сотни или тысячи случайных переменных, а не только три. Попытка определить огромные количества требуемых вероятностей быстро становится полностью неосуществимой, поскольку может быть даже не накоплено достаточного количества экспериментальных данных, которые требуются для того, чтобы отдельно оценить каждую из записей этой таблицы.
По этим причинам полное совместное распределение вероятностей в табличной форме нельзя считать практически применимым инструментальным средством для создания систем формирования рассуждений (хотя в исторических заметках в конце данной главы упоминается одно реальное приложение, основанное на этом методе).
Вместо этого данный подход следует рассматривать как теоретическую основу, на которой могут быть созданы более эффективные подходы. В оставшейся части данной главы представлены некоторые основные идеи, которые потребуются для подготовки к разработке реально осуществимых систем, описанных в главе 14.