An Information-theoretic Learning Algorithm for Neural Network Classification

David J. Miller, Ajit V. Rao, Kenneth Rose, Allen GershoNeurIPS 1995

Overview

This paper introduces a powerful learning algorithm for neural network classifiers based on Deterministic Annealing (DA). By borrowing concepts from statistical physics and information theory, the authors create a method that directly minimizes misclassification error while avoiding the "local minima" traps that plague standard gradient descent. This approach allows significantly smaller networks to outperform much larger, conventionally trained models.

The Challenge of Minimizing Error

In the mid-90s, the "holy grail" of classifier design was minimizing the actual probability of error ($P_e$). However, the error rate is a mathematically challenging objective—it is discrete, non-smooth, and riddled with local optima.

Most researchers at the time relied on shortcuts, using Mean Squared Error (MSE) or cross-entropy to approximate class probabilities rather than minimizing the error directly. While some "discriminative learning" techniques attempted to tackle $P_e$ head-on, they frequently became trapped in the first shallow local minimum they encountered. The authors set out to find a way to minimize the true objective ($P_e$) globally without getting stuck.

The Deterministic Annealing Approach

The authors propose an extension of Deterministic Annealing (DA) to solve this optimization problem. The core intuition relies on a physics-inspired cooling process:

  1. Probabilistic Assignment: Instead of making a "hard" decision (e.g., assigning a point strictly to Class A), the algorithm begins with "soft" or fuzzy assignments. Every data point has a probability of belonging to any class.
  2. The Entropy Constraint: Shannon’s entropy is used to measure the "randomness" of these assignments. Initially, entropy is maximized (the "high temperature" phase), which makes the optimization landscape smooth and easy to navigate.
  3. The Lagrangian: The algorithm minimizes a cost function analogous to the Helmholtz free energy from physics: $L = \beta \langle P_e \rangle - H$. Here, $\beta$ acts as the inverse temperature, $\langle P_e \rangle$ is the expected error, and $H$ is the entropy.
  4. The Annealing Process: Optimization starts at a high temperature (low $\beta$) with a uniform distribution. As the system slowly "cools" (increasing $\beta$), the entropy drops, and the assignments harden. By tracking the solution across temperatures, the algorithm effectively "melts" away local minima to find a superior global solution.
  5. Structural Integration: Unlike previous DA methods used merely for simple clustering, this formulation explicitly incorporates the internal structure of the classifier (such as Radial Basis Functions) into the probability distributions.

Key Insights

  • Smaller Models, Better Performance: The most striking insight is that a superior optimization algorithm allows for smaller networks. While standard practice often involves adding more neurons to improve accuracy, the authors demonstrate that a small network trained with DA can beat a massive network trained with standard descent.
  • Physics as a Map: The analogy to cooling a physical system provides a rigorous mathematical framework to transform a non-convex, "bumpy" optimization landscape into a convex, smooth one.
  • Quenching for Speed: The authors found that upon reaching a "critical temperature," the slow cooling process can be stopped. The system can then be "quenched" (jumping to zero temperature) using standard gradient descent to save computational time without sacrificing accuracy.

Experimental Results

The algorithm was evaluated on classic benchmarks, including a 40D Noisy Waveform dataset and challenging 2D/8D Mixture datasets. The DA approach consistently outperformed competing methods, particularly in terms of parameter efficiency.

Performance comparison on the Waveform dataset
  • Waveform Data: As shown in the table above, DA achieved a test error of 13% using only 4 receptive fields (M=4). To approach this performance (16-17% error), standard methods like TR-RBF or MD-RBF required between 30 and 50 receptive fields.
  • 2D Mixture: DA reached 6.1% error with just 3 units. A competing state-of-the-art method required 86 units to achieve a worse error of 9.26%.
  • 8D Mixture: DA achieved 9.4% error with 5 units, while the baseline required 128 units to reach 12.0% error.

In short, DA produces classifiers that are both more accurate and significantly more compact.

Limitations and Future Work

  • Computational Cost: The "cooling" process is more computationally expensive than a single run of backpropagation, typically running 1 to 5 times slower.
  • Scaling: The paper primarily focuses on Radial Basis Function (RBF) networks. While the authors note the method's applicability to Multi-Layer Perceptrons (MLPs) and larger-scale tasks like speech or image recognition, those applications were left for subsequent research.
  • Hyperparameter Sensitivity: The "annealing schedule"—the rate at which $\beta$ is increased—requires careful tuning. Cooling too quickly can cause the algorithm to "freeze" into a local minimum, negating its primary advantage.

Summary updated

BibTeX
@inproceedings{miller1995information,
  author = {David J. Miller and Ajit V. Rao and Kenneth Rose and Allen Gersho},
  title = {{An Information-theoretic Learning Algorithm for Neural Network Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
}
Figure