Source-linked AI summary
Improving the Accuracy and Efficiency of MAP Inference for Markov Logic
Sebastian Riedel
TL;DR
MAP inference for Markov Logic must be both efficient and accurate, but the paper reports that MaxWalkSAT is slow and inaccurate on two relatively simple tasks. It introduces Cutting Plane Inference, which incrementally solves partial network groundings with conventional MAP solvers; across both tasks, CPI makes ILP faster while exact and makes MWS faster and more accurate.
Problem
MaxWalkSAT is slow and inaccurate on Semantic Role Labelling and Joint Entity Resolution, challenging efficient and accurate MAP inference for larger relational applications.
Method
Cutting Plane Inference incrementally solves partial versions of a complete Ground Markov Network, alternating first-order query processing with numerical optimization using a base solver.
Results
Across both tasks, CPI makes exact ILP more efficient while preserving exactness and makes approximate MWS faster and more accurate.
Takeaways & Limitations
CPI extends MAP inference to a wider class of Statistical Relational Learning tasks by combining deterministic query processing with optimization of partial problems.
Takeaways & Limitations
Exact MAP inference is PP-complete in general, so CPI cannot be expected to work for arbitrary formulae, weights, and problems, at least with ILP as base solver.
Abstract
from arXiv · showhide
In this work we present Cutting Plane Inference (CPI), a Maximum A Posteriori (MAP) inference method for Statistical Relational Learning. Framed in terms of Markov Logic and inspired by the Cutting Plane Method, it can be seen as a meta algorithm that instantiates small parts of a large and complex Markov Network and then solves these using a conventional MAP method. We evaluate CPI on two tasks, Semantic Role Labelling and Joint Entity Resolution, while plugging in two different MAP inference methods: the current method of choice for MAP inference in Markov Logic, MaxWalkSAT, and Integer Linear Programming. We observe that when used with CPI both methods are significantly faster than when used alone. In addition, CPI improves the accuracy of MaxWalkSAT and maintains the exactness of Integer Linear Programming.
1 INTRODUCTION
Relational tasks require joint reasoning because labels depend on related objects, motivating Statistical Relational Learning and efficient, accurate inference for Markov Logic. The paper introduces CPI, which incrementally solves smaller instantiated portions of a network using existing MAP solvers.
- Motivation: Relational tasks assign labels whose validity depends on labels assigned to related objects.In Semantic Role Labelling, two phrases cannot both be agents of the same verb.
- Motivation: Statistical Relational Learning uses first-order descriptions to represent repetitive graphical-model structure compactly.This representation can avoid full network instantiation and separate application modeling from algorithm development.
- Problem: MAP inference with MaxWalkSAT was slow and inaccurate even on relatively simple Semantic Role Labelling and Joint Entity Resolution models.Efficient and accurate inference on such models is presented as necessary before scaling to larger joint-inference applications.
- Method: CPI is a meta algorithm inspired by the Cutting Plane Method that incrementally instantiates only network portions whose current solution can be further optimized.It uses an existing inference method to solve partial problems that are often smaller and less complex than the complete network.
- Results: Across both tasks, CPI makes ILP significantly faster while preserving exactness, and makes MWS faster and more accurate than the corresponding standalone solver.For Semantic Role Labelling, CPI with ILP also achieves state-of-the-art results with minimal engineering effort.
2 MARKOV LOGIC
Markov Logic combines first-order logic with Markov networks to model uncertainty over possible worlds while retaining repetitive relational structure. Its formulas and weights define a log-linear distribution whose ground features evaluate formula satisfaction.
- Markov Logic: Markov Logic combines First Order Logic and Markov Networks into an expressive Statistical Relational Learning language.It has been used for Information Extraction and Entity Resolution.
- Notation: A possible world is a set of ground atoms, and a grounding replaces logical variables with constants.The paper defines atoms, possible worlds, satisfaction, and grounding through this notation.
- Semantics: Unlike First Order Logic, an MLN assigns probabilities to possible worlds, allowing violated formulae to be less likely rather than impossible.The paper illustrates this with an agent-position relation that may fail in passive constructions.
- Semantics: An MLN is a set of formula-weight pairs that, together with finite constants, defines a log-linear probability distribution over possible worlds.The resulting strictly positive distribution corresponds to a Ground Markov Network, and very large weights can encode hard constraints.
3 MAP INFERENCE
MAP inference selects the most probable hidden atoms given observed atoms in a Markov Logic Network. The paper describes approximate MaxWalkSAT and exact Integer Linear Programming as solver options for this optimization.
- MAP Problem: MAP inference finds the hidden ground atoms with maximum a posteriori probability given observed ground atoms.The hidden predicates are the remaining predicates after separating observable predicates from the full predicate set.
- MAP Problem: The MAP objective can be viewed as a scoring function that evaluates the goodness of a problem-solution pair.In the Semantic Role Labelling example, observed left-atoms support inference over hidden agent-atoms.
- MaxWalkSAT: MaxWalkSAT is an approximate randomized method that flips atoms in unsatisfied clauses, sometimes choosing the flip with the largest score increase.It repeats this process for a fixed number of flips and may restart to seek a better solution.
- Integer Linear Programming: Integer Linear Programming optimizes a linear objective under linear inequalities while requiring all or some variables to be integers.It is used for MAP problems because of exactness, declarative formulation, and efficient solvers.
- Integer Linear Programming: The Markov Logic-to-ILP mapping replaces feature applications with auxiliary variables and converts logical constraints into linear constraints.The transformation includes logical equivalences, observed or decision variables, conjunctive normal form, and linearized disjunctions.
4 CUTTING PLANE INFERENCE
Cutting Plane Inference (CPI) incrementally expands a partial grounding by finding under-optimized groundings, then re-solves the resulting smaller MAP problem with an existing solver. Its error is tied to the base solver and newly added clauses, while runtime is not theoretically bounded; experiments and related-work comparisons position it as a general Markov Logic meta algorithm.
- Algorithm: CPI avoids full grounding by solving a partial Markov Network and adding groundings whose feature-weight products are not maximally satisfied.The method repeatedly optimizes the current partial score, identifies under-optimized ground formulae, and extends the partial grounding.
- Algorithm: CPI terminates when no new ground formulae are found or a maximum iteration count is reached, retaining the best solution encountered.Each iteration solves the current partial problem and updates the best full score when appropriate.
- Guarantees: The solution error is bounded by the base solver’s partial-problem error plus the absolute weights of newly found ground formulae.With no newly found groundings, the bound reduces to the base solver’s error on the partial problem; exact base solvers can therefore yield exact CPI solutions in that case.
- Scope and related work: CPI has finite convergence but no runtime guarantee, so the algorithm may terminate before convergence; unlike earlier work, it handles nondeterministic constraints without branch-and-bound.The authors frame CPI as a general meta algorithm that can plug in existing propositional solvers and includes a reusable separation routine.
- Separation: The separation step finds groundings that the current solution does not maximally satisfy, using formula polarity to identify relevant assignments.Positive-weight formulas require finding false groundings, whereas negative-weight formulas require finding true groundings.
- Separation: Database query evaluation implements separation over atoms in the current solution and observations, with marginal cost relative to numeric optimization.The formula or its negation is converted into a database query, and query processing is often efficient.
5 EXPERIMENTS
Across Semantic Role Labelling and Joint Entity Resolution, CPI was evaluated with MaxWalkSAT and ILP for runtime, accuracy, and scalability. CPI improved MaxWalkSAT’s performance, preserved ILP exactness, and reduced computational demands, although full ILP was infeasible for Entity Resolution.
- Experimental setup: CPI was evaluated on Semantic Role Labelling and Joint Entity Resolution with MaxWalkSAT and Integer Linear Programming as base solvers.The experiments measured runtime and accuracy for both inference methods across the two tasks.
- Semantic Role Labelling: CPI-MWS was faster and more accurate than plain MWS on Semantic Role Labelling, while avoiding hard-constraint violations.The comparison used 100,000 flips without restarts for both methods.
- Semantic Role Labelling: CPI-ILP remained exact and sped up ILP by almost two orders of magnitude on Semantic Role Labelling.Plain ILP achieved perfect model score, and CPI retained that exactness while reducing runtime.
- Scalability: CPI-ILP scaled almost linearly with candidate nodes or decision variables, despite quadratic or higher growth in the underlying ground formulae and features.For Semantic Role Labelling, the near-linear trend held up to 50 candidates; for Entity Resolution, runtime scaled linearly with variables while features grew at least cubically with citations.
- Joint Entity Resolution: On Joint Entity Resolution, CPI made ILP feasible when the full ILP model did not fit into memory, while CPI-MWS improved accuracy over MWS alone but did not converge.CPI-MWS was terminated after 30 iterations, and CPI-ILP showed the same runtime and accuracy advantages across the reported metrics.
6 CONCLUSION
CPI generalizes cutting-plane MAP inference within Statistical Relational Learning by alternating first-order query processing with numeric optimization of partial problems. Across two real-world tasks, it improves efficiency while preserving exactness for ILP and improving both speed and accuracy for MWS, but its applicability is limited for arbitrary graphical-model problems.
- CPI incrementally solves partial versions of the complete Ground Markov Network, alternating deterministic first-order query processing with numeric optimization.The method functions as a meta algorithm within a Statistical Relational Learning framework.
- CPI was evaluated on Joint Entity Resolution and Semantic Role Labelling, two real-world tasks where MWS performed poorly.
- CPI makes ILP more efficient while remaining exact, and makes MWS both faster and more accurate on both tasks.
- Exact MAP inference in general Graphical Models is PP-complete, so CPI cannot be expected to work for arbitrary formulae, weights, and problems when ILP is the base solver.
- For positive conjunctive formulae with sparsely populated predicates, separation can produce an almost exhaustive set of violated pairs, leaving a problem nearly as large as the original.