Lifted Inference Rules with Constraints
Lifted inference rules exploit symmetries for fast reasoning in statistical relational models. Computational complexity of these rules is highly dependent on the choice of the constraint language they operate on and therefore coming up with the right kind of representation is critical to the success of lifted inference. In this paper, we propose a new constraint language, called setineq, which allows subset, equality and inequality constraints, to represent substitutions over the variables in the theory. Our constraint formulation is strictly more expressive than existing representations, yet easy to operate on. We reformulate the three main lifting rules: decomposer, generalized binomial and the recently proposed single occurrence for MAP inference, to work with our constraint representation. Experiments on benchmark MLNs for exact and sampling based inference demonstrate the effectiveness of our approach over several other existing techniques.
Summary:   Lifted inference enables tractable inference in large probabilistic models by exploiting symmetries and independencies over variables. This paper provides a comprehensive method to (a) specify constraints; (b) use them for lifted inference; and (c) produce constraints from evidence. The authors first introduce setineq a constraint language for specifying symmetries and independencies using set membership and (in)equality constraints, and supply basic operators for manipulating these constraints. Next, The authors develop algorithms to use these constraints and basic operators to produce lifting rules (Decomposer/Binomial). Finally, the authors present a greedy method for deriving constraints from evidence. The authors test a Java-based implementation of the setineq-based constraint specification against other lifted inference implementations and show superior scaling and equivalent output to unconstrained representations.         Quality:   This paper has a number of technical contributions in representation and implementation of lifted inference methods. Experimental evaluation uses standard benchmark datasets, seems to provide fair comparisons to related work, and shows impressive performance.        Clarity:   My main issues with this paper relate to clarity. The paper relies heavily on the supplemental material for proofs, algorithms, and the Single Occurrence rule, and including some of this supplemental material in the main paper may be helpful.Since the paper covers a great deal of ground, each contribution must be framed carefully. The formal specification of setineq and the join/partition operators are clearly presented and benefits from many examples to help the reader understand how constraints are specified. However, the remainder of the paper would be improved with restructuring, proofreading (see below), and additional examples. One potential improvement would be moving Section 4.4 to section 3, since is relatively independent of the lifted inference rules and strongly relates to producing a constraint tuple from evidence. Additionally, revising section 4.4 may be helpful - the section is very terse and it's difficult to distinguish the paper's contributions from the previous work. In the lifted inference rules, the description of the Binomial algorithm (4.3) is extremely difficult to read. Examples for Theorem 4.1 and 4.2 would lend the preceding (somewhat dense) exposition some intuitive appeal.         Originality:   To the best of my knowledge, this work is original and relevant related work is cited.        Significance:   My understanding is that this provides an incremental refinement to lifted inference, and provides a starting point for deeper investigation. The empirical results seem very strong, and I wouldn't be surprised to see following work building more advanced lifted inference methods on setineq.        Typos:   Bell number (210)   grammar (240)   set definition (253)   set V^y_l (254)   argumene (297)   nmw (304)   Professors and Students (365)