Inferning with High Girth Graphical Models
Inferning with High Girth Graphical Models
复制标题
用高周长图形模型进行推理
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Globerson
中科院分区：
文献类型：
--
作者：
Uri Heinemann;A. Globerson
图形模型的无监督学习在许多领域都是一个重要的任务。虽然最大似然学习在计算上是困难的，但确实存在一致的学习算法(例如，伪似然及其变体)。然而，学习的模型中的推理仍然很难，因此它们不能直接使用。换句话说，在给定概率查询的情况下，它们不能保证提供接近真实答案的答案。
在本文中，我们提供了一种学习算法，它保证提供近似正确的概率推理。我们专注于一类特殊的模型，即相关衰减区的高周长图。众所周知，在这类模型中，近似推理(例如，使用循环BP)产生的边际接近真实边际。受此启发，我们提出了一个算法，它总是返回这种类型的模型，因此在它返回的模型中，推理是近似正确的。我们得到的有限样本结果保证了超过一定的样本大小，所得到的模型将以高水平的精度回答概率查询。
在合成数据上的结果表明，我们学习的模型确实优于其他算法获得的模型，这些算法不会返回高周长图。
Unsupervised learning of graphical models is an important task in many domains. Although maximum likelihood learning is computationally hard, there do exist consistent learning algorithms (e.g., psuedo-likelihood and its variants). However, inference in the learned models is still hard, and thus they are not directly usable. In other words, given a probabilistic query they are not guaranteed to provide an answer that is close to the true one.
In the current paper, we provide a learning algorithm that is guaranteed to provide approximately correct probabilistic inference. We focus on a particular class of models, namely high girth graphs in the correlation decay regime. It is well known that approximate inference (e.g, using loopy BP) in such models yields marginals that are close to the true ones. Motivated by this, we propose an algorithm that always returns models of this type, and hence in the models it returns inference is approximately correct. We derive finite sample results guaranteeing that beyond a certain sample size, the resulting models will answer probabilistic queries with a high level of accuracy.
Results on synthetic data show that the models we learn indeed outperform those obtained by other algorithms, which do not return high girth graphs.