Joint Analysis of Multiple Algorithms and Performance Measures

Cassio P. de Campos, Alessio Benavoli

Introduction

In machine learning research, evaluating whether one algorithm is "better" than another is rarely straightforward. Performance is often multidimensional, involving trade-offs between accuracy, computational speed, and model complexity. Traditionally, researchers have relied on univariate statistical tests like the Wilcoxon signed-rank test, applying them to each metric individually. However, this approach suffers from the "multiple comparisons" problem and fails to capture the dependencies between different performance measures.

The Challenge of Multi-Metric Evaluation

When metrics are at odds—for instance, when a new algorithm is more accurate but significantly more complex—researchers often resort to ad-hoc solutions like weighted sums or Pareto optimality. These methods lack statistical rigor or are difficult to evaluate formally.

Table 1: Comparison of accuracy and complexity across multiple datasets, illustrating the trade-offs inherent in algorithm evaluation.

Proposed Methodology

The authors introduce a framework for the joint analysis of multiple criteria based on "dominance statements." These statements are vectors indicating whether Algorithm B outperformed Algorithm A across $m$ different measures.

1. Generalized Likelihood Ratio Test (GLRT)

A frequentist approach that evaluates whether a specific dominance pattern is significantly more prevalent than others in the observed data.

2. Bayesian Test

Utilizes a multinomial-Dirichlet conjugate prior to estimate the posterior probability of various dominance orderings between algorithms.

3. Bayesian Network (BN) Integration

The core innovation of this work is the use of Bayesian Networks to model the conditional dependencies between performance metrics. By identifying redundancies (e.g., the relationship between Accuracy and F-measure), the BN "prunes" the model. This reduction in parameters allows the statistical tests to remain reliable even with the small sample sizes typical of machine learning datasets.

Experimental Validation

The framework was tested using synthetic data to generate ROC curves and real-world data from 80 classification datasets in the WEKA repository. The study compared six classifiers (AODE, Bayesian Network, Naive Bayes, J48graft, Random Forest, and Logistic Regression) across three metrics: Accuracy, F-measure, and Weighted-AUC.

Key Findings

  • Increased Statistical Power: The joint analysis framework can identify a statistically significant winner even when individual univariate tests are inconclusive. By considering the consistency of performance across all metrics, the joint test gains more "power."
  • Unit-Agnostic Comparison: By focusing on the sign of the difference between metrics rather than their absolute values, the method avoids the difficulties of normalizing disparate units (e.g., milliseconds vs. percentages).
  • Efficiency via BN: Modeling metric dependencies with Bayesian Networks significantly improved the performance of the Bayesian test, allowing it to achieve higher AUC in synthetic trials compared to the GLRT.

Conclusion and Future Work

This research provides a robust statistical foundation for comparing machine learning algorithms across multiple performance dimensions. While the current approach faces computational challenges as the number of algorithms increases, it offers a more nuanced and powerful alternative to traditional single-metric testing. Future research will explore learning "spaces of orderings" to handle larger sets of algorithms and further investigate how BN structures can reveal fundamental relationships between different performance measures.

Summary updated

Abstract

There has been an increasing interest in the development of new methods using Pareto optimality to deal with multi-objective criteria (for example, accuracy and time complexity). Once one has developed an approach to a problem of interest, the problem is then how to compare it with the state of art. In machine learning, algorithms are typically evaluated by comparing their performance on different data sets by means of statistical tests. Standard tests used for this purpose are able to consider jointly neither performance measures nor multiple competitors at once. The aim of this paper is to resolve these issues by developing statistical procedures that are able to account for multiple competing measures at the same time and to compare multiple algorithms altogether. In particular, we develop two tests: a frequentist procedure based on the generalized likelihood ratio test and a Bayesian procedure based on a multinomial-Dirichlet conjugate model. We further extend them by discovering conditional independences among measures to reduce the number of parameters of such models, as usually the number of studied cases is very reduced in such comparisons. Data from a comparison among general purpose classifiers are used to show a practical application of our tests.
BibTeX
@article{campos2017joint,
  author = {Cassio P. de Campos and Alessio Benavoli},
  title = {{Joint Analysis of Multiple Algorithms and Performance Measures}},
  journal = {New Gener. Comput.},
  year = {2017},
  doi = {10.1007/s00354-016-0005-8},
}
Figure