...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Pattern Analysis and Machine Intelligence, IEEE Transactions on >Fast Inference with Min-Sum Matrix Product
【24h】

Fast Inference with Min-Sum Matrix Product

机译：最小和矩阵乘积的快速推断

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

摘要

The MAP inference problem in many graphical models can be solved efficiently using a fast algorithm for computing min-sum products of n times n matrices. The class of models in question includes cyclic and skip-chain models that arise in many applications. Although the worst-case complexity of the min-sum product operation is not known to be much better than O(n^3), an O(n^{2.5}) expected time algorithm was recently given, subject to some constraints on the input matrices. In this paper, we give an algorithm that runs in O(n^2 log n) expected time, assuming that the entries in the input matrices are independent samples from a uniform distribution. We also show that two variants of our algorithm are quite fast for inputs that arise in several applications. This leads to significant performance gains over previous methods in applications within computer vision and natural language processing.
机译：使用快速算法计算n乘n矩阵的最小和，可以有效解决许多图形模型中的MAP推理问题。所讨论的模型类别包括在许多应用程序中出现的循环模型和跳过链模型。尽管最小和积运算的最坏情况复杂度不知道比O（n ^ 3）好得多，但是最近给出了O（n ^ {2.5}）预期时间算法，但要考虑到输入矩阵。在本文中，假设输入矩阵中的条目是来自均匀分布的独立样本，我们给出了一种在预期时间O（n ^ 2 log n）中运行的算法。我们还表明，对于几种应用中出现的输入，我们算法的两个变体都非常快。与计算机视觉和自然语言处理应用程序中的先前方法相比，这可以显着提高性能。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号