• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference
【24h】

Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference

机译：规范产品的信念传播：近似推断的原始-双重消息传递

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Inference problems in graphical models can be represented as a constrained optimization of a free-energy function. In this paper, we treat both forms of probabilistic inference, estimating marginal probabilities of the joint distribution and finding the most probable assignment, through a unified message-passing algorithm architecture. In particular we generalize the belief propagation (BP) algorithms of sum-product and max-product and tree-reweighted (TRW) sum and max product algorithms (TRBP) and introduce a new set of convergent algorithms based on “convex-free-energy” and linear-programming (LP) relaxation as a zero-temperature of a convex-free-energy. The main idea of this work arises from taking a general perspective on the existing BP and TRBP algorithms while observing that they all are reductions from the basic optimization formula of $f+sum_{i}h_{i}$ where the function $f$ is an extended-valued, strictly convex but nonsmooth and the functions $h_{i}$ are extended-valued functions (not necessarily convex). We use tools from convex duality to present the “primal-dual ascent” algorithm which is an extension of the Bregman successive projection scheme and is designed to handle optimization of the general type $f+sum_{i}h_{i}$. We then map the fractional-free-energy variational principle for approximate inference onto the optimization formula above and introduce the “norm-product” message-passing algorithm. Special cases of the norm-product include sum-product and max-product (BP algorithms), TRBP and NMPLP algorithms. When the fractional-free-energy is set to be convex (convex-free-energy) the norm-product is globally convergent for the estimation of -n-nmarginal probabilities and for approximating the LP-relaxation. We also introduce another branch of the norm-product which arises as the “zero-temperature” of the convex-free-energy which we refer to as the “convex-max-product”. The convex-max-product is convergent (unlike max-product) and aims at solving the LP- relaxation.
机译：图形模型中的推理问题可以表示为自由能函数的约束优化。在本文中，我们通过统一的消息传递算法体系结构来处理两种形式的概率推理，估计联合分布的边际概率并找到最可能的分配。特别是，我们概括了和积和最大积以及树加权（TRW）和最大积算法（TRBP）的置信传播（BP）算法，并介绍了基于“无凸能量”的一组新的收敛算法和线性规划（LP）松弛作为零自由能的零温度。这项工作的主要思想来自对现有BP和TRBP算法的总体了解，同时观察到它们都是$ f + sum_ {i} h_ {i} $的基本优化公式的简化，其中函数$ f $是一个扩展值的，严格凸的但不光滑的函数，而函数$ h_ {i} $是扩展值的函数（不一定是凸的）。我们使用凸对偶的工具介绍“原始对偶上升”算法，该算法是Bregman连续投影方案的扩展，旨在处理通用类型$ f + sum_ {i} h_ {i} $的优化。然后，我们将用于近似推理的分数自由能变分原理映射到上面的优化公式上，并引入“范数乘积”消息传递算法。规范积的特殊情况包括和积和最大积（BP算法），TRBP和NMPLP算法。当将自由分数能量设置为凸（无曲线能量）时，范数乘积在全局上收敛，以估计-n nmarginal概率并近似LP松弛。我们还介绍了标准积的另一个分支，即“无凸能量”的“零温度”，我们称其为“凸-最大积”。凸最大积是收敛的（不同于最大积），其目的是解决LP松弛。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号