Точный вероятностный вывод в сетях DBN
Кратко рассмотрев некоторые идеи, касающиеся представления сложных процессов в виде сетей DBN, перейдем теперь к вопросу вероятностного вывода. В определенном смысле на этот вопрос уже был получен ответ: динамические байесовские сети прежде всего представляют собой байесовские сети, а мы уже имеем алгоритмы для осуществления вероятностного вывода в байесовских сетях. При наличии последовательности наблюдений может быть создано представление сети DBN в виде полной байесовской сети путем повторения временнь/х срезов до тех пор, пока сеть не станет достаточно большой, чтобы в ней можно было учесть все наблюдения, как показано на рис. 15.12. Такой метод называется развертыванием. (С формальной точки зрения сеть DBN эквивалентна полубесконечной сети, полученной путем развертывания в одну сторону до бесконечности. Но временнь/е срезы, вводимые за пределами последнего наблюдения, не оказывают влияния на вероятностные выводы в пределах периода наблюдения и поэтому могут быть исключены.) После того как сеть DBN развернута, в ней может использоваться любой из алгоритмов вероятностного вывода (алгоритм с устранением переменной, методы соединенного дерева и т.д.), описанные в главе 14.
К сожалению, непродуманное применение развертывания не всегда оказывается достаточно эффективным. В частности, если требуется выполнение фильтрации или сглаживания с использованием длинной последовательности наблюдений e1:t, то для развернутой сети потребуется пространство О (t), а рост ее по мере добавления новых результатов наблюдений будет происходить неограниченно. Более того, если после каждого добавления новых результатов наблюдения будет просто вновь вызываться на выполнение алгоритм вероятностного вывода, то затраты времени на вероятностный вывод в расчете на каждое обновление также будут расти пропорционально 0( t).
Еще раз обратившись к разделу 15.2, можно отметить, что постоянных затрат времени и пространства в расчете на каждое обновление при фильтрации можно достичь, если существует возможность выполнять вычисление в рекурсивной форме. По сути обновление результатов фильтрации в уравнении 15.3 осуществляется по принципу исключения путем суммирования переменных состояния, относящихся к предыдущему временному этапу, что позволяет получить распределение для нового временного этапа. Исключение переменных путем суммирования представляет собой именно то, что выполняет алгоритм устранения переменной (см. листинг 14.2), и, как оказалось, применение процедуры устранения переменной к переменным во временном порядке точно моделирует функционирование рекурсивного обновления результатов фильтрации в уравнении 15.3. В модифицированном алгоритме предусмотрено одновременное хранение в памяти не больше двух временнь/х срезов: начиная со среза 0, добавляем срез 1, затем исключаем путем суммирования срез 0, после этого добавляем срез 2, на следующем этапе исключаем путем суммирования срез 1 и т.д. Такая организация вычислений позволяет добиться постоянных затрат пространства и времени в расчете на каждое обновление результатов фильтрации. (Такой же производительности можно достичь путем введения соответствующих модификаций в алгоритм соединенного дерева.) В упр. 15.10 предлагается проверить это утверждение на примере сети для задачи с зонтиком.
До сих пор рассматривались только преимущества рекурсивного подхода, но он имеет и недостатки: как оказалось, "постоянные" значения временной и пространственной сложности каждой операции обновления почти во всех случаях экспоненциально зависят от количества переменных состояния. В связи с этим в ходе осуществления процесса устранения переменной количество факторов возрастает так, что в их состав начинают входить все переменные состояния (или, точнее, все те переменные состояния, которые имеют родительские переменные в предыдущем временном срезе). Максимальный размер фактора составляет 0(dn+1), а стоимость обновления измеряется как О (сГ+2).
Безусловно, такие значения намного меньше по сравнению со стоимостью обновления НММ, которая составляет 0(d2n), но они все еще неприемлемы при наличии большого количества переменных. С этим обескураживающим фактом довольно трудно смириться, поскольку он означает, что даже несмотря на то, что сети DBNмогут использоваться для представления очень сложных временных процессов с многочисленными переменными, характеризующимися разрозненными связями между ними, не существует возможности эффективно и точно формировать вероятностные рассуждения об этих процессах. Сама модель DBN, которая представляет априорное совместное распределение по всем переменным, может быть разложена на составляющие ее таблицы условных вероятностей, но обусловленное последовательностью наблюдений апостериорное совместное распределение (т.е. прямое сообщение), как правило, не поддается разбиению на факторы. До сих пор еще никому не удалось найти способа решения этой проблемы, несмотря на то, что многие важные области науки и техники получили бы огромную выгоду благодаря такому решению. Поэтому нам приходится обращаться к приближенным методам.