This paper considers the problem of testing the maximum in-degree of the
Bayes net underlying an unknown probability distribution $P$ over $\{0,1\}^n$,
given sample access to $P$. We show that the sample complexity of the problem
is $\tilde{\Theta}(2^{n/2}/\varepsilon^2)$. Our algorithm relies on a
testing-by-learning framework, previously used to obtain sample-optimal
testers; in order to apply this framework, we develop new algorithms for
``near-proper'' learning of Bayes nets, and high-probability learning under
$\chi^2$ divergence, which are of independent interest.

本文研究了在给定概率分布 P（{0,1}^n 上），并具有样本访问的情况下，测试潜在贝叶斯网络的最大入度的问题。研究表明，该问题的样本复杂度为  Θ(2^(n/2)/ε^2) 。我们的算法依赖于先前用于获得样本最优测试器的测试通过学习框架；为了应用该框架，我们开发了新的算法来进行 “近似适当” 的贝叶斯网络学习，并在 χ^2 差异下高概率学习，这具有独立兴趣。

贝叶斯网络近似最优度数测试

Near-Optimal Degree Testing for Bayes Nets

Many machine learning applications use latent variable models to explain
structure in data, whereby visible variables (= coordinates of the given
datapoint) are explained as a probabilistic function of some hidden variables.
Finding parameters with the maximum likelihood is NP-hard even in very simple
settings. In recent years, provably efficient algorithms were nevertheless
developed for models with linear structures: topic models, mixture models,
hidden markov models, etc. These algorithms use matrix or tensor decomposition,
and make some reasonable assumptions about the parameters of the underlying
model.
But matrix or tensor decomposition seems of little use when the latent
variable model has nonlinearities. The current paper shows how to make
progress: tensor decomposition is applied for learning the single-layer {\em
noisy or} network, which is a textbook example of a Bayes net, and used for
example in the classic QMR-DT software for diagnosing which disease(s) a
patient may have by observing the symptoms he/she exhibits.
The technical novelty here, which should be useful in other settings in
future, is analysis of tensor decomposition in presence of systematic error
(i.e., where the noise/error is correlated with the signal, and doesn't
decrease as number of samples goes to infinity). This requires rethinking all
steps of tensor decomposition methods from the ground up.
For simplicity our analysis is stated assuming that the network parameters
were chosen from a probability distribution but the method seems more generally
applicable.

本文介绍了如何使用张量分解学习单层嘈杂或网络的方法，并解决了存在系统性误差时如何对张量分解进行分析的问题，这一方法在其他设置中可能有用。

可证明的 Noisy-or 网络学习

Provable learning of Noisy-or Networks

Tasks such as record linkage and multi-target tracking, which involve
reconstructing the set of objects that underlie some observed data, are
particularly challenging for probabilistic inference. Recent work has achieved
efficient and accurate inference on such problems using Markov chain Monte
Carlo (MCMC) techniques with customized proposal distributions. Currently,
implementing such a system requires coding MCMC state representations and
acceptance probability calculations that are specific to a particular
application. An alternative approach, which we pursue in this paper, is to use
a general-purpose probabilistic modeling language (such as BLOG) and a generic
Metropolis-Hastings MCMC algorithm that supports user-supplied proposal
distributions. Our algorithm gains flexibility by using MCMC states that are
only partial descriptions of possible worlds; we provide conditions under which
MCMC over partial worlds yields correct answers to queries. We also show how to
use a context-specific Bayes net to identify the factors in the acceptance
probability that need to be computed for a given proposed move. Experimental
results on a citation matching task show that our general-purpose MCMC engine
compares favorably with an application-specific system.

使用通用的概率建模语言和泛用的 Metropolis-Hastings MCMC 算法，通过使用部分世界的 MCMC 状态，探索了一种基于上下文特定贝叶斯网络的可通用的 MCMC 引擎，可进行如记录链接和多目标跟踪之类的推理任务。实验结果表明，我们的通用 MCMC 引擎与特定应用系统相比具有较高的吻合度。