Bounding the Cost of Search-Based Lifted Inference
Recently, there has been growing interest in systematic search-based and importance sampling-based lifted inference algorithms for statistical relational models (SRMs). These lifted algorithms achieve significant complexity reductions over their propositional counterparts by using lifting rules that leverage symmetries in the relational representation. One drawback of these algorithms is that they use an inference-blind representation of the search space, which makes it difficult to efficiently pre-compute tight upper bounds on the exact cost of inference without running the algorithm to completion. In this paper, we present a principled approach to address this problem. We introduce a lifted analogue of the propositional And/Or search space framework, which we call a lifted And/Or schematic. Given a schematic-based representation of an SRM, we show how to efficiently compute a tight upper bound on the time and space cost of exact inference from a current assignment and the remaining schematic. We show how our bounding method can be used within a lifted importance sampling algorithm, in order to perform effective Rao-Blackwellisation, and demonstrate experimentally that the Rao-Blackwellised version of the algorithm yields more accurate estimates on several real-world datasets.
The paper introduces lifted and/or schematics, which are an abstract representation of the PTP search space. Analyzing the schematic lets us quantify the size of the search space. This is of independent theoretical interest (although the theory is not quite there yet to provide deep insights), and is practically useful in the context of Rao-Blackwellized importance sampling.I believe this type of work is important; we still lack understanding of lifted inference algorithms. The proposed schematics are not really simple enough to provide a whole lot of insight, but it's a move in the right direction. The presentation is okay, although I cannot verify many of the technical points with the time available to me.Given that this is a theoretical paper, I wonder how powerful the framework is in terms of liftability. Can these schematics capture all known classes of models that are domain-liftable?The paper misses the opportunity to relate to other similar techniques.How are dtrees (used in recursive conditioning and knowledge compilation) related to and/or schematics?How are first-order NNF circuits related to lifted and/or schematics? They look very similar, with counting nodes having a single child, which induces a summation when evaluated, and so on. There is some work on the complexity of evaluating partition functions from first-order NNF circuits, where the result is that it is exponential in the number of nested counting operations (existential quantifiers). This result seems related to the analysis in Section 4.How does this relate to the first-order decomposition trees of Taghipour et al.? The footnote on page 3 says that these are not as tight: I would expect more details here (and perhaps an example of where the complexity differs).I like the importance sampling algorithm that uses the theory in a meaningful way. It's very convincing. I know these experiments are preliminary, but I would still like more details on the setup. For example, I do not believe that 10% evidence on webkb leaves you with any symmetries to exploit. I suspect that the evidence predicates were chosen to maximize the remaining symmetries (only evidence on page class, not on links?). It would be good to clarify.Typos: The theta_i on line 105 should be a t_i. With exchangeable variables on line 171, you mean exchangeable constants (the random variables after shattering are not fully exchangeable in general). Line 212: of depends.