Deep Convolutional Sum-Product Networks

Cory J. Butz, Jhonatan de S. Oliveira, André E. dos Santos, André L. TeixeiraAAAI 2019 · DOI

Abstract

Deep Convolutional Sum-Product Networks (DCSPNs) bridge the gap between the high-performance architecture of Convolutional Neural Networks (CNNs) and the rigorous mathematical framework of probabilistic graphical models. By introducing specific structural constraints and "augmentation" techniques, DCSPNs create deep, valid probability distributions that achieve state-of-the-art results in image completion tasks while remaining computationally efficient.

Introduction

In generative modeling, a persistent trade-off exists between expressivity and tractability. Convolutional Neural Networks (CNNs) offer immense expressivity but often function as "black boxes" without a clear, valid joint probability distribution. Conversely, Sum-Product Networks (SPNs) provide exact, efficient probabilistic inference but have historically struggled to scale to the deep architectures required for complex computer vision tasks. Previous "Convolutional SPNs" were limited by pooling operations that rapidly reduced spatial resolution. DCSPNs overcome these limitations, allowing for deep structures that maintain mathematical guarantees for validity.

Methodology

The SPN-CNN Mapping

To ensure a CNN functions as a valid SPN, it must satisfy two conditions: completeness (sum nodes share the same scope) and decomposability (product nodes have disjoint scopes). The authors map these requirements to standard CNN operations:

  • Sum Layers: Implemented as convolutional layers where filters represent weights.
  • Product Layers: Implemented as sum-pooling in log-space. To maintain decomposability, pooling windows must be non-overlapping (stride $\ge$ window size).
Equivalence between CNN layers and SPN sum-product operations.

Deepening via Augmentation

A simple linear stack of non-overlapping pooling layers quickly exhausts spatial resolution. To enable depth, DCSPNs utilize a Directed Acyclic Graph (DAG) structure and "augmentation" techniques.

  • Channel Augmentation: Concatenating branches to increase depth without shrinking spatial dimensions.
  • Width/Height Augmentation: Combining branches that observe different image regions to build complex dependencies while respecting scope rules.
Structural augmentation techniques (a-d) for maintaining model depth and spatial resolution.

Additionally, a vectorized Most Probable Explanation (MPE) algorithm allows the model to perform image completion by propagating masks backward to find the most likely pixel values.

Evaluation and Results

DCSPNs were evaluated on image completion benchmarks using the Olivetti Face and Caltech datasets.

Performance Metrics

On the Olivetti Faces "left-completion" task, DCSPNs achieved a Mean Squared Error (MSE) of 455, significantly outperforming previous SPN models (779) and even DCGANs (935).

Key Insights

  • Robustness to Small Data: On the Caltech Dolphin dataset (65 images), DCSPNs performed remarkably well, showing less sensitivity to data scarcity than typical deep learning models.
  • Sampling Diversity: Unlike GANs prone to mode collapse, DCSPN sampling demonstrated significant variability, confirming a robust underlying probabilistic model.
  • Local Structure: Alternating 1x2 and 2x1 pooling windows proved more effective at capturing spatial dependencies than standard square windows.

Conclusion

DCSPNs demonstrate that with appropriate constraints on filter sizes and strides, CNN architectures can serve as rigorous joint probability distributions. By leveraging DAG-based augmentations, these models achieve the depth necessary for high-performance generative tasks without sacrificing probabilistic tractability. Future work includes automating architecture design through search and further exploring the integration of adversarial training techniques.

Summary updated

BibTeX
@inproceedings{butz2019deep,
  author = {Cory J. Butz and Jhonatan de S. Oliveira and André E. dos Santos and André L. Teixeira},
  title = {{Deep Convolutional Sum-Product Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33013248},
}
Figure