作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (20): 186-188. doi: 10.3969/j.issn.1000-3428.2011.20.064

• 人工智能及识别技术 • 上一篇    下一篇

多次推理中的BP算法优化

吴孝滨,任志平   

  1. (上海交通大学计算机科学与工程系生物计算与生物信息实验室,上海 200240)
  • 收稿日期:2011-04-26 出版日期:2011-10-20 发布日期:2011-10-20
  • 作者简介:吴孝滨(1985-),男,硕士研究生,主研方向:生物信息学,统计推理,机器学习;任志平,硕士研究生
  • 基金资助:
    “985”二期工程科研基金资助项目(T222103003)

Optimization of BP Algorithm in Repeated Inference

WU Xiao-bin, REN Zhi-ping   

  1. (Lab of Biological Computation and Information, Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2011-04-26 Online:2011-10-20 Published:2011-10-20

摘要: 使用BP算法求解效用最大化问题时,容易产生大量冗余计算。为此,对标准BP算法进行优化,在推理过程中,对一些受限定条件影响较小的结点,直接利用前次推理结果,无需重新计算其边缘概率,并证明这种优化不会显著影响推理结果。将该算法应用于组合竞拍模型进行测试。仿真结果表明,相对于标准BP算法,该优化算法能提升求解效用最大化问题时的收敛效率。

关键词: 多次推理, BP算法, 消息传播, 有效推理, 组合竞拍

Abstract: It always produces redundant computation when applying Belief Propagation(BP) algorithm to MEU problem. To improve such a situation, an optimization to BP is proposed that reuse last influent result instead of recomputing the marginal probability if the node is not significantly affected by the change of condition, and prove is given to confirm that the optimization does not significantly affect the influence result. A simulation by applying the optimized algorithm to combinatorial auctions gives the result that compare to the standard BP algorism, optimized algorism efficiently improve the efficiency of inference without significantly affect the quality of the solutions.

Key words: repeated inference, Belief Propagation(BP) algorithm, message propagation, efficient inference, combinatorial auctions

中图分类号: