Learning Shallow Context-Free Languages under Simple Distributions
Pieter W. Adriaans

Abstract:
In this paper I present the EMILE 3.0 algorithm. It can learn shallow 
context-free grammars efficiently. It does so under circumstances that, 
from a perspective of complexity, come resonably close to the conditions 
under which human beings learn a language. A language is shallow in its 
descriptive length if all the relevant constructions we need to know to 
learn it have a complexity that is logarithmic in the descriptive length 
of the grammar as a whole. I claim that natural languages are shallow 
and that shallowness in itself is an interesting general constraint in 
the context of formal learning theory. I also introduce the concept of 
separability. A language is separable if the validity of rules can be 
tested by means of memberbership queries using simple substitutions. 
Although I do not believe that human languages are strictly separable I 
do think it is an important aspect of efficient human communication. I 
illustrate the structure of the algorithm by means of an extensive 
example, and I indicate how a careful analysis of the bias involved in 
natural language learning may lead to versions of EMILE 3.0 that can be 
implemented in real-life dialogue systems. I claim that the EMILE 
approach could serve as a valuable metamodel for evaluating clustering 
approaches to language learning. The results of EMILE are mainly 
theoretical. They could potentially also be used to develop more 
efficient variants of other approaches to language learning.