Learning Stochastic Categorial Grammars

Learning Stochastic Categorial Grammars Miles Osborne and Ted Briscoe Computer Laboratory, Cambridge University Cambridge CB2 3QG, UK {Miles.Osborne,Ted.Briscoe}@cl.cam.ac.uk Abstract Stochastic categorial grammars (SCGs) are introduced as a more appropriate formal- ism for statistical language learners to es- timate than stochastic context free gram- mars. As a vehicle for demonstrating SCG estimation, we show, in terms of crossing rates and in coverage, that when training material is limited, SCG estimation using the Minimum Description Length Princi- ple is preferable to SCG estimation using an indifferent prior. 1 Introduction Stochastic context free grammars (SCFGs), which are standard context free grammars extended with a probabilistic interpretation of the generation of strings, have been shown to model some sources with hidden branching processes more efficiently than stochastic regular grammars (Lari and Young, 1990). Furthermore, SCFGs can be automatically estimated using the Inside-Outside algorithm, which is guaranteed to produce a SCFG that is (locally) optimal (Baker, 1990). Hence, SCFGs appear to be suitable formalisms for the estimation of wide- covering grammars, capable of being used as part of a system that assigns logical forms to sentences. Unfortunately, from a Natural Language Process- ing perspective, SCFGs are not appropriate gram- mars to learn. Firstly, as Collins demonstrates (Collins, 1996), accurate parse selection, which is important for ambiguity resolution, requires lexical statistics. SCFGs, as standardly used in the Inside- Outside algorithm, are in Chomsky Normal Form (CNF), which restricts rules to being at most bi- nary branching. Such rules are not lexicalised, and hence, to lexicalise (CNF) CFGs requires adding a complex statistical model that simulates the projec- tion of head items up the parse tree. Given the embryonic status of grammatical statistical models and the difficulties of accurately estimating the pa- rameters of such a model, it seems more prudent to prefer whenever possible simpler statistical mod- els with fewer parameters, and treat lexicalisation as part of the grammatical formalism, and not as part of the statistical framework (for example (Sch- abes, 1992)). Secondly, (stochastic) CFGs are well- known as being linguistically inadequate formalisms for problems such as non-constituent coordination. Hence, a learner using a SCFG will not have an ap- propriate formalism with which to construct an ad- equate grammar. Stochastic categorial grammars (SCGs), which are classical categorial grammars extended with a prob- abilistic component, by contrast, have a grammat- ical component that is naturally lexicalised. Fur- thermore, Combinatory Categorial Grammars have been shown to account elegantly for problematic ar- eas of syntax such as non-constituent co-ordination (Steedman, 1989), and so it seems likely that SCGs, when suitably extended, will be able to inherit this linguistic adequacy. We therefore believe that SCGs are more useful formalisms for statistical language learning than SCFGs. Future work will reinforce the differences between SCFGs and SCGS, but in this paper, we instead concentrate upon the estima- tion of SCGs. Stochastic grammars (of all varieties) are usually estimated using the Maximum Likelihood Principle, which assumes an indifferent prior probability dis- tribution. When there is sufficient training mate- rial, Maximum Likelihood …

Content truncated to 500 words