Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery

Details Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery

2011-01-18

arxiv.org/abs/1101.3381v1

Computer Science

Artificial Intelligence

28 pages, 8 figures and 7 tables

Scientific paper

This work introduces the IB-score, a family of independence-based score functions for robust learning of Markov networks independence structures. Markov networks are a widely used graphical representation of probability distributions, with many applications in several fields of science. The main advantage of the IB-score is the possibility of computing it without the need of estimation of the numerical parameters, an NP-hard problem, usually solved through an approximate, data-intensive, iterative optimization. We derive a formal expression for the IB-score from first principles, mainly maximum a posteriori and conditional independence properties, and exemplify several instantiations of it, resulting in two novel algorithms for structure learning: IBMAP-HC and IBMAP-TS. Experimental results over both artificial and real world data show these algorithms achieve important error reductions in the learnt structures when compared with the state-of-the-art independence-based structure learning algorithm GSMN, achieving increments of more than 50% in the amount of independencies they encode correctly, and in some cases, learning correctly over 90% of the edges that GSMN learnt incorrectly. Theoretical analysis shows IBMAP-HC proceeds efficiently, achieving these improvements in a time polynomial to the number of random variables in the domain.

Affiliated with

Also associated with

No associations

Rating

Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-286274