Research Interests

Knowledge Discovery and Data Mining	Business Intelligence
Applied Machine Learning	Web Mining
Ensemble Methods	Constructive Learning Algorithms
Rules Induction	Neural Networks
Grammatical Inference	Online Learning

Dissertation

Constructive Learning: Inducing Grammars and Neural Networks

My dissertation research focuses on two broad areas of Machine Learning: Regular Grammar Inference -- learning a target regular grammar (or equivalently a DFA) from a set of labeled examples; and Constructive Neural Network Learning Algorithms -- techniques for incrementally constructing near minimal neural network topologies for pattern classification and inductive knowledge acquisition tasks.

Regular Grammar Inference

The problem of identifying the smallest deterministic finite state automaton (DFA) consistent with a given sample is known to be NP-complete. Efficient algorithms for exact identification of the target DFA assume that additional information is available to the learner. A structurally complete set of positive examples can be mapped to a lattice of finite state automata (FSA). This lattice represents the hypothesis space which can be searched with the help of a knowledgeable teacher who answers membership queries Explicitly enumerating the entire hypothesis space is practically infeasible. We have designed a version space based framework for implicitly representing the entire lattice by two sets of candidate FSA and for using a bi-directional search strategy to converge to the target.

In practical scenarios, the learner might be called upon to learn an approximation to the target DFA from an intermittent sequence of labeled examples and the teacher's responses to membership queries. Incremental (or on-line) algorithms that converge to the target in the limit are thus of interest. The IID is a polynomial time incremental algorithm for learning DFA. This algorithm maintains a current hypothesis which is guaranteed to be consistent with all examples seen by the learner up to that point and is guaranteed to converge to the target in the limit.

Probably Approximately Correct (PAC) learning of DFA is a hard problem in the sense that no known polynomial time algorithm exists for efficiently PAC learning DFA. The learnability of DFA under the uniform distribution or some restricted class of simple distributions was an open research question. We have answered this question in the affirmative by designing a framework for learning DFA from simple examples where the examples are drawn according to the universal distribution which in turn multiplicatively dominates a broad class of distributions called simple distributions.

Constructive Neural Network Learning Algorithms

Constructive neural network learning algorithms offer and attractive framework for incrementally growing networks of threshold logic units (TLU) for pattern classification and knowledge acquisition tasks. Constructive algorithms offer several advantages over traditional feed forward neural network algorithms such as the backpropagation in that they obviate the need for an ad-hoc a-priori choice of the network topology; they do not require the expensive error backward propagation; and they are guaranteed to converge to zero classification errors. The existing constructive learning algorithms are designed for two category pattern classification assuming that the patterns have binary/bipolar valued attributes. We have designed a unified framework for provably correct extension of these constructive learning algorithms to handle multiple output classes and real-valued attributes.

Constructive learning algorithms attain a parsimonious network topology by adding and training one or at most a small group of TLUs at a time. However, owing to the limited training time and the inherent representational bias of the network topology constructive algorithms often yield networks that are larger than necessary for the particular task. We have designed three elementary strategies for pruning redundant neurons in the MTiling constructive networks. Results of experiments with several real-world datasets demonstrate a significant to modest reduction in the network size without sacrificing the network's generalization capability. We are presently studying more powerful pruning strategies and cross-validation based training schemes that avoid over-fitting.

Knowledge-based neural networks incorporate prior domain knowledge into the initial network architecture. Network construction algorithms can grow networks to incrementally refine and augment the pre-specified domain knowledge. Constructive neural networks lend themselves readily to lifelong learning scenarios wherein the network is trained to gradually learn a group of related tasks over time. An adaptation of constructive learning algorithms to the knowledge-based and lifelong learning frameworks is currently being pursued.

Acknowledgements

This research was funded in part by the grants from the National Science Foundation (IRI-9409580 and IRI-9643299) and the John Deere Foundation to Dr. Vasant Honavar.

Research Publications

Click here to see my publications.