Bottom-Up Learning of Markov Network Structure
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. Authors propose bottom-up search as an alternative, inspired by the analogous approach in the field of rule induction. The 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.