Information Forests

Zhao Yi, Stefano Soatto, Maneesh Dewan, Yiqiang Zhan

TL;DR

This paper introduces "Information Forests" (IFs), a novel classification approach that generalizes Random Forests. Instead of focusing on creating pure class partitions, IFs aim to create partitions that are maximally "informative" for classification by maximizing information divergence between class-conditional distributions. This allows IFs to tackle problems that are not easily solvable by traditional methods, especially when dealing with complex or noisy data.

What Problem Does This Paper Address?

The paper addresses the challenge of classifying data in scenarios where traditional methods, like standard Random Forests (RFs), struggle. Specifically, it targets problems where the overall distribution of features for different classes is not discriminative. Imagine trying to detect a person in an image: the general distribution of colors or intensities in the person's region might be very similar to the background. Standard RFs, which rely on splitting data to create "pure" (class-homogeneous) subsets, might fail here. IFs aim to overcome this by identifying "informative subsets" or "parts" of the data where classification is simpler, even if the whole is not. This is akin to finding specific features or regions that reveal class differences, rather than trying to make the entire dataset separable at once.

Methods

The core innovation of Information Forests lies in their splitting criterion. While standard Random Forests use discriminative criteria like entropy or Gini impurity to create partitions that are as pure as possible with respect to class labels, IFs employ a generative criterion. They aim to maximize the information divergence (specifically, Kullback-Leibler divergence) between the class-conditional distributions within the resulting partitions. This means IFs seek to create subsets where the probability of observing certain features given class 1 is significantly different from the probability of observing those features given class 0.

The process is hierarchical and recursive, similar to decision trees. At each node, IFs evaluate potential splits (using simple "decision stumps" based on features and thresholds). The best split is chosen not by maximizing purity, but by maximizing the information divergence. Classification is deferred until a certain "confidence" threshold is met, meaning the partitions are sufficiently informative. This approach can be seen as a form of mixed generative/discriminative learning, active learning, and semi-supervised learning.

Datasets

Not discussed in the paper. The paper focuses on the theoretical framework and algorithmic derivation, using conceptual examples (like image detection) rather than specific datasets for empirical evaluation.

Key Insights and Ideas

  • "Informative" Partitions over "Pure" Partitions: The fundamental shift is from creating subsets that are pure in class labels to creating subsets that are informative for distinguishing between classes. This is crucial for problems where global separability is low.
  • Deferring Classification: IFs don't force a classification decision at every node. Instead, they continue to partition the data until the subsets are "simple enough" to classify with high confidence, measured by information divergence.
  • Generative Splitting Criterion: Replacing the discriminative entropy-based splits with a generative information divergence criterion is the key technical novelty. This allows IFs to find subtle class differences in specific regions.
  • Generalization of Random Forests: IFs are presented as a superset of Random Forests. By setting a divergence threshold (τ) to zero, IFs effectively reduce to Random Forests.
  • Handling "Not Solvable as Whole" Problems: The framework is explicitly designed for problems where the overall data distribution is not discriminative, but localized "parts" or "regions" reveal class differences.

Key Results

The paper primarily presents the theoretical framework and derivation of Information Forests. It establishes that IFs generalize Random Forests and offers a method for constructing these forests. The paper outlines the splitting criteria based on maximizing information divergence and minimizing entropy for leaf nodes. It also discusses approximations for computing information divergence to make the training process tractable. While quantitative results are not presented, the qualitative argument is that IFs will produce more balanced and shallower trees for certain types of problems compared to standard RFs, especially when the set of available classifiers is restricted.

Limitations and Future Work

  • Computational Complexity: Training IFs involves optimizing information divergence at each node, which can be computationally intensive. The paper acknowledges the need for efficient approximations, such as using lower bounds of information divergence or projecting onto feature space.
  • Empirical Evaluation: The paper focuses on the theoretical derivation and does not present empirical results on benchmark datasets.
  • Future Work: The authors state that in forthcoming work, they intend to characterize the performance of IFs both empirically and analytically. They also mention that a more thorough analysis of IFs' properties and the class of problems they are well-suited for is forthcoming.

Summary updated

Abstract

We describe Information Forests, an approach to classification that generalizes Random Forests by replacing the splitting criterion of non-leaf nodes from a discriminative one - based on the entropy of the label distribution - to a generative one - based on maximizing the information divergence between the class-conditional distributions in the resulting partitions. The basic idea consists of deferring classification until a measure of “classification confidence” is sufficiently high, and instead breaking down the data so as to maximize this measure. In an alternative interpretation, Information Forests attempt to partition the data into subsets that are “as informative as possible” for the purpose of the task, which is to classify the data. Classification confidence, or informative content of the subsets, is quantified by the Information Divergence. Our approach relates to active learning, semi-supervised learning, mixed generative/discriminative learning.
BibTeX
@inproceedings{yi2012information,
  author = {Zhao Yi and Stefano Soatto and Maneesh Dewan and Yiqiang Zhan},
  title = {{Information Forests}},
  booktitle = {ITA},
  year = {2012},
  url = {https://openreview.net/forum?id=YHq82ZbqTS},
}
Figure