Discovering the Markov network structure
This work addresses the challenge of inferring graphical models for probabilistic inference, but it appears incremental as it builds on existing theorems and methods.
The paper tackles the problem of discovering the Markov network structure from a probability distribution by proving the supermodularity of information content and developing an algorithm based on this property, illustrated with a discrete distribution example where the Hammersley-Clifford theorem holds despite zero-probability realizations.
In this paper a new proof is given for the supermodularity of information content. Using the decomposability of the information content an algorithm is given for discovering the Markov network graph structure endowed by the pairwise Markov property of a given probability distribution. A discrete probability distribution is given for which the equivalence of Hammersley-Clifford theorem is fulfilled although some of the possible vector realizations are taken on with zero probability. Our algorithm for discovering the pairwise Markov network is illustrated on this example, too.