Ets learning of kernel languages
Lev Goldfarb, John Abela · 2003
The Evolving Transformations Systems (ETS) model is a new inductive learning model proposed by Goldfarb in 1990. The development of the ETS model was motivated by need for the unification of the two competing approaches that model learning - numeric (vector space) and symbolic. This model provides a new method for describing classes (or concepts) and also a framework for learning classes from a finite number of positive and negative training examples. In the ETS model, a class is described in terms of a finite set of weighted transformations (or operations) that act on members of the class. This thesis investigates the ETS learning of kernel languages. Kernel languages, first proposed by Goldfarb in 1992, are a subclass of the regular languages. A kernel language is specified by a finite number of weighted transformations (string rewrite rules) and a finite number of string called the kernels. One of the aims of this thesis is to show the usefulness and versatility of using distance, induced by the transformations, for both the class description of formal languages and also for directing the learning process. To this end, the author adopted a pragmatic approach and designed and implemented a new ETS learning algorithm—Valletta. Valletta learns multiple-kernel languages, with both random and misclassification noise, and has a user-defined inductive bias. This allows the user to indicate which ETS hypotheses (descriptions) are preferred over others. Valletta always finds an ETS language description that is consistent with the training examples—if one exists. Since ETS is a new model, few tools were available. A number of new tools were therefore purposely developed for this thesis. These include a string-edit distance function, Evolutionary Distance, a technique for reducing strings to their normal forms modulo a non-confluent string rewriting system, new refined formal definitions of transformations system (TS) descriptions of formal languages, and a distance-driven search technique for Valletta's search engine. The usefulness of Valletta is demonstrated on a number of examples of learning kernel languages. Valletta performed very well on all the datasets and always converged to the correct class description in a reasonable time. (Abstract shortened by UMI.)