O algoritmo forward

Quão provável é o que vimos?

Suponha que vimos os movimentos Pequeno, Grande, Grande. Quão provável é essa sequência no nosso modelo? Poderíamos listar todos os caminhos ocultos (Calmo-Calmo-Calmo, Calmo-Calmo-Tempestuoso etc.), calcular a probabilidade de cada um e somá-las. Com $K$ estados e $T$ dias são $K^{T}$ caminhos, demais. O algoritmo forward faz a mesma soma em $T\cdot K^{2}$ passos reaproveitando o trabalho. Ele guarda um número $\alpha_t(j)$ : a probabilidade das primeiras $t$ observações e de estar no estado $j$ no dia $t$ .

\alpha_1(j)=\pi_jB_j(o_1),\qquad \alpha_t(j)=\Big[\sum_i\alpha_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad P(o_1,\dots,o_T)=\sum_j\alpha_T(j)

(1)

Leia a recorrência em palavras: para estar no estado $j$ hoje, veio-se de algum estado $i$ ontem (soma sobre $i$ com a probabilidade de transição) e então o estado de hoje produziu a observação de hoje. Dividir $\alpha_t$ pelo seu total dá as probabilidades filtradas, sua crença sobre o estado de hoje dados os dados até hoje. Um problema prático: multiplicar muitos números pequenos dá números que tendem a zero. Então a cada passo divide-se pelo total $c_t$ e guarda-se. O log da probabilidade dos dados é então simplesmente a soma dos $\ln c_t$ .

Pequeno, Grande, GrandeDia 1:

\alpha_1=(0{,}6\cdot0{,}9,\ 0{,}4\cdot0{,}3)=(0{,}54,\ 0{,}12)

, total

c_1=0{,}66

. Dia 2 (um movimento grande): Calmo recebe

(0{,}54\cdot0{,}9+0{,}12\cdot0{,}2)\cdot0{,}1=0{,}051

e Tempestuoso

(0{,}54\cdot0{,}1+0{,}12\cdot0{,}8)\cdot0{,}7=0{,}105

, total

0{,}156

, então a probabilidade filtrada de Tempestuoso é

0{,}105/0{,}156=0{,}673

. O dia 3 dá

\alpha_3=(0{,}00669,\ 0{,}06237)

. A probabilidade de toda a sequência é

0{,}00669+0{,}06237=0{,}0691

e seu log é

-2{,}673

Algoritmo forward: soma sobre todos os caminhos ocultos em $T\cdot K^{2}$ passos em vez de $K^{T}$ .
Probabilidades filtradas: normalize $\alpha_t$ para obter sua crença sobre o estado de hoje com os dados até hoje.
Escalonamento: divida por $c_t$ a cada passo e some os $\ln c_t$ para evitar underflow.

Lab: o que é avaliado

O primeiro valor forward15 pts
O total do primeiro dia10 pts
Filtrado após dois dias15 pts
A probabilidade da sequência15 pts
A log-verossimilhança10 pts
O que o algoritmo forward economiza10 pts
Associar o vocabulário10 pts
Por que os valores são reescalados15 pts

Quão provável é o que vimos?

\alpha_1(j)=\pi_jB_j(o_1),\qquad \alpha_t(j)=\Big[\sum_i\alpha_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad P(o_1,\dots,o_T)=\sum_j\alpha_T(j)

(1)

Pequeno, Grande, GrandeDia 1:

\alpha_1=(0{,}6\cdot0{,}9,\ 0{,}4\cdot0{,}3)=(0{,}54,\ 0{,}12)

, total

c_1=0{,}66

. Dia 2 (um movimento grande): Calmo recebe

(0{,}54\cdot0{,}9+0{,}12\cdot0{,}2)\cdot0{,}1=0{,}051

e Tempestuoso

(0{,}54\cdot0{,}1+0{,}12\cdot0{,}8)\cdot0{,}7=0{,}105

, total

0{,}156

, então a probabilidade filtrada de Tempestuoso é

0{,}105/0{,}156=0{,}673

. O dia 3 dá

\alpha_3=(0{,}00669,\ 0{,}06237)

. A probabilidade de toda a sequência é

0{,}00669+0{,}06237=0{,}0691

e seu log é

-2{,}673

Algoritmo forward: soma sobre todos os caminhos ocultos em $T\cdot K^{2}$ passos em vez de $K^{T}$ .
Probabilidades filtradas: normalize $\alpha_t$ para obter sua crença sobre o estado de hoje com os dados até hoje.
Escalonamento: divida por $c_t$ a cada passo e some os $\ln c_t$ para evitar underflow.

Lab: o que é avaliado

O primeiro valor forward15 pts
O total do primeiro dia10 pts
Filtrado após dois dias15 pts
A probabilidade da sequência15 pts
A log-verossimilhança10 pts
O que o algoritmo forward economiza10 pts
Associar o vocabulário10 pts
Por que os valores são reescalados15 pts

Quão provável é o que vimos?

Lab: o que é avaliado

Entre para executar o seu código.

O algoritmo forward

Quão provável é o que vimos?

Lab: o que é avaliado

Entre para executar o seu código.