Deep Nonparametric Estimation of Discrete Conditional Distributions via Smoothed Dyadic Partitioning

Wesley Tansey, Karl Pichotta, James G. ScottarXiv 2017 · DOI · arXiv

Abstract

We present an approach to deep estimation of discrete conditional probability distributions. Such models have several applications, including generative modeling of audio, image, and video data. Our approach combines two main techniques: dyadic partitioning and graph-based smoothing of the discrete space. By recursively decomposing each dimension into a series of binary splits and smoothing over the resulting distribution using graph-based trend filtering, we impose a strict structure to the model and achieve much higher sample efficiency. We demonstrate the advantages of our model through a series of benchmarks on both synthetic and real-world datasets, in some cases reducing the error by nearly half in comparison to other popular methods in the literature.

Introduction

In many deep learning tasks—such as generating images (PixelCNN) or synthesizing speech (WaveNet)—models must output a discrete conditional probability distribution. For instance, given surrounding pixels, what is the probability that the next pixel intensity is exactly 128?

Currently, researchers typically face a trade-off between two suboptimal approaches:

  1. Multinomial Models: These treat every possible value as an independent category. While flexible, they are "spatially blind," failing to recognize that a pixel value of 127 is similar to 128. This leads to high noise and poor sample efficiency.
  2. Mixture Models (e.g., GMMs): These assume data follows a specific parametric shape. While smooth, they often struggle to capture the "spiky" data or sharp boundaries common in real-world datasets, such as pixel values clustering at 0 or 255.

Smoothed Dyadic Partitioning (SDP) bridges this gap, offering a model as flexible as a multinomial but as spatially aware as a parametric model.

Methods: The Two Pillars of SDP

SDP relies on two core mechanisms to improve estimation:

1. Dyadic Decomposition

Instead of predicting all categories simultaneously, the model utilizes a balanced binary tree structure. To determine the probability of a specific value, the model makes a sequence of "left vs. right" decisions. This recursive decomposition is computationally efficient—requiring only $O(\log n)$ steps—and provides significantly better numerical stability than standard methods.

The dyadic partitioning structure recursively splits the discrete space into a binary tree.

2. Graph-Based Smoothing

To ensure spatial awareness, the authors apply graph-based trend filtering during training. This penalty forces the predicted probabilities of neighboring values to be similar, allowing the model to "borrow statistical strength" from nearby points. To maintain speed, this smoothing is applied locally within a small neighborhood around the target value during training.

Key Results and Insights

The authors evaluated SDP against several baselines, including Multinomial models, Gaussian Mixture Models (GMM), and Logistic Mixture Models (LMM), across synthetic and real-world datasets (UCI repository, MNIST, and CIFAR-10).

Sample Efficiency and Error Reduction

SDP consistently outperformed baselines, particularly in low-data regimes. By recognizing spatial neighbors, SDP produces accurate distributions with far fewer training examples. On the CIFAR-50K dataset, SDP reduced the Root Mean Squared Error (RMSE) to 13.42, nearly halving the error of the Multinomial (22.66) and GMM (23.02) models.

Comparison of TV Error across different sample sizes for GMM and Edge-Biased distributions.

Winning at the Edges

Real-world data often features "edge cases" where values cluster at boundaries (e.g., 0 or 255 in pixel data). SDP handles these boundaries significantly better than Gaussian models, which tend to "leak" probability mass beyond the valid range. The tree structure allows the model to capture fine-grained details that parametric models would otherwise smooth away.

Conclusion

Smoothed Dyadic Partitioning offers a robust framework for discrete probability estimation. While it faces some scaling challenges in very high-dimensional spaces and introduces a 3-4x training overhead due to the smoothing penalty, its gains in sample efficiency and accuracy are substantial. Future work may involve integrating SDP into large-scale architectures like PixelCNN++ to further advance state-of-the-art generative modeling.

Summary updated

Abstract

We present an approach to deep estimation of discrete conditional probability distributions. Such models have several applications, including generative modeling of audio, image, and video data. Our approach combines two main techniques: dyadic partitioning and graph-based smoothing of the discrete space. By recursively decomposing each dimension into a series of binary splits and smoothing over the resulting distribution using graph-based trend filtering, we impose a strict structure to the model and achieve much higher sample efficiency. We demonstrate the advantages of our model through a series of benchmarks on both synthetic and real-world datasets, in some cases reducing the error by nearly half in comparison to other popular methods in the literature. All of our models are implemented in Tensorflow and publicly available at https://github.com/tansey/sdp .
BibTeX
@misc{tansey2017deep,
  author = {Wesley Tansey and Karl Pichotta and James G. Scott},
  title = {{Deep Nonparametric Estimation of Discrete Conditional Distributions via Smoothed Dyadic Partitioning}},
  year = {2017},
  eprint = {1702.07398},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.07398},
}
Figure