Efficient, Correct, Unsupervised Learning of Context-Sensitive Languages

TY - CHAP

T1 - Efficient, Correct, Unsupervised Learning of Context-Sensitive Languages

AU - Clark, Alexander

PY - 2010/7/1

Y1 - 2010/7/1

N2 - A central problem for NLP is grammar induction: the development of unsupervised learning algorithms for syntax. In this paper we present a lattice-theoretic representation for natural language syntax, called Distributional Lattice Grammars. These representations are objective or empiricist, based on a generalisation of distributional learning, and are capable of representing all regular languages, some but not all context-free languages and some non-context-free languages. We present a simple algorithm for learning these grammars together with a complete self-contained proof of the correctness and efficiency of the algorithm.

AB - A central problem for NLP is grammar induction: the development of unsupervised learning algorithms for syntax. In this paper we present a lattice-theoretic representation for natural language syntax, called Distributional Lattice Grammars. These representations are objective or empiricist, based on a generalisation of distributional learning, and are capable of representing all regular languages, some but not all context-free languages and some non-context-free languages. We present a simple algorithm for learning these grammars together with a complete self-contained proof of the correctness and efficiency of the algorithm.

M3 - Conference paper

SP - 28

EP - 37

BT - Proceedings of the Fourteenth Conference on Computational Natural Language Learning

PB - Association for Computational Linguistics

ER -