PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Latent Variable Interpretation in Sum-Product Networks

Robert Peharz, Robert Gens, Franz Pernkopf, Pedro Domingos

arXiv:1601.06180v2cs.AIcs.LG

TL;DR

Explicitly adding latent-state indicators can conflict with SPN completeness and leave the probabilistic model incompletely specified. The paper addresses this with SPN augmentation and establishes a sound latent-variable interpretation; it also proves that Viterbi-style backtracking returns an MPE solution for selective SPNs, including augmented SPNs.

  • Problem

    Explicitly introducing latent-variable state indicators can conflict with SPN completeness, leaving the probabilistic model incompletely specified.

    Source: §1 · p. 1, §2 · pp. 3–4

  • Method

    SPN augmentation adds twin sum nodes alongside indicator variables, and the paper uses it to establish a sound latent-variable model and derive the EM algorithm.

    Source: §1 · p. 1, §6 · p. 12

  • Results

    The Viterbi-style backtracking algorithm returns an MPE solution for selective SPNs, including augmented SPNs.

    Source: §1 · p. 2, §4 · p. 8

  • Takeaways & Limitations

    Augmented SPNs admit a Bayesian-network interpretation in which sum-weights are structured conditional probability tables.

    Source: §6 · p. 12

    Deterministic twin-weights can favor an arbitrary latent state when that variable is irrelevant, producing a low-depth bias.

    Source: §4 · p. 9

Abstract

from arXiv · show

One of the central themes in Sum-Product networks (SPNs) is the interpretation of sum nodes as marginalized latent variables (LVs). This interpretation yields an increased syntactic or semantic structure, allows the application of the EM algorithm and to efficiently perform MPE inference. In literature, the LV interpretation was justified by explicitly introducing the indicator variables corresponding to the LVs' states. However, as pointed out in this paper, this approach is in conflict with the completeness condition in SPNs and does not fully specify the probabilistic model. We propose a remedy for this problem by modifying the original approach for introducing the LVs, which we call SPN augmentation. We discuss conditional independencies in augmented SPNs, formally establish the probabilistic interpretation of the sum-weights and give an interpretation of augmented SPNs as Bayesian networks. Based on these results, we find a sound derivation of the EM algorithm for SPNs. Furthermore, the Viterbi-style algorithm for MPE proposed in literature was never proven to be correct. We show that this is indeed a correct algorithm, when applied to selective SPNs, and in particular when applied to augmented SPNs. Our theoretical results are confirmed in experiments on synthetic data and 103 real-world datasets.

1 INTRODUCTION

The introduction frames sum nodes as latent-variable choices that provide structure and support EM, but says the indicator-variable account can conflict with completeness and underspecify the model. It previews augmentation-based foundations and a qualified correctness result for MPE.

1 INTRODUCTION

  • The latent-variable interpretation gives SPNs a structured model that supports ancestral sampling, semantic variables such as classes, and EM learning.Source: §1 · p. 1
  • Explicitly adding state indicators can conflict with completeness and leave the latent-variable model underspecified; augmentation adds twin sums to address these problems.Source: §1 · p. 1
  • Viterbi-style backtracking finds MPE solutions in selective SPNs, including augmented SPNs, while its use on non-augmented SPNs assumes deterministic twin weights and can cause low-depth bias.Source: §1 · p. 2

1.1 Background and Notation

  • SPNs combine distribution leaves with sum and product nodes; completeness and decomposability support efficient inference, while selectivity requires at most one nonzero child per sum.Source: §1.1 · pp. 2–3
  • Derivatives with respect to indicator variables represent modified-evidence queries and can be evaluated for all variables and values in one back-propagation pass.Source: §1.1 · p. 3

1.2 Related Work

  • Prior work connected arithmetic circuits and SPNs to network-polynomial representations; a Bayesian-network representation organizes sum-node latent variables and model variables bipartitely with structured CPTs.Source: §1.2 · p. 3

2 LATENT VARIABLE INTERPRETATION

The paper repairs the indicator-variable interpretation of SPN sum nodes and formalizes augmented SPNs as latent-variable models with conditional-independence and weight semantics.

2 LATENT VARIABLE INTERPRETATION

  • Introducing latent-state indicators can make an ancestor sum incomplete and leave the latent-variable model unspecified when that sum is not on a selected branch.The latent state is irrelevant to the model-variable distribution on that branch, but its conditional distribution is not specified.Source: §2 · pp. 3–4

2.1 Augmentation of SPNs

  • Augmentation inserts links and indicators, adding twin sums where needed to preserve completeness and specify latent-state distributions.Normalized twin weights preserve the original SPN function when the latent variables are marginalized; uniform twin weights are a natural choice.Source: §2 · p. 4, §2.1 · pp. 4–5
  • An augmented SPN remains complete and decomposable, represents the original distribution over model variables, and fully specifies a joint model over model and latent variables.The augmented SPN can be quadratically larger in the worst case, and this bound is achieved by some SPN structures.Source: §2.1 · p. 5

2.2 Conditional Independencies in Augmented SPNs and Probabilistic Interpretation of Sum-Weights

  • Augmented-SPN latent variables are conditionally independent of non-descendants given their parent latent variables, and sum and twin weights encode conditional probabilities.The sum weights apply when parent latent variables select a path to the sum; twin weights apply for the complementary event.Source: §2.2 · p. 6
  • The augmented model has a Bayesian-network representation in which parent latent variables feed each sum's latent variable, which in turn connects to model variables in that sum's scope.When twin weights equal sum weights, the latent variables become independent of their parents, recovering the BN structure described in.Source: §2.2 · p. 6

3 EM ALGORITHM

The paper derives EM updates for SPN sum weights and input distributions from the augmented latent-variable model, using posterior statistics computed through SPN inference.

3 EM ALGORITHM

  • The paper formally derives standard EM updates for sum weights and exponential-family input distributions using augmented SPNs.The approach keeps twin weights fixed so that EM optimizes the original SPN's weights.Source: §3 · p. 6

3.1 Updates for Weights

  • A switching parent identifies whether parent latent variables select a sum or its twin, allowing the sum-weight update to use the corresponding expected posterior counts.Twin weights remain fixed, and the required posteriors can be computed through the differential approach without explicitly constructing the augmented SPN.Source: §3.1 · pp. 6–7

3.2 Updates for Input Distributions

  • For input distributions, distribution selectors identify which input model generated a variable, and exponential-family updates use expected sufficient statistics.The derivation is presented for univariate inputs; multivariate updates are said to be readily derivable, and Gaussian statistics over intervals admit closed-form integration.Source: §3.2 · p. 7
  • The resulting EM algorithm uses upward and backward passes to accumulate expected statistics and update sum weights and input-distribution parameters.The authors report empirical verification of the derivation and successful standard-EM training when a suitable structure is available.Source: §3.2 · p. 8

4 MOST PROBABLE EXPLANATION

MPE is generally NP-hard in SPNs, but the paper proves a Viterbi-style algorithm correct for selective SPNs. Augmentation makes SPNs selective over model and latent variables, enabling tractable MPE inference over both, though the result need not match MPE for the original model variables alone.

4 MOST PROBABLE EXPLANATION

  • MPE is generally NP-hard in SPNs, but selective SPNs admit a Viterbi-style solution using max-product networks.The selective-SPN result makes the backtracking algorithm applicable to augmented SPNs as well.Source: §4 · p. 8
  • Theorem 2 establishes that the max-product network maximizes probability in its corresponding selective SPN, with assignments recovered by Viterbi-style backtracking.At sum nodes, backtracking chooses the child with the maximal weighted maximum; at product nodes, it combines the children’s maximizing assignments.Source: §4 · p. 8
  • Augmented SPNs are selective over model and latent variables, so MPE is tractable over both, but discarding latent states need not yield the original SPN’s MPE solution.For each sum and latent-state assignment, exactly one indicator is set, so at most one child of the sum or its twin can be nonzero.Source: §4 · p. 8
  • The earlier algorithm on original SPNs simulates augmented-SPN MPE under deterministic twin-weights, a special case of the corrected-weight procedure.The correction factors reproduce the twin-node inputs; with all correction factors equal to 1, the twin-weights are deterministic.Source: §4 · p. 9
  • Deterministic twin-weights create a low-depth bias, favoring the less-structured P1 over P2 and P3; uniform weights instead penalize less-structured distributions.The authors leave further investigation of these effects to future work.Source: §4 · p. 9, Figure 8 · p. 9

5 EXPERIMENTS

The experiments test EM learning and Viterbi-style MPE inference. They report exact MPE recovery in augmented SPNs, while EM results depend on parameter choices and, for test-set gains, iteration selection.

5.1 Experiments with EM Algorithm

  • The EM study used 103 datasets, varied parameter updates, initialization, and missing-data settings, and ran 8,652 trials totaling 259,560 iterations.Missing-data settings randomly discarded 33% or 66% of observations; Gaussian variances had a lower bound of 0.01.Source: §5.1 · p. 10
  • Training log-likelihood increased over EM iterations, supporting monotonicity in the experiments except for tiny post-convergence decreases attributed to numerical artifacts.The reported exceptions were always below 10^-8.Source: §5.1 · p. 10, Figure 9 · p. 10
  • Post-training original parameters without Gaussian variances increased test likelihood on 83.5% of datasets for M and 92.23% for WM.With oracle iteration selection, average relative test-log-likelihood gains were 0.58% for M and 1.39% for WM; much of the gain occurred in the first iteration.Source: §5.1 · p. 10, Table 1 · p. 11
  • Variance-updating sets WV, MV, and WMV decreased test log-likelihood on more than 60% of datasets, but improved it by at least 14% on average in the remaining 40%.The improvement applies to the remaining datasets, not the full set.Source: §5.1 · p. 11
  • With random initialization, weight-only EM improved training likelihood on every dataset and exceeded original test likelihood on 67.96% using oracle iteration selection.The reported test comparison uses the iteration with the best test likelihood.Source: §5.1 · p. 11, Table 2 · p. 11

5.2 Experiments with MPE Inference

  • MPEUNI and MPEDET each found an MPE solution in augmented SPNs with, respectively, uniform and deterministic twin-weights.The comparisons use ground-truth solutions found by exhaustive enumeration.Source: §5.2 · p. 11, Table 3 · p. 11, Table 4 · p. 11
  • For original SPNs, MPEDET gave slightly better average approximations than MPEUNI, but the authors caution that the tested distributions were rather similar.They identify closer study of approximate MPE for original SPNs as future research.Source: §5.2 · p. 11, Table 5 · p. 12

6 CONCLUSION

The conclusion presents SPN augmentation as a sound basis for the latent-variable interpretation and related EM and MPE results. It also reports experimental support and successful standard EM training given a suitable network structure.

6 CONCLUSION

  • SPN augmentation provides a sound hierarchical latent-variable model, where the original explicit insertion of latent variables did not yield a sound probabilistic model.The paper also interprets augmented SPNs as Bayesian networks and sum-weights as structured conditional probability tables.Source: §6 · p. 12
  • The authors derive EM updates for sum-weights and single-dimensional input distributions from exponential families using augmented SPNs.The conclusion specifies single-dimensional input distributions.Source: §6 · p. 12
  • Viterbi-style backtracking recovers an MPE solution in selective SPNs, including augmented SPNs, although MPE inference is generally NP-hard for SPNs.The conclusion says experiments provide empirical evidence for the theoretical results and that standard EM can train generative SPNs given a suitable structure.Source: §6 · p. 12

A.1 Proof of Proposition 1

The proof establishes that augmentation preserves the represented distribution while producing a complete and decomposable SPN with the latent variables in the root scope.

A.1 Proof of Proposition 1

  • Setting all latent-state indicators to 1 marginalizes the added variables and leaves the augmented SPN's output equal to the original SPN's output.The proof states this equality for every assignment to the original variables.Source: §A.1 · p. 12
  • Adding private copies of sum children preserves completeness and decomposability, and introducing each latent variable places it in the root scope.Introducing latent variables can make ancestor sums incomplete, requiring the subsequent repair steps.Source: §A.1 · p. 12
  • The repair augments links missing a conditioning sum's latent variable, rendering that sum complete without making the links nondecomposable.The proof attributes possible incompleteness to links that lack the relevant latent variable in their scope.Source: §A.1 · p. 12

A.2 Proof of Proposition 2

The proof argues that deleting selected indicators and links preserves the configured SPN's structural properties and its output for the fixed assignment.

A.2 Proof of Proposition 2

  • Deleting indicators and their links preserves the scopes of sums and their ancestors because each affected sum is left with one child.The proof also states that the resulting graph remains rooted and acyclic.Source: §A.2 · p. 12
  • Completeness and decomposability remain intact because deleted indicators do not change the scopes of their sum nodes or ancestors.The proof also argues that reachable nodes and their descendants remain reachable.Source: §A.2 · p. 12
  • For the fixed assignment, deleted indicators and links evaluate to zero in the augmented SPN, so the configured and augmented outputs agree.The proof extends the equality from sums and twin sums to the root output.Source: §A.2 · p. 12

A.3 Proof of Lemma 1

The proof establishes that a configured SPN has a unique path to exactly one of S or its twin ¯S.

A.3 Proof of Lemma 1

  • A configured SPN contains a path to either S or ¯S, but not both.Source: §A.3 · p. 12
  • The induction begins with the root as the sole path and extends that path uniquely at each step.Source: §A.3 · p. 12
  • Decomposability gives product nodes a single scoped child, while relevant sum nodes have a single configured child.Source: §A.3 · p. 12

A.4 Proof of Theorem 1

The proof uses induction over the ancestors of S to establish the stated relation at the root, then treats the twin sum analogously.

A.4 Proof of Theorem 1

  • At the base case, the indicator link outputs 1 and the sum outputs wk.Source: §A.4 · p. 13
  • Induction over the ancestors of S establishes that each node's value with ZS=k is wk times its value without that condition.Source: §A.4 · p. 13
  • Completeness supplies the sum-node induction step, while decomposability gives a product node a single child with ZS in its scope.Source: §A.4 · p. 13
  • When the twin sum ¯S is absent, the corresponding claim is trivial; otherwise, the proof proceeds analogously.Source: §A.4 · p. 13

A.5 Proof of Theorem 2

The proof proceeds by induction over SPN nodes and uses decomposability and selective-sum support structure in its max-node step.

A.5 Proof of Theorem 2

  • The induction establishes the theorem for all nodes, including max nodes.Source: §A.5 · p. 13
  • At product nodes, decomposability permits the max and product operations to be switched.Source: §A.5 · p. 13
  • For a selective sum, child supports partition the sum's support, so an input with positive value has a single active child.Source: §A.5 · p. 13

Related papers

Loading 1601.06180v2…