$B!{(B Viterbi algorithm

$N \times T$$B$N(B2$B$D$N9TNs(B SEQSCORE $B$H(B BACKPTR $B$rMQ0U$9$k(B

• SEQSQORE(i,t)
  t$BHVL\$NC18l$,(B category i $B$G=P8=$9$k$H$-$NJ8F,$+$i$N:GBg3NN((B,
  

  $$PROB(L_i\vert\phi) \cdot PROB(w_1\vert L_i)$$ SEQSCORE(i,1) = (7)

  $$\max_{j=1..N} (SUBSCORE(j,t-1) \cdot PROB(L_i\vert L_j) \cdot PROB(w_t\vert L_i))$$ SEQSCORE(i,t) = (8)

  
  
  $B$H$$$&:F5"E*$JDj5A(B($BA22=<0(B)
• BACKPTR(i,t)
  t$BHVL\$NC18l$K(B SEQSCORE(i,t) $B$rM?$($k(B t-1$BHVL\$NC18l$NIJ;l(B i
  $B$D$^$j(B(8) $B$N(B $\max_{j=1..N}$ $B$N(B j $B$K$"$?$k(B

$B$3$N(B2$B$D$N(B matrix $B$rMQ0U$7(B,$B:G8e$K(B max_j=1..N(SEQSCORE(j,T)) $B$+$i(B BACKPTR(i,t) $B$r8e$m8~$-$K$?$I$C$F9T$1$P3NN($r:GBg$K$9$k%Q%9$,5a$^$k(B, (Figure 7,9)

($BNc(B) ``flies like a flower`` (T=4,N=4)
Figure 7.4,Figure 7.6 $B$r8+$J$,$i(B matrix $B$r:n$C$F$$$/(B,
(Figure 7,4 $B$K:\$C$F$J$$O"@\3NN($O(B 0.0001 $B$H$9$k(B)

• $B=i4|2=(B
  T=1 (flies), Figure 7.10 $B:8?^(B
  
  $$\begin{eqnarray*}SEQSCORE(V,flies) &=& 0.0001 \cdot 0.076 = 7.6 \cdot 10^{-6} \\... ...T,flies) &=& 0.71 \cdot 0 = 0 \\ \\ BACKPTR(i,flies) &=& \phi \end{eqnarray*}$$
  
  
• $B7+$jJV$7(B
  T=2 (like), Figure 7.10 $B1&?^(B
  
  $$\begin{eqnarray*}SEQSCORE(V,like) &=& max\{7.6 \cdot 10^{-6} \cdot PROB(V\vert V... ...0725 \cdot 0.0001\} \cdot 0 = 0 \\ BACKPTR(ART,like) &=& \phi \end{eqnarray*}$$
  
  T=3,4 (like,flower) Figure 7.11,Figure 7.12
  $B>JN,(B..
• $B:GBg%Q%9$N SEQSCORE(N,flower) $B$,:GBg(B, $B$3$3$+$i(B BACKSTORE(i,t) $B$r5U$K(B $B$?$I$l$P(B (flies/N) $\rightarrow$ (like/V) $\rightarrow$ (a/ART) $\rightarrow$ (flower/N) $B$H$$$&7k2L$,F@$i$l$k(B

 

Table 1: $B>e(B SEQSCORE(i,j),$B2<(B 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 $B$r;H$&$H9b$$@:EY$rF@$k$3$H$,CN$i$l$F$$$k(B(95%)