Markov network structure learning: A randomized feature generation approach

The structure of a Markov network is typically learned in one of two ways. The first approach is to treat this task as a global search problem. However, these al-gorithms are slow as they require running the expen-sive operation of weight (i.e., parameter) learning many times. The second approach involves learning a set of local models and then combining them into a global model. However, it can be computationally expensive to learn the local models for datasets that contain a large number of variables and/or examples. This paper pur-sues a third approach that views Markov network struc-ture learning as a feature generation problem. The algo-rithm combines a data-driven, specific-to-general search strategy with randomization to quickly generate a large set of candidate features that all have support in the data. It uses weight learning, with L1 regularization, to select a subset of generated features to include in the model. On a large empirical study, we find that our algorithm is equivalently accurate to other state-of-the-art methods while exhibiting a much faster run time