First-Order Decomposition Trees
Lifting attempts to speedup probabilistic inference by exploiting symmetries in the model. Exact lifted inference methods, like their propositional counterparts, work by recursively decomposing the model and the problem. In the propositional case, there exist formal structures, such as decomposition trees (dtrees), that represent such a decomposition and allow us to determine the complexity of inference a priori. However, there is currently no equivalent structure nor analogous complexity results for lifted inference. In this paper, we introduce FO-dtrees, which upgrade propositional dtrees to the first-order level. We show how these trees can characterize a lifted inference solution for a probabilistic logical model (in terms of a sequence of lifted operations), and make a theoretical analysis of the complexity of lifted inference in terms of the novel notion of lifted width for the tree.
The paper presents a lifted generalization of 
      decomposition trees used to analyze and effective specify a 
      computation tree for the analysis of lifted graphical models. 
      The paper is exceptionally well-written -- it uses a clean 
      notation and is full of examples to guide the reader's understanding. 
      From a quality perspective, this paper is among the top rank of papers 
      I've reviewed for NIPS. The idea is also novel and seemingly 
      worthy of publication -- first-order decision trees (FODTs) strike me 
      as a useful internal data structure for guiding the application of 
      lifted inference. Yet, on the other hand, it should be pointed out 
      that FODTs don't permit novel lifted computations, they only help one 
      organize them and analyze a notion of width which bounds the 
      computational complexity of evaluation w.r.t. an FODT. In some 
      sense the ability to do this computational analysis would have been 
      implicit in any prior implementation that had to recursively break 
      down a model and apply operations, namely the cited work of Milch et 
      al, but again this paper formalizes the recursive structure and 
      analysis in a way that I'm not aware has been done before. It 
      seems to me that while newcomers to lifted inference will find this 
      paper very informative (although perhaps still requiring a lot of 
      background reading), I would say that those who have implemented a 
      lifted inference system would not at all be surprised by what is being 
      presented here. Yet the latter group consists of a quite small group 
      of people. In the end, my decision on this paper comes down to 
      a few competing issues: (1) The usefulness of having this 
      paper in the literature to present a clean formalism for the 
      implementation and analysis of lifted inference. (2) The 
      computational analysis would have been implicit in previous approaches 
      (that certainly had to use a recursive decomposition of the problem 
      and for which computation at each step could be bounded). (3) The 
      paper does not enable any novel efficient inference, it simply 
      provides a clean way to implement and analyze existing inference 
      techniques.