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

计算机工程 ›› 2007, Vol. 33 ›› Issue (04): 223-224. doi: 10.3969/j.issn.1000-3428.2007.04.078

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

束搜索算法的候选选取方法研究

许中卫1 , 2,李 炜1,吴建国1   

  1. (1. 安徽大学计算智能与信号处理教育部重点实验室,合肥 230039;2. 山东大学威海分校计算机系,威海 264209)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-02-20 发布日期:2007-02-20

Research on Candidates Selection Methods of Beam Search Algorithm

XU Zhongwei1,2, LI Wei1, WU Jianguo1   

  1. (1. Ministry of Education’s Key Laboratory of Intelligence Computing and signal Processing, Anhui University, Hefei 230039; 2. Dept. of Computer Science, Shandong University in Weihai, Weihai 264209)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-02-20 Published:2007-02-20

摘要: 在假设空间中进行爬山搜索是机器学习算法中常用的策略,爬山算法不能保证得到全局最优解,为了减少收敛到局部最优解的风险,束搜索应用而生。宽度为k的束搜索,在每一步以k个最佳候选为入口进行搜索(产生分支),并从结果集中再次选取k个候选作为下一步的搜索入口。但目前多数算法只是在结果集中简单选取具有最大启发式性能量度值的k个成员。该文讨论了束搜索算法,提出了几种合理的候选选取方法,并在UCI数据库上进行对比实验测试,给出了实验结果。

关键词: 机器学习, 束搜索, 聚类, 归纳逻辑程序设计。

Abstract: The hill-climbing search through hypothesis space is widespread used in many learning algorithms. It can’t grantee getting the globally optimal solution. In order to reduce the risk of converging to locally optimal hypotheses, beam search approach is explored. But in most of search algorithms, the k candidates with the most high performance measure value are selected. This paper presents some variations of beam search approaches. With these approaches, the k candidates could be selected in more reasonable way that can reduce the risk of converging to locally optimal solution in some extent. The experiments are done on the UCI repository of machine learning databases.

Key words: Machine learning, Beam search, Clustering, Inductive logic programming