Strategies for piecing-together local-to-global markov network learning algorithms

Abstract

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 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 is alternative strategies. The first 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 belong 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 remove such edge. At the end of the work, we show that inconsistencies are an important source of errors in these algorithms, and demonstrate empirically interesting improvements in the quality of learned structures, using this new piecing-together alternative instead of the basic \OR rule".