• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Improved Greedy Algorithms for Learning Graphical Models
【24h】

Improved Greedy Algorithms for Learning Graphical Models

机译：学习图形模型的改进贪婪算法

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

摘要

We propose new greedy algorithms for learning the structure of a graphical model of a probability distribution, given samples drawn from the distribution. While structure learning of graphical models is a widely studied problem with several existing methods, greedy approaches remain attractive due to their low computational cost. The most natural greedy algorithm would be one which, essentially, adds neighbors to a node in sequence until stopping; it would do this for each node. While it is fast, simple and parallel, this naive greedy algorithm has the tendency to add non-neighbors that show high correlations with the given node. Our new algorithms overcome this problem in three different ways. The recursive greedy algorithm iteratively recovers the neighbors by running the greedy algorithm in an inner loop, but each time only adding the last added node to the neighborhood set. The second forward-backward greedy algorithm includes a node deletion step in each iteration that allows non-neighbors to be removed from the neighborhood set which may have been added in the previous steps. Finally, the greedy algorithm with pruning runs the greedy algorithm until completion and then removes all the incorrect neighbors. We provide both analytical guarantees and empirical performance for our algorithms. We show that in graphical models with strong non-neighbor interactions, our greedy algorithms can correctly recover the graph, whereas the previous greedy and convex optimization-based algorithms do not succeed.
机译：我们提出了新的贪心算法，用于学习概率分布图形模型的结构，并从分布中抽取样本。虽然图形模型的结构学习是几种现有方法的广泛研究的问题，但是贪婪方法由于其计算成本低而仍然具有吸引力。最自然的贪婪算法实际上是将邻居按顺序添加到节点直到停止的算法。它将对每个节点执行此操作。虽然这种快速，简单和并行的方法，但是这种朴素的贪婪算法倾向于添加与给定节点显示高度相关性的非邻居。我们的新算法以三种不同的方式克服了这个问题。递归贪婪算法通过在内部循环中运行贪婪算法来迭代地恢复邻居，但是每次仅将最后添加的节点添加到邻居集中。第二种向前-向后贪婪算法在每个迭代中都包括一个节点删除步骤，该步骤允许从邻居集中删除非邻居，而邻居可以在先前的步骤中添加。最后，带有修剪的贪婪算法将运行贪婪算法直到完成，然后删除所有不正确的邻居。我们为算法提供了分析保证和经验性能。我们表明，在具有强非邻居交互作用的图形模型中，我们的贪婪算法可以正确地恢复图，而先前的贪婪和凸优化算法则无法成功。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号