14.6.2 Advanced: Further Details of the Collins Parser

The actual Collins parser models are more complex (in a couple of ways) than the simple model presented in the previous section. Collins Model 1 includes a distance

feature. Thus instead of computing $ P_{L} $ and $ P_{R} $ as follows:

$$ P_{L}(L_{i}(lw_{i},lt_{i})|P,H,hw,ht) $$

$$ P_{R}(R_{i}(rw_{i},rt_{i})|P,H,hw,ht) $$

Collins Model 1 conditions also on a distance feature:

$$ P_{L}(L_{i}(lw_{i},lt_{i})|P,H,hw,ht,distance_{L}(i-1)) $$

$$ P_{R}(R_{i}(rw_{i},rt_{i})|P,H,hw,ht,distance_{R}(i-1)) $$

The distance measure is a function of the sequence of words below the previous modifiers (i.e. the words which are the yield of each modifier non-terminal we have already generated on the left). Fig. 14.11, adapted from Collins (2003) shows the computation of the probability $ P(R_2(rh_2,rt_2)|P,H,hw,ht,distance_R(1)) $:

| Figure 14.11 | The next child $ R_{2} $ is generated with probability $ P(R_{2}(rh_{2},rt_{2})|P,H,hw,ht,distance_{R}(1)) $. | The distance is the yield of the previous dependent nonterminal $ R_{1} $. Had there been another intervening dependent, its yield would have been included as well. Adapted from Collins (2003). |

| --- | --- | --- |

The simplest version of this distance measure is just a tuple of two binary features based on the surface string below these previous dependencies: (1) is the string of length zero? (i.e. were were no previous words generated?) (2) does the string contain a verb?

Collins Model 2 adds more sophisticated features, conditioning on subcategorization frames for each verb, and distinguishing arguments from adjuncts.

Finally, smoothing is as important for statistical parsers as it was for N-gram models. This is particularly true for lexicalized parsers, since (even using the Collins or other methods of independence assumptions) the lexicalized rules will otherwise condition on many lexical items that may never occur in training.

Consider the probability $ P_{R}(R_{i}(rw_{i},rt_{i})|P,hw,ht) $. What do we do if a particular right-hand side constituent never occurs with this head? The Collins model addresses this problem by interpolating three backed-off models: fully lexicalized (conditioning on the headword), backing off to just the head tag, and altogether unlexicalized:

| Backoff Level | $ P_{R}(R_{i}(rw_{i},rt_{i}...)) $ | Example |

| --- | --- | --- |

| 1 | $ P_{R}(R_{i}(rw_{i},rt_{i})|P,hw,ht) $ | $ P_{R}(NP(sacks,NNS)|VP,VBD,dumped) $ |

| 2 | $ P_{R}(R_{i}(rw_{i},rt_{i})|P,ht) $ | $ P_{R}(NP(sacks,NNS)|VP,VBD) $ |

| 3 | $ P_{R}(R_{i}(rw_{i},rt_{i})|P) $ | $ P_{R}(NP(sacks,NNS)|VP) $ |

Similar backoff models are built also for $P_L$ and $P_H$. Although we've used the word 'backoff', in fact these are not backoff models but interpolated models. The three models above are linearly interpolated, where $e_1$, $e_2$, and $e_3$ are the maximum likelihood estimates of the three backoff models above:

$$ P_{R}(...)=\lambda_{1}e_{1}+(1-\lambda_{1})(\lambda_{2}e_{2}+(1-\lambda_{2})e_{3}) $$

The values of $ \lambda_1 $ and $ \lambda_2 $ are set to implement Witten-Bell discounting (Witten and Bell, 1991) following Bikel et al. (1997).

Unknown words are dealt with in the Collins model by replacing any unknown word in the test set, and any word occurring less than 6 times in the training set, with a special UNKNOWN word token. Unknown words in the test set are assigned a part-of-speech tag in a preprocessing step by the Ratnaparkhi (1996) tagger; all other words are tagged as part of the parsing process.

The parsing algorithm for the Collins model is an extension of probabilistic CKY; see Collins (2003). Extending the CKY algorithm to handle basic lexicalized probabilities is left as an exercise for the reader.

14.7 EVALUATING PARSERS

The standard techniques for evaluating parsers and grammars are called the PARSEVAL measures, and were proposed by Black et al. (1991) based on the same ideas from signal-detection theory that we saw in earlier chapters. The intuition of the PARSEVAL metric is to measure how much the constituents in the hypothesis parse tree look like the constituents in a hand-labeled gold reference parse. PARSEVAL thus assumes we have a human-labeled "gold standard" parse tree for each sentence in the test set; we generally draw these gold standard parses from a treebank like the Penn Treebank.

Given these gold standard reference parses for a test set, a given constituent in a hypothesis parse $C_{h}$ of a sentence $s$ is labeled “correct” if there is a constituent in the reference parse $C_{r}$ with the same starting point, ending point, and non-terminal symbol.

We can then measure the precision and recall just as we did for chunking in the previous chapter.

$$ \mathrm{labeled~recall}:=\frac{\#\,\mathrm{of~correct~constituents~in~hypothesis~parse~of}\,s}{\#\,\mathrm{of~correct~constituents~in~reference~parse~of}\,s} $$

$$ labeled~precision:={\frac{\#~of~correct~constituents~in~hypothesis~parse~of~s}{\#~of~total~constituents~in~hypothesis~parse~of~s}} $$

As with other uses of precision and recall, instead of reporting them separately, we often report a single number, the F-measure (van Rijsbergen, 1975): The F-measure is defined as:

$$ F_{\beta}=\frac{(\beta^{2}+1)P R}{\beta^{2}P+R} $$

The $ \beta $ parameter is used to differentially weight the importance of recall and precision, based perhaps on the needs of an application. Values of $ \beta > 1 $ favor recall, while values

of $ \beta < 1 $ favor precision. When $ \beta = 1 $, precision and recall are equally balanced; this is sometimes called $ F_{\beta=1} $ or just $ F_1 $:

$$ F_{1}=\frac{2PR}{P+R} $$

The F-measure derives from a weighted harmonic mean of precision and recall. Recall that the harmonic mean of a set of numbers is the reciprocal of the arithmetic mean of the reciprocals:

$$ Harmonic Mean(a_{1},a_{2},a_{3},a_{4},...,a_{n})=\frac{n}{\frac{1}{a_{1}}\frac{1}{a_{2}}\frac{1}{a_{3}}\cdots\frac{1}{a_{n}}} $$

and hence F-measure is

$$ F=\frac{1}{\frac{1}{\alpha P}\times\frac{1}{(1-\alpha)R}}\quad\text{or}\left(\text{with}\beta^{2}=\frac{1-\alpha}{\alpha}\right)\quad\mathrm{F}=\frac{(\beta^{2}+1)\mathrm{PR}}{\beta^{2}\mathrm{P}+\mathrm{R}} $$

We additionally use a new metric, crossing brackets, for each sentence s:

cross-brackets: the number of constituents for which the reference parse has a bracketing such as ((A B) C) but the hypothesis parse has a bracketing such as (A (B C)).

As of the time of this writing, the performance of modern parsers that are trained and tested on the Wall Street Journal treebank is somewhat higher than 90% recall, 90% precision, and about 1% cross-bracketed constituents per sentence.

For comparing parsers which use different grammars, the PARSEVAL metric includes a canonicalization algorithm for removing information likely to be grammar-specific (auxiliaries, pre-infinitival "to", etc.) and for computing a simplified score. The interested reader should see Black et al. (1991). The canonical publicly-available implementation of the PARSEVAL metrics is called evalb (Sekine and Collins, 1997).

You might wonder why we don't evaluate parsers by measuring how many sentences are parsed correctly, instead of measuring constituent accuracy. The reason we use constituents is that measuring constituents gives us a more fine-grained metric. This is especially true for long sentences, where most parsers don't get a perfect parse. If we just measured sentence accuracy, we wouldn't be able to distinguish between a parse that got most of the constituents wrong, and one that just got one constituent wrong.

Nonetheless, constituents are not always an optimal domain for parser evaluation. For example, using the PARSEVAL metrics requires that our parser produce trees in the exact same format as the gold standard. That means that if we want to evaluate a parser which produces different styles of parses (dependency parses, or LFG feature structures, etc.) against say the Penn Treebank (or against another parser which produces Treebank format), we need to map the output parses into Treebank format. A related problem is that constituency may not be the level we care the most about. We might be more interested in how well the parser does at recovering grammatical dependencies (subject, object, etc), which could give us a better metric for how useful the

parses would be to semantic understanding. For these purposes we can use alternative evaluation metrics based on measuring the precision and recall of labeled dependencies, where the labels indicate the grammatical relations (Lin, 1995; Carroll et al., 1998; Collins et al., 1999). Kaplan et al. (2004), for example, compared the Collins (1999) parser with the Xerox XLE parser (Riezler et al., 2002), which produces much richer semantic representations, by converting both parse trees to a dependency representation.

14.8 ADVANCED: DISCRIMINATIVE RERANKING

The models we have seen of parsing so far, the PCFG parser and the Collins lexicalized parser, are generative parsers. By this we mean that the probabilistic model implemented in these parsers gives us the probability of generating a particular sentence by assigning a probability to each choice the parser could make in this generation procedure.

Generative models have some significant advantages; they are easy to train using maximum likelihood and they give us an explicit model of how different sources of evidence are combined. But generative parsing models also make it hard to incorporate arbitrary kinds of information into the probability model. This is because the probability is based on the generative derivation of a sentence; it is difficult to add features that are not local to a particular PCFG rule.

Consider for example how to represent global facts about tree structure. Parse trees in English tend to be right-branching; we'd therefore like our model to assign a higher probability to a tree which is more right-branching, all else being equal. It is also the case that heavy constituents (those with a large number of words) tend to appear later in the sentence. Or we might want to condition our parse probabilities on global facts like the identity of the speaker (perhaps some speakers are more likely to use complex relative clauses, or use the passive). Or we might want to condition on complex discourse factors across sentences. None of these kinds of global factors is trivial to incorporate into the generative models we have been considering. A simplistic model that for example makes each non-terminal dependent on how right-branching the tree is in the parse so far, or makes each NP non-terminal sensitive to the number of relative clauses the speaker or writer used in previous sentences, would result in counts that are far too sparse.

We discussed this problem in Ch. 6, where the need for these kinds of global features motivated the use of log-linear (MEMM) models for POS tagging instead of HMMs. For parsing, there are two broad classes of discriminative models: dynamic programming approaches and two-stage models of parsing that use discriminative reranking. We'll discuss discriminative reranking in the rest of this section; see the end of the chapter for pointers to discriminative dynamic programming approaches.

In the first stage of a discriminative reranking system, we can run a normal statistical parser of the type we've described so far. But instead of just producing the single best parse, we modify the parser to produce a ranked list of parses together with their probabilities. We call this ranked list of N parses the N-best list (the N-best list was

first introduced in Ch. 9 when discussing multiple-pass decoding models for speech recognition). There are various ways to modify statistical parsers to produce an N-best list of parses; see the end of the chapter for pointers to the literature. For each sentence in the training set and the test set, we run this N-best parser and produce a set of N parse/probability pairs.

The second stage of a discriminative reranking model is a classifier which takes each of these sentences with their N parse/probability pairs as input, extracts some large set of features and chooses the single best parse from the N-best list. We can use any type of classifier for the reranking, such as the log-linear classifiers introduced in Ch. 6.

A wide variety of features can be used for reranking. One important feature to include is the parse probability assigned by the first-stage statistical parser. Other features might include each of the CFG rules in the tree, the number of parallel conjuncts, how heavy each constituent is, measures of how right-branching the parse tree is, how many times various tree fragments occur, bigrams of adjacent non-terminals in the tree, and so on.

The two-stage architecture has a weakness: the accuracy rate of the complete architecture can never be better than the accuracy rate of the best parse in the first-stage N-best list. This is because the reranking approach is merely choosing one of the N best parses; even if we picked the very best parse in the list, we can't get 100% accuracy if the correct parse isn't in the list! Therefore it is important to consider the ceiling oracle accuracy (often measured in F-measure) of the N-best list. The oracle accuracy (F-measure) of a particular N-best list is the accuracy (F-measure) we get if we chose the parse that had the highest accuracy. We call this an oracle accuracy because it relies on perfect knowledge (as if from an oracle) of which parse to pick.² Of course it only makes sense to implement discriminative reranking if the N-best F-measure is higher than the 1-best F-measure. Luckily this is often the case; for example the Charniak (2000) parser has an F-measure of 0.897 on section 23 of the Penn Treebank, but the Charniak and Johnson (2005) algorithm for producing the 50-best parses has a much higher oracle F-measure of 0.968.

___ LNG

We said earlier that statistical parsers can take advantage of longer-distance information than N-grams, which suggests that they might do a better job at language modeling/word prediction. It turns out that if we have a very large amount of training data, a 4-gram or 5-gram grammar is nonetheless still the best way to do language modeling. But in situations where there is not enough data for such huge models, parser-based language models are beginning to be developed which have higher accuracy N-gram models.

Two common applications for language modeling are speech recognition and machine translation. The simplest way to use a statistical parser for language modeling for either of these applications is via a two-stage algorithm of the type discussed in the

previous section and in Sec. ??. In the first stage, we run a normal speech recognition decoder, or machine translation decoder, using a normal N-gram grammar. But instead of just producing the single best transcription or translation sentence, we modify the decoder to produce a ranked N-best list of transcriptions/translations sentences, each one together with its probability (or, alternatively, a lattice).

Then in the second stage, we run our statistical parser and assign a parse probability to each sentence in the $ N $-best list or lattice. We then rerank the sentences based on this parse probability and choose the single best sentence. This algorithm can work better than using a simple trigram grammar. For example, on the task of recognizing spoken sentences from the Wall Street Journal using this two-stage architecture, the probabilities assigned by the Charniak (2001) parser improved the word error rate by about 2 percent absolute, over a simple trigram grammar computed on 40 million words (Hall and Johnson, 2003). We can either use the parse probabilities assigned by the parser as-is, or we can linearly combine it with the original $ N $-gram probability.

An alternative to the two-pass architecture, at least for speech recognition, is to modify the parser to run strictly left-to-right, so that it can incrementally give the probability of the next word in the sentence. This would allow the parser to be fit directly into the first-pass decoding pass and obviate the second-pass altogether. While a number of such left-to-right parser-based language modeling algorithms exist (Stolcke, 1995; Jurafsky et al., 1995; Roark, 2001; Xu et al., 2002), it is fair to say that it is still early days for the field of parser-based statistical language models.

14.10 HUMAN PARSING

Are the kinds of probabilistic parsing models we have been discussing also used by humans when they are parsing? This question lies in a field called human sentence processing? Recent studies suggest that there are at least two ways in which humans apply probabilistic parsing algorithms, although there is still disagreement on the details.

One family of studies has shown that when humans read, the predictability of a word seems to influence the reading time; more predictable words are read more quickly. One way of defining predictability is from simple bigram measures. For example, Scott and Shillcock (2003) had participants read sentences while monitoring their gaze with an eye-tracker. They constructed the sentences so that some would have a verb-noun pair with a high bigram probability (such as (14.37a)) and others a verb-noun pair with a low bigram probability (such as (14.37b)).

a) HIGH PROB: One way to avoid confusion is to make the changes during vacation;

b) LOW PROB: One way to avoid discovery is to make the changes during vacation

They found that the higher the bigram predictability of a word, the shorter the time that participants looked at the word (the initial-fixation duration).

While this result only provides evidence for $ N $-gram probabilities, more recent experiments have suggested that the probability of an upcoming word given the syntactic

parse of the preceding sentence prefix also predicts word reading time Hale (2006), Levy (2007).

Interestingly, this effect of probability on reading time has also been shown for morphological structure; the time to recognize a word is influenced by entropy of the word and the entropy of the word's morphological paradigm. Moscoso del Prado, Martin et al. (2004).

The second family of studies has examined how humans disambiguate sentences which have multiple possible parses, suggesting that humans prefer whichever parse is more probable. These studies often rely on a specific class of temporarily ambiguous sentences called garden-path sentences. These sentences, first described by Bever (1970), are sentences which are cleverly constructed to have three properties that combine to make them very difficult for people to parse:

1. They are temporarily ambiguous: The sentence is unambiguous, but its initial portion is ambiguous.

2. One of the two or more parses in the initial portion is somehow preferable to the human parsing mechanism.

3. But the dispreferred parse is the correct one for the sentence.

The result of these three properties is that people are “led down the garden path” toward the incorrect parse, and then are confused when they realize it’s the wrong one. Sometimes this confusion is quite conscious, as in Bever’s example (14.38); in fact this sentence is so hard to parse that readers often need to be shown the correct structure. In the correct structure raced is part of a reduced relative clause modifying The horse, and means “The horse [which was raced past the barn] fell”; this structure is also present in the sentence “Students taught by the Berlitz method do worse when they get to France”.

(14.38) The horse raced past the barn fell.

In Marti Hearst's example (14.39), subjects often misparse the verb houses as a noun (analyzing the complex houses as a noun phrase, rather than a noun phrase and a verb). Other times the confusion caused by a garden-path sentence is so subtle that it can only be measured by a slight increase in reading time. Thus in example (14.40) readers often mis-parse the solution as the direct object of forgot rather than as the subject of an embedded sentence. This mis-parse is subtle, and is only noticeable because experimental participants take longer to read the word was than in control sentences. This "mini-garden-path" effect at the word was suggests that subjects had

chosen the direct object parse and had to re-analyze or rearrange their parse now that they realize they are in a sentential complement.

(14.39) The complex houses married and single students and their families.

The complex houses

The complex houses

(14.40) The student forgot the solution was in the back of the book.

The students forgot the solution was

The students forgot the solution was

While many factors seem to play a role in these preferences for a particular (incorrect) parse, at least one factor seems to be syntactic probabilities, especially lexicalized (subcategorization) probabilities. For example, the probability of the verb forgot taking a direct object ( $ VP \rightarrow VNP $) is higher than the probability of it taking a sentential complement ( $ VP \rightarrow VS $); this difference causes readers to expect a direct object after forget and be surprised (longer reading times) when they encounter a sentential complement. By contrast, a verb which prefers a sentential complement (like hope) didn't cause extra reading time at was.

Similarly, the garden path in (14.39) may be caused by the fact that $ P(\text{houses}|\text{Noun}) > P(\text{houses}|\text{Verb}) $ and $ P(\text{complex}|\text{Adjective}) > P(\text{complex}|\text{Noun}) $, and the garden path in (14.38) at least partially by the low probability of the reduced relative clause construction.

Besides grammatical knowledge, human parsing is affected by many other factors which we will describe later, including resource constraints (such as memory limitations, to be discussed in Ch. 15), thematic structure (such as whether a verb expects semantic agents or patients, to be discussed in Ch. 19) and discourse constraints (Ch. 21).

14.11 SUMMARY

This chapter has sketched the basics of probabilistic parsing, concentrating on probabilistic context-free grammars and probabilistic lexicalized context-free grammars.

• Probabilistic grammars assign a probability to a sentence or string of words, while attempting to capture more sophisticated syntactic information than the N-gram grammars of Ch. 4.

• A probabilistic context-free grammar (PCFG) is a context-free grammar in which every rule is annotated with the probability of choosing that rule. Each PCFG rule is treated as if it were conditionally independent; thus the probability of a sentence is computed by multiplying the probabilities of each rule in the parse of the sentence.

• The probabilistic CKY (Cocke-Kasami-Younger) algorithm is a probabilistic version of the CKY parsing algorithm. There are also probabilistic versions of other parsers like the Earley algorithm.

• PCFG probabilities can be learning by counting in a parsed corpus, or by parsing a corpus. The Inside-Outside algorithm is a way of dealing with the fact that the sentences being parsed are ambiguous.

• Raw PCFGs suffer from poor independence assumptions between rules and lack of sensitivity to lexical dependencies.

• One way to deal with this problem is to split and merge non-terminals (automatically or by hand).

• Probabilistic lexicalized CFGs are another solution to this problem in which the basic PCFG model is augmented with a lexical head for each rule. The probability of a rule can then be conditioned on the lexical head or nearby heads.

Parsers for lexicalized PCFGs (like the Charniak and Collins parsers) are based on extensions to probabilistic CKY parsing.

Parsers are evaluated using three metrics: labeled recall, labeled precision, and cross-brackets.

• There is evidence based on garden-path sentences and other on-line sentence-processing experiments that the human parser uses some kinds of probabilistic information about grammar.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Many of the formal properties of probabilistic context-free grammars were first worked out by Booth (1969) and Salomaa (1969). Baker (1979) proposed the Inside-Outside algorithm for unsupervised training of PCFG probabilities, and used a CKY-style parsing algorithm to compute inside probabilities. Jelinek and Lafferty (1991) extended the CKY algorithm to compute probabilities for prefixes. Stolcke (1995) drew on both of these algorithms in adapting the Earley algorithm to use with PCFGs.

A number of researchers starting in the early 1990s worked on adding lexical dependencies to PCFGs, and on making PCFG rule probabilities more sensitive to surrounding syntactic structure. For example Schabes et al. (1988) and Schabes (1990) presented early work on the use of heads. Many papers on the use of lexical dependencies were first presented at the DARPA Speech and Natural Language Workshop in

June, 1990. A paper by Hindle and Rooth (1990) applied lexical dependencies to the problem of attaching prepositional phrases; in the question session to a later paper Ken Church suggested applying this method to full parsing (Marcus, 1990). Early work on such probabilistic CFG parsing augmented with probabilistic dependency information includes Magerman and Marcus (1991), Black et al. (1992), Bod (1993), and Jelinek et al. (1994), in addition to Collins (1996), Charniak (1997), and Collins (1999) discussed above. Other recent PCFG parsing models include Klein and Manning (2003a) and Petrov et al. (2006).

This early lexical probabilistic work led initially to work focused on solving specific parsing problems like preposition-phrase attachment, using methods including Transformation Based Learning (TBL) (Brill and Resnik, 1994), Maximum Entropy (Ratnaparkhi et al., 1994), Memory-Based Learning (Zavrel and Daelemans, 1997), log-linear models (Franz, 1997), decision trees using semantic distance between heads (computed from WordNet) (Stetina and Nagao, 1997), and Boosting (Abney et al., 1999).

Another direction extended the lexical probabilistic parsing work to build probabilistic formulations of grammar other than PCFGs, such as probabilistic TAG grammar (Resnik, 1992; Schabes, 1992), based on the TAG grammars discussed in Ch. 12, probabilistic LR parsing (Briscoe and Carroll, 1993), and probabilistic link grammar (Lafferty et al., 1992). An approach to probabilistic parsing called supertagging extends the part-of-speech tagging metaphor to parsing by using very complex tags that are in fact fragments of lexicalized parse trees (Bangalore and Joshi, 1999; Joshi and Srinivas, 1994), based on the lexicalized TAG grammars of Schabes et al. (1988). For example the noun purchase would have a different tag as the first noun in a noun compound (where it might be on the left of a small tree dominated by Nominal) than as the second noun (where it might be on the right). Supertagging has also been applied to CCG parsing and HPSG parsing (Clark and Curran, 2004a; Matsuzaki et al., 2007; Blunsom and Baldwin, 2006). Non-supertagging statistical parsers for CCG include Hockenmaier and Steedman (2002).

Goodman (1997), Abney (1997), and Johnson et al. (1999) gave early discussions of probabilistic treatments of feature-based grammars. Other recent work on building statistical models of feature-based grammar formalisms like HPSG and LFG includes Riezler et al. (2002), Kaplan et al. (2004), and Toutanova et al. (2005).

We mentioned earlier that discriminative approaches to parsing fall into the two broad categories of dynamic programming methods and discriminative reranking methods. Recall that discriminative reranking approaches require N-best parses. Parsers based on A* search can easily be modified to generate N-best lists just by continuing the search past the first-best parse (Roark, 2001). Dynamic programming algorithms like the ones described in this chapter can be modified by eliminating the dynamic programming and using heavy pruning (Collins, 2000; Collins and Koo, 2005; Bikel, 2004), or via new algorithms (Jiménez and Marzal, 2000; Gildea and Jurafsky, 2002; Charniak and Johnson, 2005; Huang and Chiang, 2005), some adapted from speech recognition algorithms such as Schwartz and Chow (1990) (see Sec. ??).

By contrast, in dynamic programming methods, instead of outputting and then reranking an N-best list, the parses are represented compactly in a chart, and log-linear and other methods are applied for decoding directly from the chart. Such modern

methods include Johnson (2001), Clark and Curran (2004b), and Taskar et al. (2004). Other reranking developments include changing the optimization criterion (Titov and Henderson, 2006).

Another important recent area of research is dependency parsing; algorithms include Eisner's bilexical algorithm (Eisner, 1996b, 1996a, 2000), maximum spanning tree approaches (using on-line learning) (McDonald et al., 2005b, 2005a), and approaches based on building classifiers for parser actions (Kudo and Matsumoto, 2002; Yamada and Matsumoto, 2003; Nivre et al., 2006; Titov and Henderson, 2007). A distinction is usually made between projective and non-projective dependencies. Non-projective dependencies are those in which the dependency lines cross; this is not very common in English, but is very common in many languages with more free word order. Non-projective dependency algorithms include McDonald et al. (2005a) and Nivre (2007). The Klein-Manning parser combines dependency and constituency information (Klein and Manning, 2003c).

Manning and Schütze (1999) has an extensive coverage of probabilistic parsing. Collins' (1999) dissertation includes a very readable survey of the field and introduction to his parser.

The field of grammar induction is closely related to statistical parsing, and a parser is often used as part of a grammar induction algorithm. One of the earliest statistical works in grammar induction was Horning (1969), who showed that PCFGs could be induced without negative evidence. Early modern probabilistic grammar work showed that simply using EM was insufficient (Lari and Young, 1990; Carroll and Charniak, 1992). Recent probabilistic work such as Yuret (1998), Clark (2001), Klein and Manning (2002), and Klein and Manning (2004), are summarized in Klein (2005) and Adrians and van Zaanen (2004). Work since that summary includes Smith and Eisner (2005), Haghighi and Klein (2006), and Smith and Eisner (2007).

EXERCISES

14.1 Implement the CKY algorithm.

14.2 Modify the algorithm for conversion to CNF from Ch. 13 to correctly handle rule probabilities. Make sure that the resulting CNF assigns the same total probability to each parse tree.

14.3 Recall that Exercise ?? asked you to update the CKY algorithm to handles unit productions directly rather than converting them to CNF. Extend this change to probabilistic CKY.

14.4 Fill out the rest of the probabilistic CKY chart in Fig. 14.4.

14.5 Sketch out how the CKY algorithm would have to be augmented to handle lexicalized probabilities.

14.6 Implement your lexicalized extension of the CKY algorithm.

14.7 Implement the PARSEVAL metrics described in Sec. 14.7. Next either use a treebank or create your own hand-checked parsed testset. Now use your CFG (or other) parser and grammar and parse the testset and compute labeled recall, labeled precision, and cross-brackets.

Abney, S. P. (1997). Stochastic attribute-value grammars. Computational Linguistics, 23(4), 597–618.

Abney, S. P., Schapire, R. E., and Singer, Y. (1999). Boosting applied to tagging and PP attachment. In EMNLP/VLC-99, College Park, MD, pp. 38–45.

Adriaans, P. and van Zaanen, M. (2004). Computational grammar induction for linguists. Grammars; special issue with the theme "Grammar Induction", 7, 57–68.

Baker, J. K. (1979). Trainable grammars for speech recognition. In Klatt, D. H. and Wolf, J. J. (Eds.), Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, pp. 547–550.

Bangalore, S. and Joshi, A. K. (1999). Supertagging: An approach to almost parsing. Computational Linguistics, 25(2), 237–265.

Bever, T. G. (1970). The cognitive basis for linguistic structures. In Hayes, J. R. (Ed.), Cognition and the Development of Language, pp. 279–352. Wiley.

Bikel, D. M. (2004). Intricacies of Collins' parsing model. Computational Linguistics, 30(4), 479–511.

Bikel, D. M., Miller, S., Schwartz, R., and Weischedel, R. (1997). Nymble: a high-performance learning name-finder. In Proceedings of ANLP-97, pp. 194–201.

Black, E., Abney, S. P., Flickinger, D., Gdaniec, C., Grishman, R., Harrison, P., Hindle, D., Inqria, R., Jelinek, F., Klavans, J. L., Liberman, M. Y., Marcus, M. P., Roukos, S., Santorini, B., and Strzalkowski, T. (1991). A procedure for quantitatively comparing the syntactic coverage of English grammars. In Proceedings DARPA Speech and Natural Language Workshop, Pacific Grove, CA, pp. 306–311. Morgan Kaufmann.

Black, E., Jelinek, F., Lafferty, J. D., Magerman, D. M., Mercer, R. L., and Roukos, S. (1992). Towards history-based grammars: Using richer models for probabilistic parsing. In Proceedings DARPA Speech and Natural Language Workshop, Harriman, NY, pp. 134–139. Morgan Kaufmann.

Blunsom, P. and Baldwin, T. (2006). Multilingual deep lexical acquisition for hpsgs via supertagging. In EMNLP 2006.

Bod, R. (1993). Using an annotated corpus as a stochastic grammar. In EACL-93, pp. 37–44.

Booth, T. L. (1969). Probabilistic representation of formal languages. In IEEE Conference Record of the 1969 Tenth Annual Symposium on Switching and Automata Theory, pp. 74–81.

Booth, T. L. and Thompson, R. A. (1973). Applying probability measures to abstract languages. IEEE Transactions on Computers, C-22(5), 442–450.

Brill, E. and Resnik, P. (1994). A rule-based approach to prepositional phrase attachment disambiguation. In COLING-94, Kyoto, pp. 1198–1204.

Briscoe, T. and Carroll, J. (1993). Generalized Probabilistic LR parsing of natural language (corpora) with unification-based grammars. Computational Linguistics, 19(1), 25–59.

Carroll, G. and Charniak, E. (1992). Two experiments on learning probabilistic dependency grammars from corpora. Tech. rep. CS-92-16, Brown University.

Carroll, J., Briscoe, T., and Sanfilippo, A. (1998). Parser evaluation: a survey and a new proposal. In LREC-98, Granada, Spain, pp. 447–454.

Charniak, E. and Johnson, M. (2005). Coarse-to-fine n-best parsing and MaxEnt discriminative reranking. In ACL-05, Ann Arbor.

Charniak, E. (1997). Statistical parsing with a context-free grammar and word statistics. In AAAI-97, Menlo Park, pp. 598–603. AAAI Press.

Charniak, E. (2000). A maximum-entropy-inspired parser. In Proceedings of the 1st Annual Meeting of the North American Chapter of the ACL (NAACL'00), Seattle, Washington, pp. 132–139.

Charniak, E. (2001). Immediate-head parsing for language models. In ACL-01, Toulouse, France.

Chelba, C. and Jelinek, F. (2000). Structured language modeling. Computer Speech and Language, 14, 283–332.

Clark, A. (2001). The unsupervised induction of stochastic context-free grammars using distributional clustering. In CoNLL-01.

Clark, S. and Curran, J. R. (2004a). The importance of supporting for wide-coverage CCG parsing. In COLING-04, pp. 282–288.

Clark, S. and Curran, J. R. (2004b). Parsing the WSJ using CCG and Log-Linear Models. In ACL-04, pp. 104–111.

Collins, M. and Koo, T. (2005). Discriminative reranking for natural language parsing. Computational Linguistics, 31(1), 25–69.

Collins, M. (1996). A new statistical parser based on bigram lexical dependencies. In ACL-96, Santa Cruz, California, pp. 184–191.

Collins, M. (1999). Head-driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia.

Collins, M. (2000). Discriminative reranking for natural language parsing. In ICML 2000, Stanford, CA, pp. 175–182.

Collins, M. (2003). Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4), 589–637.

Collins, M., Hajič, J., Ramshaw, L. A., and Tillmann, C. (1999). A statistical parser for Czech. In ACL-99, College Park, MA, pp. 505–512.

Eisner, J. (1996a). An empirical comparison of probability models for dependency grammar. Tech. rep. IRCS-96-11, Institute for Research in Cognitive Science, Univ. of Pennsylvania.

Eisner, J. (1996b). Three new probabilistic models for dependency parsing: An exploration. In COLING-96, Copenhagen, pp. 340–345.

Eisner, J. (2000). Bilexical grammars and their cubic-time parsing algorithms. In Bunt, H. and Nijholt, A. (Eds.), Advances in Probabilistic and Other Parsing Technologies, pp. 29–62. Kluwer.

Francis, H. S., Gregory, M. L., and Michaelis, L. A. (1999). Are lexical subjects deviant?. In CLS-99. University of Chicago.

Franz, A. (1997). Independence assumptions considered harmful. In ACL/EACL-97, Madrid, Spain, pp. 182–189.

Gildea, D. and Jurafsky, D. (2002). Automatic labeling of semantic roles. Computational Linguistics, 28(3), 245–288.

Givón, T. (1990). Syntax: A functional typological introduction. John Benjamins, Amsterdam.

Goodman, J. (1997). Probabilistic feature grammars. In Proceedings of the International Workshop on Parsing Technology.

Haghighi, A. and Klein, D. (2006). Prototype-driven grammar induction. In COLING/ACL 2006, pp. 881–888.

Hale, J. (2006). Uncertainty about the rest of the sentence. Cognitive Science, 30(4), 609–642.

Hall, K. and Johnson, M. (2003). Language modeling using efficient best-first bottom-up parsing. In IEEE ASRU-03, pp. 507–512.

Hindle, D. and Rooth, M. (1990). Structural ambiguity and lexical relations. In Proceedings DARPA Speech and Natural Language Workshop, Hidden Valley, PA, pp. 257–262. Morgan Kaufmann.

Hindle, D. and Rooth, M. (1991). Structural ambiguity and lexical relations. In Proceedings of the 29th ACL, Berkeley, CA, pp. 229–236.

Hockenmaier, J. and Steedman, M. (2002). Generative models for statistical parsing with Combinatory Categorical Grammar. In ACL-02, Philadelphia, PA.

Horning, J. J. (1969). A study of grammatical inference. Ph.D. thesis, Stanford University.

Huang, L. and Chiang, D. (2005). Better k-best parsing. In IWPT-05, pp. 53–64.

Jelinek, F. and Lafferty, J. D. (1991). Computation of the probability of initial substring generation by stochastic context-free grammars. Computational Linguistics, 17(3), 315–323.

Jelinek, F., Lafferty, J. D., Magerman, D. M., Mercer, R. L., Ratnaparkhi, A., and Roukos, S. (1994). Decision tree parsing using a hidden derivation model. In ARPA Human Language Technologies Workshop, Plainsboro, N.J., pp. 272–277. Morgan Kaufmann.

Jiménez, V. M. and Marzal, A. (2000). Computation of the n best parse trees for weighted and stochastic context-free grammars. In Advances in Pattern Recognition: Proceedings of the Joint IAPR International Workshops, SSPR 2000 and SPR 2000, Alicante, Spain, pp. 183–192. Springer.

Johnson, M. (1998). PCFG models of linguistic tree representations. Computational Linguistics, 24(4), 613–632.

Johnson, M. (2001). Joint and conditional estimation of tagging and parsing models. In ACL-01, pp. 314–321.

Johnson, M., Geman, S., Canon, S., Chi, Z., and Riezler, S. (1999). Estimators for stochastic “unification-based” grammars. In ACL-99, pp. 535–541.

Joshi, A. K. and Srinivas, B. (1994). Disambiguation of super parts of speech (or supertags): Almost parsing. In COLING-94, Kyoto, pp. 154–160.

Jurafsky, D., Wooters, C., Tajchman, G., Segal, J., Stolcke, A., Fosler, E., and Morgan, N. (1995). Using a stochastic context-free grammar as a language model for speech recognition. In IEEE ICASSP-95, pp. 189–192. IEEE.

Kaplan, R. M., Riezler, S., King, T. H., Maxwell, J. T., Vasserman, A., and Crouch, R. (2004). Speed and accuracy in shallow and deep stochastic parsing. In HLT-NAACL-04.

Klein, D. (2005). The unsupervised learning of Natural Language Structure. Ph.D. thesis, Stanford University.

Klein, D. and Manning, C. D. (2001). Parsing and hypergraphs. In The Seventh International Workshop on Parsing Technologies.

Klein, D. and Manning, C. D. (2002). A generative constituent-context model for improved grammar induction. In ACL-02.

Klein, D. and Manning, C. D. (2003a). A* parsing: Fast exact Viterbi parse selection. In HLT-NAACL-03.

Klein, D. and Manning, C. D. (2003b). Accurate unlexicalized parsing. In HLT-NAACL-03.

Klein, D. and Manning, C. D. (2003c). Fast exact inference with a factored model for natural language parsing. In Becker, S., Thrun, S., and Obermayer, K. (Eds.), Advances in Neural Information Processing Systems 15. MIT Press.

Klein, D. and Manning, C. D. (2004). Corpus-based induction of syntactic structure: Models of dependency and constituency. In ACL-04.

Kudo, T. and Matsumoto, Y. (2002). Japanese dependency analysis using cascaded chunking. In CoNLL-02, pp. 63–69.

Lafferty, J. D., Sleator, D., and Temperley, D. (1992). Grammatical trigrams: A probabilistic model of link grammar. In Proceedings of the 1992 AAAI Fall Symposium on Probabilistic Approaches to Natural Language.

Lari, K. and Young, S. J. (1990). The estimation of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech and Language, 4, 35–56.

Levy, R. (2007). Expectation-based syntactic comprehension. Cognition. In press.

Lin, D. (1995). A dependency-based method for evaluating broad-coverage parsers. In IJCAI-95, Montreal, pp. 1420–1425.

Magerman, D. M. and Marcus, M. P. (1991). Pearl: A probabilistic chart parser. In Proceedings of the 6th Conference of the European Chapter of the Association for Computational Linguistics, Berlin, Germany.

Manning, C. D. and Schütze, H. (1999). Foundations of Statistical Natural Language Processing. MIT Press.

Marcus, M. P. (1990). Summary of session 9: Automatic acquisition of linguistic structure. In Proceedings DARPA Speech and Natural Language Workshop, Hidden Valley, PA, pp. 249–250. Morgan Kaufmann.

Marcus, M. P., Santorini, B., and Marcinkiewicz, M. A. (1993). Building a large annotated corpus of English: The Penn treebank. Computational Linguistics, 19(2), 313–330.

Matsuzaki, T., Miyao, Y., and ichi Tsujii, J. (2007). Efficient hpsg parsing with supertagging and cfg-filtering. In IJCAI-07.

McDonald, R., Pereira, F. C. N., Ribarov, K., and Hajič, J. (2005a). Non-projective dependency parsing using spanning tree algorithms. In HLT-EMNLP-05.

McDonald, R., Crammer, K., and Pereira, F. C. N. (2005b). Online large-margin training of dependency parsers. In ACL-05, Ann Arbor, pp. 91–98.

Moscoso del Prado Martín, F., Kostic, A., and Baayen, R. H. (2004). Putting the bits together: An information theoretical perspective on morphological processing. Cognition, 94(1), 1–18.

Ney, H. (1991). Dynamic programming parsing for context-free grammars in continuous speech recognition. IEEE Transactions on Signal Processing, 39(2), 336–340.

Nivre, J. (2007). Incremental non-projective dependency parsing. In NAACL-HLT 07.

Nivre, J., Hall, J., and Nilsson, J. (2006). Malparser: A data-driven parser-generator for dependency parsing. In LREC-06, pp. 2216–2219.

Petrov, S., Barrett, L., Thibaux, R., and Klein, D. (2006). Learning accurate, compact, and interpretable tree annotation. In COLING/ACL 2006, Sydney, Australia, pp. 433–440. ACL.

Ratnaparkhi, A. (1996). A maximum entropy part-of-speech tagger. In EMNLP 1996, Philadelphia, PA, pp. 133–142.

Ratnaparkhi, A., Reynar, J. C., and Roukos, S. (1994). A Maximum Entropy model for prepositional phrase attachment. In ARPA Human Language Technologies Workshop, Plainsboro, N.J., pp. 250–255.

Resnik, P. (1992). Probabilistic tree-adjoining grammar as a framework for statistical natural language processing. In Proceedings of the 14th International Conference on Computational Linguistics, Nantes, France, pp. 418–424.

Riezler, S., King, T. H., Kaplan, R. M., Crouch, R., III, J. T. M., and Johnson, M. (2002). Parsing the wall street journal using a lexical-functional grammar and discriminative estimation techniques. In ACL-02, Philadelphia, PA.

Roark, B. (2001). Probabilistic top-down parsing and language modeling. Computational Linguistics, 27(2), 249–276.

Salomaa, A. (1969). Probabilistic and weighted grammars. Information and Control, 15, 529–544.

Schabes, Y. (1990). Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA†.

Schabes, Y. (1992). Stochastic lexicalized tree-adjoining grammars. In Proceedings of the 14th International Conference on Computational Linguistics, Nantes, France, pp. 426–433.

Schabes, Y., Abeillé, A., and Joshi, A. K. (1988). Parsing strategies with 'lexicalized' grammars: Applications to Tree Adjoining Grammars. In COLING-88, Budapest, pp. 578–583.

Schwartz, R. and Chow, Y.-L. (1990). The N-best algorithm: An efficient and exact procedure for finding the N most likely sentence hypotheses. In IEEE ICASSP-90, Vol. 1, pp. 81–84. IEEE.

Scott, M. and Shillcock, R. (2003). Eye movements reveal the on-line computation of lexical probabilities during reading. Psychological Science, 14(6), 648–652.

Sekine, S. and Collins, M. (1997). The evalb software. http://cs.nyu.edu/cs/projects/proteus/evalb.

Smith, D. A. and Eisner, J. (2007). Bootstrapping feature-rich dependency parsers with entropic priors. In EMNLP/CoNLL 2007, Prague, pp. 667–677.

Smith, N. A. and Eisner, J. (2005). Guiding unsupervised grammar induction using contrastive estimation. In IJCAI Workshop on Grammatical Inference Applications, Edinburgh, pp. 73–82.

Stetina, J. and Nagao, M. (1997). Corpus based PP attachment ambiguity resolution with a semantic dictionary. In Zhou, J. and Church, K. W. (Eds.), Proceedings of the Fifth Workshop on Very Large Corpora, Beijing, China, pp. 66–80.

Stolcke, A. (1995). An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2), 165–202.

Taskar, B., Klein, D., Collins, M., Koller, D., and Manning, C. D. (2004). Max-margin parsing. In EMNLP 2004.

Titov, I. and Henderson, J. (2006). Loss minimization in parseranking. In EMNLP 2006.

Titov, I. and Henderson, J. (2007). A latent variable model for generative dependency parsing. In IWPT-07.

Toutanova, K., Manning, C. D., Flickinger, D., and Oepen, S. (2005). Stochastic HPSG Parse Disambiguation using the Redwoods Corpus. Research on Language & Computation, 3(1), 83–105.

van Rijsbergen, C. J. (1975). Information Retrieval. Butterworths, London.

Witten, I. H. and Bell, T. C. (1991). The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory, 37(4), 1085–1094.

Xu, P., Chelba, C., and Jelinek, F. (2002). A study on richer syntactic dependencies for structured language modeling. In ACL-02, pp. 191–198.

Yamada, H. and Matsumoto, Y. (2003). Statistical dependency analysis with support vector machines. In Noord, G. V. (Ed.), IWPT-03, pp. 195–206.

Yuret, D. (1998). Discovery of Linguistic Relations Using Lexical Attraction. Ph.D. thesis, MIT.

Zavrel, J. and Daelemans, W. (1997). Memory-based learning: Using similarity for smoothing. In ACL/EACL-97, Madrid, Spain, pp. 436–443.

15 LANGUAGE AND COMPLEXITY

This is the dog, that worried the cat, that killed the rat, that ate the malt, that lay in the house that Jack built.

Mother Goose, The House that Jack Built

This is the malt that the rat that the cat that the dog worried killed ate.

Victor H. Yngve (1960)

Much of the humor in musical comedy and comic operetta comes from entwining the main characters in fabulously complicated plot twists. Casilda, the daughter of the Duke of Plaza-Toro in Gilbert and Sullivan's The Gondoliers, is in love with her father's attendant Luiz. Unfortunately, Casilda discovers she has already been married (by proxy) as a babe of six months to “the infant son and heir of His Majesty the immeasurably wealthy King of Barataria”. It is revealed that this infant son was spirited away by the Grand Inquisitor and raised by a “highly respectable gondolier” in Venice as a gondolier. The gondolier had a baby of the same age and could never remember which child was which, and so Casilda was in the unenviable position, as she puts it, of “being married to one of two gondoliers, but it is impossible to say which”. By way of consolation, the Grand Inquisitor informs her that “such complications frequently occur”.

Luckily, such complications don't frequently occur in natural language. Or do they? In fact there are sentences that are so complex that they are hard to understand, such as Yngve's sentence above, or the sentence:

“The Republicans who the senator who she voted for chastised were trying to cut all benefits for veterans”.

Studying such sentences, and more generally understanding what level of complexity tends to occur in natural language, is an important area of language processing. Complexity plays an important role, for example, in deciding when we need to use a particular formal mechanism. Formal mechanisms like finite automata, Markov models, transducers, phonological rewrite rules, and context-free grammars, can be described

in terms of their power, or equivalently in terms of the complexity of the phenomena that they can describe. This chapter introduces the Chomsky hierarchy, a theoretical tool that allows us to compare the expressive power or complexity of these different formal mechanisms. With this tool in hand, we summarize arguments about the correct formal power of the syntax of natural languages, in particular English but also including a famous Swiss dialect of German that has the interesting syntactic property called cross-serial dependencies. This property has been used to argue that context-free grammars are insufficiently powerful to model the morphology and syntax of natural language.

In addition to using complexity as a metric for understanding the relation between natural language and formal models, the field of complexity is also concerned with what makes individual constructions or sentences hard to understand. For example we saw above that certain nested or center-embedded sentences are difficult for people to process. Understanding what makes some sentences difficult for people to process is an important part of understanding human parsing.

15.1 THE CHOMSKY HIERARCHY

How are automata, context-free grammars, and phonological rewrite rules related? What they have in common is that each describes a formal language, which we have seen is a set of strings over a finite alphabet. But the kind of grammars we can write with each of these formalism are of different generative power. One grammar is of greater generative power or complexity than another if it can define a language that the other cannot define. We will show, for example, that a context-free grammar can be used to describe formal languages that cannot be described with a finite-state automaton.

It is possible to construct a hierarchy of grammars, where the set of languages describable by grammars of greater power subsumes the set of languages describable by grammars of lesser power. There are many possible such hierarchies; the one that is most commonly used in computational linguistics is the Chomsky hierarchy (Chomsky, 1959), which includes four kinds of grammars: Fig. 15.1 shows the four grammars in the Chomsky hierarchy as well as a useful fifth type, the mildly context-sensitive languages.

This decrease in the generative power of languages from the most powerful to the weakest can in general be accomplished by placing constraints on the way the grammar rules are allowed to be written. Fig. 15.2 shows the five types of grammars in the extended Chomsky hierarchy, defined by the constraints on the form that rules must take. In these examples, A is a single non-terminal, and $ \alpha $, $ \beta $, and $ \gamma $ are arbitrary strings of terminal and non-terminal symbols. They may be empty unless this is specifically disallowed below. x is an arbitrary string of terminal symbols.

Turing-equivalent, Type 0 or unrestricted grammars have no restrictions on the form of their rules, except that the left-hand side cannot be the empty string $ \epsilon $. Any (non-null) string can be written as any other string (or as $ \epsilon $). Type 0 grammars characterize the recursively enumerable languages, that is, those whose strings can be listed

| Type | Common Name | Rule Skeleton | Linguistic Example |

| --- | --- | --- | --- |

| 0 | Turing Equivalent | $ \alpha \rightarrow \beta $, s.t. $ \alpha \neq \epsilon $ | HPSG, LFG, Minimalism |

| 1 | Context Sensitive | $ \alpha A\beta \rightarrow \alpha \gamma \beta $, s.t. $ \gamma \neq \epsilon $ | |

| - | Mildly Context Sensitive | | TAG, CCG |

| 2 | Context Free | $ A \rightarrow \gamma $ | Phrase Structure Grammars |

| 3 | Regular | $ A \rightarrow xB $ or $ A \rightarrow x $ | Finite State Automata |

(enumerated) by a Turing Machine.

Context-sensitive grammars have rules that rewrite a non-terminal symbol A in the context $ \alpha A\beta $ as any non-empty string of symbols. They can be either written in the form $ \alpha A\beta \to \alpha\gamma\beta $ or in the form $ A \to \gamma/\alpha \not\models \beta $. We have seen this latter version in the Chomsky-Halle representation of phonological rules (Chomsky and Halle, 1968) like this flapping rule:

$$ \mathrm{/t/}\to[\mathrm{dx}]/\mathrm{\check{V}}\mathrm{\_\_\mathrm{V}} $$

While the form of these rules seems context-sensitive, Ch. 7 showed that phonological rule systems that do not have recursion are actually equivalent in power to the regular grammars.

Another way of conceptualizing a rule in a context-sensitive grammar is as rewriting a string of symbols $ \delta $ as another string of symbols $ \phi $ in a “non-decreasing” way; such that $ \phi $ has at least as many symbols as $ \delta $.

We studied \textbf{context-free} grammars in Ch. 12. Context-free rules allow any single non-terminal to be rewritten as any string of terminals and non-terminals. A non-terminal may also be rewritten as $ \epsilon $, although we didn't make use of this option in

Ch. 12.

Regular grammars are equivalent to regular expressions. That is, a given regular language can be characterized either by a regular expression of the type we discussed in Chapter 2, or by a regular grammar. Regular grammars can either be right-linear or left-linear. A rule in a right-linear grammar has a single non-terminal on the left, and at most one non-terminal on the right-hand side. If there is a non-terminal on the right-hand side, it must be the last symbol in the string. The right-hand-side of left-linear grammars is reversed (the right-hand-side must start with (at most) a single non-terminal). All regular languages have both a left-linear and a right-linear grammar. For the rest of our discussion, we will consider only the right-linear grammars.

For example, consider the following regular (right-linear) grammar:

$$ S \rightarrow a A $$

$$ S\ \to\ bB $$

$$ A\ \to\ aS $$

$$ B\ \to\ b b S $$

$$ S\to\epsilon $$

It is regular, since the left-hand-side of each rule is a single non-terminal and each right-hand side has at most one (rightmost) non-terminal. Here is a sample derivation in the language:

$$ \begin{aligned}S\Rightarrow aA\Rightarrow aaS\Rightarrow aabbB\Rightarrow aabbbS\Rightarrow aabbbaA\\\Rightarrow aabbbaaS\Rightarrow aabbbaa\end{aligned} $$

We can see that each time S expands, it produces either aaS or bbbS; thus the reader should convince themselves that this language corresponds to the regular expression $ (aa \cup bbb)^* $.

We will not present the proof that a language is regular if and only if it is generated by a regular grammar; it was first proved by Chomsky and Miller (1958) and can be found in textbooks like Hopcroft and Ullman (1979) and Lewis and Papadimitriou (1988). The intuition is that since the non-terminals are always at the right or left edge of a rule, they can be processed iteratively rather than recursively.

The fifth class of languages and grammars that is useful to consider is the mildly context-sensitive grammars and the mildly context-sensitive languages. Mildly context-sensitive languages are a proper subset of the context-sensitive languages, and a proper superset of the context-free languages. The rules for mildly context-sensitive languages can be described in a number of ways; indeed it turns out that various grammar formalisms, including Tree-Adjoining Grammars (Joshi, 1985), Head Grammars Pollard (1984), Combinatory Categorical Grammars (CCG), (Steedman, 1996, 2000) and also a specific version of Minimalist Grammars (Stabler, 1997), are all weakly equivalent (Joshi et al., 1991).

15.2 HOW TO TELL IF A LANGUAGE ISN'T REGULAR

How do we know which type of rules to use for a given problem? Could we use regular expressions to write a grammar for English? Or do we need to use context-free rules or even context-sensitive rules? It turns out that for formal languages there are methods for deciding this. That is, we can say for a given formal language whether it is representable by a regular expression, or whether it instead requires a context-free grammar, and so on.

So if we want to know if some part of natural language (the phonology of English, let's say, or perhaps the morphology of Turkish) is representable by a certain class of grammars, we need to find a formal language that models the relevant phenomena and figure out which class of grammars is appropriate for this formal language.

Why should we care whether (say) the syntax of English is representable by a regular language? One main reason is that we'd like to know which type of rule to use in writing computational grammars for English. If English is regular, we would write regular expressions, and use efficient automata to process the rules. If English is context-free, we would write context-free rules and use the CKY algorithm to parse sentences, and so on.

Another reason to care is that it tells us something about the formal properties of different aspects of natural language; it would be nice to know where a language "keeps" its complexity; whether the phonological system of a language is simpler than the syntactic system, or whether a certain kind of morphological system is inherently simpler than another kind. It would be a strong and exciting claim, for example, if we could show that the phonology of English was capturable by a finite-state machine rather than the context-sensitive rules that are traditionally used; it would mean that English phonology has quite simple formal properties. Indeed, this fact was shown by Johnson (1972), and helped lead to the modern work in finite-state methods shown in Chapters 3 and 4.