The Chomsky hierarchy was explicitly intended to represent the hypotheses from distributional learning algorithms; yet these standard representations are well known to be hard to learn, even under quite benign learning paradigms, because of the computationally complexity of inferring rich hidden structures like trees.

There is a lot of interest in unsupervised learning of natural language -- current approaches (e.g. Klein and Manning, Johnson's Adaptor Grammars) use modifications of existing models such as tree or dependency structures together with sophisticated statistical models in order to recover structures that are as close as possible to gold standard manual annotations.

This tutorial will cover a different approach: recent algorithms for the unsupervised learning of representations of natural language based on distributional learning (Clark & Eyraud 2007; Clark, Eyraud and Habrard, 2008; Clark 2009). This research direction involves abandoning the standard models and designing new representation classes for formal languages that are richly structured but where the structure is not hidden but based on observable structures of the language -- the syntactic monoid or a lattice derived from that monoid. These representation classes are as a result easy to learn.

We will look briefly at algorithms for learning deterministic automata, and then move on to algorithms for learning context free and context sensitive languages. These algorithms explicitly model the distribution of substrings of the language: they are efficient (polynomial update time) and provably correct for a class of languages that includes all regular languages, many context free languages and a few context sensitive languages. This class may be rich enough to represent natural language syntax.