7.3 Part-of-Speech Tagging

$BC18l$NB0$9$k(Bcategories($BIJ;l(B)$B$r7hDj$9$kLdBj(B (tagset $B$NNc(B figure 7.3)

• $BC18lNs(B $w_1,w_2,\cdots, ,w_T$ $B$K3d$jEv$F$k(B categories $C_1,C_2,\cdots,C_T$$B$N$&$A(B,$B$=$N3NN((B
  

  $$PROB(C_1,C_2,\cdots,C_T\vert w_1,w_2,\cdots ,w_T)$$ (1)

  
  
  $B$r:GBg$K$9$k3d$jEv$F$r5a$a$k$3$H$,LdBj(B
• Bayes' Rule $B$h$j(B (1)$B$O(B
  

  $$\frac{PROB(C_1,C_2,\cdots,C_T) \cdot PROB(w_1,w_2,\cdots ,w_T\vert C_1,C_2,\cdots,C_T)}{PROB(w_1,w_2,\cdots ,w_T)}$$ (2)

  
  

• (2) $B$NJ,Jl(B $PROB(w_1,w_2,\cdots ,w_T$) $B$O(B $C_1,C_2,\cdots,C_T$ $B$N(B $B3d$jEv$F$K$O0MB8$7$J$$$N$G(B
  

  $$PROB(C_1,C_2,\cdots,C_T) \cdot PROB(w_1,w_2,\cdots ,w_T\vert C_1,C_2,\cdots,C_T)$$ (3)

  
  
  $B$r:GBg$K$9$l$P$h$$(B
  $B@\(B $B5a$a$k$3$H$O:$Fq(B
• n-gram model
  • (3) $B$NBh(B1$B9`(B $PROB(C_1,C_2,\cdots,C_T)$
    C_i $B$O$=$N(B n-1$B8DA0$NIJ;l$N$_$K0MB8$9$k$H$$$&2>Dj(B (n=2 bigram, n=3 trigram)
    bigram $B$N>l9g(B,
    

    $$PROB(C_1,C_2,\cdots,C_T) \simeq \prod_{i=1}^T PROB(C_i\vert C_{i-1})$$ (4)

    
    
    $B$H$J$k(B, $BNc$($P(B ART,N,V,N $B$H$$$&(Bcategory$BNs$r3d$jEv$F$k>l9g$O(B
    
    $$\begin{eqnarray*}PROB(ART,N,V,N) \simeq PROB(ART\vert\phi) \cdot PROB(N\vert ART) \cdot PROB(V\vert N) \cdot PROB(N\vert V) \end{eqnarray*}$$
    
    $n\geq4$ $B$N(B n-gram $B$b2DG=$@$,(B, data sparseness,$B7W;;NL$NLdBj$G8=(3) $B$NBh(B2$B9`(B $PROB(w_1,w_2,\cdots ,w_T\vert C_1,C_2,\cdots,C_T)$
    $B3F(B category $B$KB0$9$kC18l$OA08e$NC18l$HFHN)$G$"$k$H$$$&2>Dj(B
    

    $$PROB(w_1,w_2,\cdots ,w_T\vert C_1,C_2,\cdots,C_T) \simeq \prod_{i=1}^T PROB(w_i\vert C_i)$$ (5)

    
    

  • (4)(5)$B$N6a;w$h$j(B,$BA4BN$H$7$F(B
    

    $$\prod_{i=1}^T PROB(C_i\vert C_{i-1}) \cdot PROB(w_i\vert C_i)$$ (6)

    
    
    $B$r:GBg2=$9$k(B $C_1,C_2,\cdots,C_T$$B$r5a$a$k$3$H$K5"Ce$5$l$k(B
• $B $BC1$KIQEY$r5a$a$l$P$h$$(B
  
  $$\begin{eqnarray*}PROB(C_i=V\vert C_{i-1} = N) \simeq \frac{Count(N\ at\ postion\ i-1\ and\ V\ at\ i)}{Count(N\ at\ postion\ i-1)} \end{eqnarray*}$$
  
  Figure 7.4 $B$r;2>H(B, PROB(w_i|C_i) $B$O(B, Figure 7.5 $B$N$h$&$J(B matrix $B$r:n$l$P5a$^$k(B, Figure 7.6 $B$O(B matrix $B$+$i5a$a$?3NN(CM(B
• $B:GBgCM$N5a$aJ}(B
  • brute force method
    $B$9$Y$F$NAH9g$o$;$r$7$i$_$D$V$7$KD4$Y$k(B $\rightarrow N^T$ $BDL$j(B
  • Markov model (Markov assumption, Markov chains)
    $B$"$k>uBV$,(B,$B0JA0$N>uBV$K0MB8$7$?3NN($GA+0\$9$k(B,
    $\prod_{i=1}^T PROB(C_i\vert C_{i-1}) $B$O$^$5$7$/(B$ Markov model $B$G2r7h$G$-$k(B, Figure 7.7
  • HMM (Hidden Markov Model)
    Figure 7.7 $B$OIJ;l$N>uBVA+0\$N$_(B
    $B PROB(w_i|C_i) $B$r9MN8$9$kI,MW$,$"$k(B,
    $B3F>uBV$GC18l$N=P8=3NN($,(B Markov Chains $B$NCf$K(B $B1#$l$F$$$k(B$B$H$$$&0U(B $BL#$G(B Hidden Markov Model
    
    ($BNc(B)
    ``Flies like a flower'' $B$,(B ``N V ART N'' $B$H2r@O$5(B $B$l$?>l9g(B, HMM $B$NFbIt>uBV(B($B1#$l$?ItJ,$N>uBV(B)$B$N3NN($O(B
    
    $$\begin{eqnarray*}PROB(flies\vert N) \cdot PROB(like\vert V) \cdot PROB(a\vert AR... ...\\ = 0.25 \cdot 0.1 \cdot 0.36 \cdot 0.63 = 5.4 \cdot 10^{-5} \end{eqnarray*}$$
    
    $B$H$J$k(B, HMM $B$N30It>uBV(B($BI=$K=P$F$$$k>uBVA+0\$N3NN((B)$B$O(B, MM $B$HF1$8$@$+$i(B
    
    $$\begin{eqnarray*}PROB(N\vert\phi) \cdot PROB(V\vert N)\cdot PROB(V\vert ART) \cdot PROB(N\vert ART) \\ = 0.081 \end{eqnarray*}$$
    
    total $B$G(B ``N V ART N'' $B$H$$$&(B category $B$,IUM?$5$l$k3NN((B $B$O(B
    $5.4 \cdot 10^{-5} \cdot 0.081= 4.37 \cdot 10^{-6}$ $B$H(B $B$J$k$s$@$1$I(B, $B$3$NCM$O$^$5$7$/(B
    
    $$\begin{eqnarray*}\prod_{i=1}^T PROB(C_i\vert C_{i-1}) \cdot PROB(w_i\vert C_i) \end{eqnarray*}$$
    
    (6)$B<0$r5a$a$?$3$H$HEy$7$$(B, $B$D$^$j(B (7) $B$H(B HMM $B$OEy2A(B
  • HMM $\rightarrow$ MM
    Figure 7.8 $B$N$h$&$K(B HMM $B$N1#$l$?ItJ,$rI=$K=P$7$F!J1#$l$?(B $BItJ,$r$R$H$D$N>uBV$K$7$F(B) MM $B$K$9$3$H$,$G$-$k(B, $B$3$l$r$7$i$_$D$V$7$KD4$Y$k$H(B, 4⁴ = 256$B$N%Q%9(B, $BC18l?t(B,category $B?t$,A}$($k$H7W;;NL$,GzH/$7$F$/$k(B (N category, T words $\rightarrow N^T$ $BDL$j(B),
    $B7k6I(B $B$3$l$O0JA0=R$Y$?(B brute force method $B$HF1$8$3$H(B
  • Viterbi algorithm
    $BC18l$N(B category $B$OC1=c$J(B markov model,
    $B C_i $B$r7W;;$9$k$N$K$O(B C_i-1 $B$N>pJs$5$($"$l$P$h$/(B, C_i-2 $B$+$i(B C_i-1 $B$NA+0\$N$&$A:GNI$N%Q%90J30$O(B $B9M$($kI,MW$,$J$$(B,
    $B7W;;NL$r(B $k\cdot T \cdot N^2$ $B$^$G8:$i$9$3$H$,2DG=(B (k = constant value)