14.6.1 The Collins Parser

Modern statistical parsers differ in exactly which independence assumptions they make. In this section we describe a simplified version of Collins's (1999) Model 1, but there are a number of other parsers that are worth knowing about; see the summary at the end of the chapter.

原书第 527 页

The first intuition of the Collins parser is to think of the right-hand side of every (internal) CFG rule as consisting of a head non-terminal, together with the non-terminals to the left of the head, and the non-terminals to the right of the head. In the abstract, we think about these rules as follows:

$$ LHS\to L_{n}L_{n-1}\dots L_{1}HR_{1}\dots R_{n-1}R_{n} $$

Since this is a lexicalized grammar, each of the symbols like $ L_1 $ or $ R_3 $ or H or LHS is actually a complex symbol representing the category and its head and head tag, like VP(dumped,VP) or NP(sacks,NNS).

Now instead of computing a single MLE probability for this rule, we are going to break down this rule via a neat generative story, a slight simplification of what is called Collins Model 1. This new generative story is that given the left-hand side, we first generate the head of the rule, and then generate the dependents of the head, one by one, from the inside out. Each of these generation steps will have its own probability.

We are also going to add a special STOP non-terminal at the left and right edges of the rule; this non-terminal will allow the model to know when to stop generating dependents on a given side. We'll generate dependents on the left side of the head until we've generated STOP on the left side of the head, at which point we move to the right side of the head and start generating dependents there until we generate STOP. So it's as if we are generating a rule augmented as follows:

$$ P\left(VP(dumped,VBD)\rightarrow STOP~VBD(dumped,VBD)\ N P(sacks,NNS)\ PP(into,P)\ STOP\right. $$

Let's see the generative story for this augmented rule. We're going to make use of three kinds of probabilities: $ P_{H} $ for generating heads, $ P_{L} $ for generating dependents on the left, and $ P_{R} $ for generating dependents on the right.

| --- | --- |

| 2) Then generate the left dependent (which is STOP, since there isn't one) with probability $ P(STOP | VP(dumped,VBD) VBD(dumped,VBD)) $ | VP(dumped,VBD)\nSTOP VBD(dumped,VBD) |

| 3) Then generate right dependent NP(sacks,NNS) with probability $ P_r(NP(sacks,NNS | VP(dumped,VBD), VBD(dumped,VBD))) $ | VP(dumped,VBD)\nSTOP VBD(dumped,VBD) NP(sacks,NNS) |

| 4) Then generate the right dependent PP(into,P) with probability $ P_r(PP(into,P | VP(dumped,VBD), VBD(dumped,VBD))) $ | VP(dumped,VBD)\nSTOP VBD(dumped,VBD) NP(sacks,NNS) PP(into,P) |

| 5) Finally generate the right dependent STOP with probability $ P_r(STOP | VP(dumped,VBD), VBD(dumped,VBD))) $ | VP(dumped,VBD)\nSTOP VBD(dumped,VBD) NP(sacks,NNS) PP(into,P) STOP |

原书第 528 页

In summary, the probability of this rule:

$$ P\left(VP(dumped,VBD)\rightarrow VBD(dumped,VBD)\right.NP(sacks,NNS)PP(into,P) $$

is estimated as:

$$ \begin{aligned}P_{H}(VBD|VP,dumped)&\times&P_{L}(STOP|VP,VBD,dumped)\\&\times&P_{R}(NP(sacks,NNS)|VP,VBD,dumped)\\&\times&P_{R}(PP(into,P)|VP,VBD,dumped)\\&\times&P_{R}(STOP|VP,VBD,dumped)\end{aligned} $$

Each of these probabilities can be estimated from much smaller amounts of data than the full probability in (14.27). For example, the maximum likelihood estimate for the component probability $ P_R(NP(sacks, NNS)|VP, VBD, dumped) $ is:

$$ \frac{P_{R}(NP(sacks,NNS)|VP,VBD,dumped)=}{\underline{Count(VP(dumped,VBD)with NNS(sacks)as a daughter somewhere on the right)}}\over\underline{Count(VP(dumped,VBD))} $$

These counts are much less subject to sparsity problems than complex counts like those in (14.27).

More generally, if we use $h$ to mean a headword together with its tag, $l$ to mean a word+tag on the left and $r$ to mean mean a word+tag on the right, the probability of an entire rule can be expressed as:

1. Generate the head of the phrase $ H(hw, ht) $ with probability $ P_{H}(H(hw, ht)|P, hw, ht) $

2. Generate modifiers to the left of the head with total probability:

$$ \prod_{i=1}^{n+1}P_{L}(L_{i}(lw_{i},lt_{i})|P,H,hw,ht) $$

such that $ L_{n+1}(lw_{n+1},lt_{n+1}) = \text{STOP} $, and we stop generating once we've generated a STOP token.

3. Generate modifiers to the right of the head with total probability:

$$ \prod_{i=1}^{n+1}P_{P}(R_{i}(rw_{i},rt_{i})|P,H,hw,ht) $$

such that $ R_{n+1}(rw_{n+1},rt_{n+1}) = STOP $, and we stop generating once we've generated a STOP token.