7.7 A Simple Context-Dependent Best-First Parser

• best-first algorithm $B$O(B $B8zN($h$$(B parse $B$Ne$K$D$J$,$k(B algorithm $B$G$OL5$$(B
• context-dependent $B$J(B lexical information $B$K4X$9$k3NN($r;H$C$C$F(B $B@:EY8~>e$r;n$_$k(B
• Category C $B$,(B $BC18l(B w $B$G;O$^$k(B rule R_i $B$GE83+$5$l$?3NN((B $B$r5a$a$k(B
  
  $$\begin{eqnarray*}PROB(R\vert C,w) = \frac{Count(\char93 \ times\ rule\ R\ used\ ... ...g\ with\ w)} {Count(\char93 \ times\ cat\ C\ starts\ with\ w)} \end{eqnarray*}$$
  
  Figure 7.23
  • house vs. peaches
    house $B$O(B NP $\rightarrow$ N N $B$K$J$j$d$9$$(B (0.82)
    peaches$B$O(B NP $\rightarrow$ N $B$K$J$j$d$9$$(B (0.65)
  • like vs. put
    like $B$O(B VP $\rightarrow$ NP $B$K$J$j$d$9$$(B (0.9)
    put $B$O(B VP $\rightarrow$ V NP PP $B$K$J$j$d$9$$(B (0.93) (put $B!A(B in)
• context-dependent $B$J3NN($r;H$&$H@:EY$,8~>e$9$k(B 49% $\rightarrow$ 66%
  $B@:EY$N8~>e$NB>$K8zN(E*$J2r@O$b9T$&$3$H$,$G$-$k(B, chart $B?t(B 65 $\rightarrow$ 36
  (Figure 7.24)
• $B$J$<@:EY$,8~>e$9$k$N$+(B?
  • The man put the bird in the house.
  • The man likes bird in the house.
  $B$rHf$Y$F$_$k(B Figure 7.25, 7.26
  • context-free $B$J3NN(CM$rMQ$$$k$H(B, $B3FC18l$r8+$J$$$N$G(B,2$B$D$H$b(B $BF1$8(B parse tree $B$,F@$i$l$k(B $\rightarrow$ $B$^$A$,$$(B
  • $B $\rightarrow$ context $B$r9MN8$7$?$[$&$,$$$$$K$-$^$C$F$$$k(B
• $B$5$i$K8-$/$9$k$?$a$K$O(B?
  • w $B$N$_$r8+$F$$$?(B (unigram) $B3NN($N7W;;$r(B bigram $B$d(B trigram $B$K3HD%$9$k(B ($B$?$@$7(B $BB?NL$N(B traing data $B$,I,MW(B)
  • VP $\rightarrow$ V NP PP $B$H$$$&$h$&$J(B rule $B$N>l9g(B V $B$@$1$G$J$/(B PP $B$N ($BLdBjE@(B: VP $\rightarrow$ V NP $B$H$N3NN($NHf3S$,:$Fq$K$J$k(B)
  • closed class words
    prepositions, articles, quantifiers, conjunctions $\rightarrow$ $B$3$l$i$O(B enumerate $B$G$-$k$N$G4JC1$K?dDj2DG=(B
  • open class words
    $B$[$s$H$O$3$l$i$b8DJL$K07$$$?$$$N$@$1$I(B, data sparseness $B$N(B $BLdBj$GFq$7$$(B
    • $BHs>o$K$h$/=P$F$/$kC18l$N$_$r8DJL$K07$&(B
    • $B ($BF0:n$r<($9F0;l$r$R$H$D$N(B class $B$K$^$H$a$F$3$l$i$OF1$8?6$k(B $BIq$$$r$9$k$H2>Dj(B ..etc)