Learning a Bayesian networks with bounded treewidth is important for reducing
the complexity of the inferences. We present a novel anytime algorithm (k-MAX)
method for this task, which scales up to thousands of variables. Through
extensive experiments we show that it consistently yields higher-scoring
structures than its competitors on complete data sets. We then consider the
problem of structure learning from incomplete data sets. This can be addressed
by structural EM, which however is computationally very demanding. We thus
adopt the novel k-MAX algorithm in the maximization step of structural EM,
obtaining an efficient computation of the expected sufficient statistics. We
test the resulting structural EM method on the task of imputing missing data,
comparing it against the state-of-the-art approach based on random forests. Our
approach achieves the same imputation accuracy of the competitors, but in about
one tenth of the time. Furthermore we show that it has worst-case complexity
linear in the input size, and that it is easily parallelizable.

本文提出一种新的 k-MAX 算法用于学习具有有界三角形宽度的贝叶斯网络，改进了数据不完全的结构 EM 算法，进而实现了缺失数据的填充。该算法可以在短时间内获得和竞争者相同的缺失数据恢复精度，并且具有线性最坏时间复杂度和易于并行化等优点。

从完整和不完整数据集中高效学习有界树宽贝叶斯网络

Efficient Learning of Bounded-Treewidth Bayesian Networks from Complete  and Incomplete Data Sets

In recent years there has been a flurry of works on learning Bayesian
networks from data. One of the hard problems in this area is how to effectively
learn the structure of a belief network from incomplete data- that is, in the
presence of missing values or hidden variables. In a recent paper, I introduced
an algorithm called Structural EM that combines the standard Expectation
Maximization (EM) algorithm, which optimizes parameters, with structure search
for model selection. That algorithm learns networks based on penalized
likelihood scores, which include the BIC/MDL score and various approximations
to the Bayesian score. In this paper, I extend Structural EM to deal directly
with Bayesian model selection. I prove the convergence of the resulting
algorithm and show how to apply it for learning a large class of probabilistic
models, including Bayesian networks and some variants thereof.

本文介绍了一种使用名为结构 EM 的算法进行贝叶斯模型学习的方法，该算法可以有效地从不完整数据中学习信念网络的结构，并可用于学习各种概率模型，包括贝叶斯网络和其变体。