TL;DR
This paper introduces a novel approach to combine multiple machine learning classifiers using Data Envelopment Analysis (DEA). They demonstrate that DEA can effectively extend the ROC convex hull method to handle multi-class classification problems, outperforming traditional model combination techniques.
What Problem Does This Paper Address?
Combining multiple machine learning models, often referred to as ensemble methods, is a well-established technique to improve classification performance. However, many existing methods for model combination are ad-hoc, lacking a principled way to determine which models to combine and how to weight their contributions. While Receiver Operating Characteristic (ROC) analysis has been proposed for model combination, it's primarily limited to two-class (binary) classification problems. The challenge is to develop a robust and principled method for combining classifiers that can handle the more general case of multi-class problems.
Methods
The core of this paper is the application of Data Envelopment Analysis (DEA) to model combination. DEA is a linear programming technique used to measure the efficiency of decision-making units (DMUs) based on their inputs and outputs.
- Equivalence with ROC for Binary Classification: The authors first prove that for two-class problems, the convex hull identified by ROC analysis (ROCCH) is equivalent to the efficient frontier identified by DEA. They model a classifier as a DMU, with the false positive rate (FP) as input and the true positive rate (TP) as output.
- Extension to Multi-Class Classification: For k-class problems, the paper proposes a DEA formulation where the confusion matrix of a classifier is used. The off-diagonal elements (misclassifications) are treated as inputs, and the diagonal elements (correct classifications) are treated as outputs.
- Efficient Models Only (EMO) Approach: Based on the DEA efficiency scores, the authors propose a method called "Efficient Models Only" (EMO). This approach selects only the classifiers identified as "efficient" by the DEA model (those on the efficient frontier) and then uses a majority voting scheme among these selected models to make the final prediction. This method aims to systematically determine the number of models to combine based on their efficiency.
Datasets
The authors evaluated their approach on 20 datasets:
- 13 datasets from the UCI Repository of Machine Learning Databases, commonly used in machine learning and data mining.
- 7 web usage datasets from a market data vendor, used to predict online customer purchases.
These datasets were divided into in-sample (training) and out-of-sample (testing) sets. The paper does not introduce new benchmarks but compares its proposed method against standard un-weighted average (UWA) and variance-based weighting (VBW) methods.
Key Insights and Ideas
- DEA as a Unifying Framework: The paper elegantly demonstrates that DEA can serve as a unifying framework for model combination, bridging the gap between ROC analysis for binary classification and extending it to multi-class scenarios.
- Principled Model Selection: The EMO approach offers a principled way to select which models to combine, moving beyond ad-hoc heuristics. By focusing on "efficient" models, it leverages more information from the confusion matrix than traditional error metrics.
- Endogenous Determination of Ensemble Size: The EMO method automatically determines the number of models to include in the ensemble based on their DEA efficiency scores, which is a significant advantage over methods that require manual selection of ensemble size.
- Improved Performance with Fewer Models: The results suggest that combining only the efficient models can lead to better performance even when using a significantly smaller subset of the available classifiers.
Key Results
The proposed EMO method, which combines only the DEA-identified efficient models, outperformed two benchmark methods (UWA and VBW) on 13 out of 20 datasets in terms of out-of-sample mean squared error (MSE). The average MSE for EMO was 0.188, compared to 0.197 for UWA and 0.196 for VBW. Notably, EMO achieved this superior performance by using an average of 8.8 models in combination, compared to an average of 25.4 models used by the benchmark methods.
Limitations and Future Work
- Limitations: The paper acknowledges that the choice of DEA model (specifically the BCC model with VRS) influences the results. While they argue for its suitability, other DEA models might yield different outcomes. The computational cost of running DEA for a large number of classifiers on large datasets could also be a consideration.
- Future Work: The authors plan to further investigate different weighting schemes within the DEA framework and explore using DEA to combine multiple models learned from a single classifier. They also suggest studying additional weighting schemes and using the method to combine multiple models learned from a given classifier.
Summary updated