A Connectionist Parser for Structure Unification Grammar

A CONNECTIONIST PARSER FOR STRUCTURE UNIFICATION GRAMMAR James B. Henderson* Department of Computer and Information Science University of Pennsylvania 200 South 33rd Philadelphia, PA 19104, USA (henders@linc.cis.upenn.edu) ABSTRACT This paper presents a connectionist syntactic parser which uses Structure Unification Grammar as its grammatical framework. The parser is im- plemented in a connectionist architecture which stores and dynamically manipulates symbolic rep- resentations, but which can't represent arbitrary disjunction and has bounded memory. These problems can be overcome with Structure Unifica- tion Grammar's extensive use of partial descrip- tions. INTRODUCTION The similarity between connectionist models of computation and neuron computation suggests that a study of syntactic parsing in a connection- ist computational architecture could lead to sig- nificant insights into ways natural language can be parsed efficiently. Unfortunately, previous in- vestigations into connectionist parsing (Cottrell, 1989, Fanty, 1985, Selman and Hirst, 1987) have not been very successful. They cannot parse arbi- trarily long sentences and have inadequate gram- mar representations. However, the difficulties with connectionist parsing can be overcome by adopt- ing a different connectionist model of computa- tion, namely that proposed by Shastri and Ajjana- gadde (1990). This connectionist computational architecture differs from others in that it directly manifests the symbolic interpretation of the infor- mation it stores and manipulates. It also shares the massive parallelism, evidential reasoning abil- ity, and neurological plausibility of other connec- tionist architectures. Since virtually all charac- terizations of natural language syntax have relied heavily on symbolic representations, this architec- ture is ideally suited for the investigation of syn- tactic parsing. *This research was supported by ARO grant DAAL 03-89-C-0031, DARPA grant N00014-90-J- 1863, NSF grant IRI 90-16592, and Ben Franklin grant 91S.3078C-1. The computational architecture proposed by Shastri and Ajjanagadde (1990) provides a rather general purpose computing framework, but it does have significant limitations. A computing mod- ule can represent entities, store predications over those entities, and use pattern-action rules to ma- nipulate this stored information. This form of rep- resentation is very expressive, and pattern-action rules are a general purpose way to do compu- tation. However, this architecture has two lim- itations which pose difficult problems for pars- ing natural language. First, only a conjunction of predications can be stored. The architecture cannot represent arbitrary disjunction. This lim- itation implies that the parser's representation of syntactic structure must be able to leave unspec- ified the information which the input has not yet determined, rather than having a disjunction of more completely specified possibilities for com- pleting the sentence. Second, the memory ca- pacity of any module is bounded. The number of entities which can be stored is bounded by a small constant, and the number of predications per predicate is also bounded. These bounds pose problems for parsing because the syntactic struc- tures which need to be recovered can be arbitrarily large. This problem can be solved by allowing the parser to output the syntactic structure incremen- tally, thus allowing the parser to forget the infor- mation which it has already output and which …

Content truncated to 500 words