Paper: Efficient Correct Unsupervised Learning for Context-Sensitive Languages

ACL ID W10-2904
Title Efficient Correct Unsupervised Learning for Context-Sensitive Languages
Venue International Conference on Computational Natural Language Learning
Session Main Conference
Year 2010
Authors

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.