Efficient Optimization of Performance Measures by Classifier Adaptation

Nan Li, Ivor W. Tsang, Zhi-Hua ZhouIEEE TPAMI 2013 · OpenReview

TL;DR

This paper introduces CAPO, a two-step approach to efficiently train classifiers that optimize complex, domain-specific performance measures. CAPO first trains readily available "auxiliary" classifiers and then adapts them to the target performance metric, achieving better results and higher efficiency than existing methods, especially for nonlinear classifiers.

What Problem Does This Paper Address?

In real-world machine learning applications, it's often crucial to optimize performance measures that are specific to the problem domain. These measures, like F1-score or AUC, can be nonlinear and nonsmooth, making it difficult to directly train classifiers that optimize them. Traditional methods often train classifiers in isolation, which struggles with these complex performance metrics, especially when aiming for nonlinear classifiers. Existing methods like SVMperf can handle some performance measures but face computational challenges when extended to nonlinear cases. This paper aims to bridge this gap by proposing a method that leverages existing, efficient learning algorithms to build nonlinear classifiers that optimize these challenging performance measures.

Methods

The core of the proposed method is a two-step approach called CAPO (Classifier Adaptation for Performance measures Optimization).

  1. Train Auxiliary Classifiers: This step utilizes existing, off-the-shelf learning algorithms to train "auxiliary" classifiers. These can be any type of classifier (e.g., SVM, neural networks, decision trees) and are trained to optimize a general loss function, not necessarily the target performance measure. The key idea is that these auxiliary classifiers provide a good initial "guess" or approximation of the desired classifier.
  2. Adapt Auxiliary Classifiers: The trained auxiliary classifiers are then adapted to optimize the specific, concerned performance measure. This adaptation is framed as a classifier adaptation problem under a function-level adaptation framework. The authors show that this adaptation can be reduced to a quadratic programming problem, similar to linear SVMperf, which can be solved efficiently. This step essentially fine-tunes the auxiliary classifier to meet the specific performance goals.

CAPO can handle multiple auxiliary classifiers by forming an ensemble, balancing the weights of auxiliary classifiers and the adaptation delta function. The method also leverages feature augmentation to efficiently solve the adaptation problem, transforming it into a form solvable by a cutting-plane algorithm similar to linear SVMperf.

Datasets

The paper evaluates CAPO on five publicly available datasets:

  • IJCNN1: From the IJCNN 2001 neural network competition.
  • Mitfaces: A face detection dataset from CBCL at MIT.
  • Reuters: A text classification dataset for discriminating money-fx documents.
  • Splice: A DNA sequence dataset for recognizing splice junctions.
  • USPS*: A handwritten digit recognition dataset, classifying digits "01234" against "56789".

Key Insights and Ideas

  • Leveraging "Good Enough" Classifiers: Instead of directly tackling the hard problem of optimizing complex performance measures, CAPO uses readily available, efficient algorithms to train "good enough" auxiliary classifiers first. This simplifies the initial learning phase.
  • Adaptation as a Second Act: The real magic happens in the adaptation step. By framing the problem as adapting an existing classifier, CAPO can efficiently fine-tune it to achieve specific, often nonlinear, performance goals.
  • Nonlinearity from Auxiliary Classifiers: CAPO can generate nonlinear classifiers even if the adaptation (delta) function is linear, by using nonlinear auxiliary classifiers. This is crucial for many real-world applications where nonlinear decision boundaries are preferred.
  • Efficiency Through Approximation: The auxiliary classifiers act as approximations of the target classifier. This reduces the search space for the adaptation process, leading to significantly faster training times compared to methods that search the entire function space directly.
  • Flexibility: CAPO is a flexible framework that can accommodate various types of auxiliary classifiers and a wide range of performance measures, including those based on contingency tables and AUC.

Key Results

  • Performance Improvement: CAPO consistently achieved better performance than its auxiliary classifiers alone and often outperformed state-of-the-art methods like SVMperf and SVM with cost models, especially for nonlinear performance measures like F1-score and PRBEP. For example, on IJCNN1, CAPO* achieved a PRBEP of 0.8605, while SVMperf achieved only 0.6016.
  • Computational Efficiency: CAPO demonstrated significant speedups in training time, particularly for parameter selection. Kernelized nonlinear methods like SVMperf and SVMlight often failed to complete tasks within 24 hours, whereas CAPO methods were much faster. For instance, optimizing F1-score on Splice, CAPO* took 58.4 seconds, while SVMperf took over 10,000 seconds.
  • Robustness: CAPO was found to be robust to parameter choices (C and B) and scaled well with increasing training data size.
  • Ensemble Advantage: Using multiple diverse auxiliary classifiers (CAPO*) generally led to better performance and efficiency than using a single auxiliary classifier.

Limitations and Future Work

  • Linear Delta Function: The current CAPO implementation uses a linear delta function for adaptation. While effective, the authors suggest that exploring nonlinear delta functions could be a promising avenue for future work.
  • Auxiliary Classifier Specialization: Experiments suggest that using common, off-the-shelf classifiers as auxiliaries is sufficient, and specially designing auxiliary classifiers for the target performance measure might not offer significant superiority, especially considering the added cost of training them. However, this could be explored further.
  • Curriculum Learning: While CAPO shares similarities with curriculum learning by breaking down a complex task, it doesn't explicitly employ a curriculum learning strategy, which could be an area for future research.

Summary updated

Abstract

In practical applications, machine learning algorithms are often needed to learn classifiers that optimize domain specific performance measures. Previously, the research has focused on learning the needed classifier in isolation, yet learning nonlinear classifier for nonlinear and nonsmooth performance measures is still hard. In this paper, rather than learning the needed classifier by optimizing specific performance measure directly, we circumvent this problem by proposing a novel two-step approach called CAPO, namely, to first train nonlinear auxiliary classifiers with existing learning methods and then to adapt auxiliary classifiers for specific performance measures. In the first step, auxiliary classifiers can be obtained efficiently by taking off-the-shelf learning algorithms. For the second step, we show that the classifier adaptation problem can be reduced to a quadratic program problem, which is similar to linear $({\rm SVM}^{\rm perf})$ and can be efficiently solved. By exploiting nonlinear auxiliary classifiers, CAPO can generate nonlinear classifier which optimizes a large variety of performance measures, including all the performance measures based on the contingency table and AUC, while keeping high computational efficiency. Empirical studies show that CAPO is effective and of high computational efficiency, and it is even more efficient than linear $({\rm SVM}^{\rm perf})$.
BibTeX
@article{li2013efficient,
  author = {Nan Li and Ivor W. Tsang and Zhi-Hua Zhou},
  title = {{Efficient Optimization of Performance Measures by Classifier Adaptation}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2013},
  url = {https://openreview.net/forum?id=m5rNFHR-N-p},
}
Figure