An Integer Polynomial Programming Based Framework for Lifted MAP Inference
In this paper, we present a new approach for lifted MAP inference in Markov logic networks (MLNs). The key idea in our approach is to compactly encode the MAP inference problem as an Integer Polynomial Program (IPP) by schematically applying three lifted inference steps to the MLN: lifted decomposition, lifted conditioning, and partial grounding. Our IPP encoding is lifted in the sense that an integer assignment to a variable in the IPP may represent a truth-assignment to multiple indistinguishable ground atoms in the MLN. We show how to solve the IPP by first converting it to an Integer Linear Program (ILP) and then solving the latter using state-of-the-art ILP techniques. Experiments on several benchmark MLNs show that our new algorithm is substantially superior to ground inference and existing methods in terms of computational efficiency and solution quality.
Paper Summary: The paper presents an approach to encode the MAP inference problem in Markov logic networks as an integer polynomial program (IPP) using three steps: lifted decomposition, lifted conditioning, and partial grounding. In order to solve the IPP, it converts it into an integer linear program using [25], and then resorts to using the standard Gurobi solver.Originality: The techniques of lifted decomposition, lifted condition and partial grounding have previously been used for lifted MAP inference for MLNs previously [6,18]. So the main contribution of the paper is to realise that the MAP inference problem can be formulated as an IPP. Solving the problem in this way does seem to result in faster inference, but the practical usefulness of such an approach is unclear (see below).Clarity: The paper is a difficult read. The main problem is that the paper is not self-contained, and relies on the reader's familiarity with [6]. It also uses several terms without definition, for example,- Line 162: What are the 'arguments' i_R and j_S?- Line 172: What are the 'atoms of a predicate'? This is confusing since the previous section describes atoms as predicates (line 94).- Line 179: What is the function D?While these terms become clearer from context, especially through the examples provided, they still hurt the paper's clarity. The general NIPS audience will not be familiar with MLNs, which have been proposed relatively recently. While I understand that it is difficult to define everything concretely within the page limit, it would help to publish an accompanying self-contained technical report.Significance: The experiments compare to the state of the art [11,14,18], and demonstrate significant speed-up for three MLNs. However, some details are missing. How were the weights for the MLN estimated? Is there a separate training set? While the performance of the methods has been reported only in terms of the cost, can it also be reported in terms of the accuracy of the output? Although the main aim of the paper is better optimisation, it's case would be made much stronger if better optimisation leads to better accuracy. Also, is there any theoretical bound on the size of the IPP obtained using the proposed method? If not, at least the empirical size of the IPP and the ILP should be reported.Post-rebuttal comments: My main concern with the paper is that the experiments are conducted on artificial MLNs (with hand-tuned weights), and the performance is reported purely in terms of the cost and not the accuracy. Nonetheless, since the main objective of the paper is improved inference and the experiments are able to demonstrate the benefit of the proposed method in this regard, I vote for accepting the paper. If accepted, please include the explanations provided in the rebuttal, as well as the size of the IPP and ILP. It would also be beneficial to release a longer, self-contained tech report instead of relying on the readers familiarity with the state of the art.