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.
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).
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:
- Synthetic Toy Data: On an XOR-like dataset of four 2D Gaussians, MELC achieved nearly 100% accuracy, significantly outperforming linear SVMs (~50%).
- 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.
- 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