Variante de Grow Shrink para mejorar la calidad de Markov blankets

BROMBERG, FACUNDO; SCHLUTER, FEDERICO

Pelotas, BRAZIL

Conferencia; Conferencia Latinoamericana de Informática (CLEI); 2009

CLEI

             This work introduces Grow-Shrink with Search (GSS), anovel adaptation of the Grow-Shrink (GS) algorithm that learns a setof direct dependences of a random variable; called the Markov Blanket(MB) of the variable. We focus on the use of MBs for learning undirectedprobabilistic graphical models (a.k.a. Markov networks). As in the GSalgorithm, GSS learns the MB by executing a series of statistical testsof conditional independence. The reliability of these tests decreases withthe amount of data. While GS ignores this fact deciding on potentiallyincorrect MBs, GSS decides through a novel quality measure also intro-duced in this work, based on the posterior probability of a MB given thedata. GSS proceeds as an optimization search over all possible indepen-dence assignments of the tests performed, searching for the assignmentthat maximizes this quality measure. This is in direct contrast to GSthat performs a greedy optimization based on local decisions, i.e., the in-dependence tests. Experimental results shows improvements up to 10%of the Hamming distance (normalized) of the learned MB vs. the realMB.