Programming with Personalized PageRank: A Locally Groundable First-Order Probabilistic Logic
This addresses efficiency issues in probabilistic inference for AI researchers, though it is incremental as it builds on stochastic logic programs.
The paper tackles the computational expense of grounding in probabilistic first-order logic systems by introducing a language that enables approximate local grounding, resulting in grounding time independent of database size and order-of-magnitude speedups through parallelization.
In many probabilistic first-order representation systems, inference is performed by "grounding"---i.e., mapping it to a propositional representation, and then performing propositional inference. With a large database of facts, groundings can be very large, making inference and learning computationally expensive. Here we present a first-order probabilistic language which is well-suited to approximate "local" grounding: every query $Q$ can be approximately grounded with a small graph. The language is an extension of stochastic logic programs where inference is performed by a variant of personalized PageRank. Experimentally, we show that the approach performs well without weight learning on an entity resolution task; that supervised weight-learning improves accuracy; and that grounding time is independent of DB size. We also show that order-of-magnitude speedups are possible by parallelizing learning.