Inductive learning with the evolving tree transformation system
Virendrakumar C. Bhavsar, Lev Goldfarb, Vithal N. Kamat · 1996
Inductive learning is one of the more difficult problems in artificial intelligence. Here, inductive learning is treated as an optimization process, the (last) state of generalization of which is characterized by the discovery of the class concept. The role of the structure inherently present, both, in the objects and the class concept has been underplayed in much of the learning tasks today. This thesis attempts to highlight the importance of structure in representation by generating a new ordered labeled (symbolic) tree representation and in learning by using these trees in a new learning machine (LM) based on the Evolving Tree Transformation System (ETTS) model. The ETTS model is an adaptation of the general inductive learning model called by Goldfarb an Evolving Transformation System (ETS), to an environment in which objects are represented as trees. The central concept of the ETTS model is a tree distance function that is defined on a set of ordered labeled trees in terms of weighted generalized edit operations. Transformation of one tree into another is made possible through these operations. An edit operation along with its weight is called a feature. A class concept is an optimal set of features that give suitable distances for the best class separation measured in terms of an optimization function. An ETTS model based LM that can perform handwritten character recognition has been designed. The LM consists of two main algorithms--a generalized edit operations based tree Distance Algorithm (DA) and a Learning Algorithm (LA). A reprocessing algorithm has also been developed that accepts handwritten characters and feeds symbolic trees to the LM. The symbolic trees are isomorphic to (preserve the structure of) the characters unlike many other representations. A dynamic programming styled DA that runs in polynomial time and space and that is amenable to parallelization has been built. The generalized edit operations in DA refer to elementary operations that operate on a single node and also to macro operations that operate on multiple node subtrees. The nature of the optimization function is studied to build a simple and reliable LA that essentially optimizes weights and builds new features. The role of weights and the need for optimizing weights associated with the tree edit operations is fully realized in this thesis for the first time. The process of building new macro features (consisting of macro operations) and adding them to the earlier set of features is own to give the class concept if the earlier set is incapable of doing so. The LA is shown to successfully learn with small training sets. The unification of the discrete (symbolic) tree structure with the continuous weights gives the concept the ability to describe the class in a compact and powerful form. The weights in the concept provides the necessary robustness and noise tolerance. The symbolic tree structure in the concept provides the necessary descriptive power to communicate in language that the external agent understands. By storing the concept rather than the instances of a class, the LM is shown to achieve parsimony in storage space and retrieval time.