Bayes nets are extensively used in practice to efficiently represent joint
probability distributions over a set of random variables and capture dependency
relations. In a seminal paper, Chickering et al. (JMLR 2004) showed that given
a distribution $P$, that is defined as the marginal distribution of a Bayes
net, it is $\mathsf{NP}$-hard to decide whether there is a parameter-bounded
Bayes net that represents $P$. They called this problem LEARN. In this work, we
extend the $\mathsf{NP}$-hardness result of LEARN and prove the
$\mathsf{NP}$-hardness of a promise search variant of LEARN, whereby the Bayes
net in question is guaranteed to exist and one is asked to find such a Bayes
net. We complement our hardness result with a positive result about the sample
complexity that is sufficient to recover a parameter-bounded Bayes net that is
close (in TV distance) to a given distribution $P$, that is represented by some
parameter-bounded Bayes net, generalizing a degree-bounded sample complexity
result of Brustle et al. (EC 2020).

Bayes nets are widely used to represent probability distributions and dependency relations; this paper extends the NP-hardness result of LEARN and proves the NP-hardness of a promise search variant, while also providing a positive result on sample complexity for recovering a parameter-bounded Bayes net.

参数有界贝叶斯网络的可学习性

Learnability of Parameter-Bounded Bayes Nets

In this paper, we establish a novel connection between total variation (TV)
distance estimation and probabilistic inference. In particular, we present an
efficient, structure-preserving reduction from relative approximation of TV
distance to probabilistic inference over directed graphical models. This
reduction leads to a fully polynomial randomized approximation scheme (FPRAS)
for estimating TV distances between distributions over any class of Bayes nets
for which there is an efficient probabilistic inference algorithm. In
particular, it leads to an FPRAS for estimating TV distances between
distributions that are defined by Bayes nets of bounded treewidth. Prior to
this work, such approximation schemes only existed for estimating TV distances
between product distributions. Our approach employs a new notion of $partial$
couplings of high-dimensional distributions, which might be of independent
interest.

通过图模型和概率推理，本论文建立了总变差距离的新连接，提出了一种有效的降维方法，实现了对有界树宽的贝叶斯网分布进行总变差距离的估计。

总变差距离估计像概率推断一样简单

Total Variation Distance Estimation Is as Easy as Probabilistic  Inference

Inference in Bayes Nets (BAYES) is an important problem with numerous
applications in probabilistic reasoning. Counting the number of satisfying
assignments of a propositional formula (#SAT) is a closely related problem of
fundamental theoretical importance. Both these problems, and others, are
members of the class of sum-of-products (SUMPROD) problems. In this paper we
show that standard backtracking search when augmented with a simple memoization
scheme (caching) can solve any sum-of-products problem with time complexity
that is at least as good any other state-of-the-art exact algorithm, and that
it can also achieve the best known time-space tradeoff. Furthermore,
backtracking's ability to utilize more flexible variable orderings allows us to
prove that it can achieve an exponential speedup over other standard algorithms
for SUMPROD on some instances.
The ideas presented here have been utilized in a number of solvers that have
been applied to various types of sum-of-product problems. These system's have
exploited the fact that backtracking can naturally exploit more of the
problem's structure to achieve improved performance on a range of
probleminstances. Empirical evidence of this performance gain has appeared in
published works describing these solvers, and we provide references to these
works.

使用简单的记忆化方案可以将标准回溯搜索与最先进的精确算法相混合，以更好的时间复杂度解决任何 sum-of-products 问题，并且具有最佳的时间空间权衡，并且这种方法可以实现其他标准算法的指数加速，适用于各种类型的 sum-of-product 问题，已有多项研究验证了其性能优势。

使用回溯搜索解决 #SAT 和贝叶斯推断

Solving #SAT and Bayesian Inference with Backtracking Search

This paper develops a declarative language, P-log, that combines logical and
probabilistic arguments in its reasoning. Answer Set Prolog is used as the
logical foundation, while causal Bayes nets serve as a probabilistic
foundation. We give several non-trivial examples and illustrate the use of
P-log for knowledge representation and updating of knowledge. We argue that our
approach to updates is more appealing than existing approaches. We give
sufficiency conditions for the coherency of P-log programs and show that Bayes
nets can be easily mapped to coherent P-log programs.

本文提出了一个基于 Answer Set Prolog 作为逻辑基础、以因果贝叶斯网络为概率基础的声明式语言 P-log，用于知识表示和知识更新，并给出了多个例子表明更新方法更加优越。同时，论文给出了实现 P-log 程序的充分条件，并证明了 Bayes nets 的易于映射到符合条件的 P-log 程序上。