Bottom-Up Learning of Markov Network Structure

Jesse Davis and Pedro Domingos

Abstract:

The structure of a Markov network is typically learned using top-down search. At each step, the search specializes a feature by conjoining it to the variable or feature that most improves the score. This is inefficient, testing many feature variations with no support in the data, and highly prone to local optima. We propose bottom-up search as an alternative, inspired by the analogous approach in the field of rule induction. Our BLM algorithm starts with each complete training example as a long feature, and repeatedly generalizes a feature to match its k nearest examples by dropping variables. An extensive empirical evaluation demonstrates that BLM is both faster and more accurate than the standard top-down approach, and also outperforms other state-of-the-art methods.

Download:

Paper (PDF)

Datasets used:

20 Newsgroups, Raw data
Abalone
Adult
Audio (raw data) Preprocessed available on request.
Raw data, Book
Covertype
KDDCup 2000 From Daniel Lowd.
MSNBC
MSWeb From Daniel Lowd.
NLTCS
Plants
Reuters, Raw data
WebKB, Raw data
School (raw data) Preprocessed available on request.
Wine
Some of the other datasets may be available upon request.

Online Appendix

results

Code:

BLM (.tgz)
Della Pietra et al. (.tgz)
Link to Lily Mihalkova's BUSL code