In the current version of the EUREKA system, we use C4.5 to induce a decision tree based on the training data. C4.5 has proven to be effective in predicting the strategy choices for these test domains. In addition, the output of the system is available as a symbolic rule base, which may allow the system developer to determine the factors that affect strategy selection for a given application domain.
Other machine learning approaches can also be used to perform strategy selection in the EUREKA system. To test the results of various existing approaches, we supplied the data from all of the 15 Puzzle classification experiments described in the previous section as input to to versions of C4.5, the ID3 decision tree induction algorithm [27], the CN2 sequential covering algorithm [7], a backpropagation neural net [31], a Bayesian classifier [5], and a majority-wins classifier. As with the other experiments, results are based on ten-fold cross-validation.
Table 14 shows that the decision tree algorithms performed best on this particular data set. Ultimately, the best machine learning algorithm in this context is the algorithm that consistently yields the best speedup. If we consider normalized problem speedups, the algorithm that produces the best classification on average will also produce the greatest speedup. We will continue to explore various machine learning methods to determine the approach that will work best for this type of application.