Language learning from stochastic input

Language learning from positive data in the Gold model of inductive inference is investi-gated in a setting where the data can be mod-eled as a stochastic process. Specifically, the input strings are assumed to form a sequence of identically distributed, independent random variables, where the distribution depends on the language being presented. A scheme is developed which can be tuned to learn, with probability one, any family of recursive lan-guages, given a recursive enumeration of total indices for the languages in the family and a procedure to compute a lower bound to the probability of occurrence of a given string in a given language. Variations of the scheme work under other assumptions, e.g., if the prob-abilities of the strings form a monotone se-quence with respect to a given enumeration. The learning algorithm is rather simple and appears psychologically plausible. A more so-phisticated version of the learner is also devel-oped, based on a probabilistic version of the notion of tell-tale subset. This version yields, as a special case, Angluin’s learner for the fam-ilies of languages that are learnable from all texts (and not just from a set of texts of prob-ability one).