Submitted by
Assigned_Reviewer_8
Q1: Comments to author(s).
First provide a summary of the paper, and then address the following
criteria: Quality, clarity, originality and significance. (For detailed
reviewing guidelines, see
http://nips.cc/PaperInformation/ReviewerInstructions)
This work proposes the structure of First Order dtrees
(FOdtrees) for inference in probabilistic logical models (PLMs), which is
analogue to dtrees for propositional graphical models. The authors show
how to determine from the structure if a lifted solution exists, how to
read a lifted solution analogously to dtrees, and how the structure
determines the complexity of inference.
The definition of FOdtree
is possible through the definition of a new type of node, DPG node  a
triplet of logvars with same domain, a set of objects and a constraint. As
in dtrees for propositional models, the leaves are factors. For lifting,
the isomorphic is captured in the DPG nodes, and counting can be done in
the same way as in lifted variable elimination. The proofs for determining
if a model is liftable, how to read a solution and determine complexity 
all seem analogue to dtrees.
The contribution of this work is by
allowing lifted inference in PLMs, analyzing complexity and providing the
infrastructure for approximate lifted inference. While this incrementally
adding upon existing works, the exact formulation of the model seems as an
important step. The writing provides the required definitions and
background.
Q2: Please summarize your review in 12
sentences
This work provides an exact formulation of FOdtrees,
that compactly represent PLMs. They exploit symmetries and allow to use
lifted inference as for dtrees for propositional graphical models. The
contribution is the exact formulation for a model that mostly seems
analogue to previous works. Submitted by
Assigned_Reviewer_9
Q1: Comments to author(s).
First provide a summary of the paper, and then address the following
criteria: Quality, clarity, originality and significance. (For detailed
reviewing guidelines, see
http://nips.cc/PaperInformation/ReviewerInstructions)
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 wellwritten  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  firstorder 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. Q2: Please summarize your review in 12
sentences
A novel and clean formalism for the implementation and
analysis of lifted inference, but lacking the ability to do novel lifted
inference over prior work and a formalization of ideas implicit in
previous work.
I weakly vote for acceptance simply because AI and
ML have often made progress when notations have been introduced that allow
the community to discuss and reason about complex systems, and this paper
offers one such useful notational formalism. Submitted by
Assigned_Reviewer_10
Q1: Comments to author(s).
First provide a summary of the paper, and then address the following
criteria: Quality, clarity, originality and significance. (For detailed
reviewing guidelines, see
http://nips.cc/PaperInformation/ReviewerInstructions)
The paper revolves around formally analyzing the
complexity of exact lifted inference algorithms such as lifted variable
elimination and lifted weighted model counting using special structures
called lifted (or firstorder) decomposition trees (or dtrees). Dtrees,
developed by Darwiche are a useful tool for formally analyzing the
complexity of exact propositional inference schemes; the paper extends
them to the firstorder level. The paper also presents a notion of lifted
width which is analogous to the notion of "width" in propositional
inference.
Quality: Overall the paper is wellwritten and correct.
The quality of writing is also excellent
Clairty: The paper is
clear. However, since I'm an expert on this topic, I don't know if
outsiders will understand it well unless they have some background on
lifted inference.
Originality: I would give it a slightly lower
originality score because such ideas have been mentioned before in a
number of earlier papers on exact lifted inference. However, this is the
first paper that gives it a thorough and formal treatment.
Significance: The paper presents several important, formal results
which can prove to be quite useful to the lifted inference community. I
would suggest a journal paper on this topic however since it may be hard
for a nonexpert to understand some
subtleties. Q2: Please summarize your review in 12
sentences
Overall, this paper is quite useful, theoretically
correct and will advance the stateoftheart in lifted inference. It
should be included in the program.
Q1:Author
rebuttal: Please respond to any concerns raised in the reviews. There are
no constraints on how you want to argue your case, except for the fact
that your text should be limited to a maximum of 6000 characters. Note
however that reviewers and area chairs are very busy and may not read long
vague rebuttals. It is in your own interest to be concise and to the
point.
We thank the reviewers for their valuable and
generally positive comments.
Reviewer 2 (Assigned_Reviewer_8)
mentions that FOdtrees are largely analogous to dtrees, making the work
somewhat incremental.
We would like to emphasize that there are
significant differences between FOdtrees and their propositional
counterparts. FOdtrees require the ability to explicitly represent
symmetries (i.e., either due to isomorphic decomposition or counting) that
occur in the probabilistic logical models. As a consequence, the standard
treewidth bound is not as precise as it could be. Thus, we propose a
lifted notion of width that allows one to formally characterize the
improvements over standard propositional inference due to liftability.
Reviewer 3 (Assigned_Reviewer_9) raises the following two points:
(1) the paper does not introduce novel lifted inference operators, and
(2) the computational analysis would have been implicit in previous
approaches, and is thus not that surprising to those who have implemented
a lifted inference system.
Despite the first publication on lifted
inference being 10 years old, few theoretical results on this topic exist.
The goal of this paper is to provide rigorous analysis and theoretical
results that help put the state of the art in lifted inference on formal
grounds. To the best of our knowledge, existing results either (1) take a
local view and specify the complexity of individual operators in a
specific algorithm or (2) show the complexity of solving a problem in a
lifted way (without grounding the model) is polynomial in the domain size.
In contrast, our work is the first that allows for a global, formal,
detailed complexity analysis based on the structure of a model. We believe
this is an important contribution by itself, which is orthogonal to the
introduction of new operators.
While those few people who have
implemented a lifted inference system may have come up with a complexity
analysis of their algorithm, currently no such result explicitly exists in
the literature. We are unaware of any structurebased complexity analysis
that applies to PLMs in general, any notion similar to the liftedwidth
introduced in the paper, and any proposals based on decomposition trees
(dtrees) or any other formal structure. Moreover, our proposed structure
(FOdtree) is not bound to a specific algorithm (or formalism) and allows
for analyzing many exact lifted inference algorithms in a unified way.
This should be valuable for understanding the relationship among them
(note that most previous comparisons have been performed empirically on
select models).
In our opinion, the fact that these results are
implicit in previous approaches does not mean that they are obvious to
everyone who has ever implemented a lifted inference system: at least to
us, they were not, any time soon after implementing a lifted inference
system.
