Сглаживание
Как было указано выше, сглаживание — это процесс вычисления распределения вероятностей значений переменных в прошлых состояниях при наличии свидетельств вплоть до нынешнего состояния, иными словами, P(xk|e1:t) для l
= a P(Xk|ei:k) Р (ek+i:t IXk/ei:k) (Применение правила Байеса)
= a P(Xk|ei:k) P(ek+i:t|xk) (Применение правила условной
независимости)
= a f1:k bk+i:t (15.6)
где используется сообщение bk+1:t=P (ek+1:t | хк), определяемое как "обратное", по аналогии с прямым сообщением fi:k. Прямое сообщение f1:k может быть вычислено путем фильтрации в прямом направлении от 1 до к в соответствии с уравнением 15.3. Как оказалось, обратное сообщение bk+1:t может быть вычислено с помощью рекурсивного процесса, который осуществляется в обратном направлении от t: где последний этап преобразования следует из свойства условной независимости ек+1 и ek+2:t, если дано хк+1. Из трех множителей в этой операции суммирования первый и третий можно получить непосредственно с помощью модели, а второй представляет собой "рекурсивный вызов". С использованием обозначения для сообщений получим следующее:
bk+i:t = Backward (bk+2:t,ek+i:t)
где функция Backward осуществляет обновление, описанное в уравнении 15.7. Как и при рекурсии в прямом направлении, время и пространство, требуемые для каждого обновления, являются постоянными и поэтому независимыми от t.
Теперь становится вполне очевидно, что оба терма, приведенные в уравнении 15.6, можно вычислить с помощью рекурсий по времени, одна из которых проходит в прямом направлении от 1 до к и в которой используется уравнение фильтрации 15.3, а другая проходит в обратном направлении от t до к+1 и в ней используется уравнение 15.7. Следует отметить, что этап обратной рекурсии инициализируется с помощью выражения bt+1:t=P (et+1:t | xt) =1, где 1 — вектор из единиц (поскольку et+i:t — пустая последовательность, вероятность наблюдения равна 1).
Итак, применим этот алгоритм к примеру с зонтиком и вычислим сглаженную оценку вероятности дождя в момент времени t=l по данным наблюдений за появлением директора с зонтиком в дни 1 и 2. Согласно уравнению 15.6, это значение определяется следующим образом:
P(tfi|ui,u2) = a P(J?i|ui) P(u2|J?i) (15.8)
Как нам уже известно, первый терм равен <. 818, . 182>, согласно результатам применения процесса прямой фильтрации, описанного выше. Второй терм можно вычислить, применив обратную рекурсию по уравнению 15.7:
Подставляя эти значения в уравнение 15.8, можно найти, что сглаженная оценка вероятности дождя в день 1 такова:
Таким образом, в данном случае сглаженная оценка выше, чем отфильтрованная оценка (0 .818). Это связано с тем, что появление директора с зонтиком в день 2 повышает вероятность того, что в день 2 шел дождь; в свою очередь, поскольку дожди обычно являются затяжными, это приводит к повышению вероятности дождя и в день 1.
И для прямой, и для обратной рекурсии требуется постоянное количество времени в расчете на каждый этап; поэтому временная сложность сглаживания по отношению к свидетельству e1:t составляет 0{ t). Этим выражением определяется также сложность сглаживания в конкретном интервале времени к. А если требуется провести сглаживание всей последовательности, то один из очевидных методов состоит в выполнении всего процесса сглаживания по одному разу для каждого интервала времени, в котором должно быть выполнено сглаживание. Такой подход приводит к получению временной сложности О (t2). Но в лучшем подходе можно было бы использовать очень простое приложение динамического программирования, чтобы свести сложность к величине 0{ t). Один из намеков на то, как это сделать, можно найти в приведенном выше анализе примера с зонтиком, где была показана возможность повторного использования результатов прямой фильтрации. Ключом к созданию алгоритма с линейными затратами времени является регистрация результатов прямой фильтрации по всей последовательности. В таком случае можно выполнить обратную рекурсию от t вплоть до 1, вычисляя сглаженную оценку для каждого этапа к из вычисленного обратного сообщения bk+1:t и хранимого прямого сообщения f1:k. Этот алгоритм, обоснованно названный прямым—обратным алгоритмом (forward—backward algorithm), показан в листинге 15.1.
Листинг 15.1. Прямой—обратный алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Операторы Forward и Backward определены в уравнениях 15.3 и 15.7
function Forward-Backward(ev,prior) returns вектор распределений вероятностей
inputs: ev, вектор значений свидетельств для этапов l,...,t
prior, распределение априорных вероятностей в начальном состоянии, Р(Х0)
local variables: fv, вектор прямых сообщений для этапов 0,...,t Ъ, представление обратного сообщения,
первоначально состоящее из одних единиц, 1 sv, вектор сглаженных оценок для этапов l,...,t
fv[0] <— prior for i=l to t do
fv[i] <- Forward(fv[i-l],ev[i]) for i=t downto 1 do
sv[i] <— Normalize (fv[i] xb)
b <— Backward(b,ev[i]) return sv
вычисляет сглаженные оценки для всей последовательности. Итак, вполне понятно, что прямой—обратный алгоритм фактически представляет собой частный случай алгоритма распространения в полидереве, используемого в сочетании с методами кластеризации (хотя эти два алгоритма были разработаны независимо).
Прямой—обратный алгоритм лежит в основе вычислительных методов, применяемых во многих таких приложениях, где приходится иметь дело с последовательностями зашумленных результатов наблюдений, начиная от распознавания речи и заканчивая слежением за самолетами с помощью радара. Как было описано выше, с точки зрения практики он имеет два недостатка. Первым из них является пространственная сложность, которая может оказаться слишком высокой применительно к приложениям, где пространство состояний велико, а последовательности имеют большую длину. В нем используется пространство 0( | f | t), где | f | — размер представления прямого сообщения. Такую потребность в пространстве можно уменьшить до 0( | f | log t) с помощью соответствующего увеличения временной сложности на коэффициент log t, как показано в упр. 15.3. В некоторых случаях (см. раздел 15.3) может использоваться алгоритм с постоянными потребностями в пространстве, но без лишних затрат времени.
Вторым недостатком этого несложного алгоритма является то, что он требует модификации для использования в оперативных приложениях, где сглаженные оценки должны вычисляться для более ранних временнь/х срезов по мере того, как к концу последовательности непрерывно добавляются новые наблюдения. Наиболее часто возникает требование по обеспечению сглаживания с постоянным запаздыванием, при котором необходимо вычислять сглаженную оценку Р (Xt_d| e1:t) для постоянного значения d. Это означает, что сглаживание выполняется для временного среза, отстоящего на d этапов от текущего времени t; по мере возрастания t сглаживание не должно отставать. Безусловно, что прямой—обратный алгоритм можно вызывать на выполнение применительно к данным d-этапного "окна" по мере добавления результатов каждого нового наблюдения, но такой подход, по-видимому, является неэффективным. В разделе 15.3 будет показано, что сглаживание с постоянным запаздыванием в некоторых случаях может выполняться за постоянное время в расчете на каждое обновление, независимо от запаздывания d.