Computer Science ›› 2015, Vol. 42 ›› Issue (Z11): 42-48.

Previous Articles     Next Articles

Accelerating the Recovery of Markov Blanket Using Topology Information

FU Shun-kai, SU Zhi-zhen, Sein Minn and LV Tian-yi   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Markov blanket(MB) has been known as the optimal feature subset for prediction,and there exist fertile works to induce MB by local search since 1996.A novel one called FSMB was proposed which heavily relies on conditional independence(CI) test to determine the existence of connection between nodes,so it is kind of constraint-based learning as well.However,it differs from previous works by treating candidate CI tests unfairly.FSMB extracts critical d-separation topology information from conducted CI tests,and applies them to sort and perform those more likely to uncover independent relations with priority.Search space therefore is expected to shrink quickly in a more efficient manner.Experimental studies indicate that FSMB achieves tremendous improvement over state-of-art works PCMB and IPC-MB in term of time efficiency,but with no sacrifice on learning quality.When given large networks(e.g.100 and 200 nodes),FSMB runs even more efficiently than IAMB which is recognized as the fastest algorithm by now,requiring up to 40% fewer CI tests,and produces much higher quality of results.Experiments with UCI data sets and four classical classification models indicate that the classification accuracy of the models trained on the output of FSMB are close to or exceed performance achieved by models trained on all features,hence FSMB is an effective feature subset selector.

Key words: Markov blanket,Bayesian network,Local search,Structure learning,Constraint-based learning,Conditional independence test

[1] Pearl J.Probabilistic reasoning in expert systems[M].San Ma-tego:Morgan Kaufmann,1988
[2] Koller D,Sahami M.Toward optimal feature selection[C]∥the 13th International Conference on Machine Learning(ICML).Bari,Italy:Morgan Kaufmann,1996
[3] Chickering D M,Geiger D,Heckerman D.Learning BayesianNetwork is NP-Hard[R].Microsoft Research,1994
[4] Campos C P D,Zeng Z,Ji Q.Efficient structure learning ofBayesian networks using constraints[J].Journal of Machine Learning Research(JMLR),2011,12(11):663-689
[5] Tsamardinos I,Aliferis C,Statnikov A,et al.Algorithms forlarge scale Markov blanket discovery[C]∥16th International FLAIRS Conference,2003.AAAI,2003
[6] Zhang Y,Zhang Z,Liu K,et al.An improved IAMB algorithm for Markov blanket discovery[J].Journal of Computers,2010,5(11):1755-1761
[7] Zhang Y,Xu H,Huang Y,et al.S-IAMB algorithm for Markov blanket discovery[C]∥Asia-Pacific Conference on Information Processing(APCIP’09).Washington:IEEE Computer Society
[8] Tsamardinos I,Aliferis C F,Statnikov A.Time and sample efficient discovery of Markov blankets and direct causal relations[C]∥9th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining(KDD).ACM,2003
[9] Aliferis C,Tsamardinos I,Statnikov A.HITON,A Novel Mar-kov Blanket Algorithm for Optimal Variable Selection[C]∥Annual Symposium on American Medical Informatics Association(AMIA).2003
[10] Pena J M,Nilsson R,Bjorkegren J,et al.Towards scalable and data efficient learning of Markov boundaries[J].International Journal of Approximate Reasoning,2007,45(2):211-232
[11] Fu S,Desmarais M C.Fast Markov blanket discovery algorithm via local learning within single pass[C]∥21st Conference of the Canadian Society for Computational Studies of Intelligence(Canadian AI).Springer,2008
[12] Zeng Y X,Xiang H Y,Mao H.Dynamic ordering-based search algorithm for Markov blanket discovery[C]∥15th Pacific-Asia Conference on Data Mining,2011.Shenzhen,China:Springer,2011
[13] Acid S,De Campos L M,Castellano J G.Learning Bayesian network classifiers:Searching in a space of partially directed acyclic graphs[J].Machine Learning,2005,59(3):213-235
[14] Fu Shun-kai, Minn M C D S, Lv Tian-yi.A Survey of Advances in Feature Selection by Markov Blanket[C]∥ICNC-FSKD,2014.Xiamen,China,2014
[15] Koller D,Friedman N.Probabilistic graphical models:Principles and Techniques[M].MIT Press,2009
[16] Bromberg F,Margaritis D,Honavar V.Efficient Markov net-work structure discovery using independence tests[J].Journal of Artificial Intelligence Research,2009,35(1):449-484
[17] Fu S,Desmarais M C.Tradeoff analysis of different Markovblanket local learning approaches[C]∥12th Pacific-Asia Confe-rence on Advances in Knowledge Discovery and Data Mining(PAKDD).Osaka,Japan:Springer,2008
[18] Duda R O,Hart P E.Pattern Classification and Scene Analysis[M].John Wiley & Sons,1973-2-9
[19] Zhang H,Jiang L,Su J.Hidden Naive Bayes[C]∥AAAI.2005

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!