On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models

Boyao Li, Alexandar J. Thomson, Matthew M. Engelhard, David Page

TL;DR

This paper bridges the gap between deep neural networks (DNNs) and probabilistic graphical models (PGMs) by constructing an infinite tree-structured PGM that precisely mirrors any given DNN. This novel connection reveals that DNN forward propagation is an approximation of PGM inference, offering a clearer probabilistic interpretation of DNNs and paving the way for hybrid PGM-DNN algorithms.

What Problem Does This Paper Address?

Deep neural networks (DNNs) are powerful function approximators, but their complex, non-linear structure makes them notoriously difficult to interpret and understand probabilistically. While connections have been drawn to models like Gaussian processes, a direct, precise probabilistic interpretation of a general DNN has been elusive. This lack of interpretability hinders debugging, understanding model behavior, and developing new algorithms that leverage the strengths of both DNNs and probabilistic models. The authors aim to provide a formal, theoretical link between DNNs and PGMs, specifically by showing how a DNN can be viewed as an approximation to a well-defined probabilistic model.

Methods

The core contribution is the construction of an infinite tree-structured Probabilistic Graphical Model (PGM) that exactly corresponds to any given DNN. This construction involves two main steps:

  1. Separating Shared Parents: The first step involves creating copies of nodes that share parents in the original DNN's directed acyclic graph (DAG). This process "unrolls" the network into a tree-like structure, ensuring that each path from an input to an output is represented.
  2. Creating L Copies: The second step further refines this structure by creating $L$ copies of each non-output node and its ancestral subtrees. As $L$ approaches infinity, the authors prove that the inference and gradient calculations in this infinite PGM precisely match the forward pass and gradient calculations in the original DNN.

This construction allows them to view the DNN's forward pass as an approximation of exact inference in this infinite PGM. They also propose a novel Hamiltonian Monte Carlo (HMC) sampling algorithm for fine-tuning DNNs, which is theoretically justified by this PGM construction.

Datasets

  • Synthetic Datasets: Generated from simple Bayesian Networks (BNs) and Markov Networks (MNs) with varying weights. These datasets are used to evaluate the calibration performance of their proposed HMC fine-tuning method against standard DNN training and Gibbs sampling.
  • Covertype Dataset: A real-world dataset used for classification tasks. Similar to the synthetic experiments, it's used to compare the calibration performance of SGD, Gibbs, and HMC fine-tuning.

Key Insights and Ideas

  • DNNs as Approximate PGM Inference: The most significant insight is that a DNN's forward pass is not just a function approximation but a precise approximation of inference in a specific, infinite tree-structured PGM. This provides a formal probabilistic interpretation for DNNs.
  • Sigmoid Activations as Bayesian Networks: For networks with sigmoid activations, the authors show a direct correspondence to Bayesian Belief Networks (BBNs), which are then further related to Markov Networks (MNs).
  • HMC for Improved Calibration: The theoretical PGM construction provides a strong justification for using HMC sampling for fine-tuning DNNs, particularly for improving model calibration. This is because HMC, in this context, approximates a more theoretically sound sampling method than standard SGD.
  • Bridging the Gap: The work offers a unified framework that can potentially merge the strengths of PGMs (interpretability, uncertainty quantification) with DNNs (scalability, performance).

Key Results

  • Theoretical Equivalence: The paper formally proves that as the number of copies ($L$) in the constructed PGM approaches infinity, the inference and gradient calculations in the PGM exactly match the forward pass and gradient calculations of the original DNN.
  • Improved Calibration: Experimental results on synthetic datasets and the Covertype dataset show that HMC fine-tuning, guided by the PGM theory, can significantly improve the calibration of DNNs compared to standard SGD training, especially for smaller values of $L$ (e.g., $L=10$). For instance, on the Covertype (label 1) dataset, HMC-10 achieved an Expected Calibration Error (ECE) of $2.352 \times 10^{-2}$, significantly lower than DNN's $4.207 \times 10^{-2}$.
  • Faster than Gibbs: While HMC is slower than SGD, it is considerably faster than Gibbs sampling for fine-tuning, making it a more practical option for improving calibration.

Limitations and Future Work

  • Infinite PGM: The constructed PGM is infinite, making direct inference or sampling computationally intractable. The theoretical results are crucial for understanding the DNN's behavior, but practical applications rely on approximations.
  • Sigmoid Focus: While extensions to ReLU and other activations are discussed, the core theoretical results are most directly established for sigmoid activations. Further theoretical and empirical work is needed for other activation functions.
  • Normalization Approximations: The paper suggests that modified batch and layer normalization might approximate Markov network normalization, but formal analyses are left for future work.
  • Other PGM Algorithms: The authors propose exploring other PGM algorithms (e.g., loopy belief propagation, contrastive divergence) for fine-tuning and inference in more complex DNN-PGM hybrids.
  • Reverse Reasoning: Extending the framework to enable reverse reasoning (e.g., inferring causes from effects) in DNNs is a promising future direction.
  • Hybrid Systems: The work opens doors for building and fine-tuning larger systems composed of both DNN and PGM components, which is particularly relevant for complex biological systems.

Summary updated

Abstract

Deep neural networks (DNNs) lack the precise semantics and definitive probabilistic interpretation of probabilistic graphical models (PGMs). In this paper, we propose an innovative solution by constructing infinite tree-structured PGMs that correspond exactly to neural networks. Our research reveals that DNNs, during forward propagation, indeed perform approximations of PGM inference that are precise in this alternative PGM structure. Not only does our research complement existing studies that describe neural networks as kernel machines or infinite-sized Gaussian processes, it also elucidates a more direct approximation that DNNs make to exact inference in PGMs. Potential benefits include improved pedagogy and interpretation of DNNs, and algorithms that can merge the strengths of PGMs and DNNs.
BibTeX
@inproceedings{li2024neural,
  author = {Boyao Li and Alexandar J. Thomson and Matthew M. Engelhard and David Page},
  title = {{On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=KcmhSrHzJB},
}
Figure