Fusing First-order Knowledge Compilation and the Lifted Junction Tree Algorithm
This work addresses efficiency issues in probabilistic inference for AI and machine learning applications, though it is incremental as it builds on and combines existing algorithms.
The paper tackles the problem of inefficient multiple-query inference in probabilistic models with first-order constructs by integrating first-order knowledge compilation (FOKC) into the lifted junction tree algorithm (LJT), resulting in faster computation times for certain inputs compared to existing methods like LJT, LVE, and FOKC alone.
Standard approaches for inference in probabilistic formalisms with first-order constructs include lifted variable elimination (LVE) for single queries as well as first-order knowledge compilation (FOKC) based on weighted model counting. To handle multiple queries efficiently, the lifted junction tree algorithm (LJT) uses a first-order cluster representation of a model and LVE as a subroutine in its computations. For certain inputs, the implementations of LVE and, as a result, LJT ground parts of a model where FOKC has a lifted run. The purpose of this paper is to prepare LJT as a backbone for lifted inference and to use any exact inference algorithm as subroutine. Using FOKC in LJT allows us to compute answers faster than LJT, LVE, and FOKC for certain inputs.