Artificial Intelligence Research Laboratory Department of Computer Science Iowa State University

Automata Induction, Grammar Inference, and Language Acquisition
   Personnel   Project Summary   Funding   Publications   Additional Information   Projects   AI Lab  

• Dr. Vasant Honavar, Principal Investigator.
• Dr. Rajesh Parekh, Former Ph.D. Student.
• Mr. Codrin Nichitiu , Visiting Researcher (from ENS Lyon, France).

Project Summary

Grammatical Inference, variously refered 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 modelling, prediction, natural language acquisition, data mining and knowledge discovery.

Regular grammars are the simplest class of formal grammars in the Chomsky hierarrchy. An understanding of the issues and problems encountered in learning regular languages (or equivalently, identification of the corresponding DFA) are therefore likely to provide insights into the problem of learning more general classes of languages. Consequently, regular grammar inference from examples has received a great deal of attention in theoretical computer science, machine learning, syntactic pattern recognition, computational learning theory, and grammar inference communities.

Exact learning of the target DFA from an arbitrary presentation of labeled examples is a hard problem. Gold showed that the problem of identifying the minimum state DFA consistent with a presentation S comprising of a finite non-empty set of positive examples S+ and possibly a finite non-empty set of negative examples S- is NP-hard. Under the standard complexity theoretic assumption P not equal to 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. In the face of these negative results, efficient learning algorithms for identification of DFA assume that additional information is provided to the learner. Trakhtenbrot and Barzdin described a polynomial time algorithm for constructing the smallest DFA consistent with a complete labeled sample i.e., a sample that includes all strings up to a particular length and the corresponding label that states whether the string is accepted by the target DFA or not. The regular positive and negative inference (RPNI) algorithm identifies in time that is polynomial in the sum of lengths of the examples, a DFA that is consistent with the given sample S. Further, as shown by Oncina and Garcia, if S is a superset of a characteristic set for the target DFA (which roughly means that each state transition is sampled at least once in some sample) then the DFA output by the RPNI algorithm is guaranteed to be equivalent to the target.

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. Using a variant of Trakhtenbrot and Barzdin's algorithm, Lang empirically demonstrated that random DFAs are approximately learnable from a sparse uniform sample. However, exact identification of the target DFA was not possible even in the average case with a randomly drawn training sample. Several efforts have been made to study the learnability of concept classes under restricted classes of distributions. Li and Vitanyi proposed a model for PAC learning with simple examples called the simple PAC model wherein the class of distributions is restricted to simple distributions (wherein examples are drawn according to the Universal distribution where strings with low Kolmogorov complexity are sampled with a high probability).

Our work has shown (among other things) that the class of DFA that have low Kolmogorov complexity are efficiently learnable if samples are drawn according to the Universal distribution. Some directions that are currently being explored include: efficient algorithms for learning interesting subclasses of grammars; application of grammar inference to characterizing macromolecular sequence families (DNA, RNA, and protein sequences), and incremental grammar induction.

Funding

• Constructive Neural Network Learning Algorithms for Pattern Classification, National Science Foundation, (1994-1999). Vasant Honavar. $111,537 (plus $10,000 in matching funds).
• Integrated Intelligent Diagnosis and Advisory Systems - Analysis, John Deere Foundation, 1995-1996. Vasant Honavar. $15,000.
• Grant, Integrated Intelligent Diagnosis Systems, John Deere Foundation, 1996-1998. Vasant Honavar. $15,000.

Publications

• Honavar, V. and Slutzki, G. (1998) (Ed.). Proceedings of the Fourth International Colloquium on Grammatical Inference. (LNCS Vol. 1433). Berlin: Springer-Verlag.
• Parekh, R. & Honavar, V. (2000). Automata Induction, Grammar Inference, and Language Acquisition. Invited chapter. In: Handbook of Natural Language Processing. Dale, Moisl & Somers (Ed). New York: Marcel Dekker. In press.
• Parekh, R. and Honavar, V. (2000). Learning DFA from Simple Examples. Machine Learning In press.
• 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.
• Parekh, R., Nichitiu, C., and Honavar, V. (1998). A Polynomial Time Incremental Algorithm for Learning DFA. In: Proceedings of the Fourth International Colloquium on Grammatical Inference (ICGI'98), Ames, IA. Lecture Notes in Computer Science vol. 1433 pp. 37-49. Berlin: Springer-Verlag.
• Parekh, R.G. and Honavar, V. (1997) Learning DFA from Simple Examples. In: Proceedings of the International Workshop on Algorithmic Learning Theory. (ALT 97). Sendai, Japan. Lecture notes in Computer Science. Vol. 1316 pp. 116-131.
• Parekh, R. and Honavar, V. (1996). An Incremental, Interactive Algorithm for Regular Grammar Inference In: Proceedings of the Third International Colloquium on Grammar Inference (ICGI'96), Montpellier, France. September 24-27, 96. Lecture Notes in Computer Science, Springer-Verlag, vol. 1147, pp. 238-250.
• Parekh, R.G. (1998). Constructive Learning: Inducing Grammars and Neural Networks. Doctoral Dissertation. Department of Computer Science, Iowa State University.

© Vasant Honavar, 1999.