Efficient, Correct, Unsupervised Learning for Context-Sensitive Languages

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 28–37, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Efficient, correct, unsupervised learning of context-sensitive languages Alexander Clark Department of Computer Science Royal Holloway, University of London alexc@cs.rhul.ac.uk Abstract A central problem for NLP is grammar in- duction: the development of unsupervised learning algorithms for syntax. In this pa- per we present a lattice-theoretic represen- tation for natural language syntax, called Distributional Lattice Grammars. These representations are objective or empiri- cist, based on a generalisation of distribu- tional learning, and are capable of repre- senting all regular languages, some but not all context-free languages and some non- context-free languages. We present a sim- ple algorithm for learning these grammars together with a complete self-contained proof of the correctness and efficiency of the algorithm. 1 Introduction Grammar induction, or unsupervised learning of syntax, no longer requires extensive justification and motivation. Both from engineering and cog- nitive/linguistic angles, it is a central challenge for computational linguistics. However good al- gorithms for this task are thin on the ground. There are numerous heuristic algorithms, some of which have had significant success in inducing constituent structure (Klein and Manning, 2004). There are algorithms with theoretical guarantees as to their correctness – such as for example Bayesian algorithms for inducing PCFGs (John- son, 2008), but such algorithms are inefficient: an exponential search algorithm is hidden in the con- vergence of the MCMC samplers. The efficient algorithms that are actually used are heuristic ap- proximations to the true posteriors. There are al- gorithms like the Inside-Outside algorithm (Lari and Young, 1990) which are guaranteed to con- verge efficiently, but not necessarily to the right answer: they converge to a local optimum that may be, and in practice nearly always is very far from the optimum. There are naive enumerative algorithms that are correct, but involve exhaus- tively enumerating all representations below a cer- tain size (Horning, 1969). There are no correct and efficient algorithms, as there are for parsing, for example. There is a reason for this: from a formal point of view, the problem is intractably hard for the standard representations in the Chomsky hierar- chy. Abe and Warmuth (1992) showed that train- ing stochastic regular grammars is hard; Angluin and Kharitonov (1995) showed that regular gram- mars cannot be learned even using queries; these results obviously apply also to PCFGs and CFGs as well as to the more complex representations built by extending CFGs, such as TAGs and so on. However, these results do not necessarily ap- ply to other representations. Regular grammars are not learnable, but deterministic finite automata are learnable under various paradigms (Angluin, 1987). Thus it is possible to learn by changing to representations that have better properties: in par- ticular DFAs are learnable because they are “ob- jective”; there is a correspondence between the structure of the language, (the residual languages) and the representational primitives of the formal- ism (the states) which is expressed by the Myhill- …

Content truncated to 500 words