A new class of upper bounds on the log partition function
A new class of upper bounds on the log partition function
复制标题
DOI：
10.1109/tit.2005.850091
复制
发表时间：
2005-07-01
影响因子：
2.5
通讯作者：
Willsky, AS
中科院分区：
文献类型：
--
作者：
Wainwright, MJ;Jaakkola, TS;Willsky, AS
我们在马尔可夫随机场 (MRIT) 的对数划分函数上引入了一类新的上限。该量在各种情况下发挥着重要作用，包括近似边际分布、参数估计、组合枚举、统计决策理论和大偏差界限。我们的推导基于凸对偶性和信息几何的概念：特别是，它利用指数域中的分布混合以及指数和平均参数之间的勒让德映射。在树结构分布的凸组合的特殊情况下，我们获得了一系列变分问题，类似于 Bethe 变分问题，但具有以下理想性质： i) 它们是凸的，并且具有唯一的全局最优值； ii) 最优值给出了对数配分函数的上限。该最优值由稳态条件定义，与定义和积算法的固定点的条件非常相似，或者更一般地说，由 Bethe 变分问题的任何局部最优值定义。与和积固定点一样，优化参数的元素可以用作原始模型边缘的近似值。该分析自然地扩展到超树结构分布的凸组合，从而建立了与菊池近似和变体的联系。
We introduce a new class of upper bounds on the log partition function of a Markov random field (MRIT). This quantity plays an important role in various contexts, including approximating marginal distributions, parameter estimation, combinatorial enumeration, statistical decision theory and large-deviations bounds. Our derivation is based on concepts from convex duality and information geometry: in particular, it exploits mixtures of distributions in the exponential domain, and the Legendre mapping between exponential and mean parameters. In the special case of convex combinations of tree-structured distributions, we obtain a family of variational problems, similar to the Bethe variational problem, but distinguished by the following desirable properties: i) they are convex, and have a unique global optimum; and ii) the optimum gives an upper bound on the log partition function. This optimum is defined by stationary conditions very similar to those defining fixed points of the sum-product algorithm, or more generally, any local optimum of the Bethe variational problem. As with sum-product fixed points, the elements of the optimizing argument can be used as approximations to the marginals of the original model. The analysis extends naturally to convex combinations of hypertree-structured distributions, thereby establishing links to Kikuchi approximations and variants.