Efficient Markov network discovery using particle filters

TitleEfficient Markov network discovery using particle filters
Publication TypeJournal Article
Year of Publication2009
AuthorsMargaritis D, Bromberg F
JournalComputational Intelligence
Volume25
Issue4
Pagination367–394
Date Published11/2009
Keywordsgraphical model structure learning, Markov networks, particle filters, sequential Monte Carlo
Abstract

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.

URLhttp://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.2009.00347.x/abstract;jsessionid=C95A98B67CD44AF9ABF59B3B0CCAA979.f01t02?userIsAuthenticated=false&deniedAccessCustomisedMessage=
DOI10.1111/j.1467-8640.2009.00347.x
Texto completo: 
Miembros del DHARMa que son autores:: 
Peer reviewed?: 
1
Internacional?: 
1