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

Ikhlef Bechar

math.OCSep 25, 2017

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

Authors: Ikhlef Bechar

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

Abstract

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.

Explore similar work

May 5, 2026cs.DS

Exact and Approximate Algorithms for Polytree Learning

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of

n

variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time

O((2+ε)^n)

for arbitrarily small

ε> 0

and any constant in-degree bound

k

, improving over the fastest previously known algorithm of time complexity

O(3^n)

. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of

k

from the optimal one for arbitrary scores and a factor of

2

for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

Juha Harviainen, Frank Sommer, Manuel Sorge

Department of Computer Science, University of Helsinki, Helsinki, Finland · Institute of Computer Science, Friedrich-Schiller Universität Jena, Jena, Germany · Institute of Logic and Computation, TU Wien, Vienna, Austria

Bayesian Networks Approximation Algorithms Np-Hard Polynomials Exact Efficient Inference+1

Ask PDF

May 12, 2026cs.LG

On the Approximation Complexity of Matrix Product Operator Born Machines

Matrix product operator Born machines (MPO-BMs) are tractable tensor-network models for probabilistic modeling, but their efficient approximation capability remains unclear. We characterize this boundary from both negative and positive perspectives. First, we prove that KL approximation is NP-hard for MPO-BMs in the continuous setting, ruling out universal efficient approximation in the worst case. Second, for score-based variational inference, we show that, under a locality and spectral-gap conditions on the loss-induced Hamiltonian, structured targets (e.g., path-graph Markov random fields) admit MPO-BM approximations with polynomial bond dimension and provable KL guarantees. Third, under the same locality structure, we prove that polynomially many score queries suffice to estimate the induced Hamiltonian and obtain such guarantees. Our results provide a theoretical characterization of when MPO-BMs are fundamentally hard to approximate and when they become efficiently learnable.

Chao Li, Zerui Tao, Yuchen Cong +2

RIKEN-AIP · Jutentedo University

Tensor Networks Variational Inference Matrix Multiplication Hamiltonian

Ask PDF

Jul 6, 2026stat.ML

Decomposition for Bayesian Networks: Local and Parallel Inference

Probabilistic inference in high-dimensional Bayesian networks is difficult because exact manipulation of the joint distribution scales exponentially with network size. We propose a decomposition framework based on directed convex subgraphs and introduce a minimal d-decomposition tree. Together, they provide a principled alternative to classical junction-tree constructions. The proposed framework represents the joint distribution by lower-dimensional sub-models that can be learned and stored separately. This decomposition reduces computational cost and naturally enables parallel computation. Based on a minimal d-decomposition tree, we further develop two parallel algorithms for parameter estimation and probabilistic inference. Experiments show that the proposed method substantially improves computational efficiency over junction-tree methods while maintaining inference accuracy, especially for low-dimensional queries.

Pei Heng, Xinyi Hu, Yi Sun

Institute of Statistics and Data Science, Xinjiang University of Finance and Economics, Urumqi, China

Bayesian Networks Probabilistic Inference Network Science Decomposition Convex Sets

Ask PDF