Apprentissage de sphères maximales d’exclusion avec garanties théoriques

Guillaume Metzler, Xavier Badiche, Brahim Belkasmi, Stéphane Canu, Élisa Fromont, Amaury Habrard, Marc SebbanHAL 2017

TL;DR

This paper introduces ME2, a novel algorithm for learning "exclusion spheres" to identify minority class data points in highly imbalanced datasets. ME2 offers theoretical guarantees on its performance and demonstrates superior results on challenging datasets where traditional methods falter.

What Problem Does This Paper Address?

Machine learning often struggles with imbalanced datasets, where one class (the majority) vastly outnumbers another (the minority). Standard algorithms, aiming to minimize overall error, tend to ignore the minority class, leading to poor detection rates. This is a critical issue in fields like fraud detection or medical anomaly identification, where missing minority class instances has significant consequences. Existing solutions like over/under-sampling or ensemble methods have limitations. This paper tackles the challenge of learning effective models for imbalanced data by proposing a method that learns local "exclusion spheres" centered on minority class examples, designed to exclude majority class examples.

Methods

The core of the proposed method, ME2 (Maximum Excluding Ellipsoids), is inspired by Support Vector Data Description (SVDD). Instead of learning a single ball to encompass all data, ME2 learns multiple local models. Each local model is an ellipsoid centered on a minority class example, aiming to "exclude" majority class examples. A key innovation is the use of metric learning to learn a Mahalanobis distance, allowing for ellipsoids that can adapt their shape and orientation. This is achieved by learning a positive semi-definite matrix M, which projects data into a new space. The algorithm is formulated as an optimization problem with theoretical guarantees on stability and generalization, derived using uniform stability frameworks.

Datasets

The paper evaluates ME2 on seven real-world imbalanced datasets from the UCI and KEEL databases. These datasets vary in their imbalance ratios, with the rate of positive examples ranging from 0.76% to 10.9%.

Key Insights and Ideas

  • Local Exclusion Spheres: The idea of learning local models (ellipsoids) for each minority class instance, rather than a global model, is crucial for handling complex data distributions and high imbalance.
  • Metric Learning for Ellipsoids: By learning a Mahalanobis distance (via matrix M), ME2 can adapt the shape and orientation of the exclusion regions, allowing them to better fit the data's local geometry compared to simple spheres.
  • Theoretical Guarantees: Providing theoretical guarantees on uniform stability and generalization is a significant contribution, offering confidence in the algorithm's robustness.
  • Performance on Highly Imbalanced Data: ME2 shines on datasets with very low minority class representation, where other methods fail to detect any positive instances.

Key Results

ME2 demonstrates superior performance on highly imbalanced datasets, achieving the best F-Measure scores on five out of seven tested datasets. Specifically, on datasets with a low rate of positive examples (less than 2%), ME2 significantly outperforms other methods, including random forests and support vector machines, which often fail to detect any positive instances. While ME2 is slightly less effective on datasets with higher positive rates (e.g., Yeast3, Abalone), it still shows competitive results.

Limitations and Future Work

The paper acknowledges that ME2's performance can be slightly less effective on datasets with higher positive class rates compared to simpler methods. The authors suggest future work could explore combining multiple ellipsoids to improve predictions and further investigate the theoretical link between the learned metric/radius and the generalization error of nearest neighbor classifiers.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{metzler2017apprentissage,
  author = {Guillaume Metzler and Xavier Badiche and Brahim Belkasmi and Stéphane Canu and Élisa Fromont and Amaury Habrard and Marc Sebban},
  title = {{Apprentissage de sphères maximales d’exclusion avec garanties théoriques}},
  booktitle = {HAL},
  year = {2017},
}
Figure