A Sampling-Based Heuristic for Tree Search Applied to Grammar Induction

In the field of OperationResearchand Artificial Intelligence, several stochastic searchalgorithms have been designed based on the theory of global random search (Zhigljavsky 1991). Basically, those techniquesiteratively samplethe searchspacewithrespect to a probability distribution whichis updatedaccording to the result of previous samplesand somepredefined strategy. Genetic Algorithms(GAs)(Goldberg 1989) or Greedy RandomizedAdaptive Search Procedures (GRASP) (Feo 8z Resende1995) are particular instancesof this paradigm. In this paper, wepresent SAGE, a search algorithm based on the same fundamentMmechanisms as those techniques. However, it addressesa class of problemsfor which it is difficult to designtransformation operators to performlocal searchbecauseof intrinsic constraintsin the definition of the problemitself. For those problems, a proceduralapproachis the natural wayto construct solutions, resultingin a state spacerepresented as a tree or a DAG. Theaimof this paper is to describe the underlying heuristics used bySAGE to addressproblemsbelongingto that class. Theperformance of SAGE is analyzed on the problemof grammar inductionand its successfulapplication to problems from the recent AbbadingoDFA learning competition is presented.

Authors

• Hugues Juillé Jordan B. Pollack

Keywords

No keywords are indexed for this paper.