Partially Distribution-Free Learning of Regular Languages from Positive Samples

Partially Distribution-Free Learning of Regular Languages from Positive Samples Alexander Clark ISSCO / TIM, University of Geneva UNI-MAIL, Boulevard du Pont-d’Arve, CH-1211 Gen`eve 4, Switzerland asc@aclark.demon.co.uk Franck Thollard EURISE, Universit´e Jean Monnet,23, Rue du Docteur Paul Michelon, 42023 Saint-Etienne C´edex 2, France thollard@univ-st-etienne.fr Abstract Regular languages are widely used in NLP to- day in spite of their shortcomings. Efficient algorithms that can reliably learn these lan- guages, and which must in realistic applications only use positive samples, are necessary. These languages are not learnable under traditional distribution free criteria. We claim that an ap- propriate learning framework is PAC learning where the distributions are constrained to be generated by a class of stochastic automata with support equal to the target concept. We discuss how this is related to other learning paradigms. We then present a simple learning algorithm for regular languages, and a self-contained proof that it learns according to this partially distri- bution free criterion. 1 Introduction Regular languages, especially generated by de- terministic finite state automata are widely used in Natural Language processing, for various dif- ferent tasks (Mohri, 1997). Efficient learning algorithms, that have some guarantees of cor- rectness, would clearly be useful. Existing al- gorithms for learning deterministic automata, such as (Carrasco and Oncina, 1994) have only guarantees of identification in the limit (Gold, 1967), generally considered not to be a good guide to practical utility. Unforunately the prospects for learning according to the more useful PAC-learning criterion are poor after the well known result of (Kearns and Valiant, 1989). Distribution-free learning criteria require algo- rithms to learn for every possible combination of concept and distribution. Under this worst- case analysis many simple concept classes are unlearnable. However in many situations it is more realistic to assume that there is some re- lationship between the concept and the distri- bution, and furthermore in general only positive examples will be available. There are two ways of modelling this. The simplest is to study the learnability of distribu- tions (Kearns et al., 1994; Ron et al., 1995). In this case the samples are drawn from the distri- bution that is being learned. The choice of error function then becomes critical – the most nat- ural (and difficult) being the Kullback-Leibler divergence. This means that any successful al- gorithm must produce hypotheses that assign a non-zero probability to every string. If what we are interested in is learning the underlying non- probabilistic concept then these hypotheses will be useless. We have elsewhere proved (Clark and Thollard, 2004) a suitable result similar to that of (Ron et al., 1995), bounding the diver- gence, but that proof involves some more elab- orate technical machinery. The second way is to consider a traditional concept-learning problem, but to restrict the class of distributions to some set that only gen- erates positive examples, and has some relation to the target concept. It is this latter possibility that we explore here. In the particular case of learning languages we will have an instance space of …

Content truncated to 500 words