Search diversification and backtracking strategies for DFA learning

Abstract

Many real world phenomena can be represented through some form of sequence or structure. Deterministic finite state automata (DFA) are very commonly used to represent language sequences in the area of inductive machine learning. State merging techniques use the concept of a DFA in order to learn the language sequences which the latter represents. There are various state merging algorithms which try to address the problem of learning. Two such algorithms are Evidence Driven State Merging (EDSM), proposed by Rodney Price in 1998 and Shared Evidence-Driven State Merging (S-EDSM) developed by Sandro Spina in 2004 as an improvement on the heuristic adopted by EDSM. These learning algorithms have been quite successful when compared to other state merging algorithms, but none of them has the ability to follow more than one path in the process of converging to the target automaton. Another limitation of these algorithms is that none of them can backtrack along a path if this path does not result in the optimal one. In this dissertation we are proposing a number of search diversification strategies whereby the DFA learning algorithms are induced into following more than one path for a particular learning problem. It is believed that this diversification of paths increases the probability of converging to the target language. A number of backtracking strategies are also proposed in this dissertation. The latter are incorporated into EDSM and S-EDSM for attempting to achieve better convergence results. The results obtained from this project show that the new heuristics developed for search diversification and backtracking are able to minimize the risk of converging to a target DFA which is not the optimal one.