Premium
EFFICIENT MARKOV NETWORK DISCOVERY USING PARTICLE FILTERS
Author(s) -
Margaritis Dimitris,
Bromberg Facundo
Publication year - 2009
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.2009.00347.x
Subject(s) - particle filter , independence (probability theory) , posterior probability , computer science , conditional independence , markov chain monte carlo , algorithm , flexibility (engineering) , statistical hypothesis testing , markov chain , population , data mining , artificial intelligence , machine learning , mathematics , statistics , bayesian probability , kalman filter , demography , sociology
In this paper, we introduce an efficient independence‐based algorithm for the induction of the Markov network (MN) structure of a domain from the outcomes of independence test conducted on data. Our algorithm utilizes a particle filter (sequential Monte Carlo) method to maintain a population of MN structures that represent the posterior probability distribution over structures, given the outcomes of the tests performed. This enables us to select, at each step, the maximally informative test to conduct next from a pool of candidates according to information gain, which minimizes the cost of the statistical tests conducted on data. This makes our approach useful in domains where independence tests are expensive, such as cases of very large data sets and/or distributed data. In addition, our method maintains multiple candidate structures weighed by posterior probability, which allows flexibility in the presence of potential errors in the test outcomes.