Markov Network Structure Learning: A Randomized Feature Generation Approach

by Jan Van Haaren and Jesse Davis

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 algorithms are slow as they require running the expensive 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 pursues a third approach that views Markov network structure learning as a feature generation problem. The algorithm 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.

Downloads

• Paper Markov Network Structure Learning: A Randomized Feature Generation Approach (pdf, 205 kB)
• Source code (zip, 666 kB, including installation instructions, a manual and a tutorial)
• Installation instructions (pdf, 50 kB)
• Manual (pdf, 100 kB)
• Tutorial (pdf, 55 kB)

Information

For more information, contact This e-mail address is being protected from spambots. You need JavaScript enabled to view it .

BibTeX reference

@inproceedings{345604,
  author = "Van Haaren, Jan and Davis, Jesse",
  title = "Markov network structure learning: {A} randomized feature generation approach",
  booktitle = "Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, ",
  month = Jul,
  year = "2012",
  url = "https://lirias.kuleuven.be/handle/123456789/345604",
}