Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 185
Текст из файла (страница 185)
Некоторое упрощение может быть достигнуто на основе следующих простых наблюдений: терм Р (ь) представляет собой константу и может быть перенесен за пре- Такое выражение, квк 2. Р(а, е), обозначает сумму Р(я=а, Е=е) по всем возможным значениям е. При этом может возникать неоднозначность, связанная с тем, что Р(е) используется для обозначения и Р (е=сгье), и Р (е=е), но вз контекста должно быть ясно, какой смысл имеет это выражение; в частности, в контексте суммы подразумевается последнее значение.
677 Глава 14. Вероятностные рассуждения делы выражений суммирования по а и е, а терм Р( е) — перенесен за пределы Вы- ражения суммирования по а. Поэтому получаем следующее: Р(Ь) з,т) = а Р(Ь),) Р(е) ~) Р(а)Ь, е) Р(7)а) Р(т) а) (14.3) Это выражение можно вычислить, последовательно обрабатывая в цикле его переменные и перемножая в ходе этого элементы таблицы СРТ. При каждом суммировании необходимо также выполнить цикл по возможным значениям переменной. Структура этих вычислений показана на рис.
14.8. Используя числа, приведенные на рис. 142, получим выражение Р(Ь)2',т) =ахО. 00059224. Соответствующее вычисление для .Ь приводит к получению выражения ахО. 0014919, поэтому имеет место следующее: Р(В)у,т) = П <0.00059224,0.0014919> = <0.284,0.718> Таким образом, вероятность взлома, при условии, что поступили звонки от обоих соседей, составляет около 28% Процесс вычисления выражения, приведенного в уравнении 14.3, показан в ниле дерева синтаксического анализа выражения на рис. 14.8.
В алгоритме Епптегас1ои-йв)<, приведенном в листинге 14.1, вычисление подобных деревьев осуществляется с использованием рекурсии в глубину. Таким образом, пространственная сложность алгоритма Епозпегагуоп-Аз)< зависит от количества переменных только линейно; по сути этот алгоритм вычисляет суммы по полному совместному распределению, даже не формируя его явно, К сожалению, его временная сложность для сети с п булевыми переменными всегда составляет 0(2"); это лучше по сравнению с оценкой 0(и2") для простого подхода, описанного выше, но все еше довольно велика.
В отношении дерева, приведенного на рис. 14.8, необходимо сделать еше одно замечание — в нем явно показаны повторяющиеся подвыражения, вычисляемые с помощью этого алгоритма, Произведения Р(7 ~ а) Р(т)а) и Р(7(-а) Р(т)- а) вычисляются дважды, по одному для каждого значения е. В следующем разделе описан общий метол, позволяющий избежать таких избыточных вычислений. Листинг 14.1. Алгоритм перебора для получения ответов на запросы в бвйесовскнх сетях Енпоеаоп Епптегаг1оп-лвх(Х, е, Ьп) гееигпв распределение по Х апривв: Х, переменная запроса е, наблюдаемые значения переменных Е Ьп, байесовская сеть с переменными (х) ьу е и х) /* х — скрытые переменные *7 Я(Х) ь- распределение по х, первоначально пустое гог еаои значение х, переменной Х ао дополнить е значением х, переменной Х ()(х,) ь- Епптегаге-А11(чагв(Ьи), е) геевгп Ногта11зе(Я(Х)) Енпоеаоп Епптегаге-А11(чагв, е) гесигпв действительное число 1г Епрсут(чагв) Сиеп гееигп 1.0 1' Ь- Рьгзг(чагв) 18 переменная у имеет значение у в множестве е 678 Часть У.
Неопределенные знания и рассуждения в условиях неопределенности Енеп геппгп Р(у(рагепса(у) )хвпптегасе-А11(лезг(уагз), е) Е1ЕЕ ГЕЕПГП,) В(У(РаГЕПЕН(У) )ХЕПЧЗВЕГаЕЕ-А11(БАЕВЕ(таха), Ез), У где е„ представляет собой множество е, дополненное значением У = у Р()')а) 0,9 Р(т(а) 0,7 Рис. 14.8. Структура вырозкения, показанного в уравнении 14.3. Процесс вычисления осуществляется сверху вниз; при этом значения вдоль каждого пути умножаются и суммируются в узлах "+'1 Одратите внимание но то, чпю пути для 8 и и повторяются Алгоритм устранения переменной Описанный выше алгоритм перебора можно сушественно улучшить, исключив повторные вычисления такого типа, как показано на рис. 14.8. Его идея проста: выполнить вычисление один раз и сохранить результаты для дальнейшего использования.
В этом выражается одна из форм динамического программирования. СуШествует несколько версий такого подхода; в данной главе будет представлен алгоритм се устранения переменной (чаг)а(з)е ейпппайоп), который является наиболее простым. Устранение переменной осу(цествляется путем вычисления выражений, подобных представленному в уравнении 14юч в порядке справа налево (т.е. на рис.
14.8 — сверху вниз). Промежуточные результаты сохраняются, а операции суммирования по каждой переменной выполняются только для тех частей выражения, которые зависят от этой переменной. Проиллюстрируем этот процесс на примере сети с описанием взлома. Нам необходимо вычислить следуюшее выражение: В(В(З',т) = а В(В),) В(е) Ч) В(а(В,е)Р~Яа)Р(т~а) В Е А У и 679 Глава 14.
Вероятностные рассуждения Обратите внимание на то, что каждая часть этого выражения аннотирована именем связанной с ней переменной; эти части называются Ж факторами. Этапы работы алгоритма устранения переменной описаны ниже. ° Фактор для (Ч, Р (в ~ а), не требует суммирования по )и (поскольку значение )и уже фиксировано). Мы сохраним эту вероятность при условии, что задано каждое значение а в виде следующего двухэлементного вектора: Р(е(д) Ем(А) = ( ( ) (Обозначение Ем показывает, что для получения Е используется м.) ° Аналогичным образом сохраняется фактор для т в виде двухэлементного вектора Е,(А).
° Фактор для А выражается распределением Р(а ~ В, е), которое представляет собой матрицу Е„(А, В, В) с размерами 2х2х2, ° Теперь необходимо устранить путем суммирования из произведения этих трех факторов переменную А, что позволит получить матрицу 2х2, индексы которой пробегают только по В и В. Поместим штрих над А в имени этой матрицы для указания на то, что А устранена путем суммирования: Еммм(в,в) = ~~) Ем(а,в,в) х Ем(а) х Ем(а) д Ем(а, В, Е) хЕм(а) хЕм(а) мвм(- а, В, Е) хям(-1а) хям(-1а) Применяемый в этом выражении процесс умножения называется процессом получения Ж точечного произведения (решим)зе ргойцс() и будет вскоре описан.
° Обработаем таким же образом переменную и, исключим В путем суммирования из произведения Е, ( Е) и Е,мм ( В, Е): Емммм(в) = Ем(е) мямле(в, е) ~мям(- е)хямщ(в, е) ° Теперь мы можем вычислить ответ, умножив фактор для В (т.е, Е,(В) = Р (В) ) на накопленную матрипу Е ( В): В(В(У,т) = а Ем(В)хя„(В) В упр. 14.7, а предлагается проверить, действительно ли данный процесс приводит к получению правильного ответа. Исследуя приведенную выше последовательность этапов, можно убедиться в том, что требуются две основные вычислительные операции: получение точечного произведения пары факторов и исключение некоторой переменной путем суммирования из произведения факторов. Точечное произведение — это не результат умножения матриц и не результат по- элементного умножения.
Точечное произведение двух факторов, Е, и Е„прелставляет собой новый фактор Е, переменные которого являются объединением переменных из Е, и Е,. Предположим, что два фактора имеют общие переменные У,, ..., Ум. В таком случае получим следующее: Е(Х,...Х;, Ум...км,г,...г,) = Е,(Х,...Х,, Зь..х,) Е,(гь..ум,г,...г1) 680 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности Если все переменные являются бинарными, то факторы Е, и Е, имеют 2а и и 2"" элементов соответственно, а точечное произведение включает 2""' элементов. Например, если даны два фактора, Е, (А, В) и Е, (В, С), с распределениями вероятностей, показанными ниже, то точечное произведение Е„х Е, задается в табл.
14.2 как Е, (А, В, С) . Таблипа 14.2. 1)ример произволении факторов С Еа(А,В,С) В С Га(В С) и А В Е1(А,В) .3 х.2 .з х.в .т х.а х.4 .9 х.2 .9 х.в .1 х.б .З х.4 Операция исключения некоторой переменной путем суммирования из произведения факторов также является несложной. Единственное затруднение заключается в следующем: в этой операции необхолимо учитывать, что любой фактор, который не зависит от переменной, подлежащей исключению путем суммирования, может быть вынесен за пределы выражения суммирования, например, как показано ниже. Еа ( е) хЕ„(А, В, е) хЕа (А) ХЕм (А) Х е Еа(А)хЕм(А)х~~) Еа(е)хЕ„(А,В, е) е Теперь вычисляется точечное произведение в выражении суммирования и переменная исключается путем суммирования из результирующей матрицы следующим образом: Е, (А) ХЕ,(А) Х~ Е,(Е) ХЕ,(А, В, Е) = Е,(А) ХЕм(А) ХЕ,,(А, В) е Обратите внимание на то, что матрицы не умножаются до тех пор, пока не потребуется исключить некоторую переменную путем суммирования из накопленного произведения.
В данный момент умножаются только те матрицы, которые включают переменную, подлежащую исключению путем суммирования. Если даны процедуры получения точечного произведения и исключения путем суммирования, то сам алгоритм устранения переменной может быть записан весьма просто, как показано в листинге 14.2. 681 Глава 14. Вероятностные рассуждения Листинг 14.2. Алгоритм устранения переменной, предназначенный для получения ответов на за- преты в байесовских сетях Емпспьоп В1звгзпаезоп-дя)г(Х, е, Ьп) тевмтпв распределение по Х зпрптяг Х, переменная запроса е, свидетельство, определяемое как некоторое событие Ьп, байесовская сеть, которая задает совместное распределение Р(Хг,..., Х ) Еаосотя ь- [1; ггагя е- веиетяе(згатя[ьп)) Еот еасЛ тат зп иагя со еаосогя е- [паке-васеот(иаг, е))еаототя) хЕ переменная ггаг является скрытой Еьеп Еаотогя ь- Вевг-оов(ггаг, Еаотогя) гетптп Нотиа1зве(Розптызяе-Ргобнот(еассогя)) Рассмотрим еще один запрос: р(доьпСа11я ~ Вигу1агу= Сгпе) .
Как обычно, на первом этапе необходимо записать вложенное выражение суммирования: Р( г)ь) = а Р(ь) ~) Р(е) ~) Р(а)ь, е) )'( г)а) ~~) Р(яг)а) Если бы мы вычисляли это выражение справа налево, то заметили бы нечто интересное: терм ,'Г р(т~ а) равен 1 по определению! Поэтому сразу отпадает необходимость учитывать это выражение; переменная гч не имеет отношения к данному запросу. Эту мысль можно выразить иным образом: результат запроса р(уолпса11я ~ вигд1агу= сгое) не изменится, если из сети вообще буде г исключена переменная угагуба11я. Вообще говоря, из сети может быть удалена любая листовая вершина, если она нс относится к переменной запроса или к переменной свидетельства.
После ее удаления могут еще оставаться некоторые листовые вершины, которые также могут не относится к данному запросу. Продолжая указанный процесс, мы в конечном итоге обнаружим, что гж* к запросу не относится любая переменная, которая не является потомком переменной запроса или ггеременной свидетельства. Поэтому алгоритм устранения переменной позволяет удалять все эти переменные, прежде чем приступать к вычислению ответа на запрос. Сложность точного вероятностного вывода Выше было показано, что устранение переменной является более эффективным по сравнению с перебором, поскольку позволяет предотвратить повторяюгциеся вычисления (а также обеспечить удаление не относящихся к делу переменных).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
