The Grow-Shrink strategy for learning Markov network structures constrained by context-specific independences

2014/07/30 by Edera, Alejandro, Strappa, Yanela, Bromberg, Facundo · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1407.8088

Abstract

Markov networks are models for compactly representing complex probability distributions. They are composed by a structure and a set of numerical weights. The structure qualitatively describes independences in the distribution, which can be exploited to factorize the distribution into a set of compact functions. A key application for learning structures from data is to automatically discover knowledge. In practice, structure learning algorithms focused on "knowledge discovery" present a limitation: they use a coarse-grained representation of the structure. As a result, this representation cannot describe context-specific independences. Very recently, an algorithm called CSPC was designed to overcome this limitation, but it has a high computational complexity. This work tries to mitigate this downside presenting CSGS, an algorithm that uses the Grow-Shrink strategy for reducing unnecessary computations. On an empirical evaluation, the structures learned by CSGS achieve competitive accuracies and lower computational complexity with respect to those obtained by CSPC.

Cited by

• Causal Discovery in Multivariate Time Series through Mutual Information Featurization

Related

• Learning Markov networks with context-specific independences
• Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery
• Structure Learning Using Forced Pruning
• Learning Markov Network Structure using Brownian Distance Covariance
• Constraint-free Graphical Model with Fast Learning Algorithm