Using active testing and meta-level information for selection of classification algorithms

The problem of selecting the best classification algorithm for a specific problem continues to be very relevant, especially since the number of classification algorithms keeps growing significantly. Testing all alternatives is not really a viable option: if we compare all pairs of algorithms, as is often advocated, the number of comparisons grows exponentially. To avoid this problem we suggest a method referred to as active testing, whose aim is to reduce the number of comparisons by carefully selecting which tests should be carried out. This method uses meta-knowledge concerning past experiments and proceeds in an iterative manner. It takes the form of a competition in which, in each iteration, the candidate best algorithm is pitted against its most promising competitor. The winner proceeds to the next round, while the loser is removed from consideration. To speed up the process of testing each pair of competitors on new datasets, we use a fast method that exploits meta-information on partial learning curves measured on prior datasets to predict which algorithm is better. We stop when there are no more viable competitors. This method was evaluated in a leave-one-out fashion, and results show that it is indeed effective in determining the best algorithm using a limited number of tests.nrpages: 8status: publishe