Nonextensive information theoretical machine

Chao-Bing Song, Shu-Tao XiaarXiv 2016 · arXiv

Abstract

The Nonextensive Information Theoretical Machine (NITM) is introduced as a comprehensive framework that leverages nonextensive information theory to unify several cornerstone algorithms in machine learning. By employing Tsallis entropy, NITM provides a single mathematical structure capable of expressing various loss functions (e.g., hinge, exponential) and regularization techniques (e.g., Gaussian, Student-t priors). This flexibility allows for the adaptation of models to the specific statistical "texture" of a dataset, frequently leading to superior performance compared to standard fixed-loss models.

Introduction

In the landscape of classical machine learning, algorithms such as Support Vector Machines (SVMs) and AdaBoost are often treated as distinct entities with disparate theoretical foundations. SVMs typically rely on hinge loss and $\ell_2$ (Gaussian) regularization, whereas AdaBoost is built upon exponential loss. These choices are largely rooted in Shannon information theory, which assumes "extensivity"—the principle that the total entropy of a system is the sum of its independent parts.

However, real-world complex systems often exhibit long-range interactions and power-law distributions that Shannon’s framework is ill-equipped to model. The Nonextensive Information Theoretical Machine (NITM) addresses this gap by providing a unified theory based on nonextensive information theory (NIT), specifically utilizing Tsallis entropy and divergence. This approach allows for a more natural representation of power-law distributions and provides a "meta-model" that encompasses traditional algorithms as special cases.

Unified Loss Functions

The primary innovation of NITM lies in its ability to recover well-known loss functions by varying a single "entropy index," denoted as $q'$. This parameterization allows the model to transition smoothly between different discriminative behaviors.

Table 1: Mapping of the entropy index $q'$ to standard loss functions within the NITM framework.

As shown in the table above, the framework is highly versatile:

  • As $q' \to -\infty$, the model recovers the $\ell_{0/1}$ loss.
  • At $q' = 0$, the framework yields the Hinge loss, characteristic of SVMs.
  • At $q' = 0.5$, it produces the Squared Hinge loss.
  • At $q' = 1$, it recovers the Exponential loss used in AdaBoost.

This unification suggests that the mathematical forms of SVMs and AdaBoost are not fundamentally different but rather occupy different points on the spectrum of Tsallis entropy.

Generalized Regularization and Optimization

Beyond loss functions, NITM generalizes regularization by replacing the standard Gaussian prior (which leads to $\ell_2$ regularization) with a Student-t prior. The Student-t distribution is inherently more flexible; by adjusting its degrees of freedom ($\nu$), the model can accommodate "heavy-tailed" distributions, making it more robust to outliers in the weight space. As $\nu \to \infty$, the Student-t prior reverts to a standard Gaussian prior.

The resulting objective functions are convex for specific ranges of the entropy indices. The authors provide both primal and dual formulations, which can be solved using efficient gradient-based methods such as BFGS for smooth functions and subgradient BFGS for non-smooth functions like the hinge loss.

Experimental Evaluation

The NITM framework was evaluated on six benchmark datasets from the UCI repository: Appendicitis, Australian, Banana, Hepatitis, Ionosphere, and Magic. Using 10-fold stratified cross-validation, the researchers compared 66 different model variations (combinations of $\nu$ and $q'$) for each dataset.

The results confirmed that no single configuration is universally optimal, adhering to the "No Free Lunch" theorem. However, NITM's strength lies in its ability to find the optimal settings for a specific data distribution:

  • Appendicitis: Performed best with a small $q'$, aligning with hinge loss.
  • Magic: Preferred a large $q'$ (exponential loss) and a large $\nu$ (Gaussian regularization).
  • Hepatitis: Showed a preference for middle-range values of $\nu$, suggesting a data structure that is neither strictly Gaussian nor extremely heavy-tailed.

Conclusion

The Nonextensive Information Theoretical Machine offers a powerful, unified perspective on discriminative learning. By treating entropy indices as hyperparameters, practitioners can move beyond the arbitrary selection of loss functions and priors, instead tailoring their models to the underlying statistical properties of their data. While this introduces additional complexity in hyperparameter tuning, the potential for performance gains and the theoretical elegance of a unified framework make NITM a significant contribution to information-theoretic machine learning.

Summary updated

BibTeX
@misc{song2016nonextensive,
  author = {Chao-Bing Song and Shu-Tao Xia},
  title = {{Nonextensive information theoretical machine}},
  year = {2016},
  eprint = {1604.06153},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1604.06153},
}
Figure