13.5.1 Finite-State Rule-Based Chunking

Syntactic base-phrases of the kind we're considering can be characterized by finite-state automata (or finite-state rules, or regular expressions) of the kind discussed earlier in Chs. 2 and 3. In finite-state rule-based chunking, a set of rules is hand-crafted to capture the phrases of interest for any particular application. In most rule-based systems, chunking proceeds from left-to-right, finding the longest matching chunk from the beginning of the sentence, it then continues with the first word after the end of the previously recognized chunk. The process continues until the end of the sentence. This is a greedy process and is not guaranteed to find the best global analysis for any given input.

The primary limitation placed on these chunk rules is that they can not contain any recursion; the right-hand side of the rule can not reference directly, or indirectly, the category that the rule is designed to capture. In other words, rules of the form $ NP \rightarrow Det\ Nominal\ are\ fine $, but rules such as Nominal $ \rightarrow Nominal\ PP $ are not. Consider the following example chunk rules adapted from Abney (1996).

$$ \mathit{N P}\;\to\;\left(\mathit{D e t}\right)\mathit{N o u n}^{*}~\mathit{N o u n} $$

NP $ \rightarrow $ Proper-Noun

$$ VP\ \to\ \textit{Verb} $$

$$ VP\ \to\ Aux\ Verb $$

The process of turning these rules into a single finite-state transducer is the same we introduced in Ch. 3 to capture spelling and phonological rules for English. Finite state transducers are created corresponding to each rule and are then unioned together to form a single machine that can then be determined and minimized.

As we saw in Ch. 3, a major benefit of the finite-state approach is the ability to use the output of earlier transducers as inputs to subsequent transducers to form cascades. In partial parsing, this technique can be used to more closely approximate the output of true context-free parsers. In this approach, an initial set of transducers is used, in the way just described, to find a subset of syntactic base-phrases. These base-phrases are then passed as input to further transducers that detect larger and larger constituents such as prepositional phrases, verb phrases, clauses, and sentences. Con

原书第 502 页

The morning flight from Denver has arrived

Figure 13.18 Chunk-based partial parsing via a set of finite-set cascades. $ FST_{1} $ transduces from part-of-speech tags to base noun phrases and verb phrases. $ FST_{2} $ finds prepositional phrases. Finally, $ FST_{3} $ detects sentences.

sider the following rules, again adapted from Abney (1996).

$$ \mathrm{F S T}_{2}\mathrm{P P}\rightarrow\mathrm{P r e p o s i t i o n}\mathrm{N P} $$

$$ \begin{array}{r}{\begin{array}{r l}{F S T_{3}}&{{}S\to P P^{*}N P P P^{*}V P P P^{*}}\end{array}}\end{array} $$

Combining these two machines with the earlier rule-set results in a three machine cascade. The application of this cascade to Ex. 13.8 is shown in Fig. 13.18.