Efficient Markov Network Structure Discovery Using Independence Tests

Area of Science:

• Machine Learning
• Statistical Modeling
• Artificial Intelligence

Background:

• Traditional Markov network structure learning methods, like maximum likelihood estimation, are computationally expensive (NP-hard).
• Existing algorithms often struggle with parameter estimation, hindering efficient structure learning.
• Statistical independence tests offer a more computationally feasible approach.

Purpose of the Study:

• To introduce two novel algorithms, GSMN* and GSIMN, for efficient Markov network structure learning.
• To leverage statistical independence tests to overcome the limitations of maximum likelihood estimation.
• To enhance efficiency by exploiting conditional independence properties and introducing the Triangle theorem.

Main Methods:

• Developed GSMN*, an adaptation of the Grow-Shrink algorithm for Bayesian networks.
• Introduced GSIMN, which extends GSMN* by utilizing Pearl's properties and the novel Triangle theorem to infer additional independences.
• Employed statistical independence tests as the core mechanism for structure inference.

Main Results:

• Both GSMN* and GSIMN demonstrate efficient structure learning compared to older methods.
• GSIMN achieves significant computational savings over GSMN*.
• GSIMN generates Markov networks of comparable or improved quality, showing near-optimality in inferred independences.

Conclusions:

• Independence-based algorithms like GSMN* and GSIMN provide an efficient alternative for Markov network structure learning.
• GSIMN offers a substantial improvement in efficiency by intelligently inferring independences using the Triangle theorem.
• The proposed methods are effective on both artificial and real-world datasets.