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