Приближенный вероятностный вывод в сетях DBN
В главе 14 были описаны два алгоритма аппроксимации — взвешивание с учетом правдоподобия (см. листинг 14.5) и метод Монте-Карло на основе цепи Маркова (алгоритм МСМС, см. листинг 14.6). Из этих двух алгоритмов наиболее легко к контексту DBN адаптируется первый алгоритм. Тем не менее, как будет показано ниже, в стандартный алгоритм взвешивания с учетом правдоподобия необходимо внести несколько усовершенствований, прежде чем появится практически применимый метод.
Напомним, что метод взвешивания с учетом правдоподобия действует по принципу осуществления в топологическом порядке выборок в узлах сети, не являющихся узлами свидетельства, и взвешивания каждой выборки с учетом правдоподобия того, что она соответствует наблюдаемым переменным свидетельства. Как и при использовании точных алгоритмов, алгоритм взвешивания с учетом правдоподобия можно было бы применить непосредственно к развернутой сети DBN, но по мере увеличения длины последовательностей наблюдений это привело бы к возникновению таких же сложностей, связанных с увеличением требований ко времени и пространству в расчете на каждое обновление. Проблема состоит в том, что в стандартном алгоритме каждая выборка обрабатывается последовательно, по всей сети. Вместо этого можно просто пропустить через сеть DBN все N выборок вместе, проходя каждый раз через один временной срез. Этот модифицированный алгоритм имеет такую же общую форму, как и другие алгоритмы фильтрации, но в нем в качестве прямого сообщения используется множество из N выборок. Поэтому первым ключевым усовершенствованием должно быть то, чтобы в этом алгоритме в качестве приближенного представления текущего распределения вероятностей состояния использовались сами выборки. Такая организация работы соответствует требованию обеспечения "постоянных" затрат времени в расчете на каждое обновление, хотя само это постоянное значение зависит от количества выборок, необходимых для достижения приемлемой аппроксимации истинного апостериорного распределения. Кроме того, нет необходимости развертывать сеть DBN, поскольку в памяти требуется держать только текущий временной срез и следующий временной срез.
В описании метода взвешивания с учетом правдоподобия, приведенного в главе 14, было указано, что точность алгоритма снижается, если переменные свидетельства находятся в "прямом направлении" от переменных, по которым осуществляется выборка, поскольку в таком случае выборки формируются, не испытывая какого-либо влияния со стороны свидетельства. Рассматривая типичную структуру сети DBN (допустим, сети DBN для задачи с зонтиком на рис. 15.12), можно убедиться в том, что в действительности выборку ранее полученных переменных состояния можно осуществлять, не пользуясь полученным в дальнейшем свидетельством. Проанализировав фактически этот вопрос более внимательно, можно обнаружить, что ни у одной из переменных состояния не имеется среди ее предков ни одной переменной свидетельства! Поэтому, хотя вес каждой выборки зависит от свидетельства, фактически сформированное множество выборок является полностью независимым от свидетельства. Например, даже если директор ходит с зонтиком каждый день, в процессе осуществления выборки все еще может создаваться впечатление, что солнечные дни не кончаются. С точки зрения практики это означает, что доля выборок, остающихся достаточно близкими к фактическому ряду событий, падает экспоненциально со значением t, т.е. с длиной последовательности наблюдений; иными словами, чтобы поддерживать заданный уровень точности, необходимо увеличивать количество выборок экспоненциально в зависимости от t. Учитывая то, что алгоритм фильтрации, работающий в реальном времени, может использовать лишь фиксированное количество выборок, на практике происходит то, что после небольшого количества этапов обновления ошибка становится весьма значительной.
Очевидно, что требуется лучшее решение. Поэтому второе важное нововведение состоит в том, что множество выборок в основном следует формировать в областях пространства состояний, характеризующихся высокой вероятностью. Такую задачу можно выполнить, отбрасывая выборки, которые, согласно наблюдениям, имеют очень малый вес, вместе с тем увеличивая количество выборок, имеющих большой вес. Благодаря этому появляется возможность создавать множества выборок, которые остаются достаточно близкими к действительным данным. Если выборки рассматриваются как информационные ресурсы для моделирования распределения апостериорных вероятностей, то имеет смысл формировать больше выборок в тех областях пространства состояний, где апостериорная вероятность выше.
Для решения именно этой задачи предназначено семейство алгоритмов, называемых алгоритмами фильтрации частиц. Метод фильтрации частиц действует следующим образом: прежде всего создается популяция из N выборок путем формирования выборок из распределения априорных вероятностей в момент времени О, Р(х0), затем, как описано ниже, для каждого временного интервала повторяется цикл обновления.
• Каждая выборка распространяется в прямом направлении путем формирования выборки значения переменной следующего состояния xt+1. Для этого в качестве выборки берется текущее значение xt и используется модель перехода Р (Xt+1 | xt) .
• Каждая выборка взвешивается с учетом правдоподобия, которое она присваивает новому свидетельству, Р (et+11 xt+1).
• В этой популяции выборок снова осуществляется формирование выборки для создания новой популяции из N выборок. Каждая новая выборка берется из текущей популяции; вероятность того, что будет получена конкретная выборка, пропорциональна ее весу. Данные о весах новых выборок уничтожаются.
Этот алгоритм подробно показан в листинге 15.3, а пример его применения к сети DBN для задачи с зонтиком приведен на рис. 15.13.
Листинг 15.3. Алгоритм фильтрации частиц, реализованный как рекурсивная операция обновления данных о состоянии (множества выборок). Каждый из этапов формирования выборок состоит в том, что формируется выборка значений соответствующих переменных временного среза в топологическом порядке, во многом так же, как и в процедуре Prior-Sample. Операция Weighted-Sample-with-Replacement может быть реализована так, чтобы она выполнялась за ожидаемое время 0(Ю
function Particle-Filtering(е, N, dbn) returns множество выборок для следующего временного интервала inputs: е, новое полученное свидетельство
N, количество выборок, которые должны сопровождаться алгоритмом
dbn, сеть DBN с распределением априорных вероятностей Р(Хо), моделью перехода P(XilXo) и моделью восприятия P(EilXi) static: S, вектор выборок с размером N, первоначально формируемый из Р(Х0)
local variables: W, вектор весов с размером N
for i = 1 to N do
S[i]
N(xt\e1:t) /N = P(xt|ei:t) (15.21)
Теперь распространим каждую выборку в прямом направлении, осуществляя формирование выборок значений переменных состояния во время t+1 и взяв для каждой выборки значения во время t. Количество выборок, достигающих состояния xt+1 из каждого состояния xt, равно вероятности перехода, умноженной на величину популяции xt, поэтому общее количество выборок, достигающих xt+1.
После этого выполним взвешивание каждой выборки по ее правдоподобию применительно к свидетельству во время t+1. Любая отдельная выборка в состоянии xt+1 получает вес P(et+11 xt+1). Это означает, что суммарный вес выборок в состоянии xt+1 после получения свидетельства et+i определяется таким образом:
(xt+i|ei:t+i) = P(et+i|xt+i) tf(xt+i|ei:t)
Далее выполняется этап повторного формирования выборки. Поскольку каждая выборка тиражируется с вероятностью, пропорциональной ее весу, количество выборок в состоянии xt+1 после повторного формирования выборки пропорционально суммарному весу в состоянии xt+1 перед повторным формированием выборки, как показано ниже.
Поэтому популяция выборок после одного цикла обновления правильно представляет прямое сообщение во время t+1.
Итак, алгоритм фильтрации частиц является согласованным, но характеризуется ли он достаточной эффективностью? Создается впечатление, что на практике ответ на этот вопрос является положительным: по-видимому, фильтрация частиц позволяет поддерживать хорошую аппроксимацию истинных апостериорных вероятностей с использованием постоянного количества выборок. Тем не менее теория еще не дает такой гарантии; в настоящее время в области фильтрации частиц продолжаются интенсивные исследования. Предложено много вариантов и усовершенствований, а спектр приложений этого алгоритма стремительно растет. Поскольку алгоритм фильтрации представляет собой алгоритм формирования выборок, его можно легко применить к гибридным и непрерывным сетям DBN, что дает возможность воспользоваться этим алгоритмом в таких областях, как отслеживание сложных движущихся образов в видеозаписях [719] и предсказание курсов акций на фондовой бирже [343].