Главная arrow книги arrow Копия Глава 15. Вероятностные рассуждения во време arrow Сглаживание
Сглаживание

Прямой—обратный алгоритм лежит в основе вычислительных методов, применяемых во многих таких приложениях, где приходится иметь дело с последовательностями зашумленных результатов наблюдений, начиная от распознавания речи и заканчивая слежением за самолетами с помощью радара. Как было описано выше, с точки зрения практики он имеет два недостатка. Первым из них является пространственная сложность, которая может оказаться слишком высокой применительно к приложениям, где пространство состояний велико, а последовательности имеют большую длину. В нем используется пространство 0( | f | t), где | f | — размер представления прямого сообщения. Такую потребность в пространстве можно уменьшить до 0( | f | log t) с помощью соответствующего увеличения временной сложности на коэффициент log t, как показано в упр. 15.3. В некоторых случаях (см. раздел 15.3) может использоваться алгоритм с постоянными потребностями в пространстве, но без лишних затрат времени.

Вторым недостатком этого несложного алгоритма является то, что он требует модификации для использования в оперативных приложениях, где сглаженные оценки должны вычисляться для более ранних временных срезов по мере того, как к концу последовательности непрерывно добавляются новые наблюдения. Наиболее часто возникает требование по обеспечению сглаживания с постоянным запаздыванием, при котором необходимо вычислять сглаженную оценкудля постоянного значения d. Это означает, что сглаживание выполняется для временного среза, отстоящего на d этапов от текущего времени t; по мере возрастания t сглаживание не должно отставать. Безусловно, что прямой—обратный алгоритм можно вызывать на выполнение применительно к данным d-этапного "окна" по мере добавления результатов каждого нового наблюдения, но такой подход, по-видимому, является неэффективным. В разделе 15.3 будет показано, что сглаживание с постоянным запаздыванием в некоторых случаях может выполняться за постоянное время в расчете на каждое обновление, независимо от запаздывания d.