Strategies for piecing-together Local- to-Global Markov networks learning algorithms

SCHLUTER, FEDERICO; BROMBERG, FACUNDO; ABRAHAM, LEANDRO

Cordoba

Congreso; Jornadas Argentinas de Informática, Argentine Symposium of Artificial Intelligence; 2011

Sociedad Argentina de Informática

We introduce in this work a set of strategies for improving the piecing-together step in Local-to-global Markov networks structure learning algorithms. For Markov networks, Local-to-global algorithms decompose the problem of learning a complete independence structure with n variables into n independent Markov blanket learning problems. On a second step these algorithms piece-together all the learned Markov blankets into a global structure using an \OR rule". Insucient data may result in incorrect learning of Markov blankets, with con icts in their decision on edge inclusion when, for two variables X and Y , X is in the blanket of Y , but Y is not in the blanket of X. In such cases the \OR rule" always decides to add the edge, making mistakes when such edge does not exist. Our contribution are alternative strategies. The rst alternative is based on the \AND rule" which proposes to add an edge between two variables X and Y to the global structure if they mutually belongs to its respective Markov blankets. The other alternative rule is based on the probability of the edges and aims to solve an inconsistency by comparing the probability of edge existence with the probability of edge absence, and taking the more probable for deciding to add or re-move such edge. At the end of the work we show that inconsistencies are an important source of errors in this algorithms, and demonstrate empirically interesting improvements in the quality of learned structures, using this new piecing-together alternatives instead of the basic \OR rule".