Decodificação de Viterbi

Posição no roteiroMódulo 2 de 3 · Tópico 2 de 4

2.2 Decodificação de Viterbi

—Nota do lab— / 100XP total—Sequência—

A única história mais provável

O algoritmo forward soma todos os caminhos ocultos para dizer quão prováveis são os dados. Muitas vezes queremos outra coisa: a melhor história única, a sequência de estados que explica os dados com a maior probabilidade. A decodificação de Viterbi a encontra. A ideia é o algoritmo forward com uma mudança: em vez de somar sobre os estados anteriores, tomar o melhor. Guarda-se uma pontuação $\delta_t(j)$ , a probabilidade do melhor caminho que termina no estado $j$ no dia $t$ , e lembra-se qual estado anterior a deu, o ponteiro para trás.

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Depois do último dia, escolha o estado com maior $\delta_T$ e volte pelos ponteiros $\psi$ para ler o caminho todo. Dois pontos práticos. Primeiro, trabalhe com logs: produtos de muitas probabilidades tendem a zero, mas os logs os transformam em somas e, como o log é crescente, o melhor caminho é o mesmo. Segundo, o melhor caminho não é o mesmo que escolher o estado mais provável de cada dia separadamente. O caminho pode ser forçado pelo que vem depois, como mostra o exemplo.

Pequeno, Grande, Grande de novoDia 1:

\delta_1=(0{,}54,\ 0{,}12)

. Dia 2 (grande): Calmo vem melhor de Calmo,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Tempestuoso vem melhor de Tempestuoso,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, e não de Calmo (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Dia 3: Tempestuoso vem de Tempestuoso,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, e Calmo só

0{,}0044

. O melhor caminho é Tempestuoso, Tempestuoso, Tempestuoso com probabilidade

0{,}0376

. No entanto, o primeiro dia sozinho parecia calmo com probabilidade

0{,}82

. Os movimentos grandes seguintes puxam toda a história para Tempestuoso. Esse caminho é

1{,}78

vez mais provável que Calmo, Tempestuoso, Tempestuoso (

0{,}0212

Viterbi troca a soma do algoritmo forward por um máximo e guarda ponteiros para trás.
O melhor caminho pode diferir do estado mais provável de cada dia tomado separadamente.
Use logs: somas de logs evitam underflow e mantêm o mesmo melhor caminho.

Lab: o que é avaliado

Uma pontuação de Viterbi no dia dois15 pts
A probabilidade do melhor caminho15 pts
O log do melhor caminho10 pts
Diante de outro caminho10 pts
O primeiro estado do melhor caminho15 pts
Os passos de Viterbi10 pts
Associar o vocabulário10 pts
Por que usar logs15 pts

0/ 8 respondidas

1Resposta numérica15 ptsSem resposta

Com $\delta_1=(0{,}54,\ 0{,}12)$ e um movimento grande no dia 2, quanto vale $\delta_2(T)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Dê quatro casas decimais.

d =

aceito: ± 0.0003

2Resposta numérica15 ptsSem resposta

Com $\delta_2=(0{,}0486,\ 0{,}0672)$ e um movimento grande no dia 3, quanto vale $\delta_3(T)=\max(0{,}0486\cdot0{,}1,\ 0{,}0672\cdot0{,}8)\cdot0{,}7$ , a probabilidade do melhor caminho? Dê quatro casas decimais.

d =

aceito: ± 0.0003

3Resposta numérica10 ptsSem resposta

Qual é o logaritmo natural da probabilidade $0{,}0376$ do melhor caminho? Dê duas casas decimais.

l =

aceito: ± 0.02

4Resposta numérica10 ptsSem resposta

Quantas vezes o melhor caminho (probabilidade $0{,}0376$ ) é mais provável que o caminho Calmo, Tempestuoso, Tempestuoso (probabilidade $0{,}0212$ )? Dê duas casas decimais.

r =

aceito: ± 0.02

5Escolha15 ptsSem resposta

O primeiro dia mostra um movimento pequeno, o que torna Calmo 82 % provável sozinho. Qual é o primeiro estado do melhor caminho para Pequeno, Grande, Grande?

6Ordenar os passos10 ptsSem resposta

Coloque em ordem os passos da decodificação de Viterbi.

Arraste para reordenar, ou foque um item, Espaço para levantá-lo, setas para movê-lo e Espaço para soltá-lo.

1Depois do último dia, escolher o estado de maior pontuação
2Começar com delta igual à probabilidade inicial vezes a primeira emissão
3Voltar pelos ponteiros para ler o caminho
4Para cada dia e estado, manter o melhor predecessor e lembrá-lo

7Associar10 ptsSem resposta

Associe cada termo ao seu significado.

Escolha o par de cada item da esquerda.

\delta_t(j)

\psi_t(j)

Algoritmo forward

Algoritmo de Viterbi

8Explicar com palavras15 ptsSem resposta

Em uma ou duas frases, explique por que a decodificação de Viterbi costuma ser escrita com logs das probabilidades e por que isso não muda o melhor caminho.

Avaliado por:Produtos de muitas probabilidades tendem a zeroLogs transformam produtos em somas e o log é crescente, então o melhor caminho é o mesmo0 / 400 caracteres

Modo matemáticaEntrada por teclado ou LaTeXTarefa 1 de 8 · Ctrl ⏎ para verificar

Decodificação de Viterbi

Posição no roteiroMódulo 2 de 3 · Tópico 2 de 4

2.2 Decodificação de Viterbi

—Nota do lab— / 100XP total—Sequência—

A única história mais provável

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Pequeno, Grande, Grande de novoDia 1:

\delta_1=(0{,}54,\ 0{,}12)

. Dia 2 (grande): Calmo vem melhor de Calmo,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Tempestuoso vem melhor de Tempestuoso,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, e não de Calmo (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Dia 3: Tempestuoso vem de Tempestuoso,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, e Calmo só

0{,}0044

. O melhor caminho é Tempestuoso, Tempestuoso, Tempestuoso com probabilidade

0{,}0376

. No entanto, o primeiro dia sozinho parecia calmo com probabilidade

0{,}82

. Os movimentos grandes seguintes puxam toda a história para Tempestuoso. Esse caminho é

1{,}78

vez mais provável que Calmo, Tempestuoso, Tempestuoso (

0{,}0212

Viterbi troca a soma do algoritmo forward por um máximo e guarda ponteiros para trás.
O melhor caminho pode diferir do estado mais provável de cada dia tomado separadamente.
Use logs: somas de logs evitam underflow e mantêm o mesmo melhor caminho.

Lab: o que é avaliado

Uma pontuação de Viterbi no dia dois15 pts
A probabilidade do melhor caminho15 pts
O log do melhor caminho10 pts
Diante de outro caminho10 pts
O primeiro estado do melhor caminho15 pts
Os passos de Viterbi10 pts
Associar o vocabulário10 pts
Por que usar logs15 pts

0/ 8 respondidas

1Resposta numérica15 ptsSem resposta

Com $\delta_1=(0{,}54,\ 0{,}12)$ e um movimento grande no dia 2, quanto vale $\delta_2(T)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Dê quatro casas decimais.

d =

aceito: ± 0.0003

2Resposta numérica15 ptsSem resposta

d =

aceito: ± 0.0003

3Resposta numérica10 ptsSem resposta

Qual é o logaritmo natural da probabilidade $0{,}0376$ do melhor caminho? Dê duas casas decimais.

l =

aceito: ± 0.02

4Resposta numérica10 ptsSem resposta

Quantas vezes o melhor caminho (probabilidade $0{,}0376$ ) é mais provável que o caminho Calmo, Tempestuoso, Tempestuoso (probabilidade $0{,}0212$ )? Dê duas casas decimais.

r =

aceito: ± 0.02

5Escolha15 ptsSem resposta

O primeiro dia mostra um movimento pequeno, o que torna Calmo 82 % provável sozinho. Qual é o primeiro estado do melhor caminho para Pequeno, Grande, Grande?

6Ordenar os passos10 ptsSem resposta

Coloque em ordem os passos da decodificação de Viterbi.

Arraste para reordenar, ou foque um item, Espaço para levantá-lo, setas para movê-lo e Espaço para soltá-lo.

1Depois do último dia, escolher o estado de maior pontuação
2Começar com delta igual à probabilidade inicial vezes a primeira emissão
3Voltar pelos ponteiros para ler o caminho
4Para cada dia e estado, manter o melhor predecessor e lembrá-lo

7Associar10 ptsSem resposta

Associe cada termo ao seu significado.

Escolha o par de cada item da esquerda.

\delta_t(j)

\psi_t(j)

Algoritmo forward

Algoritmo de Viterbi

8Explicar com palavras15 ptsSem resposta

Em uma ou duas frases, explique por que a decodificação de Viterbi costuma ser escrita com logs das probabilidades e por que isso não muda o melhor caminho.

Avaliado por:Produtos de muitas probabilidades tendem a zeroLogs transformam produtos em somas e o log é crescente, então o melhor caminho é o mesmo0 / 400 caracteres

Modo matemáticaEntrada por teclado ou LaTeXTarefa 1 de 8 · Ctrl ⏎ para verificar

Decodificação de Viterbi

A única história mais provável

Lab: o que é avaliado

Entre para executar o seu código.

Decodificação de Viterbi

A única história mais provável

Lab: o que é avaliado

Entre para executar o seu código.