Multithreshold Entropy Linear Classifier

Wojciech Marian Czarnecki, Jacek Tabor

TL;DR

This paper introduces the Multithreshold Entropy Linear Classifier (MELC), a novel approach that extends linear classification by using multiple parallel hyperplanes. MELC leverages information theory concepts like Renyi's quadratic entropy and Cauchy-Schwarz divergence to build classifiers that aim to maximize balanced accuracy metrics, offering a more nuanced approach than traditional accuracy maximization.

What Problem Does This Paper Address?

Traditional linear classifiers, like Support Vector Machines (SVMs), use a single hyperplane to separate data. While effective, this approach can struggle with linearly non-separable datasets (e.g., XOR-like patterns) where a single decision boundary is insufficient. To address this, kernel methods are often employed, but they can increase complexity. This paper tackles the challenge of improving linear classification for complex data by introducing a multithreshold linear classifier. This means instead of one decision boundary, the classifier uses multiple parallel hyperplanes to partition the data, allowing for more intricate decision boundaries within a linear projection framework. The authors also highlight a common limitation of many classifiers: optimizing for raw accuracy, which can be misleading in imbalanced datasets. They propose optimizing for balanced quality measures instead.

Methods

The core of MELC lies in its novel construction method. Instead of directly finding a separating hyperplane, MELC first projects the data onto a one-dimensional line using a learned projection vector v. Then, it estimates the probability density of the projected data for each class. The key innovation is using Renyi's quadratic entropy and Cauchy-Schwarz divergence from information theory to guide the selection of the projection vector v.

Specifically:

  • Renyi's Quadratic Entropy: This measure helps to condense the data distribution for each class.
  • Cauchy-Schwarz Divergence: This divergence is used as the primary objective function to maximize. It's shown to be scale-invariant and related to maximizing margins.
  • Optimization: The authors propose a gradient-based optimization approach to find the optimal projection vector v. They also demonstrate that this method is related to large-margin classifiers like SVMs but can handle more complex hypotheses.
  • Multithreshold Nature: The decision boundary is formed by multiple intervals on the projected line, determined by the density estimations of the projected data.

Datasets

The authors evaluated MELC on:

  • UCI Binary Datasets: Ten well-known binary datasets were used, including "australian," "breast cancer," "diabetes," "fourclass," "german number," "heart," "ionosphere," "liver-disorders," "sonar," and "splice."
  • Cheminformatics Data: Ten datasets related to predicting chemical compound activity for specific proteins were used. These datasets represent molecules using fixed-length bit sequences based on SMARTS patterns.

Key Insights and Ideas

  • Beyond Single Hyperplanes: MELC demonstrates that extending linear classification with multiple parallel hyperplanes can significantly improve performance on complex, non-linearly separable data, without resorting to computationally expensive kernel methods.
  • Information Theory as a Guide: The paper elegantly shows how information-theoretic measures like Renyi's entropy and Cauchy-Schwarz divergence can be effectively used to construct powerful classifiers, providing a strong theoretical foundation.
  • Maximizing Balanced Accuracy: By optimizing for balanced metrics like Matthew's Correlation Coefficient (MCC) and Weighted Accuracy (WAC) instead of raw accuracy, MELC is better suited for imbalanced datasets, a common issue in real-world applications.
  • Interpretable Projections: The learned projection vector v provides insights into the data's structure, potentially revealing underrepresented classes or features that are crucial for classification.
  • Regularization through Entropy: The entropy terms in the objective function act as a natural regularizer, helping to control the number of thresholds and prevent overfitting, a common pitfall in multithreshold models.

Key Results

  • Competitive Performance: MELC achieved comparable or superior results to SVMs (including class-balanced SVMs) on most UCI datasets in terms of WAC and MCC. It outperformed SVMs on datasets like "liver-disorders," "fourclass," and "diabetes."
  • Improved Cheminformatics Prediction: On cheminformatics tasks, MELC showed competitive performance and, importantly, provided better insights into data geometry, potentially identifying underrepresented compound classes.
  • Reduced Model Complexity: Despite its multithreshold nature, MELC often produced models with a small number of thresholds, especially when regularization was applied, making them computationally efficient. For example, in nine out of ten UCI datasets, MELC built a single-threshold model.
  • XOR Dataset Success: On a challenging XOR-like dataset, MELC achieved nearly 100% accuracy, significantly outperforming linear models (perceptron and SVM) which achieved at most 50% accuracy.

Limitations and Future Work

  • Computational Complexity: The authors acknowledge that the optimization process for MELC can be computationally expensive, especially for high-dimensional data. They suggest that efficient optimization remains an open research question.
  • Local Optima: The gradient-based optimization approach can lead to local optima, and the authors suggest strategies like random restarts or seeding with solutions from cheaper models (like perceptron or linear SVM) to mitigate this.
  • Parameter Tuning: While MELC is designed to be parameter-free in its basic form, introducing parameters like the kernel width scaling factor γ can improve performance but requires tuning.
  • Non-linear Cases: The paper briefly touches upon adapting MELC for non-linear problems, suggesting kernel approximation techniques like Nyström's method or random projections as future research directions.

Summary updated

Abstract

Linear classifiers separate the data with a hyperplane. In this paper we focus on the novel method of construction of multithreshold linear classifier, which separates the data with multiple parallel hyperplanes. Proposed model is based on the information theory concepts -- namely Renyi's quadratic entropy and Cauchy-Schwarz divergence. We begin with some general properties, including data scale invariance. Then we prove that our method is a multithreshold large margin classifier, which shows the analogy to the SVM, while in the same time works with much broader class of hypotheses. What is also interesting, proposed method is aimed at the maximization of the balanced quality measure (such as Matthew's Correlation Coefficient) as opposed to very common maximization of the accuracy. This feature comes directly from the optimization problem statement and is further confirmed by the experiments on the UCI datasets. It appears, that our Multithreshold Entropy Linear Classifier (MELC) obtaines similar or higher scores than the ones given by SVM on both synthetic and real data. We show how proposed approach can be benefitial for the cheminformatics in the task of ligands activity prediction, where despite better classification results, MELC gives some additional insight into the data structure (classes of underrepresented chemical compunds).
BibTeX
@article{czarnecki2015multithreshold,
  author = {Wojciech Marian Czarnecki and Jacek Tabor},
  title = {{Multithreshold Entropy Linear Classifier}},
  journal = {Expert Systems with Applications},
  year = {2015},
  doi = {10.1016/j.eswa.2015.03.007},
}
Figure