Что такое алгоритм FB

Что такое алгоритм FB — это алгоритм динамического программирования, применяемый для расчета краевых вероятностей состояний в скрытых марковских моделях. Алгоритм FB эффективно вычисляет вероятности скрытых состояний для всех шагов во времени за линейную трудоемкость. Данный метод состоит из двух последовательных этапов: прямого шага для расчета вероятностей наблюдения и обратного шага для учета будущих данных последовательности.

$\alpha_t(j) = P(o_1, \dots, o_t, q_t = S_j \mid \lambda)$

Разбор по случаям

Примеры

Расчет прямой вероятности. Рассмотрим модель с двумя состояниями.

В начальный момент времени прямой показатель равен $\alpha_1(1) = \pi_1 \cdot b_1(o_1)$.

На втором шаге мы пересчитываем значение через сумму всех возможных прошлых переходов: $\alpha_2(1) = (\alpha_1(1)a_{11} + \alpha_1(2)a_{21}) \cdot b_1(o_2)$.

Это позволяет последовательно и быстро учесть всю цепочку предшествующих наблюдений без полного перебора возможных траекторий системы.

Финишное объединение. Для отыскания вероятности нахождения системы в первом состоянии на шаге $t$ перемножаются прямая вероятность $\alpha_t(1)$ и обратная вероятность $\beta_t(1)$. Полученное произведение делят на полную вероятность всей последовательности $P(O|\lambda)$. В результате вычислений мы получаем точную итоговую апостериорную вероятность $\gamma_t(1)$ для выбранного момента времени $t$.

Частые ошибки

• Путаница между прямыми вероятностями alpha и обратными вероятностями beta при подстановке индексов времени.
• Забывание нормировки промежуточных значений, из-за чего происходит машинный переполняющий подтек при длинных цепочках.
• Отождествление алгоритма FB с алгоритмом Витерби, который ищет одну наиболее вероятную последовательность, а не апостериорные вероятности.

Коротко

Подводя итоги, повторим, что такое алгоритм FB и для чего он применяется в вычислениях. Алгоритм FB сочетает прямой и обратный проходы динамического программирования для точной оценки состояний марковских моделей.