Efficient Computation of Moments in Sum-Product Networks

Han Zhao, Geoffrey J. Gordon

Abstract

Bayesian online algorithms for Sum-Product Networks (SPNs) require updating posterior distributions after observing individual instances. This process necessitates the computation of moments of model parameters. While existing methods scale linearly for tree-structured networks, they scale quadratically ($O(N^2)$) for general directed acyclic graphs (DAGs), making Bayesian learning prohibitively expensive for complex models. This paper introduces an optimal linear-time ($O(N)$) algorithm for moment computation in DAG-structured SPNs, significantly broadening the applicability of Bayesian online learning techniques like Assumed Density Filtering (ADF).

The Challenge of Online Learning in SPNs

Sum-Product Networks are powerful deep probabilistic models that allow for exact, tractable inference. To train these models incrementally as new data arrives—a process known as online learning—researchers often turn to Bayesian methods such as Assumed Density Filtering (ADF) or Bayesian Moment Matching (BMM).

The primary bottleneck in these methods is the requirement to calculate "moments" (statistical expectations) of the model's internal parameters. While this is straightforward for trees, most high-performance SPNs are structured as DAGs where nodes can have multiple parents. Previous state-of-the-art methods for DAGs scaled quadratically relative to the network size, rendering Bayesian online learning too slow for large-scale applications. This research closes that gap by achieving linear complexity.

Methodology: Achieving Linear Time

The proposed algorithm achieves $O(N)$ complexity through three key technical innovations:

  1. Reduction to Joint Inference: The authors demonstrate that computing the moment for any specific edge in the network is mathematically equivalent to a standard joint inference problem in an SPN, using a specific set of weights derived from the prior distribution.
  2. The Differential Trick: SPNs represent a "network polynomial." Because these polynomials are multilinear (each variable appears at most to the power of one in any single term), the authors use partial derivatives to isolate specific parts of the network. This allows for the evaluation of specific edges without expanding the exponentially many paths in the DAG.
  3. Dynamic Programming: To avoid redundant calculations for every edge, the algorithm employs a two-pass approach. A bottom-up pass evaluates and caches node values, while a top-down pass uses the chain rule (similar to backpropagation) to compute derivatives for all edges simultaneously.
Figure 1: Local structure of an SPN illustrating the relationship between a sum node $D_k$, a product node $V_j$, and the connecting edge weight $w_{k,j}$ used in moment calculations.

Key Insights and Results

  • Complexity Breakthrough: The algorithm successfully computes all moments for all edges in $O(|S|)$ time and space, where $|S|$ is the total number of nodes and edges. This is a transformative improvement over the previous $O(|S|^2)$ benchmark.
  • Multilinearity as a Foundation: The efficiency of the "differential trick" relies entirely on the decomposable nature of SPNs, which ensures their underlying polynomial is multilinear.
  • Importance Weighting: The algorithm calculates a value $\lambda_{k,j}$, representing the "relative importance" of a specific edge. The updated moment becomes a weighted average of the prior belief and the new observation, scaled by this importance factor.
  • New Online Learner: By applying this algorithm, the authors derived a linear-time ADF for SPNs, providing a principled framework for instance-by-instance model updates.

Limitations and Future Directions

While the algorithm is a significant theoretical and practical advancement, there are trade-offs. The authors note that the Concave-Convex Procedure (CCCP) may still yield better log-likelihood scores in some practical scenarios because it optimizes data likelihood more directly than moment matching. Additionally, the linear-time algorithm requires approximately three times the memory of a standard SPN to cache the necessary forward and backward values.

Future work may involve applying this efficient moment computation to structure learning, potentially allowing models to discover their own optimal DAG architecture during the learning process.

Summary updated

Abstract

Bayesian online algorithms for Sum-Product Networks (SPNs) need to update their posterior distribution after seeing one single additional instance. To do so, they must compute moments of the model parameters under this distribution. The best existing method for computing such moments scales quadratically in the size of the SPN, although it scales linearly for trees. This unfortunate scaling makes Bayesian online algorithms prohibitively expensive, except for small or tree-structured SPNs. We propose an optimal linear-time algorithm that works even when the SPN is a general directed acyclic graph (DAG), which significantly broadens the applicability of Bayesian online algorithms for SPNs. There are three key ingredients in the design and analysis of our algorithm: 1). For each edge in the graph, we construct a linear time reduction from the moment computation problem to a joint inference problem in SPNs. 2). Using the property that each SPN computes a multilinear polynomial, we give an efficient procedure for polynomial evaluation by differentiation without expanding the network that may contain exponentially many monomials. 3). We propose a dynamic programming method to further reduce the computation of the moments of all the edges in the graph from quadratic to linear. We demonstrate the usefulness of our linear time algorithm by applying it to develop a linear time assume density filter (ADF) for SPNs.
BibTeX
@inproceedings{zhao2017efficient,
  author = {Han Zhao and Geoffrey J. Gordon},
  title = {{Efficient Computation of Moments in Sum-Product Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=Hy4AWYW_br},
}
Figure