Gradient-based Wang--Landau Algorithm: A Novel Sampler for Output Distribution of Neural Networks over the Input Space

Weitang Liu, Yi-Zhuang You, Ying Wai Li, Jingbo Shang

Abstract

Neural networks (NNs) are typically evaluated on finite datasets, leaving their behavior across the vast majority of the input space unknown. This paper introduces the Gradient-based Wang-Landau (GWL) algorithm, a sampling method inspired by statistical physics designed to map the global output distribution of a neural network. By integrating the Wang-Landau framework with Gibbs-With-Gradients (GWG), GWL efficiently explores high-dimensional input spaces that are inaccessible to traditional Monte Carlo methods. Our results on MNIST-trained models reveal significant biases, such as a reliance on background darkness for classification, and demonstrate that human-unrecognizable noise dominates even high-confidence regions of the model's output.

Introduction

Most neural network evaluations focus on specific subsets of data: training sets, test sets, or known out-of-distribution (OOD) examples. However, this provides an incomplete picture of a model's global mapping relationship. To truly understand a model's robustness and internal logic, we need to know how it behaves across the entire possible input space—including the infinite sea of human-unrecognizable "noise" images.

The challenge is that this space is astronomically large. Exhaustive enumeration is impossible, and traditional Monte Carlo sampling methods often get "stuck" in local regions or take far too long to converge in high-dimensional spaces. The Gradient-based Wang-Landau (GWL) algorithm aims to make sampling the entire input space computationally feasible to uncover the global behavior of trained NNs.

Methodology

The GWL sampler relies on three key pillars to overcome the limitations of traditional sampling:

  1. The Physics Analogy: In statistical physics, the "Density of States" (DOS) counts how many configurations of a system result in a specific energy level. The authors treat a neural network's output (logit) as "energy" and the input image as a "configuration." Mapping the output distribution is thus mathematically analogous to finding the DOS.
  2. The Wang-Landau (WL) Framework: The classic WL algorithm estimates the DOS on-the-fly. It uses a histogram to track visited states and systematically biases the sampler away from frequently visited regions toward under-explored ones, ensuring a broad exploration of the output range.
  3. Gradient-based Proposals (GWG): Standard WL uses random walks, which fail in high-dimensional image spaces. GWL replaces random moves with Gibbs-With-Gradients (GWG). By calculating which pixels are most likely to change the output, the sampler can navigate the vast input space much more efficiently than a random search.

Experimental Setup

The researchers validated the GWL algorithm using two primary datasets:

  • Toy Dataset: A custom-built set of $5 \times 5$ binary images. With only $2^{25}$ possible configurations, this allowed for brute-force enumeration to verify that GWL produces the ground-truth distribution perfectly.
  • MNIST-0/1: A binary version of the MNIST digit dataset containing only "0" and "1" classes, used to test the sampler on more complex $28 \times 28$ grayscale images.

Key Insights and Results

Efficiency Gains

The gradient-based approach proved transformative for sampling speed. While the original WL algorithm failed to make substantial progress on MNIST-scale problems after 10 days of computation, GWL was able to explore the full range of output values within just a few iterations. Specifically, GWL explored the logit range of a CNN from -55 to +18 in two iterations, whereas the standard WL algorithm remained stuck in a tiny window (around -55 to -53) even after 60 million steps.

The "Darkness" Backdoor

For both CNNs and ResNets trained on MNIST, the sampler revealed a striking pattern: as the model's confidence (logit value) increased, the representative images generated by the sampler had increasingly dark backgrounds. This suggests the models aren't just looking at the digits; they've learned a "shortcut" or backdoor where background pixels heavily influence the classification.

Overconfidence in the Void

The vast majority of the input space—random-looking noise—is mapped to very negative logit values. However, even in the "confident" regions where digits should be, human-unrecognizable images still dominate numerically. This provides quantitative evidence for why NNs are so susceptible to being fooled by OOD data; the regions of the input space that humans recognize as digits are statistically insignificant compared to the volume of noise that the model might classify with high confidence.

Distribution Shape

Contrary to the expected "bell curve" centered at zero, the actual output distribution of the tested CNN was heavily skewed toward negative values. This indicates a strong inherent bias in the model's global mapping that is not apparent when looking only at test set accuracy.

Limitations and Future Work

While GWL represents a significant step forward, several challenges remain. The authors have not yet provided a formal proof that the combination of WL and GWG is guaranteed to converge. Furthermore, sampling complex architectures like ResNet-18 remains time-consuming, and scaling the method to high-resolution datasets like ImageNet is a significant hurdle. Future work may also involve integrating automatic labeling to identify "human-recognizable" samples, which currently requires manual inspection.

Conclusion

The Gradient-based Wang-Landau algorithm provides a powerful new tool for auditing the global behavior of neural networks. By revealing hidden biases and the numerical dominance of noise in high-confidence regions, GWL offers a path toward more transparent and robust machine learning models.

Summary updated

Abstract

The output distribution of a neural network (NN) over the entire input space captures the complete input-output mapping relationship, offering in- sights toward a more comprehensive NN under- standing. Exhaustive enumeration or traditional Monte Carlo methods for the entire input space can exhibit impractical sampling time, especially for high-dimensional inputs. To make such difficult sampling computationally feasible, in this paper, we propose a novel Gradient-based Wang-Landau (GWL) sampler. We first draw the connection between the output distribution of a NN and the density of states (DOS) of a physical system. Then, we renovate the classic sampler for the DOS problem, Wang-Landau algorithm, by re-placing its random proposals with gradient-based Monte Carlo proposals. This way, our GWL sampler investigates the under-explored subsets of the input space much more efficiently. Extensive experiments have verified the accuracy of the output distribution generated by GWL and also showcased several interesting findings - for example, in a binary image classification task, both CNN and ResNet mapped the majority of human unrecognizable images to very negative logit values.
BibTeX
@inproceedings{liu2023gradient,
  author = {Weitang Liu and Yi-Zhuang You and Ying Wai Li and Jingbo Shang},
  title = {{Gradient-based Wang--Landau Algorithm: A Novel Sampler for Output Distribution of Neural Networks over the Input Space}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=dxTu7PlNZz},
}
Figure