PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Graphical Model Parameters with Approximate Marginal Inference

Justin Domke

arXiv:1301.3193v1cs.LGcs.CV

TL;DR

Graphical-model parameter learning must address computational complexity, approximate inference, and model mis-specification. The paper fits parameters using losses based directly on predicted marginals and introduces truncated learning to reduce inference cost. Experiments suggest marginal-based losses perform better on harder problems, especially when inference approximations and model mis-specification are substantial.

  • Problem

    High-treewidth graphical-model training faces computational complexity, the need for approximate inference, and model mis-specification.

  • Method

    The paper trains parameters using marginal-based losses that reflect a chosen approximate inference algorithm and introduces truncated learning with a fixed number of inference iterations.

  • Results

    Marginal-based loss functions perform better than likelihood-based approximations on harder problems, although surrogate likelihood generally has smaller train/test gaps.

  • Takeaways & Limitations

    Marginal-based learning more closely reflects Hamming-loss evaluation and is more amenable to truncation than surrogate likelihood.

  • Takeaways & Limitations

    Exact variational optimization remains generally intractable because the marginal polytope and entropy are difficult to characterize or compute.

Abstract

from arXiv · show

Likelihood based-learning of graphical models faces challenges of computational-complexity and robustness to model mis-specification. This paper studies methods that fit parameters directly to maximize a measure of the accuracy of predicted marginals, taking into account both model and inference approximations at training time. Experiments on imaging problems suggest marginalization-based learning performs better than likelihood-based approximations on difficult problems where the model being fit is approximate in nature.

1 INTRODUCTION

Graphical-model learning is difficult because exact inference is often intractable, while likelihood approximations may not address inference error or model mis-specification. The paper proposes marginalization-based losses and fitting methods that account for both issues during training.

  • High-treewidth graphs make exact inference computationally intractable.
  • Marginalization-based losses directly measure the quality of predictions produced by a given marginal inference algorithm.
  • Training with these losses incorporates inference approximation errors and is robust to model mis-specification.
  • The paper introduces implicit differentiation, perturbation-based gradients, and truncated fitting for marginalization-based parameter learning.Truncated fitting targets marginals after a fixed number of inference updates without assuming convergence.
  • Experiments find marginalization-based learning performs better on difficult problems where inference approximations and model mis-specification are most significant.

2 SETUP

The setup defines graphical-model distributions, conditional prediction objectives, and learning as empirical-risk minimization. It motivates marginal-based losses by distinguishing exact-output MAP decisions from componentwise MPM decisions in imaging applications.

  • 2.1 Markov Random Fields: Markov random fields factorize distributions over graph cliques and variables, with a normalization factor Z.
  • 2.2 Conditional Random Fields: Conditional random fields model p(x|y) by making factor values depend on observations y.
  • 2.3 Inference Problems: MAP inference selects the single most probable complete output under exact-match utility.
  • 2.3 Inference Problems: Hamming-based utility leads to MPM inference, which selects the most likely value for each output component independently.
  • 2.3 Inference Problems: Marginal-based losses target marginal accuracy because test-time MPM inference depends on computing p(x_i|y).
  • 2.5 Learning: Learning minimizes empirical risk over examples, with the loss function measuring how well parameters match observed data and gradients enabling optimization.

3 VARIATIONAL INFERENCE

Variational inference converts log-partition computation into optimization over marginal vectors, then approximates the feasible set or entropy to obtain tractable marginals. Mean field restricts the feasible set, whereas TRW expands it and bounds the entropy.

  • 3 Variational Inference: Approximate marginalization derives an approximate log-partition function and takes its exact gradient as the approximate marginals.
  • 3.1 Exact Variational Principle: The exact variational principle is tractable on trees but generally intractable because the marginal polytope and entropy are difficult to characterize or compute.
  • 3.2 Mean Field: Mean field replaces the marginal polytope with a tractable subset corresponding to fully factorized distributions.
  • 3.2 Mean Field: Mean field produces a lower approximate log-partition value, ˜A(θ) ≤ A(θ), because it maximizes the objective over a restricted constraint set.
  • 3.3 Tree-Reweighted Belief Propagation: TRW replaces the marginal polytope with a superset and approximates entropy with a tractable upper bound, yielding an upper bound on the log-partition function.
  • 3.3 Tree-Reweighted Belief Propagation: The TRW marginal vector can be inconsistent on general graphs because the local polytope may contain unrealizable vectors.
  • 3.3 Tree-Reweighted Belief Propagation: TRW gives ˜A(θ) ≥ A(θ), and converged message-passing marginals constitute the global optimum of its optimization problem.

4 LOSS FUNCTIONS

The section contrasts likelihood approximations with marginalization-based losses, which directly optimize predicted marginal accuracy and account for inference approximations and model mis-specification.

  • Likelihood-based approximations: Likelihood approximations include MCMC, surrogate likelihoods, saddle-point methods, pseudolikelihood, patch pseudolikelihood, and piecewise likelihood.These methods differ in whether they approximate inference, the partition function, or the likelihood structure.
  • Marginalization-based losses: Marginalization-based losses directly quantify predicted marginal quality, incorporating inference approximation errors during learning and improving robustness to model mis-specification.They optimize the predictions produced by the marginal inference algorithm used at training time.
  • Marginal-based losses: Univariate logistic loss measures the mean accuracy of univariate marginals and can be interpreted as empirical risk minimization of marginal KL-divergence.The loss uses marginal predictions from either exact or approximate inference.
  • Classification losses: Smoothed univariate classification loss approximates nondifferentiable MPM classification error with a sigmoid, but can become trapped in local minima and is excluded from the experiments.The sigmoid parameter α controls approximation quality.
  • Model mis-specification: For well-specified models, likelihood and marginal-based losses perform essentially identically, whereas mis-specification produces different parameter estimates.Figure 1 reports mean test error under exact inference as model shifts increase.

5 IMPLICIT FITTING

Implicit fitting differentiates a loss defined on approximate marginals with respect to model parameters. The gradient can be obtained through a sparse linear system, although the result does not apply to mean field's nonlinear constraint set.

  • Loss evaluation: Marginal-based loss values are computed by running inference and substituting the resulting marginals into the loss.Training additionally requires the parameter gradient dL/dθ.
  • Implicit differentiation: The loss gradient can be obtained by solving a sparse linear system that transforms dQ/dµ into dL/dθ.Q is defined directly on marginals, while L is defined in terms of parameters.
  • Scope of the result: The linear-system theorem applies under linear constraints, including the local polytope used in TRW, but not to mean field.Mean field's constraint set is nonlinear when clique and univariate marginals are considered jointly.
  • Practical computation: The subsequent methods avoid explicitly forming the constraint matrix B or solving the linear system.This makes the practical gradient procedure simpler to use.

6 PERTURBATION

The perturbation approach computes gradients by finite differences of inference outputs under slightly perturbed parameters. More-sided differences improve accuracy, but require additional inference runs.

  • Finite-difference gradients: Finite differences estimate Jacobian-vector products by rerunning inference with perturbed parameters.This provides a practical route to approximate the loss gradient.
  • Difference schemes: Two-sided and four-sided differences reduce approximation error relative to one-sided differences, at the cost of more inference calls.Two-sided differences are accurate to order o(r^2), while four-sided differences are more accurate.
  • Perturbation size: Small perturbations make numerical errors dominate, while large perturbations make approximation errors dominate.The perturbation multiplier therefore requires a tradeoff between the two error sources.
  • Experimental choice: Using two-sided differences with multiplier 1 was selected as a tradeoff among accuracy, simplicity, and computational expense.The experiments used double precision and inference convergence thresholds below 10^-15 in marginal change.

7 TRUNCATED FITTING

Truncated fitting defines learning objectives using marginals produced after a fixed number of inference iterations, rather than requiring convergence. The section develops differentiable backpropagation procedures for mean field and TRW while highlighting threshold and iteration-count risks.

  • Convergence Thresholds: A loose learning-stage convergence threshold can produce a bad estimated risk gradient and terminate learning with a bad search direction.A threshold difference of 10^-3 in estimated marginals may have little practical test-time impact yet still prevent learning from succeeding.
  • Motivation: Fixed-iteration objectives treat inference as a differentiable function from parameters to predicted marginals and loss.This avoids spending most computation exploring convergence levels that may be irrelevant to practical model performance.
  • Back Mean Field: Back mean field initializes uniform marginals, runs N iterations, and differentiates the loss evaluated on the resulting marginals.The gradient is obtained by mechanically differentiating each inference step, using stored intermediate values during reverse execution.
  • Back Mean Field: Back mean field produces univariate marginals, while mean-field clique marginals can be represented as products of those univariate marginals.Consequently, losses defined on clique marginals can equivalently be expressed using univariate marginals under mean field.
  • Back TRW: Back TRW similarly differentiates a loss after a fixed number N of inference iterations using reverse processing of stored messages.The section presents this as truncated fitting with TRW inference and gives a corresponding algorithm and theorem.
  • Truncated Partition Functions: Truncation applies directly to marginal-based losses, whereas likelihood and EM losses require a truncated partition function built from approximate entropies.With too few iterations, this surrogate-likelihood approximation can diverge; with zero iterations, arbitrary loss may be achievable when dataset feature means differ from the initial marginals.

8 EXPERIMENTS

Experiments on denoising, horse segmentation, and backgrounds compare marginal-based learning with likelihood-based alternatives under approximate inference and truncated computation. Marginal-based losses generally perform better on harder problems and remain effective with few inference iterations, while surrogate likelihood methods can diverge when iterations are too few.

  • Experimental setup: The experiments compare marginal-based learning with surrogate likelihood/EM, pseudolikelihood, and piecewise likelihood using vision datasets and approximate inference.The comparisons use the same inference method where possible and include settings with hidden variables.
  • Binary denoising: On binary denoising, marginal-based losses outperform surrogate likelihood and pseudolikelihood at high noise levels.All methods perform well at low noise, while marginal-based methods show a considerable advantage as model mis-specification becomes more pronounced.
  • Horses: On the horses dataset, TRW consistently outperforms mean field, while marginal-based losses outperform the other learning methods in training and test errors.With fewer than 20 iterations, truncated surrogate likelihood diverges and produces errors around 0.4.
  • Stanford backgrounds: On the backgrounds dataset, truncated fitting is more successful than perturbation and back-propagation under loose thresholds, although more iterations improve converged performance.The comparison uses 100 images and TRW to fit the univariate logistic loss.
  • Stanford backgrounds: On the full backgrounds experiment, marginal-based losses outperform other methods and remain effective with 5 iterations, where truncated EM diverges.Errors are estimated by five-fold cross-validation, with regularization settings chosen separately for method families.

9 CONCLUSIONS

The paper addresses model mis-specification, approximate inference, and computational complexity by learning from the marginals produced by approximate inference algorithms. Experiments find that marginal-based losses perform best on harder problems and are more amenable to truncation than likelihood-based alternatives.

  • Challenges: Graphical-model parameter learning in high-treewidth settings must address model mis-specification, approximate inference, and computational complexity.These are the three challenges emphasized in the conclusion.
  • Contribution: The proposed methods train parameters from marginals predicted by a given approximate inference algorithm, with truncated learning limiting inference to a fixed number of iterations.Truncation is also applied heuristically to surrogate likelihood.
  • Findings: Marginal-based losses outperform surrogate likelihood, pseudolikelihood, and piecewise learning on harder problems and are more amenable to truncation.Surrogate likelihood generally has smaller train/test gaps but diverges with too few iterations.

10 BIOGRAPHY

Justin Domke earned a PhD in Computer Science from the University of Maryland in 2009 and later joined NICTA's Machine Learning group in 2012.

  • Biography: Justin Domke earned a Computer Science PhD from the University of Maryland, College Park, in 2009.He was an Assistant Professor at Rochester Institute of Technology from 2009 to 2012.
  • Biography: Since 2012, Domke has been a member of the Machine Learning group at NICTA.

11 APPENDIX A: VARIATIONAL INFERENCE

The appendix develops variational formulations and inference updates for mean-field and TRW approximations. It establishes exactness or optimality results under specific structural and convergence conditions, while noting that mean-field optimization may reach only a local maximum.

  • Variational principles: The exact variational principle characterizes the log-partition function through constrained optimization over valid marginals.The derivation uses the marginal polytope and the conjugate dual representation.
  • Mean-field inference: Mean-field inference reduces the approximate partition-function problem to optimization over univariate marginals.Its updates can reach a local maximum, with normalization by Z producing the resulting marginals.
  • Mean-field inference: Mean-field optimization is non-concave, so the resulting solution is only guaranteed to be a local maximum.The appendix explicitly cautions that no global-optimality guarantee follows for the mean-field objective.
  • TRW inference: The approximate entropy is exact for tree-structured graphs when ρc = 1.This tree-specific result underpins the subsequent TRW entropy bound.
  • TRW inference: For a distribution over tree-structured graphs, the TRW entropy is an upper bound under the theorem’s edge-appearance probabilities ρc.The appendix combines tree-specific lemmas to establish the bound.
  • TRW inference: If TRW updates reach a fixed point, the resulting marginals constitute the global optimum of the TRW objective.The fixed-point equations arise from enforcing consistency constraints through message updates.

12 APPENDIX B: IMPLICIT DIFFERENTIATION

The appendix derives implicit differentiation and backpropagation procedures for approximate inference. It applies these procedures to mean-field and TRW iterations, including normalization, marginal computation, parameter updates, and message propagation.

  • Implicit differentiation: Implicit differentiation expresses how constrained variational solutions change with model parameters through derivatives of the Lagrangian constraints.The derivation uses the implicit function theorem and block-matrix derivatives.
  • Derivative rules: The normalized-products treatment supplies reusable derivative rules for products followed by normalization and for exponential or powered factors.These rules support updates to parameters and messages in the approximate inference algorithms.
  • Backpropagation through mean field: Backpropagation through mean-field mechanically differentiates each iteration from the loss through intermediate marginals to parameters and neighboring marginals.The procedure first backpropagates through normalization, then computes derivatives with respect to θ and intermediate marginals.
  • Backpropagation through TRW: Backpropagation through TRW differentiates clique marginals, univariate marginals, propagation steps, and message updates.The derivation treats normalized marginal-producing steps before propagating derivatives through the main message updates.
Loading 1301.3193v1…