Active Algorithm Selection

Feilong Chen, Rong JinAAAI 2007 · OpenReview

Abstract

Most previous studies on active learning focused on the problem of model selection, i.e., how to identify the optimal classification model from a family of predefined models using a small, carefully selected training set. In this paper, we address the problem of active algorithm selection. The goal of this problem is to efficiently identify the optimal learning algorithm for a given dataset from a set of algorithms using a small training set. In this study, we present a general framework for active algorithm selection by extending the idea of the Hedge algorithm. It employs the worst case analysis to identify the example that can effectively increase the weighted loss function defined in the Hedge algorithm. We further extend the framework by incorporating the correlation information among unlabeled examples to accurately estimate the change in the weighted loss function, and Maximum Entropy Discrimination to automatically determine the combination weights used by the Hedge algorithm. Our empirical study with the datasets of WCCI 2006 performance prediction challenge shows promising performance of the proposed framework for active algorithm selection.

Introduction

In traditional active learning, the primary objective is typically active model selection: identifying the best parameters for a specific algorithm (e.g., an SVM) by strategically labeling data points. However, in real-world scenarios, practitioners often face a more fundamental question: which type of algorithm is most suitable for a novel dataset? Choosing between a Decision Tree, a Neural Network, or a Naive Bayes classifier is a critical step that usually requires extensive labeled data.

The challenge lies in the high cost of data labeling. We aim to identify the optimal algorithm from a diverse ensemble of candidates without labeling the entire dataset. Existing methods like Query-by-Committee (QBC) often treat all algorithms as equally important, which is counter-intuitive when the ultimate goal is to distinguish a single superior "winner."

Methodology: The MaxMin Framework

The authors propose a MaxMin Framework for active algorithm selection, integrating several advanced components:

  • Hedge Algorithm Extension: The system maintains and updates weights for each candidate algorithm based on their performance on labeled data, similar to the Hedge algorithm's "expert" opinion model.
  • MaxMin Strategy: To select the next example for labeling, the framework identifies the data point that maximizes the "weighted loss" of the ensemble, regardless of the true label. This strategy prioritizes points that challenge the current leading algorithms.
  • Example Correlation: By incorporating a correlation matrix, the framework estimates the information gain of labeling a point relative to other unlabeled points, preventing redundant labeling of similar instances.
  • Maximum Entropy Discrimination (MED): This component replaces fixed "punishment" factors for algorithmic errors with dynamic factors calculated based on example difficulty. This allows for aggressive weight shifts in early learning stages and stability as the best algorithm emerges.

Experimental Results

The framework was evaluated using three datasets from the WCCI 2006 Performance Prediction Challenge: HIVA (drug discovery), ADA (marketing/census), and GINA (digit recognition). These were tested against a pool of ten distinct machine learning algorithms.

Speed of Discovery

The primary metric for efficiency was the "Critical Number"—the minimum number of labeled examples required for the best algorithm's weight to exceed 0.9, indicating high confidence in its superiority. As shown in the table below, the proposed MED+Correlation method significantly reduces the number of labels needed to identify the optimal algorithm compared to random selection or majority voting.

Table showing the number of labeled examples required to identify the best algorithm (Critical Number).

Classification Accuracy

Beyond identifying the winner faster, the framework also achieves superior classification accuracy. By the end of the labeling process, the MED+Correlation method reached significantly higher accuracy across all datasets, such as 94.6% on the HIVA dataset.

Table comparing classification accuracy across different selection methods and datasets.

Key Insights and Conclusion

  • Dynamic Punishment: The use of MED to vary the punishment factor proved crucial. As learning progressed, the punishment for errors became less severe, preventing late-stage outliers from prematurely dethroning consistent performers.
  • Global Informativeness: Incorporating example correlation consistently improved performance, demonstrating that informativeness is a global property of the dataset rather than a purely local one.

The proposed framework demonstrates that active algorithm selection can be performed much more efficiently than standard random sampling. By focusing on identifying the "winner" through weighted ensembles and dynamic error punishment, the system achieves high accuracy with minimal labeled data. Future work will address scenarios where multiple algorithms perform similarly or where the performance gap between the top candidates is marginal.

Summary updated

Abstract

Most previous studies on active learning focused on the problem of model selection, i.e., how to identify the optimal classification model from a family of predefined models using a small, carefully selected training set. In this paper, we address the problem of active algorithm selection. The goal of this problem is to efficiently identify the optimal learning algorithm for a given dataset from a set of algorithms using a small training set. In this study, we present a general framework for active algorithm selection by extending the idea of the Hedge algorithm. It employs the worst case analysis to identify the example that can effectively increase the weighted loss function defined in the Hedge algorithm. We further extend the framework by incorporating the correlation information among unlabeled examples to accurately estimate the change in the weighted loss function, and Maximum Entropy Discrimination to automatically determine the combination weights used by the Hedge algorithm. Our empirical study with the datasets of WCCI 2006 performance prediction challenge shows promising performance of the proposed framework for active algorithm selection.
BibTeX
@inproceedings{chen2007active,
  author = {Feilong Chen and Rong Jin},
  title = {{Active Algorithm Selection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=S1ZRTplObr},
}
Figure