Learning Structural Descriptions of Grammar Rules from Examples

1. INTRODUCTION

An important goal of modern linguistic theory is to show how learning a grammar can appear to be so easy, given the poor quality of the data children receive. This paper reports on a currently running LISP program which, by computationally embodymg some theories of transformational grammar, can learn syntactic rules in the manner of Winston's blocks world program [2]. The program proceeds by examining example sentences to modify its descriptions of grammar rules that make up part of its knowledge about language.

The key idea is that learning syntactic transformations is easy, given the right initial computational structure. This program uses a~ initial structure a simplified version of Marcus's PARSIFAL [lJ, a parser for English which is an interpreter for grammar rules of a particularly simple production rule form. The bas1c operation of the interpreter is taken as fixed, corresponding to an intial set of computational abilities. Only grammar rules are learned.

* This research was conducted at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under · Office of Naval Research contract number N00014-1S-C-0643, and in part by NSF' Grant MCS11-04828.

Because the rules themselves are so simple, and the operation of the interpreter so constrained, bugs have a di<~meter-hmitcd location. Further, the p;~rser itself is strictly deterministic; that is, already-built portions of the parse tree are assumed correct, and there is no backup. As shown below, these assumptions are crucial in the operation of the le;~rning aJg·orithm.

More specifically, the Marcus interpreter uses the following data structures : A parse tree, a syntactic representation of the mput sentence. The lowest, right -most node of the tree under construction is called the current active node, denoted C. Lbuffer of three (to five) cells that holds words from the input sentence or as yet not-completely analyzed phrases. Phrase structure rules that are used to turn on and off logjcally grouped sets of grammar rules (for example, the rule S-->NP·VP would first activate all grammar rules that start sentences, then turn off that group and activate noun phrase rules). The phrase structure control system was designed by Shipman [3]. Production rules (also called grammar rules) of the form: IF <pattern> Til EN <action>. Each <action> does the actual work of building the p;~rse tree, attaching words or phrases from the buffer onto the parse tree, moving new words into the buffer, ;~nd ~o forth. <Patterns> determine if the given action 1s to f1re; if the pattern given in a grammar rule matches the pattern in the buffer, the specified <action> takes place.( Patterns use common lexical features like Noun phrast, singular or V €Tb, transitive.)

The learning program acquires only the patterns and actions of the grammar rules. One of the accomplishments of this research has been to simplify the original Marcus parser to a point where there are only four valid actions: ATTACH first buffer item to C; SWITCH first and second buffer items; INSERT a specific lexical item into the first buffer slot · and INSERT-TRACE into first buffer slot. (Tracts ' are not further discussed in this paper but function as in Chomalo/'s theory; see F'iengo [4) for discussion.)

Learning proceeds by induction on the <patttrns> and <actions>, but with an important constraint: children (and this program) do not appear to receive negative data examples on what is not a sentence (see Brown and Hanlon [5] and Anderson [6] for discussion). On the other hand, children (and th1s program) do appear to receive reinforcement on what is a semantically meaningful sentence. Therefore, the current program does assume a lexicon and self.'ctional restrictiOns on the phrase-structure categories (for e>:amJ>Ie, that Mar~ is a noun and cttn fit under a noun phrase). More advanced versions of the program will probably have to assume a known case-frame representation for the input sentence given (fillmore [1)), but this has not yet been found to be necessary; a recent result obtained by Wexler [8] proves mathematically that, given a transformational grammar to be learned and only surface sentences as mput, a recursive learning procedure for the grammar does not exist (this was shown by Cold [9]), but that such a procedure does exist if surface sentences are p;ured with some representation of the underlying meaning of the sentence.

2. THE LEARNING PROCEDURE

The learning program starts w1th an interpreter, a lexicon, s1mple phrase-structure rules, selectional restrictions, but no grammar rules. The program is then given input sentences to parse. If 11 gets stuck in a parse-- if no current rule patterns match or 1f all current rules cause selectional errors - - thrn the program attempts to build a new grammar rule that will apply at that point. It does this by trying each of its possible actions m turn: attach, switch. insert, insert-trace. (This ordering was found empirically.) The first action that succeeds in satisfying the selectional restrictions is saved along with the current machine state (buffer plus current active node) as the pattern; this becomes the new rule. If no possible generated rule has worked, the active phrase structure rule is assumed to be opt 10nal. F'mally, rules with common actions within a phrase-structure . group have their patterns continually generalized via intersection.

3. AN EXAMPLE: AUXILIARY-INVERSION

Suppose that at a certain point the program has all and only the grammar rules necessary to build a parse tree for Mary did hit the ball. The program now gets as input, Did Mary hit the ball? No rule currently known can fire, for in the phrase structure packet S activated at the beginning of a sentence, the only rules have the pattern [:Noun Phrase][:Verb], and the buffer holds the pattern [·Did: auxerb][·Mary: Noun~ A new rule must be written, so the program tries each of its possible rule actions in turn. Attach fails because of selectional restrictions; did can't be attached as a noun phrase. But Switch works, because when the first and second buffer positions are switched, and the buffer now looks like [·mary][·did], an existing rule for pamng declarative sentences can match. The rest of the sentence is parsed as if It were a declarative. r mally, the switch rule is saved along with the current buffer pattern as a trigeer for the next case of auxiliary inversion. It is cruci;l to notice that the debugging is strictly local: the error is assumed to lie exactly where the error first occurred, and not in some other rule. At most one new rule is added or one old rule modified with each example sentence, a kind of incremental debugging that is analagous to Sussman's <ifbugging almost right pro!'ams [10]. In this regard it is important to point out that Wexler has proved [8] that local debugging is apparently a necessary condition for the learning of a transformational grammar.

The currently implemented LISP version of this procedure has acquired about 10% of a "core-grammar" of English origmally developed for the Marcus parser, as well as some new rules; acqu1red rules include unmarked-order, auxiliary inversion, imperative, simple there-insertion, to­ infinitive, do-support, and some passives. On the other hand, rules for parsing the complicated complement structure of English have yet to be learned, nor is it clear how they might be. future work will consider a str;ughtforward way to learn the phrase structure rules thrn;selves, by generalizing templates of phrase structure rules accordmg to Chomsky's X -bar theory (Jackendoff [11]). The relationship between the local debugging constraints assumed by the learning procedure and those constraints found necessary by Wexler [8] will also be investigated.

ACKNOWLEDGEMENTS

Spec1al thanks are of course due to Mitch Marcus, whose thesis and advice forms the foundation of this work, and to the linguistic expert1se of Candy S1dner and Beth Levin.

REVERENCES

1. Marcus, M., "A Computational Account of Some Constraints on Language," in proceedmgs of Tlttortttcal lsszus In Natrmrl Languagt Procmlng (July 19'78; TINLA P-2), pp. 236-246.
2. Winston, P., "Learning Structural Descriptions from Examples," in P. Winston, editor, Tilt Ps"JCitolon of Computer Vision, New York: McGraw-Hill, 19'75.
3. Shipman, D., and Marcus, M., "Towards Minimal Data Structures for Parsing," Proc. IJCA/·79, Tokyo, Japan, 1919.
4. [4) F'iengo, R., "On Trace Theory," Lingutsttc lnqutr1 8:1 (1911) ' pp. 35-61.
5. [51 Brown, R., and Hanlon, C.,"Dtrivauonal Complexity and Order of Acquisition in Child Speech", in J.R. Hayes, ed., Cognition and tAt Dtvtlopmtnt of Languagt, New York: John Wiley and Sons, n10.
6. Anderson, J. R., "Induction of Augmented Transition Networks", Cognltivt Scitnct, 1, (1917) pp.l25-15'7.
7. Fillmore, C.J., "The Case for Case", In Bach, E., and Harms, R.T., editors, Unlvmals in Lingulsttc TlttOT'11 New York: Holt, Rinehart, and Wmston, 1968.
8. Wt>xler, K., "Transformational Grammars are Leunable from Data of Drgree Less than or Equal to Two," Soctal Scitnces Working Papm, ~139, School of Social Sciences, Univenity of California, Irvine, 1911.
9. [91 Cold, E.M., "Language Identification In the Limit," Information and Control, 10 ( 1961) pp. 44'7-4'74.
10. Stmman, C., A Computational Modtl of Slr.Ul Arquisition, Americiln Elsevier, 1915.
11. [llJ Jackendoff, R., X·bar S1ntax: A Stud7 of Plmm Structure, Ci!mbridge, Mass: MIT Press, 19'11.