next up previous
Next: Box 7.1 Getting Reliable Up: Chapter7Ambiguity Resoltion: Statistical Methods Previous: 7.3 Part-of-Speech Tagging

○ Viterbi algorithm

$N \times T$の2つの行列 SEQSCOREBACKPTR を用意する

この2つの matrix を用意し,最後に maxj=1..N(SEQSCORE(j,T)) から BACKPTR(i,t) を後ろ向きにたどって行けば確率を最大にするパスが求まる, (Figure 7,9)

(例) ``flies like a flower`` (T=4,N=4)
Figure 7.4,Figure 7.6 を見ながら matrix を作っていく,
(Figure 7,4 に載ってない連接確率は 0.0001 とする)


 
Table 1: SEQSCORE(i,j),下 BACKPTR(i,t)
  V N P ART
flies $7.6\cdot 10^{-6}$ 0.00725 0 0
like 0.00031 $1.3 \cdot 10^{-5}$ 0.00022 0
a 0 $1.2 \cdot 10^{-7}$ 0 $7.2 \cdot 10^{-5}$
flower $2.6 \cdot 10^{-9}$ $4.3 \cdot 10^{-6}$ 0 0
         
         
  V N P ART
flies $\phi$ $\phi$ $\phi$ $\phi$
like N N N $\phi$
a $\phi$ V $\phi$ V
flower ART ART $\phi$ $\phi$

trigram を使うと高い精度を得ることが知られている(95%)


next up previous
Next: Box 7.1 Getting Reliable Up: Chapter7Ambiguity Resoltion: Statistical Methods Previous: 7.3 Part-of-Speech Tagging

1999-08-03