Topics in Grammatical Inference and Computational Learning Theory

 

Personnel

Dr. Vasant Honavar, Professor of Computer Science and of Bioinformatics and Computational Biology, Principal Investigator

 

Summary

Grammatical Inference, variously referred to as automata induction, grammar induction, and automatic language acquisition, refers to the process of learning of grammars and languages from data. Machine learning of grammars finds a variety of applications in syntactic pattern recognition, adaptive intelligent agents, diagnosis, computational biology, systems modeling, prediction, natural language acquisition, data mining and knowledge discovery. Regular grammars are the simplest class of formal grammars in the Chomsky hierarchy. An understanding of the issues and problems encountered in learning regular languages (or equivalently, identification of the corresponding deterministic finite automaton (DFA)) are therefore likely to provide insights into the problem of learning more general classes of languages. Under the standard complexity theoretic assumption P ¹ NP, Pitt and Warmuth showed that no polynomial time algorithm can be guaranteed to produce a DFA that has approximately the same number of states as the target DFA from a set of labeled examples corresponding to a DFA. When examples are drawn at random (as in the PAC setting), results proved by Kearns and Valiant suggest that an efficient algorithm for learning DFA would entail efficient algorithms for solving problems such as breaking the RSA cryptosystem, factoring Blum integers, and detecting quadratic residues, all of which are known to be hard under standard cryptographic assumptions.

Against the background of strong negative results we investigated the feasibility of learning regular languages from examples under additional assumptions concerning the distribution from which the examples are drawn, thereby addressing the problem posed by Pitt, in his seminal paper: Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution? We showed that:

• The class of simple DFA (i.e., DFA whose canonical representations have logarithmic Kolmogorov complexity) is efficiently PAC learnable under the Solomonoff Levin universal distribution (Parekh and Honavar, 1999)
• If the examples are sampled at random according to the universal distribution by a teacher that is knowledgeable about the target concept, the entire class of DFA is efficiently PAC learnable under the universal distribution, that is, DFA are efficiently learnable under the PACS Model (Parekh and Honavar, 1999; Parekh and Honavar, 2001)
• Any concept that is learnable under Gold’s model for learning from characteristic samples, Goldman and Mathias’ polynomial teachability model, and the model for learning from example based queries is also learnable under the PACS model (Parekh and Honavar, 2000; 2001).

 

 

Representative Publications

1. Parekh, R. and Honavar, V. (1999). Simple DFA are Polynomially Probably Exactly Learnable from Simple Examples. In: Proceedings of the International Conference on Machine Learning. Bled, Slovenia.

2. Parekh, R. and Honavar, V. (2001). DFA Learning from Simple Examples. Machine Learning. Vol. 44. pp. 9-35