cs.LGApr 8, 2026

Learning Markov Processes as Sum-of-Square Forms for Analytical Belief Propagation

Authors: Peter Amorese, Morteza Lahijanian

Organizations: University of Colorado Boulder

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Harnessing the predictive capability of Markov process models requires propagating probability density functions (beliefs) through the model. For many existing models however, belief propagation is analytically infeasible, requiring approximation or sampling to generate predictions. This paper proposes a functional modeling framework leveraging sparse Sum-of-Squares (SoS) forms for valid (conditional) density estimation. We study the theoretical restrictions of modeling conditional densities using the SoS form, and propose a novel functional form for addressing such limitations. The proposed architecture enables generalized simultaneous learning of basis functions and coefficients, while preserving analytical belief propagation. In addition, we propose a training method that allows for exact adherence to the normalization and non-negativity constraints. Our results show that the proposed method achieves accuracy comparable to state-of-the-art approaches while requiring significantly less memory in low-dimensional spaces, and it further scales to 12D systems when existing methods fail beyond 2D.

Figures & tables

Figure 1: Accuracy Comparison on 2D system against state-of-the-art density propagation methods
Figure 2: Visual Comparison for 6D Quadcopter system. (Left) Learned model. (Right) Monte Carlo simulation (ground truth).
Figure 3: Visual Comparison for 12D Quadcopter system. (Left) Learned model. (Right) Monte Carlo simulation (ground truth).
Experimentk=1k{=}135791113
4D Cartpole (SoS)-2.01 (0.0045)-2.79 (0.0011)-3.31 (0.0017)-3.77 (0.0016)-4.49 (0.0026)-5.99 (0.017)-8.60 (0.11)
4D Cartpole (NF)-1.88 (0.0019)-2.49 (0.011)-3.12 (0.027)-3.77 (0.056)-4.32 (0.050)-4.86 (0.085)-5.41 (0.10)
6D Quadrotor (SoS)-3.23 (0.22)-4.56 (0.57)-5.61 (0.84)-6.42 (0.82)-6.82 (0.92)-7.06 (1.0)-7.52 (1.2)
6D Quadrotor (NF)-4.01 (0.0029)-5.85 (0.013)-7.04 (0.033)-7.93 (0.017)-8.69 (0.045)-9.28 (0.031)-9.88 (0.076)
6D Dubin’s Car w/ Trailer (SoS)-4.10 (1.1)-5.60 (0.79)-5.84 (0.84)-6.33 (0.11)-6.76 (0.15)-6.97 (0.16)-6.97 (0.19)
6D Dubin’s Car w/ Trailer (NF)-3.24 (0.023)-2.96 (0.049)-2.28 (0.054)-3.64 (0.056)-4.91 (0.058)-5.64 (0.085)-6.07 (0.086)
Table 1: Accuracy comparison to the deep Normalizing Flow model. Average (test) log-likelihood values are shown as mean (std).
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Visual comparison for the 6D quadcopter system across timesteps k=0…9k=0\dots 9 . Beliefs are shown with corresponding Monte Carlo ground truth below.
Figure 5: Visual comparison for the 12D stabilizing quadcopter system across timesteps k=0…9k=0\dots 9 . Beliefs are shown with corresponding Monte Carlo ground truth below. The full state definition is x=[x,y,z,ϕ,θ,ψ,vx,vy,vz,ωp,ωq,ωr]\mathbf{x}=[x,y,z,\phi,\theta,\psi,v_{x},v_{y},v_{z},\omega_{p},\omega_{q},\omega_{r}] with position (x,y,z)(x,y,z) and Euler angles (ϕ,θ,ψ)(\phi,\theta,\psi) . Position marginals p(x,y)p(x,y) , angular velocity marginals p(r,q)p(r,q) and translational velocity marginals p(vx,vz)p(v_{x},v_{z}) are shown.
More in this topic

Belief Propagation

See all 11 papers

Explore similar work

CardsList
May 12, 2026

On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines

Matrix product operator Born machines (MPO-BMs) are tractable tensor-network models for probabilistic modeling, yet their approximation capabilities remain poorly understood in theory. In this paper, we characterize these capabilities from both negative and positive perspectives. As a negative result, we prove that constructing a polynomial-bond MPO-BM approximation to an arbitrary continuous target with bounded KL error is NP-hard. On the positive side, for score-based variational inference, we prove that targets satisfying a log-Sobolev inequality admit polynomial-bond MPO-BM approximations with provable KL guarantees when the loss-induced Hamiltonian is local and has a constant spectral gap. Furthermore, under the same conditions, we construct local importance-sampling estimators and prove that polynomially many local score queries suffice to preserve the KL guarantees.

Chao Li, Zerui Tao, Yuchen Cong +2

RIKEN-AIP · Jutentedo University

Tensor NetworksApproximation Algorithms
AskPDF
Sep 25, 2017

A polynomial time algebraic solution to exact marginal inference in Markov Random Field models

This paper develops on algebraic grounds a polynomial time exact linear solution to the hard combinatorial problem of marginal inference in Markov random field (MRF) models under general assumptions. To prove our claim, we first implicitly remodel a MRF joint distribution as the unique solution of some linear identity assuming its clique potential functions (equivalently, its individual conditional distributions) to be specified. Then, by assuming an arbitrary point subset, we relax accordingly such a (global) linear identity for deriving a second linear identity, solely, acting on a polynomial time number of entries (e.g.; local marginals or Fourier frequencies) of a solution. Then, we show, only using linear algebraic techniques, that such an identity enables to capture all the entries necessary for the exact reconstruction of an MRF marginal distribution, thus, allowing to solve for the latter, exactly and in polynomial time, using a standard linear solver. Last, but not least, this paper probably solves, once and for all, the P = NP conjecture.

Ikhlef Bechar

Aix Marseille Univ, Universit´e de Toulon, CNRS, ENSAM, LSIS La Garde 83957, France

Efficient InferenceMarkov Random FieldsMarkov ModelsProbabilistic Graphical Models
AskPDF