An analysis of the EDSM heuristic for DFA learning.

Abstract

In the area of Grammatical Inference, it is often desirable to model real world phenomena using some syntactic structure. In Machine Learning, languages are sometimes represented using Deterministic Finite State Automata (DFA). State-merging techniques can then be used by learning algorithms, in order to inductively learn a target language from a finite set of examples. Various DFA Learning Algorithms have been proposed over the years, the most successful one being the Evidence Driven State Merging (EDSM) algorithm (Price, 1998). Despite the fact that this algorithm was the first one to successfully solve most of the Abbadingo One DFA Learning Competition problems, some remain unsolved to this very day. EDSM makes use of a heuristic, which guides the state merging process, in order to try to infer the target DFA from a set of training examples. However, this heuristic rarely works well when the training sets are sparse. Over the years, a number of variations to the EDSM heuristic have been proposed, such as the Shared Evidence Driven State Merging (S-EDSM) algorithm (Spina, 2004), in an attempt to improve the algorithm's performance in such situations. Although some of these variations give better results than EDSM, they still fail to solve the remaining Abbadingo One problems. Despite EDSM's success, this algorithm is still not sufficiently well understood and investigated. Unfortunately, very little research about this algorithm has been carried out to date. In this study, the EDSM heuristic, therefore, is investigated in an attempt to better understand its behaviour. By identifying trends and patterns in the EDSM heuristic, one can better understand why and when EDSM fails. These observations can then guide the development of better EDSM variations, which would be based on evidence and not only intuition.