Speeding up Inference in Statistical Relational Learning by Clustering Similar Query Literals

Lily Mihalkova and Matthew Richardson


Markov logic networks (MLNs) are a statistical relational learning model that consists of a set of weighted first-order clauses and provides a way of softening first-order logic. Several machine learning problems have been successfully addressed by treating MLNs as a “programming language” where a set of features expressed in first-order logic is manually engineered by the designer and then weights for these features are learned from the data. Inference over the learned model is an important step in this process both because several weight-learning algorithms involve performing inference multiple times during training and because inference is used to evaluate and use the final model. “Programming” with an MLN would therefore be significantly facilitated by speeding up inference, thus providing the ability to quickly observe the performance of new hand-coded features. This paper presents a meta-inference algorithm that can speed up any of the available inference techniques by first clustering the query literals and then performing full inference for only one representative from each cluster. Our approach to clustering the literals does not depend on the weights of the clauses in the model. Thus, when learning weights for a fixed set of clauses, the clustering step incurs only a one-time up-front cost.