Overview
Wang, Mazaitis, Lao & Cohen (Machine Learning, 2015) — Introduces ProPPR, a first-order probabilistic language where approximate “local groundings” can be constructed in time independent of database size. This solves the key scalability bottleneck of probabilistic logics: grounding queries against large knowledge bases.
The Problem
Probabilistic logics are useful for inference with noisy web-extracted facts, but most (Markov Logic Networks, ProbLog, PSL) don’t scale because query grounding grows with database size.
The Innovation
ProPPR is an extension to stochastic logic programs biased towards short derivations. Key insight: constructing proofs is related to computing personalized PageRank on a linearized version of the proof space. This enables:
- The PageRank-Nibble algorithm for provably-correct approximate grounding
- Fast, easily-parallelized weight learning
- Learning that is orders of magnitude faster than Markov Logic Networks
Results
- Handles KBs with one million entities and hundreds of mutually recursive clauses
- Joint learning (mutual recursion) improves performance over isolated learning
- Closely related to the Path Ranking Algorithm (PRA)
Related
- path-ranking-algorithm — PRA: the foundational random walk approach that ProPPR extends with probabilistic logic
- never-ending-language-learner — NELL: the KB system where these inference methods were developed and tested