| 贝叶斯网络结构加速学习算法 |
| |
| 引用本文： | SEIN Minn,傅顺开. 贝叶斯网络结构加速学习算法[J]. 计算机科学, 2016, 43(2): 263-268, 272 |
| |
| 作者姓名： | SEIN Minn 傅顺开 |
| |
| 作者单位： | 华侨大学计算机科学与技术学院 厦门361021,华侨大学计算机科学与技术学院 厦门361021 |
| |
| 基金项目： | 本文受国家自然科学基金资助 |
| |
| 摘 要： | 结构学习是应用贝叶斯网络(BN)的基础。提出一种新的基于约束的学习类算法APC(Accelerated PC),它基于一系列局部结构的推导获得BN。APC不但继承了经典的PC(Peter & Clark)算法优先执行低阶条件独立(CI)测试的优点,而且能够从已执行的CI测试中推导相关拓扑信息,并利用其来挑选并优先执行更可能 d-分割 节点X和Y的候选CI测试。该策略可有效避免在搜索过程中执行无效的CI测试,例如APC算法在实验中较PC算法节省高达50%的计算量,同时实现了质量相同的学习效果。
|
| 关 键 词： | 贝叶斯网络 结构学习 基于约束的学习 条件独立性测试 |
| 收稿时间： | 2015-01-14 |
| 修稿时间： | 2015-04-10 |
Accelerating Structure Learning of Bayesian Network |
| |
| SEIN Minn and FU Shun-kai. Accelerating Structure Learning of Bayesian Network[J]. Computer Science, 2016, 43(2): 263-268, 272 |
| |
| Authors: | SEIN Minn and FU Shun-kai |
| |
| Affiliation: | College of Computer Science and Technology,Huaqiao University,Xiamen 361021,China and College of Computer Science and Technology,Huaqiao University,Xiamen 361021,China |
| |
| Abstract: | Structure learning is the basis for the application of Bayesian networks (BN).A novel algorithm called APC was proposed to recovery the whole structure via sequential induction of local structures.APC inherits the most feature of PC algorithm,i.e.effectively avoiding high-dimensional conditional independence (CI) tests.Besides,it constructs and sorts candidate sets which possibly d-separate any pair of nodes,X and Y,based on information implied in early conducted CI tests and known features of BN topology.Then,CI tests involving highly ranked candidate set are performed with priority.This strategy is expected to avoid fruitless CI tests,and up to 50% saving is observed on APC over PC in our experimental study. |
| |
| Keywords: | Bayesian network Structure learning Constraint-based learning Conditional independence test |
|
|
点击此处可从《计算机科学》下载全文 |
|
