New Rules for Domain Independent Lifted MAP Inference
Lifted inference algorithms for probabilistic first-order logic frameworks such as Markov logic networks (MLNs) have received significant attention in recent years. These algorithms use so called lifting rules to identify symmetries in the first-order representation and reduce the inference problem over a large probabilistic model to an inference problem over a much smaller model. In this paper, we present two new lifting rules, which enable fast MAP inference in a large class of MLNs. Our first rule uses the concept of single occurrence equivalence class of logical variables, which we define in the paper. The rule states that the MAP assignment over an MLN can be recovered from a much smaller MLN, in which each logical variable in each single occurrence equivalence class is replaced by a constant (i.e., an object in the domain of the variable). Our second rule states that we can safely remove a subset of formulas from the MLN if all equivalence classes of variables in the remaining MLN are single occurrence and all formulas in the subset are tautology (i.e., evaluate to true) at extremes (i.e., assignments with identical truth value for groundings of a predicate). We prove that our two new rules are sound and demonstrate via a detailed experimental evaluation that our approach is superior in terms of scalability and MAP solution quality to the state of the art approaches.
Summary:This paper proposes two rules for lifted inference in MLNs by exploiting the structure for MAP queries.The first rule is for applying MAP inference over a reduced theory such that single occurrences in equivalence classes are reduced to a unary sized domain. The second rule applies to the single occurrence theory, ignoring the tautology formulas for extreme assignments. Quality:This paper has a good quality. All theorems and lemmas have proofs in the paper or in the supported document. While the experimental results seem very promising, they are confusing with respect to the NSLGRB approach (Sarkhel et. al paper). In their paper, the results show constant growth w.r.t the domain size and time, however the pictures here show that the cost increases in time and domain size. Is there any justification of how the results presented in this paper are different from the claim of the original paper? Maybe the number of domain sizes (100 in their claims vs 500)? I am not convinced that the results are very different from Sarkhel's method. Clarity:The paper is well-organized and each section serves its purposes. There are nice definition such as the definition of single occurrence and extreme assignment.However in some places there is difficulty understanding all the theorems without explicit examples. For instance, section 4.1. requires examples mentioned in the text not in the additional document. Without this example it is a bit difficult to understand the rest of this section. Also in Algorithm2, the function getAllTautologyAtExtremes adds no new information and maybe isTautologyAtExtremes should have been explained in pseudo code instead. Originality:The originality of this paper is its major issue. First rule is essentially breaking the theory into sub-theories, assigning new weights according to their presence in an equivalence class. It seems this approach is not that different than previous network simplifications such as the decomposer. According to the proof of Theorem 4.2 a decomposer has the same definition of a single occurrence of an equivalence class. It seems that the decomposition idea in this work is very similar to the decomposer idea, only at a different level (on the MAP inference applied over a MLN). While the assignment of the new weights is different and novel but as claimed by corollary 4.1 this assignment is to some extend intuitive.Similarly the second rule is exactly derived from the paper of Sarkhel et. al. and thus is not considered a new innovative rule on its own. I would argue that the idea in this work is a modification of previous rules on MLN networks (specifically Sarkhel et. al) now applied to the MAP queries. There is not enough motivation to why this work and its ideas are novel.  Significance:According to the mentioned reasons this paper has minor significance. Due to the fact that its data are all from previous work or benchmarks, the results are not clear ( mentioned before) and the authors have failed to mention what happens to the cases where non of the formulas are single occurrences: there is a strong restriction on the theory. The major claim of independence is also mentioned in previous work and thus is not a new result for MLNs.