Multithreshold Entropy Linear Classifier: Theory and applications

Wojciech Marian Czarnecki, Jacek Tabor

Abstract

The Multithreshold Entropy Linear Classifier (MELC) is proposed as a middle ground between simple linear classifiers and complex non-linear models. By combining information theory with linear projections, MELC employs multiple parallel hyperplanes to separate data, effectively handling non-linearly separable patterns like the XOR problem. The model maximizes the Cauchy-Schwarz divergence between class densities, offering the simplicity of linear models with the flexibility of non-linear ones. Experimental results on UCI benchmarks and cheminformatics datasets show that MELC excels at maximizing balanced quality measures such as Matthew’s Correlation Coefficient (MCC).

Introduction

Standard linear classifiers, including Support Vector Machines (SVM) and Logistic Regression, typically seek a single hyperplane to bisect the feature space. While theoretically robust, these models struggle with non-linearly separable data—such as "sandwich" class distributions ($+-+$) or the classic XOR problem—unless they are kernelized. Kernelization maps data into higher-dimensional spaces, often resulting in complex, computationally expensive models that are susceptible to overfitting.

MELC addresses this limitation by maintaining the simplicity of a linear projection while increasing decision flexibility through multiple thresholds.

Comparison of linear separation (left) vs. multithreshold separation (middle, right) for non-linearly separable data.

Methods

The fundamental principle of MELC is to identify a single linear projection ($v^T x$) that optimizes class separation using multiple thresholds rather than a single bias term.

Projection and Density Estimation

Data is first projected onto a one-dimensional line. The probability distributions of each class along this projection are estimated using Kernel Density Estimation (KDE).

1D projection of class densities using Kernel Density Estimation (KDE) with multiple thresholds.

Information-Theoretic Objective

Rather than direct error minimization, MELC maximizes the Cauchy-Schwarz (CS) divergence between class densities, calculated via Renyi’s quadratic entropy. The entropy terms serve as natural regularizers; while the divergence term maximizes the "margin" between classes, the entropy terms ensure class distributions remain condensed. This mechanism prevents overfitting by discouraging an excessive number of thresholds.

Optimization

Training involves gradient-based steepest ascent on a unit sphere. To mitigate the risk of local minima inherent in non-convex optimization, the process is typically initialized with solutions from simpler models like standard SVMs or Perceptrons.

Experimental Evaluation

The authors evaluated MELC across three distinct data domains:

  1. Synthetic Toy Data: On an XOR-like dataset of four 2D Gaussians, MELC achieved nearly 100% accuracy, significantly outperforming linear SVMs (~50%).
  2. UCI Benchmarks: Across ten binary classification datasets (e.g., Breast Cancer, Diabetes, Sonar), MELC performed comparably to or better than SVMs. It notably outperformed standard linear models on the fourclass and diabetes datasets by leveraging its multithreshold capability.
  3. Cheminformatics: In predicting ligand activity for protein binding (e.g., 5-HT receptors), MELC identified "underrepresented chemical compounds"—small active clusters within larger inactive groups—that single-hyperplane models often dismiss as noise.

Discussion and Key Insights

MELC offers several advantages over traditional classifiers:

  • Scale Invariance: The Cauchy-Schwarz divergence is scale-invariant, meaning input data rescaling does not alter the optimal projection.
  • Balanced Performance: The objective function naturally prioritizes balanced measures like Matthew’s Correlation Coefficient (MCC) and Weighted Accuracy (WAC), making it ideal for imbalanced datasets.
  • Automatic Complexity Control: The entropy-based regularization allows the model to "collapse" into a single-threshold linear classifier when additional complexity is unnecessary. This occurred in 9 out of 10 UCI datasets tested.
  • Efficiency: In cheminformatics applications, MELC produced "lighter" models with fewer parameters than RBF-kernel SVMs, which is vital for high-throughput screening of large molecular databases.

Limitations and Future Work

The current $O(N^2)$ complexity of the KDE step limits scalability for very large datasets. Additionally, the non-convex nature of the optimization problem remains a challenge, though SVM-based seeding provides a practical workaround. Future research may explore "kernelizing" the MELC approach itself using Nyström methods or random projections to further extend its non-linear capabilities.

Summary updated

Abstract

Highlights • We propose a new entropy based multithreshold linear classifier with an adaptive kernel density estimation. • Proposed classifier maximizes multiple margins, while being conceptually similar in nature to SVM. • This method gives good classification results and is especially designed for unbalanced datasets. • It achieves significantly better results than SVM as part of an expert system designed for drug discovery. • Resulting model provides insight into the internal data geometry and can detect multiple clusters. Abstract This paper proposes a new multithreshold linear classifier (MELC) based on the Renyi’s quadratic entropy and Cauchy–Schwarz divergence, combined with the adaptive kernel density estimation in the one dimensional projections space. Due to its nature MELC is especially well adapted to deal with unbalanced data. As the consequence of both used model and the applied density regularization technique, it shows strong regularization properties and therefore is almost unable to overfit. Moreover, contrary to SVM, in its basic form it has no free parameters, however, at the cost of being a non-convex optimization problem which results in the existence of local optima and the possible need for multiple initializations. In practice, MELC obtained similar or higher scores than the ones given by SVM on both synthetic and real data from the UCI repository. We also perform experimental evaluation of proposed method as a part of expert system designed for drug discovery problem. It appears that not only MELC achieves better results than SVM but also gives some additional insights into data structure, resulting in more complex decision support system.
BibTeX
@article{czarnecki2015multithreshold,
  author = {Wojciech Marian Czarnecki and Jacek Tabor},
  title = {{Multithreshold Entropy Linear Classifier: Theory and applications}},
  journal = {Expert Systems with Applications},
  year = {2015},
  doi = {10.1016/j.eswa.2015.03.007},
}
Figure