Linear Time Computation of Moments in Sum-Product Networks

Han Zhao, Geoffrey J. Gordon

Introduction

Sum-Product Networks (SPNs) are powerful probabilistic models celebrated for allowing exact inference—answering questions about joint or marginal probabilities—in time that scales linearly with the size of the network. However, a major bottleneck arises when learning these networks in an online setting, where the model must update its beliefs after seeing each new data point.

To perform Bayesian online updates using frameworks like Assumed Density Filtering (ADF), one must compute the "moments" of the model's parameters. While this computation is straightforward for tree-structured SPNs, most high-performance SPNs are Directed Acyclic Graphs (DAGs) where nodes can have multiple parents. For these general graphs, previous state-of-the-art methods scaled quadratically ($O(|S|^2)$). This meant that doubling the size of the network quadrupled the training time, making Bayesian online learning computationally prohibitive for large-scale, complex SPNs.

This paper introduces the first optimal linear-time algorithm for computing parameter moments in SPNs with general DAG structures, bringing the cost of parameter updates down to the same $O(|S|)$ efficiency as standard inference.

Achieving Linear-Time Complexity

The authors achieve this dramatic reduction in computational complexity through three clever technical maneuvers:

  1. Reduction to Joint Inference: They prove that computing the moments of an edge weight is mathematically equivalent to a standard joint inference problem within the SPN, provided the weights are adjusted based on the prior distribution (typically a Dirichlet distribution).
  2. The Differential Trick: SPNs represent a "network polynomial." Because this polynomial is multilinear with respect to its weights, the authors use partial derivatives to isolate specific edges. Instead of expanding the polynomial—which would result in an exponentially large number of terms—they evaluate it efficiently through differentiation.
  3. Dynamic Programming (Two-Pass Approach): To avoid recalculating values for every single edge, they propose a dynamic programming scheme.
  4. Bottom-up pass: Evaluates the network and caches the forward values at each node.
  5. Top-down pass: Uses a backpropagation-like procedure to compute the derivatives, which represent the "importance" of each node to the root.
Diagram illustrating the connection between a sum node and a product node in an SPN, highlighting the edge weight $w_{k,j}$ targeted during the two-pass moment computation.

By combining these cached bottom-up and top-down values, the algorithm can compute the moments for all edges simultaneously in just two passes.

Key Insights

A central discovery in this work is the formalization of Edge Importance ($\lambda_{k,j}$). This term represents the ratio of the value of all "induced trees" containing a specific edge to the total value of the network. It acts as a precise measure of how much a specific edge contributes to the current observation.

The "secret sauce" enabling this calculation is the fact that SPNs are multilinear functions. This multilinearity allows the differential operator to act as a "selector," effectively filtering for all paths in the graph that pass through a specific parameter without brute-force traversal. Furthermore, the authors theoretically unify Assumed Density Filtering (ADF) and Bayesian Moment Matching (BMM), showing they belong to the same family of algorithms and differ primarily in which moments they choose to match (natural vs. first-order).

Results and Impact

The primary breakthrough of this paper is algorithmic: reducing the time complexity for moment computation in DAG-structured SPNs from $O(|S|^2)$ to $O(|S|)$.

This method is also highly space-efficient, requiring only $O(|S|)$ space—specifically, about three times the memory of the original network to store the cached passes. Ultimately, the algorithm is mathematically "optimal" in the sense that it matches the lower-bound complexity of a single inference pass.

Limitations and Future Work

While the proposed online algorithms (ADF and BMM) are now vastly faster, the authors note that batch learning methods like the Concave-Convex Procedure (CCCP) still tend to outperform them in terms of final log-likelihood scores.

Currently, this work focuses on updating parameters for a fixed network structure. However, the authors suggest that these linear-time techniques could eventually be applied to the more difficult problem of structure learning—automatically building the graph itself in an online fashion. Finally, they expect the core analysis techniques, specifically the use of the differential trick for multilinear polynomials, to find broader applications in SPN research beyond moment computation.

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{zhao2017linear,
  author = {Han Zhao and Geoffrey J. Gordon},
  title = {{Linear Time Computation of Moments in Sum-Product Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=Hy4AWYW_br},
}

Loading related content...

Figure