11.5.3 Learning in Optimality Theory

Let's conclude with a brief sketch of work which addresses the learning problem in Optimality Theory. Most work on OT learning has assumed that the constraints are already given, and the task is to learn the ranking. Two algorithms for learning rankings have been worked out in some detail; the constraint demotion algorithm of Tesar and Smolensky (2000) and the Gradual Learning Algorithm of Boersma and Hayes (2001).

The Constraint Demotion algorithm makes two assumptions: that we know all the possible OT constraints of the language, and that each surface form is annotated with its complete parse and underlying form. The intuition of the algorithm is that each of these surface observations gives us implicit evidence about the constraint ranking.

Given the underlying form, we can use the GEN algorithm to implicitly form the set of competitors. Now we can construct a set of pairs consisting of the correct observed grammatical form and each competitor. The learner must find a constraint ranking that prefers the observed learning winner over each (non-observed) competitor loser.

Because the set of constraints is given, we can use the standard OT parsing architecture to determine for each winner or loser exactly which constraints they violate.

For example, consider the learning algorithm that has observed Candidate 1, but whose current constraint ranking prefers Candidate 2, as follows (this example and the following tables are modified from Boersma and Hayes (2001)):

| /underlying form/ | $ C_{{1}} $ | $ C_{{2}} $ | $ C_{{3}} $ | $ C_{{4}} $ | $ C_{{5}} $ | $ C_{{6}} $ | $ C_{{7}} $ | $ C_{{8}} $ |

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

| Candidate 1 (learning observation) | $ ^{{*}}! $ | $ ^{{**}} $ | $ ^{{*}} $ | | $ ^{{*}} $ | | | $ ^{{*}} $ |

| Candidate 2 (learner's output) | | $ ^{{*}} $ | $ ^{{*}} $ | $ ^{{*}} $ | | $ ^{{*}} $ | | $ ^{{*}} $ |

| /underlying form/ | $ C_{1} $ | $ C_{2} $ | $ C_{3} $ | $ C_{4} $ | $ C_{5} $ | $ C_{6} $ | $ C_{7} $ | $ C_{8} $ |

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

| Candidate 1 (learning observation) | *! | ** | * | | * | | | * |

| Candidate 2 (learner's output) | | * | * | * | | * | | * |

| /underlying form/ | $ C_{{3}} $ | $ C_{{4}} $ | $ C_{{5}} $ | $ C_{{6}} $ | $ C_{{7}} $ | $ C_{{8}} $ | $ C_{{1}} $ | $ C_{{2}} $ |

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

| Candidate 1 (learning observation) | | | | * | | | * | * |

| Candidate 2 (learner's output) | | *! | | * | | | | |

The Gradual Learning Algorithm (GLA) of (Boersma and Hayes, 2001) is a generalization of Constraint Demotion that learns constraint rankings in Stochastic Optimality Theory. Since OT is a special case of Stochastic OT, the algorithm also implicitly learns OT rankings. It generalizes Constraint Demotion by being able to learn from cases of free variation. Recall from Sec. 11.3 that in Stochastic OT each constraint is associated with a ranking value on a continuous scale. The ranking value is defined as the mean of the Gaussian distribution that constitutes the constraint. The goal of the GLA is to assign a ranking value for each constraint. The algorithm is a simple extension to the Constraint Demotion algorithm, and follows exactly the same steps until the final step. Inside of the demoding constraints to a lower strata, the ranking value of each constraint violated by the learning observation (Candidate 1) is decreased slightly, and the ranking value of each constraint violated by the learner's output (Candidate 2) is increased slightly, as shown below:

| /underlying form/ | $ C_{{1}} $ | $ C_{{2}} $ | $ C_{{3}} $ | $ C_{{4}} $ | $ C_{{5}} $ | $ C_{{6}} $ | $ C_{{7}} $ | $ C_{{8}} $ |

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

| Candidate 1 (learning observation) | *! $ \rightarrow $ | * $ \rightarrow $ | | | * $ \rightarrow $ | | | |

| Candidate 2 (learner's output) | | | | ← * | | ← * | | |

11.6 SUMMARY

This chapter has introduced many of the important concepts of phonetics and computational phonology.

• Transducers can be used to model phonological rules just as they were used in Ch. 3 to model spelling rules. Two-level morphology is a theory of morphology/phonology which models phonological rules as finite-state well-formedness constraints on the mapping between lexical and surface form.

• Optimality theory is a theory of phonological well-formedness; there are computational implementations, and relationships to transducers.

• Computational models exist for syllabification, inserting syllable boundaries in phone strings.

There are numerous algorithms for learning phonological and morphological rules, both supervised and unsupervised.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Computational phonology is a fairly recent field. The idea that phonological rules could be modeled as regular relations dates to Johnson (1972), who showed that any phonological system that didn't allow rules to apply to their own output (i.e., systems that did not have recursive rules) could be modeled with regular relations (or finite-state transducers). Virtually all phonological rules that had been formulated at the time had this property (except some rules with integral-valued features, like early stress and tone rules). Johnson's insight unfortunately did not attract the attention of the community, and was independently discovered by Ronald Kaplan and Martin Kay; see Ch. 3 for the rest of the history of two-level morphology. Karttunen (1993) gives a tutorial introduction to two-level morphology that includes more of the advanced details than we were able to present here, and the definitive text on finite-state morphology is Beesley and Karttunen (2003). Other FSA models of phonology include Bird and Ellison (1994).

Earlier computational finite-state models that deal with templatic morphology in languages like Arabic include Kataja and Koskenniemi (1988), Kornai (1991), Bird and Ellison (1994), and Beesley (1996). Extensions of the Kay (1987) model include Kiraz (1997, 2000, 2001). Recent models based on extensions to the finite-state calculus include Beesley and Karttunen (2000).

Optimality theory was developed by Prince and Smolensky and circulated as a technical report (Prince and Smolensky, 1993) until its publication more than a decade later (Prince and Smolensky, 2004). A selection from the extensive finite-state literature in OT includes Eisner (1997, 2000, 2002), Gerdemann and van Noord (2000), and Riggle (2005).

Recent work on phonological learning has focused on some new areas. One is learning phonotactic constraints on the allowable word-internal sequences in the language, including probabilistic (Coleman and Pierrehumbert, 1997; Frisch et al., 2000;

Bailey and Hann, 2001; Hayes and Wilson, 2007; Aibright, 2007) as well as non-probabilistic phonotactic constraints (Hayes, 2004; Prince and Tesar, 2004; Tesar and Prince, 2007). A related task is the learning of underlying forms and phonological alternations given the observed surface forms and the set of constraints. Many of the unsupervised algorithms for learning underlying forms are based on a constraint satisfaction approach, in which sets of possible underlying forms are proposed by examining alternating surface forms, and then iteratively ruling out possible underlying forms (Tesar and Prince, 2007; Alderete et al., 2005; Tesar, 2006a, 2006b). The recent unsupervised Maximum Likelihood Learning of Lexicons and Grammars (MLG) model of Jarosz (2006, 2008) learns underlying forms and constraint rankings given surface forms in a probabilistic version of OT using the Expectation-Maximization (EM) algorithm described in Ch. 6.

Indeed, in addition to this probabilistic model of Jarosz (2008), as well as the Stochastic OT described earlier in the chapter, much recent work in computational phonology has focused on models with weighted constraints, including Harmonic Grammar and Maximum Entropy Models. For example, Harmonic Grammar is an extension to Optimality Theory (indeed, in the theory that Optimality Theory originally grew out of) in which optimality for a form is defined as maximal harmony. Harmony is defined by the sum of weighted constraints (Smolensky and Legendre, 2006). In using sums of weight rather than OT-style rankings, Harmony Theory resembles the log-linear models of Ch. 6. Recent computational work includes the application to OT of Maximum Entropy Models (Goldwater and Johnson, 2003) and the Harmonic Grammar related models of Pater et al. (2007) and Pater (2007).

Word segmentation is one of the earliest problems in computational linguistics, and models date back to Harris (1954). Among the many modern models are Bayesian ones like Brent (1999) and Goldwater et al. (2006). The word segmentation problem is important also in computational developmental psycholinguistics; for representative recent work see Christiansen et al. (1998), Kuhl et al. (2003), Thiessen and Saffran (2004) and Thiessen et al. (2005). Recent work on morphology induction includes Baroni et al. (2002), Clark (2002), and Albright and Hayes (2003).

Readers with further interest in phonology should consult phonology textbooks like Odden (2005) and Kager (2000).

EXERCISES

11.1 Build an automaton for rule (11.3).

11.2 One difference between one dialect of Canadian English and most dialects of American English is called Canadian raising. Bromberger and Halle (1989) note that some Canadian dialects of English raise /aɪ/ to [ʌi] and /aʊ/ to [ʌu] in stressed position

before a voiceless consonant. A simplified version of the rule dealing only with /aɪ/ can be stated as:

$$ \left/a\mathrm{I}/\rightarrow\left[\mathrm{AI}\right]/\text{——}\left[\begin{matrix}C\\ -voice\end{matrix}\right]\right. $$

This rule has an interesting interaction with the flapping rule. In some Canadian dialects the word rider and writer are pronounced differently: rider is pronounced [raɪər] while writer is pronounced [rʌɪər]. Write a two-level rule and an automaton for both the raising rule and the flapping rule which correctly models this distinction. You may make simplifying assumptions as needed.

11.3 Write the lexical entry for the pronunciation of the English past tense (preterite) suffix -d, and the two level-rules that express the difference in its pronunciation depending on the previous context. Don't worry about the spelling rules. (Hint: make sure you correctly handle the pronunciation of the past tenses of the words add, pat, bake, and bag.)

11.4 Write two-level rules for the Yawelmani Yokuts phenomena of Harmony, Shortening, and Lowering introduced on page 5. Make sure your rules are capable of running in parallel.

Albright, A. (2007). How many grammars am I holding up? Discovering phonological differences between word classes. In WCCFL 26, pp. 34–42.

Albright, A. and Hayes, B. (2003). Rules vs. analogy in english past tenses: A computational/experimental study. Cognition, 90, 119–161.

Alderete, J., Brasoveanu, A., Merchant, N., Prince, A., and Tesar, B. (2005). Contrast analysis aids in the learning of phonological underlying forms. In WCCFL 24, pp. 34–42.

Antworth, E. L. (1990). PC-KIMMO: A Two-level Processor for Morphological Analysis. Summer Institute of Linguistics, Dallas, TX.

Archangeli, D. (1984). Underspecification in Yawelmani Phonology and Morphology. Ph.D. thesis, MIT.

Archangeli, D. (1997). Optimality theory: An introduction to linguistics in the 1990s. In Archangeli, D. and Langendoen, D. T. (Eds.), Optimality Theory: An Overview. Blackwell, Oxford.

Bailey, T. and Hahn, U. (2001). Perception of wordlikeness: Effects of segment probability and length on the processing of nonwords. Journal of Memory and Language, 44, 568–591.

Baroni, M., Matiasek, J., and Trost, H. (2002). Unsupervised discovery of morphologically related words based on orthographic and semantic similarity. In Proceedings of ACL SIG-PHON, Philadelphia, PA.

Beesley, K. R. (1996). Arabic finite-state morphological analysis and generation. In COLING-96, Copenhagen, pp. 89–94.

Beesley, K. R. and Karttunen, L. (2000). Finite-state non-concatenative morphotactics. In Proceedings of ACL SIG-PHON, Luxembourg, pp. 50–59.

Beesley, K. R. and Karttunen, L. (2003). Finite-State Morphology. CSLI Publications, Stanford University.

Bird, S. and Ellison, T. M. (1994). One-level phonology: Autosegmental representations and rules as finite automata. Computational Linguistics, 20(1).

Blevins, J. (1995). The handbook of phonological theory. In Goldsmith, J. (Ed.), The syllable in phonological theory. Blackwell, Oxford.

Boersma, P. and Hayes, B. (2001). Empirical tests of the gradual learning algorithm. Linguistic Inquiry, 32, 45–86.

Brent, M. R. (1999). An efficient, probabilistically sound algorithm for segmentation and word discovery. Machine Learning, 34(1–3), 71–105.

Bromberger, S. and Halle, M. (1989). Why phonology is different. Linguistic Inquiry, 20, 51–70.

Chomsky, N. and Halle, M. (1968). The Sound Pattern of English. Harper and Row.

Christiansen, M. H., Allen, J., and Seidenberg, M. S. (1998). Learning to segment speech using multiple cues: A connectionist model. Language and Cognitive Processes, 13(2), 221–268.

Church, K. W. (1983). Phrase-Structure Parsing: A Method for Taking Advantage of Allophonic Constraints. Ph.D. thesis, MIT.

Clark, A. (2002). Memory-based learning of morphology with stochastic transducers. In ACL-02, Philadelphia, PA, pp. 513–520.

Cole, J. S. and Kisseberth, C. W. (1995). Restricting multi-level constraint evaluation. Rutgers Optimality Archive ROA-98.

Coleman, J. and Pierrehumbert, J. B. (1997). Stochastic phonological grammars and acceptability. In Proceedings of ACL SIGPHON.

de Marcken, C. (1996). Unsupervised Language Acquisition. Ph.D. thesis, MIT.

Eisner, J. (1997). Efficient generation in primitive optimality theory. In ACL/EACL-97, Madrid, Spain, pp. 313–320.

Eisner, J. (2000). Directional constraint evaluation in Optimality Theory. In COLING-00, Saarbrücken, Germany, pp. 257–263.

Eisner, J. (2002). Comprehension and compilation in Optimality Theory. In ACL-02, Philadelphia, pp. 56–63.

Ellison, T. M. (1992). The Machine Learning of Phonological Structure. Ph.D. thesis, University of Western Australia.

Ellison, T. M. (1994). Phonological derivation in optimality theory. In COLING-94, Kyoto, pp. 1007–1013.

Fisher, W. (1996). tsylb2 software and documentation. http://.

Frank, R. and Satta, G. (1998). Optimality theory and the generative complexity of constraint violability. Computational Linguistics, 24(2), 307–315.

Frisch, S. A., Large, N. R., and Pisoni, D. B. (2000). Perception of wordlikeness: Effects of segment probability and length on the processing of nonwords. Journal of Memory and Language, 42, 481–496.

Gaussier, E. (1999). Unsupervised learning of derivational morphology from inflectional lexicons. In ACL-99.

Gerdemann, D. and van Noord, G. (2000). Approximation and exactness in finite state optimality theory. In Proceedings of ACL SIGPHON.

Gildea, D. and Jurafsky, D. (1996). Learning bias and phonological rule induction. Computational Linguistics, 22(4), 497–530.

Goldsmith, J. (1976). Autosegmental Phonology. Ph.D. thesis, MIT.

Goldsmith, J. (1993). Harmonic phonology. In Goldsmith, J. (Ed.), The Last Phonological Rule, pp. 21–60. University of Chicago Press, Chicago.

Goldsmith, J. (2001). Unsupervised learning of the morphology of a natural language. Computational Linguistics, 27, 153–198.

Goldwater, S., Griffiths, T. L., and Johnson, M. (2006). Contextual dependencies in unsupervised word segmentation. In COLING/ACL 2006, Sydney, Australia.

Goldwater, S. and Johnson, M. (2003). Learning OT constraint rankings using a maximum entropy model. In Stockholm Workshop on Variation within Optimality Theory, pp. 111–120. Stockholm University Press.

Goldwater, S. and Johnson, M. (2005). Representational bias in unsupervised learning of syllable structure. In Proceedings of the Conference on Computational Natural Language Learning (CoNLL-2005).

Hafer, M. A. and Weiss, S. F. (1974). Word segmentation by letter successor varieties. Information Storage and Retrieval, 10(11-12), 371–385.

Hammond, M. (1997). Parsing in OT. Alternative title "Parsing syllables: Modeling OT computationally". Rutgers Optimality Archive ROA-222-1097.

Harris, Z. S. (1954). Distributional structure. Word, 10, 146–162. Reprinted in J. Fodor and J. Katz, The structure of language: Readings in the philosophy of language, Prentice-hall, 1964 and in Z. S. Harris, Papers in structural and transformational linguistics, Reidel, Dordrecht, 1970, 775–794.

Harris, Z. S. (1988). Language and Information. Columbia University Press.

Hayes, B. and Wilson, C. (2007). A maximum entropy model of phonotactics and phonotactic learning. Linguistic Inquiry. To appear.

Hayes, B. (2004). Phonological acquisition in optimality theory: the early stages. In Kager, R., Pater, J., and Zonneveld, W. (Eds.), Constraints in Phonological Acquisition. Cambridge University Press.

Jacquemin, C. (1997). Guessing morphology from terms and corpora. In SIGIR 1997, Philadelphia, PA, pp. 156–165.

Jarosz, G. (2006). Richness of the base and probabilistic unsupervised learning in optimality theory. In Proceedings of ACL SIGPHON, New York, NY, pp. 50–59.

Jarosz, G. (2008). Restrictiveness and phonological grammar and lexicon learning. In CLS 43. In press.

Johnson, C. D. (1972). Formal Aspects of Phonological Description. Mouton, The Hague. Monographs on Linguistic Analysis No. 3.

Johnson, M. (1984). A discovery procedure for certain phonological rules. In COLING-84, Stanford, CA, pp. 344–347.

Kager, R. (2000). Optimality Theory. Cambridge University Press.

Kahn, D. (1976). Syllable-based Generalizations in English Phonology. Ph.D. thesis, MIT.

Kaplan, R. M. and Kay, M. (1981). Phonological rules and finite-state transducers. Paper presented at the Annual meeting of the Linguistics Society of America. New York.

Kaplan, R. M. and Kay, M. (1994). Regular models of phonological rule systems. Computational Linguistics, 20(3), 331–378.

Karttunen, L. (1993). Finite-state constraints. In Goldsmith, J. (Ed.), The Last Phonological Rule, pp. 173–194. University of Chicago Press.

Karttunen, L. (1998). The proper treatment of optimality in computational phonology. In Proceedings of FSMNLP'98: International Workshop on Finite-State Methods in Natural Language Processing, Bilkent University. Ankara, Turkey, pp. 1–12.

Kataja, L. and Koskenniemi, K. (1988). Finite state description of Semitic morphology. In COLING-88, Budapest, pp. 313–315.

Kay, M. (1987). Nonconcatenative finite-state morphology. In EACL-87, Copenhagen, Denmark, pp. 2–10.

Kazakov, D. (1997). Unsupervised learning of naïve morphology with genetic algorithms. In ECML/Mlnet Workshop on Empirical Learning of Natural Language Processing Tasks, Prague, pp. 105–111.

Kiraz, G. A. (1997). Compiling regular formalisms with rule features into finite-state automata. In ACL/EACL-97, Madrid, Spain, pp. 329–336.

Kiraz, G. A. (2000). Multitiered nonlinear morphology using multitape finite automata: A case study on syriac and arabic. Computational Linguistics, 26(1), 77–105.

Kiraz, G. A. (2001). Computational Nonlinear Morphology with Emphasis on Semitic Languages. Cambridge University Press.

Kiraz, G. A. and Möbius, B. (1998). Multilingual syllabification using weighted finite-state transducers. In Proceedings of 3rd ESCA Workshop on Speech Synthesis, Jenolan Caves, pp. 59–64.

Kisseberth, C. W. (1969). On the abstractness of phonology: The evidence from Yawelmani. Papers in Linguistics, 1, 248–282.

Kisseberth, C. W. (1970). On the functional unity of phonological rules. Linguistic Inquiry, 1(3), 291–306.

Kornai, A. (1991). Formal Phonology. Ph.D. thesis, Stanford University, Stanford, CA†.

Koskenniemi, K. (1983). Two-level morphology: A general computational model of word-form recognition and production. Tech. rep. Publication No. 11, Department of General Linguistics, University of Helsinki.

Kuhl, P. K., F.-M., T., and Liu, H.-M. (2003). Foreign-language experience in infancy: Effects of short-term exposure and social interaction on phonetic learning. Proceedings of the National Academy of Sciences, 100, 9096–9101.

Ladefoged, P. (1993). A Course in Phonetics. Harcourt Brace Jovanovich. Third Edition.

Lakoff, G. (1993). Cognitive phonology. In Goldsmith, J. (Ed.), The Last Phonological Rule, pp. 117–145. University of Chicago Press, Chicago.

McCarthy, J. J. (1981). A prosodic theory of non-concatenative morphology. Linguistic Inquiry, 12, 373–418.

Müller, K. (2001). Automatic detection of syllable boundaries combining the advantages of treebank and bracketed corpora training. In ACL-01, Toulouse, France. ACL.

Müller, K. (2002). Probabilistic context-free grammars for phonology. In Proceedings of ACL SIGPHON, Philadelphia, PA, pp. 70–80.

Müller, K., Möbius, B., and Prescher, D. (2000). Inducing probabilistic syllable classes using multivariate clustering. In ACL00, pp. 225–232.

Newman, S. (1944). Yokuts Language of California. Viking Fund Publications in Anthropology 2, New York.

Odden, D. (2005). Introducing Phonology. Cambridge University Press.

Oncina, J., García, P., and Vidal, E. (1993). Learning subsequent transducers for pattern recognition tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15, 448–458.

Pater, J. (2007). Gradual learning and convergence. Linguistic Inquiry. In press.

Pater, J., Potts, C., and Bhatt, R. (2007). Harmonic grammar with linear programming. unpublished manuscript.

Pereira, F. C. N., Riley, M. D., and Sproat, R. (1994). Weighted rational transductions and their applications to human language processing. In ARPA Human Language Technology Workshop, Plainsboro, NJ, pp. 262–267. Morgan Kaufmann.

Prince, A. and Smolensky, P. (1993). Optimality theory: Constraint interaction in generative grammar. Appeared as Tech. rep. CU-CS-696-93, Department of Computer Science, University of Colorado at Boulder, and TEch. rep. TR-2, Rutgers Center for Cognitive Science, Rutgers University, New Brunswick, NJ, April 1993.

Prince, A. and Smolensky, P. (2004). Optimality Theory: Constraint interaction in generative grammar. Blackwell.

Prince, A. and Tesar, B. (2004). Learning phonotactic distributions. In Kager, R., Pater, J., and Zonneveld, W. (Eds.), Constraints in Phonological Acquisition, pp. 245–291. Cambridge University Press.

Riggle, J. (2005). Contenders and learning. In WCCFL 23, pp. 101–114.

Saffran, J. R., Newport, E. L., and Aslin, R. N. (1996a). Statistical learning by 8-month old infants. Science, 274, 1926–1928.

Saffran, J. R., Newport, E. L., and Aslin, R. N. (1996b). Word segmentation: The role of distributional cues. Journal of Memory and Language, 35, 606–621.

Schone, P. and Jurafsky, D. (2000). Knowledge-free induction of morphology using latent semantic analysis. In Proceedings of the Conference on Computational Natural Language Learning (CoNLL-2000).

Schone, P. and Jurafsky, D. (2001). Knowledge-free induction of inflectional morphologies. In Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-2001).

Seneff, S., Lau, R., and Meng, H. (1996). ANGIE: A new framework for speech analysis based on morpho-phonological modelling. In ICSLP-96.

Smolensky, P. and Legendre, G. (2006). The Harmonic Mind. MIT Press.

Sproat, R. (1993). Morphology and Computation. MIT Press.

Tesar, B. (2006a). Faithful contrastive features in learning. Cognitive Science, 30(5), 863–903.

Tesar, B. (2006b). Learning from paradigmatic information..

Tesar, B. and Prince, A. (2007). Using phonotactics to learn phonological alternations. In CLS 39, pp. 200–213.

Tesar, B. and Smolensky, P. (2000). Learning in Optimality Theory. MIT Press.

Thiessen, E. D., Hill, E. A., and Saffran, J. R. (2005). Infant-directed speech facilitates word segmentation. Infancy, 7, 53–71.

Thiessen, E. D. and Saffran, J. R. (2004). Spectral tilt as a cue to word segmentation in infancy and adulthood. Perception and Psychophysics, 66(2), 779–791.

Titone, D. and Connine, C. M. (1997). Syllabification strategies in spoken word processing: Evidence from phonological priming. Psychological Research, 60(4), 251–263.

Touretzky, D. S., Elvgren III, G., and Wheeler, D. W. (1990). Phonological rule induction: An architectural solution. In COGSCI-90, pp. 348–355.

Treiman, R., Bowey, J., and Bourassa, D. (2002). Segmentation of spoken words into syllables by english-speaking children as compared to adults. Journal of Experimental Child Psychology, 83, 213–238.

van den Bosch, A. (1997). Learning to Pronounce Written Words: A Study in Inductive Language Learning. Ph.D. thesis, University of Maastricht, Maastricht, The Netherlands.

Yarowsky, D. and Wicentowski, R. (2000). Minimally supervised morphological analysis by multimodal alignment. In ACL-00, Hong Kong, pp. 207–216.

12 FORMAL GRAMMARS OF ENGLISH

The first context-free grammar parse tree (Chomsky, 1956)

If on a winter's night a traveler by Italo Calvino Nuclear and Radiochemistry by Gerhart Friedlander et al. The Fire Next Time by James Baldwin A Tad Overweight, but Violet Eyes to Die For by G. B. Trudeau Sometimes a Great Notion by Ken Kesey Dancer from the Dance by Andrew Holleran Six books in English whose titles are not constituents, from Pullum (1991, p. 195)

The study of grammar has an ancient pedigree; Panini's grammar of Sanskrit was written over two thousand years ago, and is still referenced today in teaching Sanskrit. By contrast, Geoff Pullum noted in a recent talk that “almost everything most educated Americans believe about English grammar is wrong”. In this chapter we make a preliminary stab at addressing some of these gaps in our knowledge of grammar and syntax, as well as introducing some of the formal mechanisms that are available for capturing this knowledge.

The word syntax comes from the Greek syntaxis, meaning “setting out together or arrangement”, and refers to the way words are arranged together. We have seen various syntactic notions in previous chapters. The regular languages introduced in Ch. 2 offered a simple way to represent the ordering of strings of words, and Ch. 4 showed how to compute probabilities for these word sequences. Ch. 5 showed that part-of-speech categories could act a kind of equivalence class for words. This chapter

and the following ones introduce sophisticated notions of syntax and grammar that go well beyond these simpler notions. In this chapter, we introduce three main new ideas: constituency, grammatical relations, and subcategorization and dependency.

The fundamental idea of constituency is that groups of words may behave as a single unit or phrase, called a constituent. For example we will see that a group of words called a noun phrase often acts as a unit; noun phrases include single words like she or Michael and phrases like the house, Russian Hill, and a well-weathered three-story structure. This chapter will introduce the use of context-free grammars, a formalism that will allow us to model these constituency facts.

Grammatical relations are a formalization of ideas from traditional grammar such as SUBJECTS and OBJECTS, and other related notions. In the following sentence the noun phrase She is the SUBJECT and a mammoth breakfast is the OBJECT:

(12.1) She ate a mammoth breakfast.

Subcategorization and dependency relations refer to certain kinds of relations between words and phrases. For example the verb want can be followed by an infinitive, as in I want to fly to Detroit, or a noun phrase, as in I want a flight to Detroit. But the verb find cannot be followed by an infinitive (*I found to fly to Dallas). These are called facts about the subcategorization of the verb.

As we’ll see, none of the syntactic mechanisms that we’ve discussed up until now can easily capture such phenomena. They can be modeled much more naturally by grammars that are based on context-free grammars. Context-free grammars are thus the backbone of many formal models of the syntax of natural language (and, for that matter, of computer languages). As such they are integral to many computational applications including grammar checking, semantic interpretation, dialogue understanding and machine translation. They are powerful enough to express sophisticated relations among the words in a sentence, yet computationally tractable enough that efficient algorithms exist for parsing sentences with them (as we will see in Ch. 13). Later in Ch. 14 we’ll show that adding probability to context-free grammars gives us a model of disambiguation, and also helps model certain aspects of human parsing.

In addition to an introduction to the grammar formalism, this chapter also provides an brief overview of the grammar of English. We have chosen a domain which has relatively simple sentences, the Air Traffic Information System (ATIS) domain (Hemphill et al., 1990). ATIS systems are an early example of spoken language systems for helping book airline reservations. Users try to book flights by conversing with the system, specifying constraints like I'd like to fly from Atlanta to Denver. The U.S. government funded a number of different research sites to collect data and build ATIS systems in the early 1990s. The sentences we will be modeling in this chapter are drawn from the corpus of user queries to the system.

12.1 CONSTITUENCY

NOUN PHRASE How do words group together in English? Consider the noun phrase, a sequence of words surrounding at least one noun. Here are some examples of noun phrases (thanks to Damon Runyon):

Harry the Horse

a high-class spot such as Mindy's

the Broadway coppers

the reason he comes into the Hot Box

they

three parties from Brooklyn

How do we know that these words group together (or “form constituents”)? One piece of evidence is that they can all appear in similar syntactic environments, for example before a verb.

three parties from Brooklyn arrive...

a high-class spot such as Mindy's attracts...

the Broadway coppers love...

they sit

But while the whole noun phrase can occur before a verb, this is not true of each of the individual words that make up a noun phrase. The following are not grammatical sentences of English (recall that we use an asterisk (*) to mark fragments that are not grammatical English sentences):

Thus to correctly describe facts about the ordering of these words in English, we must be able to say things like “Noun Phrases can occur before verbs”.

Other kinds of evidence for constituency come from what are called preposed or postposed constructions. For example, the prepositional phrase on September seventeenth can be placed in a number of different locations in the following examples, including preposed at the beginning, and postposed at the end:

On September seventeenth, I'd like to fly from Atlanta to Denver

I'd like to fly on September seventeenth from Atlanta to Denver

I'd like to fly from Atlanta to Denver on September seventeenth

But again, while the entire phrase can be placed differently, the individual words making up the phrase cannot be:

*On September, I'd like to fly $ \underline{\text{seventeenth}} $ from Atlanta to Denver

$ ^{*} $ $ \underline{\text{On}} $ I'd like to fly September seventeenth from Atlanta to Denver

$ ^{*} $I'd like to fly $ \underline{\text{on September}} $ from Atlanta to Denver $ \underline{\text{seventeenth}} $

Section 12.6 will give other motivations for context-free grammars based on their ability to model recursive structures. See Radford (1988) for further examples of groups of words behaving as a single constituent.

12.2 CONTEXT-FREE GRAMMARS

The most commonly used mathematical system for modeling constituent structure in English and other natural languages is the Context-Free Grammar, or CFG. Context-free grammars are also called Phrase-Structure Grammars, and the formalism is equivalent to what is also called Backus-Naur Form or BNF. The idea of basing

a grammar on constituent structure dates back to the psychologist Wilhelm Wundt (1900), but was not formalized until Chomsky (1956) and, independently, Backus (1959).

A context-free grammar consists of a set of rules or productions, each of which expresses the ways that symbols of the language can be grouped and ordered together, and a lexicon of words and symbols. For example, the following productions express that a NP (or noun phrase), can be composed of either a ProperNoun or a determiner (Det) followed by a Nominal; a Nominal can be one or more Nouns.

$$ NP\ \to\ \textit{Det Nominal} $$

$$ NP\,\to\,ProperNoun $$

$$ Nominal\ \rightarrow\ Noun\ \mid Nominal Noun $$

Context-free rules can be hierarchically embedded, so we can combine the previous rules with others like the following which express facts about the lexicon:

$$ Det\ \to\ a $$

$$ Det\ \to\ the $$

$$ \textit{Noun}\to\textit{flight} $$

The symbols that are used in a CFG are divided into two classes. The symbols that correspond to words in the language (“the”, “nightclub”) are called terminal symbols; the lexicon is the set of rules that introduce these terminal symbols. The symbols that express clusters or generalizations of these are called non-terminals. In each context-free rule, the item to the right of the arrow (→) is an ordered list of one or more terminals and non-terminals, while to the left of the arrow is a single non-terminal symbol expressing some cluster or generalization. Notice that in the lexicon, the non-terminal associated with each word is its lexical category, or part-of-speech, which we defined in Ch. 5.

A CFG can be thought of in two ways: as a device for generating sentences, and as a device for assigning a structure to a given sentence. We saw this same dualism in our discussion of finite-state transducers in Ch. 3. As a generator, we can read the $ \rightarrow $ arrow as “rewrite the symbol on the left with the string of symbols on the right”.

So starting from the symbol: NP,

we can use rule 12.2 to rewrite NP as:

and then rule 12.2:

and finally via rules 12.2 and 12.2 as:

a flight

We say the string a flight can be derived from the non-terminal NP. Thus a CFG can be used to generate a set of strings. This sequence of rule expansions is called a derivation of the string of words. It is common to represent a derivation by a parse tree (commonly shown inverted with the root at the top). Fig. 12.1 shows the tree representation of this derivation.

In the parse tree shown in Fig. 12.1 we say that the node NP immediately dominates the node Det and the node Nom. We say that the node NP dominates all the nodes in the tree (Det, Nom, Noun, a, flight).

The formal language defined by a CFG is the set of strings that are derivable from the designated start symbol. Each grammar must have one designated start symbol,

which is often called S. Since context-free grammars are often used to define sentences, S is usually interpreted as the “sentence” node, and the set of strings that are derivable from S is the set of sentences in some simplified version of English.

Let's add to our list of rules a few higher-level rules that expand S, and a couple of others. One will express the fact that a sentence can consist of a noun phrase followed by a verb phrase:

$$ S\;\rightarrow\;N P\;V P\quad\mathrm{I~p r e f e r~a~m o r n i n g~f l i g h t} $$

A verb phrase in English consists of a verb followed by assorted other things; for example, one kind of verb phrase consists of a verb followed by a noun phrase:

$$ \textit{V P}\to\textit{V e r b}\textit{N P}\quad\mathrm{p r e f e r a m o r n i n g f l i g h t} $$

Or the verb phrase may have a verb followed by a noun phrase and a prepositional phrase:

$$ \textit{V P}\to\textit{V e r b}\textit{N P}\textit{P P}\quad\textit{l e a v e B o s t o n i n t h e m o r n i n g} $$

Or the verb may be followed by a prepositional phrase alone:

$$ \mathit{V P}\;\to\;\mathit{V e r b}\;\mathit{P P}\quad\mathrm{l e a v i n g~o n~T h u r s d a y} $$

A prepositional phrase generally has a preposition followed by a noun phrase. For example, a very common type of prepositional phrase in the ATIS corpus is used to indicate location or direction:

$$ {\cal P P}\;\to\;{\cal P r e p o s i t i o n~N P}\quad{\mathrm{f r o m~L o s~A n g e l e s}} $$

The NP inside a PP need not be a location; PPs are often used with times and dates, and with other nouns as well; they can be arbitrarily complex. Here are ten examples from the ATIS corpus:

to Seattle

on these flights

in Minneapolis about the ground transportation in Chicago

on Wednesday of the round trip flight on United Airlines

in the evening

of the AP fifty seven flight

on the ninth of July with a stopover in Nashville

Noun → flights | breeze | trip | morning | ...

Verb → is | prefer | like | need | want | fly

Adjective → cheapest | non-stop | first | latest

| other | direct | ...

Pronoun → me | I | you | it | ...

Proper-Noun → Alaska | Baltimore | Los Angeles

| Chicago | United | American | ...

Determiner → the | a | an | this | these | that | ...

Preposition → from | to | on | near | ...

Conjunction → and | or | but | ...

S → NP VP

I + want a morning flight

NP → Pronoun

I

| Proper-Noun Los Angeles

| Det Nominal a + flight

Nominal → Nominal Noun morning + flight

| Noun flights

VP → Verb do

| Verb NP want + a flight

| Verb NP PP leave + Boston + in the morning

| Verb PP leaving + on Thursday

PP → Preposition NP from + Los Angeles

Figure 12.3 The grammar for $ L_{0} $, with example phrases for each rule.

Fig. 12.2 gives a sample lexicon and Fig. 12.3 summarizes the grammar rules we've seen so far, which we'll call $ \mathcal{L}_0 $. Note that we can use the or-symbol | to indicate that a non-terminal has alternate possible expansions.

We can use this grammar to generate sentences of this “ATIS-language”. We start with S, expand it to NP VP, then choose a random expansion of NP (let's say to I), and a random expansion of VP (let's say to Verb NP), and so on until we generate the string I prefer a morning flight. Fig. 12.4 shows a parse tree that represents a complete derivation of I prefer a morning flight.

It is sometimes convenient to represent a parse tree in a more compact format called bracketed notation, essentially the same as LISP tree representations; here is the bracketed representation of the parse tree of Fig. 12.4:

[S [NP [Pro I]] [VP [V prefer] [NP [Det a] [Nom [N morning] [Nom [N flight]]]]]]

A CFG like that of $\mathcal{L}_{0}$ defines a formal language. We saw in Ch. 2 that a formal language is a set of strings. Sentences (strings of words) that can be derived by a grammar are in the formal language defined by that grammar, and are called grammatical sentences. Sentences that cannot be derived by a given formal grammar are not in the language defined by that grammar, and are referred to as ungrammatical. This hard line between “in” and “out” characterizes all formal languages but is only a very simplified model of how natural languages really work. This is because determining whether a given sentence is part of a given natural language (say English) often depends on the context. In linguistics, the use of formal languages to model natural languages is called generative grammar, since the language is defined by the set of possible sentences “generated” by the grammar.