Алгоритм устранения переменной
Описанный выше алгоритм перебора можно существенно улучшить, исключив повторные вычисления такого типа, как показано на рис. 14.8. Его идея проста: выполнить вычисление один раз и сохранить результаты для дальнейшего использования. В этом выражается одна из форм динамического программирования. Существует несколько версий такого подхода; в данной главе будет представлен алгоритм устранения переменной (variable elimination), который является наиболее простым. Устранение переменной осуществляется путем вычисления выражений, подобных представленному в уравнении 14.3, в порядке справа налево (т.е. на рис. 14.8 — сверху вниз). Промежуточные результаты сохраняются, а операции суммирования по каждой переменной выполняются только для тех частей выражения, которые зависят от этой переменной.
Проиллюстрируем этот процесс на примере сети с описанием взлома. Нам необходимо вычислить следующее выражение:
Обратите внимание на то, что каждая часть этого выражения аннотирована именем связанной с ней переменной; эти части называются факторами. Этапы работы алгоритма устранения переменной описаны ниже.
• Фактор для м, Р(т\ а), не требует суммирования по М(поскольку значение М уже фиксировано). Мы сохраним эту вероятность при условии, что задано каждое значение а в виде следующего двухэлементного вектора:
(Обозначение fM показывает, что для получения f используется м.)
• Аналогичным образом сохраняется фактор для J в виде двухэлементного вектора fj(A).
• Фактор для А выражается распределением Р (а \ в, е), которое представляет собой матрицу f А (А, в, Е) с размерами 2x2x2.
• Теперь необходимо устранить путем суммирования из произведения этих трех факторов переменную А, что позволит получить матрицу 2x2, индексы которой пробегают только по в и Е. Поместим штрих над А в имени этой матрицы для указания на то, что А устранена путем суммирования:
Применяемый в этом выражении процесс умножения называется процессом получения точечного произведения (pointwise product) и будет вскоре описан.
• Обработаем таким же образом переменную К исключим Е путем суммирования из произведения f Е (Е) и f AJM (в, Е):
f eajm(В) = fE(e)xfAJM(B, e)+fE(-1e)xfAJM(B/-1e)
• Теперь мы можем вычислить ответ, умножив фактор для в (т.е. fB(В) = р (В)) на накопленную матрицу f (В):
V(B\j,m) = a fв (В) xf eajm (В)
В упр. 14.7, а предлагается проверить, действительно ли данный процесс приводит к получению правильного ответа.
Исследуя приведенную выше последовательность этапов, можно убедиться в том, что требуются две основные вычислительные операции: получение точечного произведения пары факторов и исключение некоторой переменной путем суммирования из произведения факторов.
Точечное произведение — это не результат умножения матриц и не результат поэлементного умножения. Точечное произведение двух факторов, f х и f 2, представляет собой новый фактор f, переменные которого являются объединением переменных из fx и f2. Предположим, что два фактора имеют общие переменные Ylf... ,Yk.B таком случае получим следующее:
f Y1...YktZ1...Z1) = f1(X1...XtY1...Yk) f2(Y1...YklZ1...Zi)
Если все переменные являются бинарными, то факторы f х и f 2 имеют 2j+k и 2k+1 элементов соответственно, а точечное произведение включает 2d+k+1 элементов. Например, если даны два фактора, f1 {А, В) и f2 (В, С), с распределениями вероятностей, показанными ниже, то точечное произведение f х х f 2 задается в табл. 14.2 как f3 {А, В, С).
Операция исключения некоторой переменной путем суммирования из произведения факторов также является несложной. Единственное затруднение заключается в следующем: в этой операции необходимо учитывать, что любой фактор, который не зависит от переменной, подлежащей исключению путем суммирования, может быть вынесен за пределы выражения суммирования, например, как показано ниже.
fЕ ( s) Xf д {А, В, е) Xf j (А) Хгм (А) =
е
fj(A)xfMU)xT ЈE(e)xfA(A,B, е)
е
Теперь вычисляется точечное произведение в выражении суммирования и переменная исключается путем суммирования из результирующей матрицы следующим образом:
Га(А)Хгм(А)ХГ fE(e)xfA(A,B, е) = f j (A) XfM (A) Xf E/A (A, B)
e
Обратите внимание на то, что матрицы не умножаются до тех пор, пока не потребуется исключить некоторую переменную путем суммирования из накопленного произведения. В данный момент умножаются только те матрицы, которые включают переменную, подлежащую исключению путем суммирования. Если даны процедуры получения точечного произведения и исключения путем суммирования, то сам алгоритм устранения переменной может быть записан весьма просто, как показано в листинге 14.2.
Листинг 14.2. Алгоритм устранения переменной, предназначенный для получения ответов на запросы в байесовских сетях
function Elimination-Ask{X, е, bn) returns распределение по X inputs: X, переменная запроса
е, свидетельство, определяемое как некоторое событие bn, байесовская сеть, которая задает совместное распределение Р (Xi, ..., Хп)
factors <— [ ] ; vars <— Reverse (Vars [bn] ) for each var in vars do
factors <— [Make-Factor(var, e) |factors]
if переменная var является скрытой
then factors <— Sum-Out(var, factors) return Normalize(Pointwise-Product(factors))
Рассмотрим еще один запрос: Р( JohnCalls \ Burglary true). Как обычно, на первом этапе необходимо записать вложенное выражение суммирования:
Если бы мы вычисляли это выражение справа налево, то заметили бы нечто интересное: терм JmP{m \ а) равен 1 по определению! Поэтому сразу отпадает необходимость учитывать это выражение; переменная Мне имеет отношения к данному запросу. Эту мысль можно выразить иным образом: результат запроса Р{ JohnCalls] Burglary- true) не изменится, если из сети вообще будет исключена переменная MaryCalls. Вообще говоря, из сети может быть удалена любая листовая вершина, если она не относится к переменной запроса или к переменной свидетельства. После ее удаления могут еще оставаться некоторые листовые вершины, которые также могут не относится к данному запросу. Продолжая указанный процесс, мы в конечном итоге обнаружим, что к запросу не относится любая переменная, которая не является потомком переменной запроса или переменной свидетельства. Поэтому алгоритм устранения переменной позволяет удалять все эти переменные, прежде чем приступать к вычислению ответа на запрос.