Learning Markov Logic Networks Using Structural Motifs
Stanley Kok and Pedro Domingos
Abstract:
Markov logic networks (MLNs) use first-order formulas to define features
of Markov networks. Current MLN structure learners can only learn short
clauses (4-5 literals) due to extreme computational costs, and thus are
unable to represent complex regularities in data. To address this problem,
we present LSM, the first MLN structure learner capable of efficiently and
accurately learning long clauses. LSM is based on the observation that
relational data typically contains patterns that are variations of the same
structural motifs. By constraining the search for clauses to occur within
motifs, LSM can greatly speed up the search and thereby reduce the cost of
finding long clauses. LSM uses random walks to identify densely connected
objects in data, and groups them and their associated relations into a motif.
Our experiments on three real-world datasets show that our
approach is 2-5 orders of magnitude faster than the state-of-the-art ones,
while achieving the same or better predictive performance.
Download:
Paper (PDF)
Code
Slides
Proofs of Propositions
DFS Pseudocode
Examples of Long Clauses Learned by LSM