Bottom-Up Learning of Markov Network Structure
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.
20 Newsgroups, Raw data
Audio (raw data) Preprocessed available on request.
Raw data, Book
KDDCup 2000 From Daniel Lowd.
MSWeb From Daniel Lowd.
Reuters, Raw data
WebKB, Raw data
School (raw data) Preprocessed available on request.
Some of the other datasets may be available upon request.
Della Pietra et al. (.tgz)
Link to Lily Mihalkova's BUSL code