21 April 2009
2:30 - 4:00   Shalom Lappin (King's College London)
Restricting Distributions for Computational Language Learning
Joint work with Alex Clark, Royal Holloway College London

Abstract:
Classical computational learning models like Gold's (1967) identification in the limit paradigm and PAC learning require learning under all possible probability distributions over data samples. By modifying PAC learning to restrict the set of distributions, it is possible to show that different classes of languages are learnable than in the distribution free framwork. I will explore some recent work on distribution based language learning. Clark and Thollard (2004) prove that when the set of distributions is limited to those produced by Probabilistic Deterministic Finite State Automata, then the class of regular languages is PAC learnable from positive evidence only. Clark (2006) demonstrates a similar result for an interesting subclass of context free languages when the set of distributions corresponds to a specified set of Probabilistic Context Free Grammars. I will then discuss how this approach might be used to increase the range of evidence available for learning. Clark and Lappin (2009) suggest that an appropriate restriction on the set of possible distributions for PAC learning could provide the basis for a stochastic model of indirect negative evidence.