PaperlayerView exact revision on arXiv

Source-linked AI summary

Hinge-Loss Markov Random Fields and Probabilistic Soft Logic

Stephen H. Bach, Matthias Broecheler, Bert Huang, Lise Getoor

arXiv:1505.04406v3cs.LGcs.AIstat.ML

TL;DR

The paper addresses how to model rich, interdependent domains while scaling to large data sets. It introduces HL-MRFs and PSL, unifies three convex-inference perspectives, and develops scalable inference and learning algorithms. The resulting formalism combines expressive structured modeling with scalable algorithms for relational and structured data.

  • Problem

    Machine learning needs models that capture rich dependencies in structured domains while scaling to increasingly large data sets.

  • Method

    The paper introduces HL-MRFs, PSL, a first-order-logic-based language, and scalable inference and learning algorithms built around convex objectives.

  • Results

    HL-MRFs and PSL provide an expressive formalism, user-friendly language, and scalable algorithms for building large-scale models of relational and structured data.

  • Takeaways & Limitations

    The same inference and learning algorithms can support many dependency types, allowing models to be refined and reused across data sets.

  • Takeaways & Limitations

    The paper focuses on joint prediction directly and identifies comparison with learn-to-search methods as future work.

Abstract

from arXiv · show

A fundamental challenge in developing high-impact machine learning technologies is balancing the need to model rich, structured domains with the ability to scale to big data. Many important problem areas are both richly structured and large scale, from social and biological networks, to knowledge graphs and the Web, to images, video, and natural language. In this paper, we introduce two new formalisms for modeling structured data, and show that they can both capture rich structure and scale to big data. The first, hinge-loss Markov random fields (HL-MRFs), is a new kind of probabilistic graphical model that generalizes different approaches to convex inference. We unite three approaches from the randomized algorithms, probabilistic graphical models, and fuzzy logic communities, showing that all three lead to the same inference objective. We then define HL-MRFs by generalizing this unified objective. The second new formalism, probabilistic soft logic (PSL), is a probabilistic programming language that makes HL-MRFs easy to define using a syntax based on first-order logic. We introduce an algorithm for inferring most-probable variable assignments (MAP inference) that is much more scalable than general-purpose convex optimization methods, because it uses message passing to take advantage of sparse dependency structures. We then show how to learn the parameters of HL-MRFs. The learned HL-MRFs are as accurate as analogous discrete models, but much more scalable. Together, these algorithms enable HL-MRFs and PSL to model rich, structured data at scales not previously possible.

1. Introduction

The paper addresses the need for scalable models that preserve rich dependencies in large, structured domains. It introduces HL-MRFs, PSL, and scalable inference and learning methods to meet that need.

  • Rich, interdependent domains require models that capture structure while scaling to increasingly large data sets.
  • HL-MRFs are a new probabilistic graphical-model class using continuous variables and hinge-loss features to model structured dependencies.
  • Three approaches from randomized algorithms, graphical models, and fuzzy logic are shown to optimize the same convex inference objective.
  • PSL makes HL-MRFs easier to define for large relational data sets through probabilistic rules and first-order-logic-based syntax.
  • A consensus-optimization MAP method exploits sparse dependencies, while the paper also introduces learning algorithms for HL-MRF parameters.
  • HL-MRFs and PSL are evaluated across tasks including information extraction, knowledge-base construction, language, vision, and drug discovery.

2. Unifying Convex Inference for Logic-Based Graphical Models

The paper embeds logical structure in probabilistic graphical models and unifies three scalable inference perspectives into a common convex objective. This equivalence transfers approximation guarantees and message-passing algorithms across discrete and continuous interpretations.

  • Logical clauses provide feature functions for MRFs, allowing structured dependencies to be represented probabilistically rather than enforced absolutely.
  • MAP inference for logic-defined MRFs is NP-hard, motivating approximate methods based on convex programming relaxations.
  • MAX SAT relaxation offers strong solution-quality guarantees, but general-purpose convex optimization toolkits scale poorly on large MAP problems.
  • For clause-based MRFs with nonnegative weights, first-order local consistency relaxation is equivalent to the Goemans–Williamson MAX SAT relaxation.
  • The equivalence transfers MAX SAT rounding guarantees to local consistency relaxation and makes local-consistency message-passing algorithms applicable to MAX SAT relaxation.
  • Under Lukasiewicz logic, exact MAP inference for continuous MRFs matches the unified relaxed objective derived for Boolean logic.

3. Hinge-Loss Markov Random Fields

HL-MRFs generalize a unified convex objective into continuous probabilistic models built from hinge-loss penalties and linear constraints. They support richer dependencies, hard constraints, and selectable hinge variants while retaining tractable inference.

  • HL-MRFs are defined over continuous variables in [0,1] and retain convexity while supporting richer dependencies than the unified objective.
  • Each relaxed linear constraint contributes a weighted distance-to-satisfaction penalty, with larger weights imposing stronger penalties.
  • Arbitrary linear functions extend the model beyond logical clauses to represent value ranges and arithmetic relationships among variables.
  • Hard constraints restrict feasible assignments and can encode mutually exclusive possibilities and functional relationships.
  • Squared hinge losses smoothly trade off conflicting evidence and can better reflect relative evidence strength under mutual-exclusion constraints.
  • Users can choose linear or squared hinge losses for individual potentials according to the task.

4. Probabilistic Soft Logic

PSL is a probabilistic programming language for applying HL-MRFs to structured machine-learning problems. It uses templates for potentials and constraints to represent repeated probabilistic dependencies across data.

  • PSL applies HL-MRFs to structured machine-learning problems by defining templates for potentials and constraints.
  • Repeated dependencies, such as social ties, triadic closure, and functional relationships, can be represented with shared template parameters.
  • A PSL program uses declarative first-order syntax to define a class of HL-MRFs parameterized by input data.

4.1 Definition

PSL programs define rules that become hinge-loss potentials or hard linear constraints when grounded over data. The definition specifies predicates, atoms, inputs, observations, and grounding procedures that induce an HL-MRF.

  • Definition: A PSL program is a set of rules serving as templates for hinge-loss potentials or hard linear constraints.
  • Preliminaries: Ground atoms are PSL’s basic reasoning units, representing unknowns or observations with values in [0, 1].
  • Inputs: PSL inputs include closed predicates, open predicates, a ground-atom base, and an observation function assigning values or ∅.
  • Logical Rules: Grounded logical rules become potentials or hard constraints in the induced HL-MRF, allowing structural dependencies to be modeled efficiently.

4.2 Expressivity

PSL’s logical rules are expressive enough to represent arbitrary Boolean relationships through transformations into disjunctive clauses with nonnegative weights. These transformations preserve optimization or distributional behavior but can introduce computational and approximation caveats.

  • Expressivity: PSL logical rules can model arbitrary probabilistic relationships among Boolean variables, including relationships represented by Markov logic networks.
  • Expressivity: Any clause set can be converted to nonnegative-weight disjunctive clauses with the same optimizer, potentially requiring conjunctions.
  • Expressivity: Conjunctive clauses can be replaced by disjunctive clauses whose total score remains equivalent up to a constant.
  • Expressivity: Any Boolean MRF can be represented with disjunctive clauses and nonnegative weights, connecting Boolean MRF representation to MAX SAT.
  • Expressivity: The conversion may require exponentially many clauses in the potential degree, and added constants loosen the Goemans–Williamson approximation bound.

4.3 Modeling Patterns

PSL modeling patterns express domain constraints, similarity, and relational dependencies while controlling how rules scale with data. Aggregates reduce grounding growth by summarizing sets of related variables, though nonlinear similarity functions require approximation.

  • Domain and range constraints: PSL expresses functional, inverse-functional, and partial functional constraints for relations such as labels, advisors, and entity alignments.These constraints use equality or inequality rules to encode known limits on relation participation.
  • Similarity: Similarity-based rules connect comparable entities, with functionally defined predicates accepting domain-specific similarity functions that output values in [0, 1].The example uses name similarity to support predictions that two people are the same.
  • Priors: Priors favor low values for atoms without evidence, promoting sparse inferred entities, attributes, or relations.A negative-literal rule with a small weight can act as a regularizer on Link atoms.
  • Blocks and canopies: Blocking and canopies restrict dependencies to selected entity pairs, addressing the quadratic growth of possible binary links.PSL includes an InCanopy condition so only desired candidate links create dependencies.
  • Aggregates: Aggregates define variables as deterministic functions of sets of variables and avoid rule magnitudes growing with the number of groundings.For friend-interest propagation, averaging creates one grounding per person and resolves inconsistent scaling across users.
  • Aggregates: Aggregates can approximate set similarity for entity resolution, but Jaccard similarity must be linearized to preserve HL-MRF log-concavity.SameFriends uses SamePerson atoms for the intersection and a maximum set size as a lower bound on the union.

5. MAP Inference

HL-MRF MAP inference is a convex optimization problem, enabling scalable algorithms that exploit sparse dependencies and avoid fully materializing all potentials. The proposed ADMM and lazy-inference approaches achieve strong scalability, with ADMM remaining accurate relative to an interior-point method.

  • MAP Inference: HL-MRF MAP inference minimizes a convex objective rather than solving a combinatorial optimization problem.This permits standard convex-optimization methods while motivating specialized scalable algorithms.
  • Consensus Optimization Formulation: Consensus optimization decomposes the MAP problem into independent potential- and constraint-specific subproblems, iterating until copied variables agree.Local copies are constrained to equal corresponding consensus variables, preserving equivalence to the original MAP problem.
  • Consensus Optimization Formulation: ADMM updates converge to the global optimum, assuming a feasible assignment exists, while local-copy updates decompose over potentials and constraints.The local potential updates remain convex and can be solved by checking hinge-function regions rather than repeatedly applying expensive general-purpose methods.
  • Lazy MAP Inference: Lazy MAP inference can grow only the active set of unsatisfied potentials and constraints instead of fully materializing the HL-MRF.A threshold heuristic can reduce computation substantially, but then correctness is no longer guaranteed.
  • Evaluation of MAP Inference: 70 seconds was ADMM's average running time on the largest piecewise-linear problem, versus about 2,200 seconds for MOSEK's interior-point method.ADMM's running time grew linearly with problem size in this experiment, with R2 = 0.9972.
  • Evaluation of MAP Inference: 70 seconds was ADMM's average running time on the largest piecewise-quadratic problem, while its scaling remained linear with R2 = 0.9854.MOSEK could be tested only on the three smallest quadratic problems; the largest of those took about 21k seconds on average.
  • Evaluation of MAP Inference: 0.2%–0.4% was the observed relative error of ADMM compared with the interior-point solution, without increasing as problem size grew.The comparison indicates that ADMM was accurate in addition to being more scalable.

6. Weight Learning

The paper presents three HL-MRF weight-learning objectives and accounts for shared weights across potentials generated from common templates.

  • Weight Learning: Three HL-MRF weight-learning methods approximately maximize likelihood, maximize pseudolikelihood, or find a large-margin solution.The large-margin method prefers weights that distinguish the ground truth from nearby alternative states.
  • Weight Learning: Each grounded hinge-loss potential inherits the weight of its generating template, so shared template weights apply across all corresponding groundings.For every grounding j in template tq, the potential weight is wj = Wq.

6.1 Structured Perceptron and Approximate Maximum Likelihood Estimation

The structured-perceptron approach approximates maximum likelihood by using MAP states to estimate an otherwise intractable expectation, with fixed-length gradient steps projected into the feasible region.

  • Structured Perceptron and Approximate Maximum Likelihood Estimation: Maximum-likelihood weight learning is approximated by evaluating potentials at the MAP setting of y under the current parameters.The exact expectation required for the likelihood gradient is intractable.
  • Structured Perceptron and Approximate Maximum Likelihood Estimation: Fixed-length steps follow the approximate gradient, points are averaged after all steps, and infeasible updates are projected back into the feasible region.The method is expected to work best when the explored distribution space has relatively low entropy.

6.2 Maximum Pseudolikelihood Estimation

Maximum pseudolikelihood estimates each variable conditioned on the others, avoiding joint inference and enabling efficient expectation approximations for unconstrained or simple block-constrained variables.

  • Maximum Pseudolikelihood Estimation: Maximum pseudolikelihood estimation maximizes the likelihood of each variable conditioned on all other variables.Its gradient does not require joint inference and takes time linear in the size of y.
  • Maximum Pseudolikelihood Estimation: Monte Carlo integration quickly estimates the one-dimensional conditional expectation when a variable is unconstrained.The integral generally lacks a closed-form antiderivative, motivating approximation.
  • Maximum Pseudolikelihood Estimation: Low-dimensional simplex sampling provides accurate estimates for disjoint-group linear equality constraints, such as variable sets required to sum to 1.0.This block-sampling approach applies when constraints are not too interdependent.

6.3 Large-Margin Estimation

Large-margin estimation learns HL-MRF weights so ground-truth states score better than alternatives by a loss-scaled margin, using convex optimization and cutting planes. Squared potentials require slack because quadratic energy grows more slowly than linear loss near the ground truth.

  • Objective: Large-margin estimation learns weights that separate ground-truth states from alternate continuous states by a loss-scaled margin.The output space is continuous, so disagreement is represented with a continuous loss function.
  • Objective: The method uses ℓ1 distance as its loss and penalized slack to relax constraints when outputs are not perfectly separable.The resulting objective is convex and uses a user-specified penalty parameter C.
  • Optimization: Cutting-plane optimization handles the infinite constraint set by iteratively adding the most violated constraint found by a separation oracle.The oracle performs loss-augmented inference, while the working constraint set grows until no materially violated constraint remains.
  • Optimization: The separation oracle reduces loss-augmented inference to standard inference on an augmented HL-MRF when ground-truth values are Boolean.Interior ground-truth values make distance-based losses concave, complicating the oracle.
  • Squared potentials: Squared HL-MRF potentials always require slack because linear loss exceeds squared distance sufficiently close to the ground truth.Slack trades off the peakedness of the learned quadratic energy against the margin criterion.

6.4 Evaluation of Learning

The evaluation tests HL-MRF learning across node labeling, link labeling, link prediction, and image completion against discrete and continuous baselines. HL-MRFs match or exceed canonical methods while often offering faster inference and competitive image reconstruction.

  • Evaluation scope: Four experiments evaluate HL-MRF learning on node labeling, link labeling, link prediction, and image completion.The tasks are chosen because their dependencies are highly structural.
  • Overall results: HL-MRFs perform as well as or better than canonical approaches across the diverse structured-prediction tasks.For node and link labeling, the comparison uses discrete MRFs built with Markov logic networks.
  • Node and link labeling: HL-MRFs are the most accurate predictors on both Cora and Citeseer, and both HL-MRF variants are much faster than discrete MRFs.The classification experiment uses citation links to propagate document categories from observed seed labels.
  • Social-trust prediction: HL-MRFs with squared potentials score significantly higher on ROC, positive-trust precision-recall, and negative-trust precision-recall metrics.Discrete MRFs or linear HL-MRFs are statistically tied with the best score on some individual precision-recall metrics.
  • Efficiency: Convex HL-MRF inference can be much faster than sampling-based discrete inference, while HL-MRFs remain more accurate on the reported trust task.Average inference times are reported for Cora, Citeseer, and Epinions.

7. Related Work

The related work situates HL-MRFs and PSL among structured prediction, probabilistic graphical models, statistical relational learning, and scalable convex inference. It emphasizes template-based relational modeling, continuous structured prediction, and message-passing approaches to difficult inference problems.

  • Foundations: Inductive logic programming, probabilistic graphical models, statistical relational learning, and structured prediction provide complementary foundations for modeling relational dependencies and structured outputs.These fields address logical structure, uncertainty, relational data, and prediction of structured objects.
  • Scope: The paper focuses on joint prediction methods, leaving the relative advantages of joint prediction and learn-to-search methods as future work.This defines the paper’s scope within structured prediction research.
  • Relational modeling languages: PSL belongs to a family of languages that use logical or relational templates to specify probabilistic models separately from inference and learning algorithms.Related systems include probabilistic relational models, relational dependency networks, and Markov logic networks.
  • Continuous and relational reasoning: HL-MRFs extend continuous-domain probabilistic modeling, while PSL supports similarity reasoning through continuous variables and functionally defined predicates.This contrasts with formalisms focused primarily on discrete equality or Boolean dependencies.
  • Inference: Structured MAP inference is generally NP-hard, motivating approximations such as local consistency relaxations, dual decomposition, and primal message passing.Prior work studies tractable subclasses, tighter relaxations, and rounding guarantees when relaxations are tight.
  • Inference: MAX SAT, fuzzy logic, and convex-relaxation work provide additional connections to the optimization objectives underlying scalable structured inference.The related approaches include randomized MAX SAT algorithms and higher-order or symmetry-exploiting inference methods.

8. Conclusion

The conclusion presents HL-MRFs and PSL as expressive, scalable formalisms for relational and structured data, supported by scalable inference and learning algorithms.

  • HL-MRFs unite and generalize Boolean logic, probabilistic graphical models, and fuzzy logic for relational and structured data.
  • HL-MRFs occupy a useful middle ground between scalability and expressivity, achieving high-quality predictive performance across structured problems.The paper reports performance competitive with or surpassing canonical approaches.
  • PSL provides an intuitive first-order-logic syntax for designing HL-MRFs and supports rapid model refinement across datasets.PSL programs specify classes of HL-MRFs parameterized by the data used for grounding.
  • The inference and learning algorithms scale to large problems by leveraging sparse dependencies while extending standard learning objectives to HL-MRFs.
  • The paper identifies local-consistency-relaxation analysis and guarantees for MAP inference as directions for future work.

Appendix A. Proof of Theorem 2

The appendix proves that a local-consistency relaxation for clause-based MRFs can be reduced to a compact optimization over variable pseudomarginals, establishing equivalence with the MAX SAT relaxation.

  • The proof reformulates local consistency relaxation as hierarchical optimization over variable and factor pseudomarginals.Fixed variable pseudomarginals make the inner linear programs decompose independently over MRF clauses.
  • The resulting projected objective is identical to the MAX SAT relaxation objective for MRFs with disjunctive-clause potentials and nonnegative weights.
  • The inner linear programs are replaced by expressions giving their optimal values for every feasible pseudomarginal setting.The maximizers exist because the relevant problem is bounded and feasible for parameters in [0, 1]^n.
  • The proof uses Boolean-state constraints, simplex constraints, nonnegativity, and KKT conditions to characterize the inner optimization.
  • Theorem 2 concludes that the first-order local consistency relaxation and the MAX SAT relaxation are equivalent, with corresponding optimal solutions in both directions.
Loading 1505.04406v3…