Inference in discrete graphical models with variational methods is difficult
because of the inability to re-parameterize gradients of the Evidence Lower
Bound (ELBO). Many sampling-based methods have been proposed for estimating
these gradients, but they suffer from high bias or variance. In this paper, we
propose a new approach that leverages the tractability of probabilistic circuit
models, such as Sum Product Networks (SPN), to compute ELBO gradients exactly
(without sampling) for a certain class of densities. In particular, we show
that selective-SPNs are suitable as an expressive variational distribution, and
prove that when the log-density of the target model is a polynomial the
corresponding ELBO can be computed analytically. To scale to graphical models
with thousands of variables, we develop an efficient and effective construction
of selective-SPNs with size $O(kn)$, where $n$ is the number of variables and
$k$ is an adjustable hyperparameter. We demonstrate our approach on three types
of graphical models -- Ising models, Latent Dirichlet Allocation, and factor
graphs from the UAI Inference Competition. Selective-SPNs give a better lower
bound than mean-field and structured mean-field, and is competitive with
approximations that do not provide a lower bound, such as Loopy Belief
Propagation and Tree-Reweighted Belief Propagation. Our results show that
probabilistic circuits are promising tools for variational inference in
discrete graphical models as they combine tractability and expressivity.

本研究提出了一种新的方法，利用概率电路模型（如 Sum Product Networks）的可处理性，在一定类型的密度函数下，计算 ELBO 梯度的情况下，不需要采样即可精确计算。该方法在三种类型的图形模型上展示了其可行性，并证明了概率电路是离散图形模型的变分推断的有前途的工具，因为它们结合了可处理性和表达性。

离散图模型的变分推断概率电路

Probabilistic Circuits for Variational Inference in Discrete Graphical  Models

We consider the NP-hard problem of MAP-inference for undirected discrete
graphical models. We propose a polynomial time and practically efficient
algorithm for finding a part of its optimal solution. Specifically, our
algorithm marks some labels of the considered graphical model either as (i)
optimal, meaning that they belong to all optimal solutions of the inference
problem; (ii) non-optimal if they provably do not belong to any solution. With
access to an exact solver of a linear programming relaxation to the
MAP-inference problem, our algorithm marks the maximal possible (in a specified
sense) number of labels. We also present a version of the algorithm, which has
access to a suboptimal dual solver only and still can ensure the
(non-)optimality for the marked labels, although the overall number of the
marked labels may decrease. We propose an efficient implementation, which runs
in time comparable to a single run of a suboptimal dual solver. Our method is
well-scalable and shows state-of-the-art results on computational benchmarks
from machine learning and computer vision.

本文提出了一种用于找到 NP 难问题下离散图像模型 MAP 推理的部分最优解的算法，并通过使用一个线性规划松弛的精确求解器，标记出一些标签作为其最大可能的标签。

通过基于图模型的迭代松弛推断达到最大持久性

Maximum Persistency via Iterative Relaxed Inference with Graphical  Models

We propose a new yet natural algorithm for learning the graph structure of
general discrete graphical models (a.k.a. Markov random fields) from samples.
Our algorithm finds the neighborhood of a node by sequentially adding nodes
that produce the largest reduction in empirical conditional entropy; it is
greedy in the sense that the choice of addition is based only on the reduction
achieved at that iteration. Its sequential nature gives it a lower
computational complexity as compared to other existing comparison-based
techniques, all of which involve exhaustive searches over every node set of a
certain size. Our main result characterizes the sample complexity of this
procedure, as a function of node degrees, graph size and girth in factor-graph
representation. We subsequently specialize this result to the case of Ising
models, where we provide a simple transparent characterization of sample
complexity as a function of model and graph parameters.
For tree graphs, our algorithm is the same as the classical Chow-Liu
algorithm, and in that sense can be considered the extension of the same to
graphs with cycles.

提出了一种新的自然算法，用于从样本中学习一般离散图形模型（即马尔可夫随机场）的图结构，它是一种贪心的算法，并且具有较低的计算复杂度，并且通过节点度数、图大小以及因子图的环来表征其样本复杂度，在此基础上将其专门用于 Ising 模型。