Linear Programming Decoders in NLP:
Integer Programming, Message Passing, Dual Decomposition

André MartinsEMNLP 2014: Tutorials, Doha, Qatar, October 25, 2014
Slides online at http://tiny.cc/lpdnlp.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

1 / 149

Structured Prediction and NLP
Structured prediction: a machine learning framework for predicting
structured, constrained, and interdependent outputs
NLP deals with structured and ambiguous textual data (Smith, 2011):
machine translation
speech recognition
syntactic parsing
semantic parsing
information extraction...

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

2 / 149

Dependency Parsing
Map sentences to their syntactic structure.

*

Logic

plays

a

minimal

role

here

A lexicalized syntactic formalism
Grammar functions represented as lexical relationships (dependencies)(Eisner, 1996; McDonald et al., 2005; Nivre et al., 2006; Koo et al., 2007)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

3 / 149

Multi-Document Summarization
Map a set of related documents to a brief summary.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

4 / 149

Multi-Document Summarization
Map a set of related documents to a brief summary.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

4 / 149

Current State of Affairs

1

Greedy algorithms can deal with rich histories, but they aresuboptimal and suffer from error propagation2

Simple, tractable models permit exact decoding, but they make too
stringent factorization assumptions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

5 / 149

Current State of Affairs

1

Greedy algorithms can deal with rich histories, but they aresuboptimal and suffer from error propagation2

Simple, tractable models permit exact decoding, but they make too
stringent factorization assumptions

We’d like fast predictors with global features and constraints, but how?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

5 / 149

Related Recent Tutorials

Dual Decomposition and Lagrangian Relaxation for Inference in NLP(Rush & Collins ACL 2011)
Structured Predictions in NLP: Constrained Conditional Models andInteger Linear Programming (Srikumar, Goldwasser & Roth NAACL
2012)
Variational Inference in Structured NLP Models (Burkett & Klein
NAACL 2012)
Structured Belief Propagation for NLP (Gromley & Eisner ACL 2014)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

6 / 149

This Tutorial: Linear Programming Decoders
We’ll provide a unified view over these approaches (ILPs, message-passing,dual decomposition)
We’ll focus on MAP decoding, but touch briefly on marginal decoding
We’ll illustrate with three applications:1

Turbo Parsing

2

Compressive Summarization

3

Joint Coreference Resolution and Quote Attribution(Companion software: AD3 toolkit)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

7 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

8 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

9 / 149

Structured Prediction

Input set X
For each x ∈ X: a large set of candidate outputs Y(x )A compatibility function Fw (x , y ) induced by a model w(Linear model: Fw (x , y ) = w > f (x , y ))André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

10 / 149

Structured Prediction

Input set X
For each x ∈ X: a large set of candidate outputs Y(x )A compatibility function Fw (x , y ) induced by a model w(Linear model: Fw (x , y ) = w > f (x , y ))Training problem: learn the model w from data {hxi , yi i}M
i=1
Decoding problem (our focus):
yb = arg max Fw (x , y )y ∈Y(x )André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

10 / 149

Structured Prediction

Input set X
For each x ∈ X: a large set of candidate outputs Y(x )A compatibility function Fw (x , y ) induced by a model w(Linear model: Fw (x , y ) = w > f (x , y ))Training problem: learn the model w from data {hxi , yi i}M
i=1
Decoding problem (our focus):
yb = arg max Fw (x , y )y ∈Y(x )Key assumption: Fw decomposes into (overlapping) parts

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

10 / 149

Three Important Questions

Representation?
Decoding/Inference?
Learning the parameters?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

11 / 149

Recap: Hidden Markov Models
Fw is a log-probability, factoring over emissions and transitions.
P(x , y ) =Y

P(xi |yi ) P(yi |yi−1 )i| {z } |{z}emissions transitions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

12 / 149

Recap: Hidden Markov Models
Fw is a log-probability, factoring over emissions and transitions.
P(x , y ) =Y

P(xi |yi ) P(yi |yi−1 )i| {z } |{z}emissions transitions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

12 / 149

Recap: Hidden Markov Models
Fw is a log-probability, factoring over emissions and transitions.
P(x , y ) =Y

P(xi |yi ) P(yi |yi−1 )i| {z } |{z}emissions transitions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

12 / 149

Recap: Hidden Markov Models
Fw is a log-probability, factoring over emissions and transitions.
P(x , y ) =Y

P(xi |yi ) P(yi |yi−1 ) =Yi| {z } |i{z}emissions transitions

André Martins (Priberam/IT)

LP Decoders in NLPYψi (yi )ψi,i−1 (yi , yi−1 )i

http://tiny.cc/lpdnlp

12 / 149

Recap: Hidden Markov Models

Representation? Directed sequence model.
Decoding/Inference? Viterbi/forward-backward algorithms.
Learning the parameters? Maximum likelihood (count andnormalize).

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

13 / 149

Recap: Conditional Random Fields
Same factorization, but globally normalized.
P(y |x ) =1exp
Z (w, x )André Martins (Priberam/IT)



>i w f i (x , yi ) +

P

|

{z

nodes

}

LP Decoders in NLPP>
i w f i,i−1 (x , yi , yi−1 )

|

{z

edges

http://tiny.cc/lpdnlp

}

14 / 149

Recap: Conditional Random Fields
Same factorization, but globally normalized.
P(y |x ) =1exp
Z (w, x )André Martins (Priberam/IT)



>i w f i (x , yi ) +

P

|

{z

nodes

}

LP Decoders in NLPP>
i w f i,i−1 (x , yi , yi−1 )

|

{z

edges

http://tiny.cc/lpdnlp

}

14 / 149

Recap: Conditional Random Fields
Same factorization, but globally normalized.
P(y |x ) =1exp
Z (w, x )André Martins (Priberam/IT)



>i w f i (x , yi ) +

P

|

{z

nodes

}

LP Decoders in NLPP>
i w f i,i−1 (x , yi , yi−1 )

|

{z

edges

http://tiny.cc/lpdnlp

}

14 / 149

Recap: Conditional Random Fields
Same factorization, but globally normalized.
P(y |x ) =∝1exp
Z (w, x )Yψi (yi )iAndré Martins (Priberam/IT)Y

>i w f i (x , yi ) +

P

|

{z

nodes

}

P

>
i w f i,i−1 (x , yi , yi−1 )

|

{z

edges



}

ψi,i−1 (yi , yi−1 )iLP Decoders in NLP

http://tiny.cc/lpdnlp

14 / 149

Recap: Conditional Random Fields

Representation? Undirected sequence model.
Decoding/Inference? Viterbi/forward-backward algorithms.
Learning the parameters? Maximum conditional likelihood(convex optimization).

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

15 / 149

Graphical Models

HMMs and CRFs are two instances of graphical models.
In general, graphical models come in two flavours:
Directed (Bayesian Networks)
Undirected (Markov Networks)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

16 / 149

Bayesian Networks
Useful to express causality relations.
Factors are conditional probability tables.

P(y ) =Y

P(yi |parents(yi ))iAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

17 / 149

Bayesian Networks
Useful to express causality relations.
Factors are conditional probability tables.

P(y ) =Y

P(yi |parents(yi ))iAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

17 / 149

Markov Networks
Useful to express correlations between variables.
Factors correspond to cliques of the graph.

P(y ) ∝Y

ψ s (y s )s∈cliques(G)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

18 / 149

Markov Networks
Useful to express correlations between variables.
Factors correspond to cliques of the graph.

P(y ) ∝Y

ψ s (y s )s∈cliques(G)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

18 / 149

Conditional Independence

Graphical models are a great tool for modeling conditional independence
They link properties of the probability distribution with properties of thegraph (reachability, D-separation, etc.)
Lots of literature about this: Pearl (1988); Lauritzen (1996); Koller andFriedman (2009)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

19 / 149

An Intermediate Representation: Factor Graph
A bipartite graph with variable nodes and factor nodes
It makes explicit the factors of the distribution

P(y ) ∝Y

ψ i (yi ) ×

ψ s (y s )

s

i

|

Y

{z

}

unary potentials

|

{z

}

higher-order potentials

With unary potentials only, all variables would be independent
Higher-order potentials can model correlations, impose soft/hardconstraints, etc.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

20 / 149

Example: Low-Density Parity Check Codes
A message is transmitted through a noisy channel, corrupting some bits
Redundancy can help decoding the message, e.g. via additional parity
check bits that can detect/correct errors (error-correcting codes)
High-level idea: increase redundancy to build more accurate decoders(Adapted from MacKay 2003.)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

21 / 149

Inference/DecodingPψ (y |x ) =Y1×ψ i (yi ) ×
Z (ψ, x )
i
|

{z

}

unary potentialsYψ s (y s )

s

|

{z

}

higher-order potentials

Two decoding problems:
MAP decoding: compute yb = arg max Pψ (y |x )yMarginal decoding: compute every Pψ (yi |x ) and Pψ (y s |x ); andevaluate the partition function Z (ψ, x )Sometimes easy, in general intractable...

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

22 / 149

When is Decoding Easy?

independent variables (trivial)
sequence models (Viterbi, forward-backward)
graphical models without cycles (variable elimination, belief
propagation)
graphical models with low treewidth (junction tree algorithm)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

23 / 149

When is Decoding Easy?

independent variables (trivial)
sequence models (Viterbi, forward-backward)
graphical models without cycles (variable elimination, belief
propagation)
graphical models with low treewidth (junction tree algorithm)
In general, for graphs with cycles, MAP decoding is NP-hard andmarginal decoding is #P-hardAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

23 / 149

When is Decoding Easy?

independent variables (trivial)
sequence models (Viterbi, forward-backward)
graphical models without cycles (variable elimination, belief
propagation)
graphical models with low treewidth (junction tree algorithm)
In general, for graphs with cycles, MAP decoding is NP-hard andmarginal decoding is #P-hardNote: tractability depends not only on the topology, but also on thepotentials

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

23 / 149

Example: Ising and Potts Models

Ising/Potts grid

Ernst Ising, 1900–1998

Ren Potts, 1925–2005

All factors are pairwise, variables are binary (Ising) or multi-class (Potts)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

24 / 149

Example: Ising and Potts Models

Ising/Potts grid

Ernst Ising, 1900–1998

Ren Potts, 1925–2005

All factors are pairwise, variables are binary (Ising) or multi-class (Potts)
MAP decoding is tractable for attractive Ising models (i.e. Ising models
with supermodular log-potentials):log ψij (1, 1) + log ψij (0, 0) ≥ log ψij (0, 1) + log ψij (1, 0)Good approximations for attractive Potts models

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

24 / 149

Example: Ising and Potts Models

Ising/Potts grid

Ernst Ising, 1900–1998

Ren Potts, 1925–2005

All factors are pairwise, variables are binary (Ising) or multi-class (Potts)
MAP decoding is tractable for attractive Ising models (i.e. Ising models
with supermodular log-potentials):log ψij (1, 1) + log ψij (0, 0) ≥ log ψij (0, 1) + log ψij (1, 0)Good approximations for attractive Potts models... but the general case is NP-hard and hard to approximate
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

24 / 149

Example: Skip-Chain CRFs
Skip-chain CRFs are useful to model long-range dependencies

Skip-chains introduce cycles, making decoding more expensive
We could write this information in the “state” and still decode withdynamic programming, but that would blow up the number of states

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

25 / 149

Beyond Graphical Models

Some NLP problems (e.g. parsing) require representations beyond
graphical models
Dynamic programming algorithms (CKY, inside-outside) still work for
those representations
Example: case-factor diagrams (McAllester et al., 2008)
Other problems (e.g. matching, spanning trees) can be solved withcombinatorial algorithms not related with dynamic programming
All these can still be represented as GMs by “generalizing” thenotion of factor

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

26 / 149

Factors as Machines

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

27 / 149

Factors as Machines

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

27 / 149

Three Kinds of Factors

Let N(s) denote the set of variables that are neighbors of factor s.
(Its cardinality |N(s)| is called the degree of s.)
1

Dense factors: ψ s (y s ) has all O(exp(|N(s)|)) degrees of freedom

2

Structured factors: ψ s (y s ) has internal structure

3

Hard constraint factors:(ψ s (y s ) :=André Martins (Priberam/IT)

1, if y s ∈ Ys
0, otherwise.

LP Decoders in NLP

http://tiny.cc/lpdnlp

28 / 149

Examples of Structured Factors

a factor for bipartite matching (Duchi et al., 2007)
combining a sequential model (POS tagger) with a PCFG (Rushet al., 2010)
combining CCG parsing and supertagging (Auli and Lopez, 2011)
dependency parsing with head automata (Smith and Eisner, 2008;
Koo et al., 2010)
handling string-valued variables with factors that are finite statetransducers (Dreyer and Eisner, 2009)
inversion transduction grammar constraint (Burkett and Klein, 2012)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

29 / 149

Examples of Hard Constraint Factors

XOR

OR

OR-OUT
KNAPSACK

Logic factors: can express arbitrary FOL constraints
Applications: Markov logic networks (Richardson and Domingos,
2006), constrained conditional models (Roth and Yih, 2004)
Knapsack factors: can express budget constraints
Applications: summarization, diversity problems,...
(Martins et al., 2011b; Almeida and Martins, 2013; Martins et al., 2014)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

30 / 149

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

31 / 149

Approximate Decoding

What to do when exact decoding is intractable?
Sampling methods (MCMC, etc.)
Mean field algorithms
LP relaxations
Message-passing
Dual decomposition
We’ll highlight connections between several of these methods.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

32 / 149

Approximate Decoding

What to do when exact decoding is intractable?
Sampling methods (MCMC, etc.)
Mean field algorithms
LP relaxations
Message-passing
Dual decomposition
We’ll highlight connections between several of these methods.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

32 / 149

Global/Local Decoding“Local” denotes independent problems within the scope of each factor“Global” involves a global assignment of variables, consistent across factors
Key idea: “glue” the local evidence at the factors to obtain a global
assignment
Our assumption: local decoding is easy, for every factor
We want to build a good (approximate) global decoder by invoking
the local decoders.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

33 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

34 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

35 / 149

Linear Programming(Kantorovich, 1940; Dantzig, 1947)
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N. Linear constraints

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

36 / 149

Linear Programming(Kantorovich, 1940; Dantzig, 1947)
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N. Linear constraints

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

36 / 149

Linear Programming(Kantorovich, 1940; Dantzig, 1947)
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N. Linear constraints

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

36 / 149

Linear Programming(Kantorovich, 1940; Dantzig, 1947)
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N. Linear constraints

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

36 / 149

Linear Programming(Kantorovich, 1940; Dantzig, 1947)
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N. Linear constraints

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

36 / 149

Linear Programming(Kantorovich, 1940; Dantzig, 1947)

If feasible and bounded, the solution is always attained at a vertex
Can be solved in polynomial time (Khachiyan, 1980)
Lots of off-the-shelf solvers (CPLEX, Gurobi, GLPK, LP Solve, etc.)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

37 / 149

Integer Linear Programming
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N, Linear constraints
z integer.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

38 / 149

Integer Linear Programming
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N, Linear constraints
z integer.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

38 / 149

Integer Linear Programming
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N, Linear constraints
z integer.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

38 / 149

Integer Linear Programming
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N, Linear constraints
z integer.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

38 / 149

Integer Linear Programming
max s > zzs.t.

Linear objective>

a i z ≤ bi , i = 1, . . . , N, Linear constraints
z integer.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

38 / 149

Integer Linear Programming
In general, NP-hard (Karp, 1972)
Existing solvers are effective for small instances, but don’t scale
LP relaxation: drops the integer constraints
Gives an upper bound of the solution of the ILP
A common first step in exact algorithms (branch-and-bound, cutting
plane, branch-and-cut)
Here’s a very simple approximate algorithm:
1

Solve the LP relaxation

2

If the solution is integer, then it is the solution of the ILP

3

Otherwise, apply a rounding heuristic (problem-dependent)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

39 / 149

Two Representations of Polytopes
Intersection of half-spaces (H-representation) or convex hull of a set ofvertices (V-representation)

To call a solver, we need to specify a concise H-representation
However, it may be difficult or impossible to obtain one if all we have is a
V-representation
We next show how this relates to MAP decoding...
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

40 / 149

Structured Outputs as Bit-Vectors

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state
One indicator qs (y s ) per each factor configuration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state
One indicator qs (y s ) per each factor configuration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state
One indicator qs (y s ) per each factor configuration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state
One indicator qs (y s ) per each factor configuration
Overall: each global output y ∈ Y(x ) is mapped to a bit-vector

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state
One indicator qs (y s ) per each factor configuration
Overall: each global output y ∈ Y(x ) is mapped to a bit-vector

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Structured Outputs as Bit-Vectors

One indicator pi (yi ) per each variable state
One indicator qs (y s ) per each factor configuration
Overall: each global output y ∈ Y(x ) is mapped to a bit-vector
Note: not all bit vectors are valid (they must be consistent)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

41 / 149

Marginal Polytope (Wainwright and Jordan, 2008)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

42 / 149

Marginal Polytope (Wainwright and Jordan, 2008)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

42 / 149

Marginal Polytope (Wainwright and Jordan, 2008)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

42 / 149

Marginal Polytope (Wainwright and Jordan, 2008)

Vertices of MARG(G) correspond to outputs Y(x )Points of MARG(G) correspond to realizable marginals (more later)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

42 / 149

Marginal Polytope (Wainwright and Jordan, 2008)

Vertices of MARG(G) correspond to outputs Y(x )Points of MARG(G) correspond to realizable marginals (more later)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

42 / 149

Marginal Polytope (Wainwright and Jordan, 2008)

Vertices of MARG(G) correspond to outputs Y(x )Points of MARG(G) correspond to realizable marginals (more later)This is a V-representation, what about an H-representation?
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

42 / 149

H-Representation With Integer Constraints

In general, there’s no concise H-representation for MARG(G)... but we can represent its vertices if integer constraints are permitted:X

qs (y s ) = 1,

qs (y s ) ≥ 0,∀y s ∈ Ys(normalization)X∀i ∈ N(s)(marginalization)

q is integer(integer constraints)yspi (yi ) =qs (y s ),y s ∼yiThis will open the door for formulating MAP decoding as an ILP.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

43 / 149

MAP Decoding as an ILP
Recall the MAP decoding problem:
yb = arg max Pψ (y |x )y ∈Y(x )Y
1 Yψ i (yi ) ψ s (y s )(ψ, x ) iy ∈Y(x ) Z s= arg max
= arg maxXy ∈Y(x )X

θ i (yi ) +θ s (y s ),siwhere θ i (yi ) := log ψ i (yi ) and θ s (y s ) := log ψ s (y s )We can rewrite this as an ILP:
maximizeXXi

θ i (yi )pi (yi ) +

XX

yi

s

θ s (y s )qs (y s )yssubject to (p, q) ∈ MARG(G)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

44 / 149

Local Polytope

Obtained by relaxing the integer constraints
Regard p i and q s as probability distributions that must be locallyconsistent:Xqs (y s ) = 1,

qs (y s ) ≥ 0,∀y s ∈ Ys(normalization)X∀i ∈ N(s)(marginalization)

q is integer(integer constraints)yspi (yi ) =qs (y s ),y s ∼yiThe feasible points are pseudo-marginals (not necessarily valid marginals)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

45 / 149

Local and Marginal Polytopes

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

46 / 149

Local and Marginal Polytopes

LOCAL(G) is an outer bound of MARG(G)It contains all the integer vertices of MARG(G), plus spurious
fractional vertices
If the graph has no cycles, then LOCAL(G) = MARG(G)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

46 / 149

LP-MAP Decoding

Solves a linear relaxation of MAP decoding, replacing MARG(G) by
LOCAL(G):maximizeXXi

θ i (yi )pi (yi ) +

XX

yi

s

θ s (y s )qs (y s )yssubject to (p, q) ∈ LOCAL(G)If the solution is integer, we solved the problem exactly; otherwise, apply arounding heuristic
Runtime is polynomial, but the procedure is only approximate.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

47 / 149

What About Hard Constraint Factors?

XOR

OR

OR-OUT
KNAPSACK

Logic and knapsack/budget constraints can also be expressed linearlyAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

48 / 149

Logic/Budget Constraints
Assume z1 , z2 , . . . ∈ {0, 1} (binary variables)
Condition
Implication
Negationorxor
or-outStatement
if z1 then z2
z1 iff ¬z2
z1 or z2 or z3
z1 xor z2 xor z3
z12 = z1 ∨ z2

and-outz12 = z1 ∧ z2

BudgetKnapsack

at most B active units
at most B total weight

Constraint
z1 ≤ z2
z1 = 1 − z2z1 + z2 + z3 ≥ 1
z1 + z2 + z3 = 1
z12 ≥ z1 , z12 ≥ z2 ,z12 ≤ z1 + z2
z12 ≤ z1 , z12 ≤ z2 ,z12 ≥ z1 + z2 − 1
P
z ≤B
Pi i
i wi zi ≤ BMore complex expressions via composition and De Morgan’s laws
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

49 / 149

Summing Up ILPs

MAP decoding can be expressed as an Integer Linear Program (ILP)
Logic constraints can be incorporated easily
Structured factors are harder (they need to be disassembled)
The ILP can be relaxed for approximate decoding (LP-MAP)
Geometrically: an outer bound of the marginal polytope
The relaxation is tight if the graph G does not have cycles
Disadvantage: an off-the-shelf LP solver won’t exploit themodularity of the problem
Algorithms that exploit the structure of the LP will be the topic
of the remaining sections

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

50 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

51 / 149

Motivating Example: Counting Soldiers(Adapted from MacKay 2003 and Gormley & Eisner ACL’14 tutorial.)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

52 / 149

Motivating Example: Counting Soldiers(Adapted from MacKay 2003 and Gormley & Eisner ACL’14 tutorial.)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

52 / 149

Motivating Example: Counting Soldiers(Adapted from MacKay 2003 and Gormley & Eisner ACL’14 tutorial.)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

52 / 149

Motivating Example: Counting Soldiers(Adapted from MacKay 2003 and Gormley & Eisner ACL’14 tutorial.)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

52 / 149

Motivating Example: Counting Soldiers(Adapted from MacKay 2003 and Gormley & Eisner ACL’14 tutorial.)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

52 / 149

Motivating Example: Counting Soldiers(Adapted from MacKay 2003 and Gormley & Eisner ACL’14 tutorial.)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

52 / 149

Motivating Example: Counting Soldiers(Adapted from MacKay 2003 and Gormley & Eisner ACL’14 tutorial.)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

52 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

53 / 149

Sum-Product Belief Propagation
Recall that Pψ (y |x ) :=YY1×
ψ i (yi ) ×
ψ s (y s )Z (ψ, x )si

Alternate between computing two kinds of messages:
Variable-to-factor: mi→s (yi ) = ψ i (yi )Y

ns 0 →i (yi )s 0 ∈N(i)\{s}Factor-to-variable: ns→i (yi ) =X
y s ∼yiAndré Martins (Priberam/IT)

LP Decoders in NLPψ s (y s )Y

mj→s (yj )j∈N(s)\{i}

http://tiny.cc/lpdnlp

54 / 149

Beliefs
Given the messages, we compute local beliefs:
Variable beliefs:
Y

pi (yi ) ∝ ψ i (yi )ns→i (yi )s∈N(i)

Factor beliefs:
qs (y s ) ∝ ψ s (y s )Ymi→s (yi )i∈N(s)

If the graph has no cycles, these beliefs converge to the true marginalspi (yi ) → Pψ (yi |x ),qs (y s ) → Pψ (y s |x )Otherwise: loopy BP (later)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

55 / 149

Belief Propagation as Calibration
Variable-to-factor messages:
Ymi→s (yi ) = ψ i (yi )ns 0 →i (yi ) =s 0 ∈N(i)\{s}pi (yi )ns→i (yi )Factor-to-variable messages:Pns→i (yi ) =X
y s ∼yiψ s (y s )Y

mj→s (yj ) =j∈N(s)\{i}y s ∼yi qs (y s )mi→s (yi )Calibration equations (attained at convergence):pi (yi ) =X

qs (y s )y s ∼yiPunchline: to run sum-product BP, we only need local marginals
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

56 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

57 / 149

Loopy Belief Propagation

What if the graph has cycles?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

58 / 149

Loopy Belief Propagation

What if the graph has cycles?
We’ll see that marginal decoding corresponds to optimizing a free energy
objective over the marginal polytope
Sum-product “loopy” BP entails two approximations:1

Replaces MARG(G) by LOCAL(G)2

Optimizes a Bethe free energy approximation

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

58 / 149

Step #1: Dual Parametrization
For any ψ, there are marginals p, q in MARG(G) that parametrize Pψ
E.g. if the graph has no cycles:Pψ (y |x )

=

Y
Y
1
ψ i (yi ) ×
ψ s (y s )Z (ψ, x ) is=Ypi (yi )1−|N(i)| ×iYqs (y s )(* next slide)s:= Pp,q (y |x )Therefore: a distribution can be represented as a point in MARG(G)θ := log(ψ) are called canonical parameters, and (p, q) mean parameters

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

59 / 149

(*) Derivation of Dual Parametrization
Assume a tree-shaped Bayes net (each variable i has a single parent πi )YP(y ) = P(y0 )P(yi |yπi )i6=0

Y P(yi , yπ )i

= P(y0 )i6=0P(yπi )

Q==

P(y0 ) s P(ys )Q|i:j=πi |j P(yj )Qs P(ys )Q|N(0)||N(j)−1|

P(y0 )

P(y0 )

j6=0 P(yj )Q==s P(ys )|N(j)|−1j P(yj )QYpi (yi )1−|N(i)| ×

qs (y s ).

siAndré Martins (Priberam/IT)

Y

LP Decoders in NLP

http://tiny.cc/lpdnlp

60 / 149

Step #2: Entropy and Log-Partition Function
Entropy of a probability distribution: H(P) = −XP(y ) log P(y )yDefinition: the Fenchel dual of a convex function f : RD → R ∪ {+∞} isthe convex function
f ? : RD
 → R ∪ {+∞} defined pointwise as>?
f (v) := sup v u − f (u)uAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

61 / 149

Step #2: Entropy and Log-Partition Function
Entropy of a probability distribution: H(P) = −XP(y ) log P(y )yDefinition: the Fenchel dual of a convex function f : RD → R ∪ {+∞} isthe convex function
f ? : RD
 → R ∪ {+∞} defined pointwise as>?
f (v) := sup v u − f (u)uTheorem (I): the log-partition function log Z (θ) and the negative
entropy −H(Pp,q ) are Fenchel dual:
log Z (θ) =max

X(p,q)∈MARG(G)θi > p i +θ s > q s + H(Pp,q ),

s

i

|

X

{z

(negative) variational free energy}

This underlies the well-known duality between maximum likelihood in
log-linear models and maximum entropy.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

61 / 149

Step #3: Loopy BP as Variational Inference
Theorem (II): The maximizers (p ∗ , q ∗ ) are the true marginals of Pθ :(p ∗ , q ∗ ) = arg max(p,q)∈MARG(G)X

θi > p i +iAndré Martins (Priberam/IT)

LP Decoders in NLPXθ s > q s + H(Pp,q )s

http://tiny.cc/lpdnlp

62 / 149

Step #3: Loopy BP as Variational Inference
Theorem (II): The maximizers (p ∗ , q ∗ ) are the true marginals of Pθ :(p ∗ , q ∗ ) = arg max(p,q)∈MARG(G)X

θi > p i +iXθ s > q s + H(Pp,q )sDrawback: in general, MARG(G) and H(Pp,q ) are both intractable

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

62 / 149

Step #3: Loopy BP as Variational Inference
Theorem (II): The maximizers (p ∗ , q ∗ ) are the true marginals of Pθ :(p ∗ , q ∗ ) = arg max(p,q)∈MARG(G)X

θi > p i +iXθ s > q s + H(Pp,q )sDrawback: in general, MARG(G) and H(Pp,q ) are both intractable
Yedidia et al. (2001) showed that loopy BP entails two approximations:1

Replace MARG(G) by LOCAL(G)2Approximate H(Pp,q ) by the Bethe entropy HBethe (Pp,q )Both are exact when the graph does not have cycles

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

62 / 149

Bethe Entropy Approximation
Derived by “pretending” the graph has no cycles
We have seenYPψ (y |x ) ≈pi (yi )1−|N(i)| ×Y

qs (y s )si

From which we can derive
H(Pp,q ) ≈ HBethe (Pp,q )
=

X

X

i

s

(1 − |N(i)|)Hi (p i ) +Hs (q s )Hans Bethe, 1906–2005

A linear combination of local entropies:
Hi (p i ) = −Xpi (yi ) log pi (yi ),Hs (q s ) = −yiXqs (y s ) log qs (y s )ysNot concave in general!
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

63 / 149

Geometric Illustration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

64 / 149

Geometric Illustration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

64 / 149

Geometric Illustration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

64 / 149

Geometric Illustration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

64 / 149

Geometric Illustration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

64 / 149

Geometric Illustration

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

64 / 149

Geometric Illustration

If loopy BP converges, it reaches a stationary point of theapproximate variational problem
HBethe (Pp,q ) is non-concave in general ⇒ local minima
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

64 / 149

Summary of Loopy BP
Advantages:
Simple to implement
Handles structured and logic factors (only need to compute local
marginals)
Often works well in practice (if cycles are not very influential)
Often yields a reasonable approximation of log Z and H
Disadvantages:
Doesn’t give an upper/lower bound of log Z and H
Entropy approximation is not concave (local minima)
May not converge
The final beliefs may not be realizable marginals

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

65 / 149

Tree Reweighted BP (Wainwright et al., 2005)
Key idea: cover the graph with a set of trees

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

66 / 149

Tree Reweighted BP (Wainwright et al., 2005)
Key idea: cover the graph with a set of trees

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

66 / 149

Tree Reweighted BP (Wainwright et al., 2005)
Key idea: cover the graph with a set of trees

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

66 / 149

Tree Reweighted BP (Wainwright et al., 2005)
Key idea: cover the graph with a set of trees

Count the appearance probability cis > 0 of each edge

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

66 / 149

Tree Reweighted BP (Wainwright et al., 2005)
Key idea: cover the graph with a set of trees

Count the appearance probability cis > 0 of each edge

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

66 / 149

Tree Reweighted BP (Wainwright et al., 2005)
Key idea: cover the graph with a set of trees

Count the appearance probability cis > 0 of each edge
This results in a convex upper bound of −H and log Z :HTRBP (Pp,q ) =

X

(1 −

P

s∈N(i) cis )Hi (p i ) +X

Hs (q s )si(Note: if all cis = 1 this would revert to the Bethe approximation)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

66 / 149

TRBP Messages
Variable-to-factor messages:
mi→s (yi ) =ψ i (yi )Q

cis 0 (yi )s 0 ∈N(i) ns 0 →i

ns→i (yi )Factor-to-variable messages:
ns→i (yi ) =X ψ s (y s )Qcjsj∈N(s) mj→s (yj )mi→s (yi )y s ∼yiVariable beliefs:
Y

pi (yi ) ∝ ψ i (yi )

cis
ns→i
(yi )

s∈N(i)

Factor beliefs:
qs (y s ) ∝ ψ s (y s )

Y

cis
(yi )
mi→s

i∈N(s)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

67 / 149

Summary of TRBP
Advantages:
Still simple to implement
Entropy approximation is concave (no local minima)
Gives an upper bound on −H and log Z
Lots of knobs (the appearance probabilities)
Disadvantages:
Lots of knobs (the appearance probabilities)
Typically it’s a very loose boundMay not converge (but in practice always does, with dampening)
The final beliefs may not be realizable marginals

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

68 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

69 / 149

Norm-Product BP (Hazan and Shashua, 2010)

Subsumes loopy BP and TRBP
Relies on a convex approximation to the entropy using counting numbersci ≥ 0 and cs > 0 (in its simpler variant)
HNPBP (Pp,q ) =X

ci Hi (p i ) +X

cs Hs (q s )siMessages will become norms!1/p

Recall the definition of `p -norm: kxkp =

X

|xi |

p

i

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

70 / 149

NPBP Messages
Variable-to-factor messages:


mi→s (yi ) =ψ i (yi )Q

s 0 ∈N(i)ns 0 →i (yi )cs /(ci +P 0c0)s ∈N(i) s

ns→i (yi )Factor-to-variable messages:
1/cs cs
mj→s (yj ) 




X 
ns→i (yi ) = ψ s (y s )y s ∼yiYj∈N(s)\{i}Variable beliefs:
1/(ci +P 0c0)s ∈N(i) spi (yi ) ∝ ψ i (yi )Yns→i (yi )

s∈N(i)

Factor beliefs:
cs

qs (y s ) ∝ ψ s (y s )Ymi→s (yi )

i∈N(s)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

71 / 149

Summary of NPBP
Advantages:
Still simple to implement
Entropy approximation is concave (no local minima)
Always converges (primal-dual block ascent)Lots of knobs (the counting numbers)
Disadvantages:
Lots of knobs (the counting numbers)
Messages are not computed in parallel (otherwise, may not converge)
The final beliefs may not be realizable marginals

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

72 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

73 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

74 / 149

Zero-Limit Temperature
Define Z where  is a temperature parameter:Z (ψ, x ) = X Y

ψ i (yi )1/y ∈Y(x ) iYψ s (ys )1/ sIf  = 1, this becomes the partition function Z (ψ, x )If  → 0, this becomes the mode of Pψ (y |x )Note that Z (ψ, x ) = Z (ψ 1/ , x ) for any , i.e., Z can be computed by
the same means as the partition function by scaling the potentials
By choosing a small enough , any sum-product message-passing
algorithm can be used to approximate the MAP
There is a trade-off between precision and numerical stability

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

75 / 149

Max-Product Belief Propagation
For MAP decoding instead of marginal decoding
Only change: factor-to-variable messages (max instead of

ns→i (yi ) = max ψ s (y s )y s ∼yiYmj→s (yj ) =j∈N(s)\{i}X)

maxy s ∼yi qs (y s )mi→s (yi )If the graph has no cycles, beliefs will converge to max-marginals:pi (yi ) → max Pψ (y |x ),y ∼yiqs (y s ) → max Pψ (y |x )y ∼y s

Decoding the best max-marginal at each variable node gives the MAP
With cycles: not guaranteed to converge, and even if it does, norelation with LP-MAP

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

76 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

77 / 149

TRW-S (Kolmogorov, 2006)

Same rationale as sum-product TRBP: cover the graph with spanning
trees, and compute messages using edge appearance probabilities
Only differences:
ReplaceX

with max

Messages need to be computed sequentially for convergenceAs max-product loopy BP, all is required is to compute local max-marginals
Under mild assumptions, gives the solution of LP-MAP

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

78 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

79 / 149

Max-Product LP (Globerson and Jaakkola, 2008)
Derived by writing the dual of LP-MAP, and solving it with a block
coordinate descent algorithm
The message updates need to be computed in a sequential schedule
Progress in the dual objective is monotonic
Drawback: since the dual is non-smooth, we may get stuck at a
suboptimal point(From Bertsekas et al. (1999))

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

80 / 149

MPLP Messages

Variable-to-factor messages:
mi→s (yi ) = ψ i (yi )Y

ns 0 →i (yi )s 0 ∈N(i)\{s}Factor-to-variable messages:

max ψ s (y s )1/|N(s)|y s ∼yins→i (yi ) =André Martins (Priberam/IT)

Y

mj→s (yj )1/|N(s)| j∈N(s)

mi→s (yi )LP Decoders in NLP

http://tiny.cc/lpdnlp

81 / 149

Summary of MPLP
Advantages:
Very simple to implement
Handles structured and logic factors (only need to compute local
max-marginals)
Monotonically improves the dual
No parameters to tune
Disadvantages:
Can get stuck at a suboptimal solution (general problem with
nonsmooth coordinate ascent)Messages are not computed in parallel (otherwise, may not converge)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

82 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

83 / 149

Summing Up Message-Passing

BP algorithms and their variants can be used both for MAP andmarginal decoding
They need to compute local marginals (sum-product) or
max-marginals (max-product)
Always exact if the graph has no cycles; approximate otherwise
They correspond to minimizing an energy approximation over the
local polytope
Some variants do convex approximations or compute upper bounds
Two views of MAP decoding: (1) the near-zero temperature limit of
marginal decoding; (2) a non-smooth optimization problem

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

84 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

85 / 149

Dual Decomposition
Old idea in optimization (Dantzig and Wolfe, 1960; Everett III, 1963)
First proposed by Komodakis et al. (2007) in computer vision
Introduced in NLP by Rush et al. (2010) for model combination
Successful in syntax, semantics, MT: Koo et al. (2010); Chang and
Collins (2011); Martins et al. (2011b); Almeida et al. (2014); Martins
and Almeida (2014), and many others.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

86 / 149

Dual Decomposition
Old idea in optimization (Dantzig and Wolfe, 1960; Everett III, 1963)
First proposed by Komodakis et al. (2007) in computer vision
Introduced in NLP by Rush et al. (2010) for model combination
Successful in syntax, semantics, MT: Koo et al. (2010); Chang and
Collins (2011); Martins et al. (2011b); Almeida et al. (2014); Martins
and Almeida (2014), and many others.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

86 / 149

Dual Decomposition
Old idea in optimization (Dantzig and Wolfe, 1960; Everett III, 1963)
First proposed by Komodakis et al. (2007) in computer vision
Introduced in NLP by Rush et al. (2010) for model combination
Successful in syntax, semantics, MT: Koo et al. (2010); Chang and
Collins (2011); Martins et al. (2011b); Almeida et al. (2014); Martins
and Almeida (2014), and many others.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

86 / 149

Dual Decomposition
Old idea in optimization (Dantzig and Wolfe, 1960; Everett III, 1963)
First proposed by Komodakis et al. (2007) in computer vision
Introduced in NLP by Rush et al. (2010) for model combination
Successful in syntax, semantics, MT: Koo et al. (2010); Chang and
Collins (2011); Martins et al. (2011b); Almeida et al. (2014); Martins
and Almeida (2014), and many others.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

86 / 149

Recap: LP-MAP
Recall the LP-MAP problem:
maximizeXθi > p i +

X
s

i

(

subject toθs > q s∈ ∆|Ys | , ∀sqs
p i = Mis q s , ∀i, s.

(local polytope)

Matrix Mis ∈ {0, 1}|Yi |×|Ys | represents the constraints pi (yi ) =X

qs (y s )y s ∼yiWe’ll reformulate this problem by:
1

Introducing copy variables q is = p i

2Defining θ is := θ i /|N(i)|André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

87 / 149

Reformulation of LP-MAP
The problem becomes:
maximizeXθs > q s +>i∈N(s) θ is q is

P



s

subject to


|Y |

 q s ∈ ∆ s , ∀sq = M q , ∀i, s(local polytope)

is s
is

 q = p , ∀i, s.
isi

By introducing Lagrange multipliers for the last constraints, we get thefollowing Lagrangian function:
L(p, q, λ) =Xθs > q s +Pi∈N(s) θ is>s

André Martins (Priberam/IT)q is +

X

λis > (p i − q is )isLP Decoders in NLP

http://tiny.cc/lpdnlp

88 / 149

Dual of LP-MAP
The dual problem isminimizeXgs (λ)

subject to λ ∈ Λ :=

s





λ

X




λis = 0s∈N(i)

where the gs (λ) are local subproblems,gs (λ) :=
=



P



P

max θ s > q s +>i∈N(s) (θ is + λis ) q isq̄ s ∈Qs

max θ s (y s ) +y s ∈Ys(

and q̄ s ∈ Qs encodes the constraintsi∈N(s) (θ is (yi ) + λis (yi ))q s ∈ ∆|Ys |q is = Mis q s , ∀i ∈ N(s).

A subgradient can be computed by solving these local subproblems
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

89 / 149

Projected Subgradient (Komodakis et al., 2007)
initialize penalties λ to zerorepeatuntil consensus (all q is = p i ) or maximum number of iterations reached

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

90 / 149

Projected Subgradient (Komodakis et al., 2007)
initialize penalties λ to zerorepeatfor each factor s doX>q̄ s ← arg max θ s > q s +(θ is + λis ) q isq̄ s ∈Qsi∈N(s)

end foruntil consensus (all q is = p i ) or maximum number of iterations reached

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

90 / 149

Projected Subgradient (Komodakis et al., 2007)
initialize penalties λ to zerorepeatfor each factor s doX>q̄ s ← arg max θ s > q s +(θ is + λis ) q isq̄ s ∈Qsi∈N(s)

end for
X
1
pi ←
q is
|N(i)|s∈N(i)

until consensus (all q is = p i ) or maximum number of iterations reached

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

90 / 149

Projected Subgradient (Komodakis et al., 2007)
initialize penalties λ to zerorepeatfor each factor s doX>q̄ s ← arg max θ s > q s +(θ is + λis ) q isq̄ s ∈Qsi∈N(s)

end for
X
1
pi ←
q is
|N(i)|s∈N(i)λis ← λis − η(q is − p i )until consensus (all q is = p i ) or maximum number of iterations reached

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

90 / 149

Projected Subgradient (Komodakis et al., 2007)
initialize penalties λ to zerorepeatfor each factor s doX>q̄ s ← arg max θ s > q s +(θ is + λis ) q isq̄ s ∈Qsi∈N(s)

end for
X
1
pi ←
q is
|N(i)|s∈N(i)λis ← λis − η(q is − p i )until consensus (all q is = p i ) or maximum number of iterations reached

Guaranteed to converge to an -accurate solution after at mostO(1/2 ) iterations
Problem: too slow when there are many factors (Martins et al.,2011b)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

90 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

91 / 149

Accelerating Consensus

Two fundamental problems with the subgradient algorithm:
1

The dual objectiveX

gs (λ) is non-smooths2Consensus is promoted only through updating λ (no memory aboutpast updates)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

92 / 149

Accelerating Consensus

Two fundamental problems with the subgradient algorithm:
1

The dual objectiveX

gs (λ) is non-smooths2Consensus is promoted only through updating λ (no memory aboutpast updates)

How can dual decomposition be accelerated?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

92 / 149

Accelerating Consensus

Two fundamental problems with the subgradient algorithm:
1

The dual objectiveX

gs (λ) is non-smooths2Consensus is promoted only through updating λ (no memory aboutpast updates)

How can dual decomposition be accelerated?
Jojic et al. (2010) smooth the objective and use gradient methods
Martins et al. (2011a): augmented LagrangianAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

92 / 149

Accelerating Consensus

Two fundamental problems with the subgradient algorithm:
1

The dual objectiveX

gs (λ) is non-smooths2Consensus is promoted only through updating λ (no memory aboutpast updates)

How can dual decomposition be accelerated?
Jojic et al. (2010) smooth the objective and use gradient methods
Martins et al. (2011a): augmented LagrangianAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

92 / 149

Accelerated Gradient (Jojic et al., 2010)
Basic idea: make the dual objective smooth by adding an entropic
perturbation with a near-zero  temperature (also Johnson (2008))
The subproblems become local marginal computations instead of
maximizations
With Nesterov’s accelerated gradient method (Nesterov, 2005), theiteration bound goes from O(1/2 ) to O(1/)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

93 / 149

Accelerated Gradient (Jojic et al., 2010)
Basic idea: make the dual objective smooth by adding an entropic
perturbation with a near-zero  temperature (also Johnson (2008))
The subproblems become local marginal computations instead of
maximizations
With Nesterov’s accelerated gradient method (Nesterov, 2005), theiteration bound goes from O(1/2 ) to O(1/)
However: very sensitive to the temperature parameterWith low temperatures, may face numerical issues (in particular forsome hard-constraint factors)
In practice, quite slow to take off (we’ll see some plots later)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

93 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

94 / 149

Accelerating Consensus

Two fundamental problems with the subgradient algorithm:
1

The dual objectiveX

gs (λ) is non-smooths2Consensus is promoted only through updating λ (no memory aboutpast updates)

How can dual decomposition be accelerated?
Jojic et al. (2010) smooth the objective and use gradient methods X
Martins et al. (2011a): augmented LagrangianAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

95 / 149

Accelerating Consensus

Two fundamental problems with the subgradient algorithm:
1

The dual objectiveX

gs (λ) is non-smooths2Consensus is promoted only through updating λ (no memory aboutpast updates)

How can dual decomposition be accelerated?
Jojic et al. (2010) smooth the objective and use gradient methods X
Martins et al. (2011a): augmented LagrangianAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

95 / 149

Alternating Directions Dual Decomposition (AD3 )Based on the alternating direction method of multipliers (ADMM):
an old method in optimization inspired by augmented Lagrangians(Gabay and Mercier, 1976; Glowinski and Marroco, 1975)
a natural fit to consensus problems
a natural “upgrade” of the subgradient algorithm (Boyd et al., 2011)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

96 / 149

Augmented Lagrangian and ADMM
Basic idea: augment the Lagrangian function with a quadratic penalty
Lη (p, q, λ) =Xθs > q s +Pi∈N(s) θ is>q is +sX

λis > (p i − q is )isηX
kq is − p i k2−
2 isMethod of multipliers (super-linear convergence):
1

Maximize Lη (p, q, λ) jointly w.r.t. p and q (challenging)

2

Multiplier update: λis ← λis − η(q is − p i )Alternating direction method of multipliers: replace step 1 by separate
maximizations (first w.r.t. q, then p)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

97 / 149

From Subgradient to AD3 (Martins et al., 2011a)
initialize penalties λ to zerorepeatfor each factor s = 1, . . . , SX
do>q̄ s ← arg max θ s > q s +(θ is + λis ) q isq̄ s ∈Qsi∈N(s)

end for
X
1
pi ←
q is
|N(i)|s∈N(i)λis ← λis − η(q is − p i )until consensus (all q is = p i ) or maximum number of iterations reached

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

98 / 149

From Subgradient to AD3 (Martins et al., 2011a)
initialize penalties λ to zerorepeatfor each factor s = 1, . . . , X
S do
η X
>
>
q̄ s ← arg max θ s q s +kq is − p i k2
(θ is + λis ) q is −q̄ s ∈Qs
2i∈N(s)i∈N(s)

end for
X
1
q is
pi ←
|N(i)|s∈N(i)λis ← λis − η(q is − p i )until consensus (all q is = p i ) or maximum number of iterations reached

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

98 / 149

From Subgradient to AD3 (Martins et al., 2011a)
initialize penalties λ to zerorepeatfor each factor s = 1, . . . , X
S do
η X
>
>
q̄ s ← arg max θ s q s +kq is − p i k2
(θ is + λis ) q is −q̄ s ∈Qs
2i∈N(s)i∈N(s)

end for
X
1
q is
pi ←
|N(i)|s∈N(i)λis ← λis − η(q is − p i )until consensus (all q is = p i ) or maximum number of iterations reachedfaster consensus: regularize q-step towards average votes in p

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

98 / 149

From Subgradient to AD3 (Martins et al., 2011a)
initialize penalties λ to zerorepeatfor each factor s = 1, . . . , X
S do
η X
>
>
q̄ s ← arg max θ s q s +kq is − p i k2
(θ is + λis ) q is −q̄ s ∈Qs
2i∈N(s)i∈N(s)

end for
X
1
q is
pi ←
|N(i)|s∈N(i)λis ← λis − η(q is − p i )until consensus (all q is = p i ) or maximum number of iterations reachedfaster consensus: regularize q-step towards average votes in p
better stopping conditions: keeps track of primal and dual residuals
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

98 / 149

Theoretical Guarantees of AD3
Convergent in primal and dual (Glowinski and Le Tallec, 1989)
Iteration bound: O(1/) (cf. O(1/2 ) for projected subgradient)Inexact AD3 subproblems: still convergent if residuals are summable(Eckstein and Bertsekas, 1992)
Always dual feasible: can compute upper bounds and embed inbranch-and-bound toward exact decoding (Das et al., 2012)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

99 / 149

Theoretical Guarantees of AD3
Convergent in primal and dual (Glowinski and Le Tallec, 1989)
Iteration bound: O(1/) (cf. O(1/2 ) for projected subgradient)Inexact AD3 subproblems: still convergent if residuals are summable(Eckstein and Bertsekas, 1992)
Always dual feasible: can compute upper bounds and embed inbranch-and-bound toward exact decoding (Das et al., 2012)

But: AD3 local subproblems are quadratic (more involved than inprojected subgradient)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

99 / 149

Theoretical Guarantees of AD3
Convergent in primal and dual (Glowinski and Le Tallec, 1989)
Iteration bound: O(1/) (cf. O(1/2 ) for projected subgradient)Inexact AD3 subproblems: still convergent if residuals are summable(Eckstein and Bertsekas, 1992)
Always dual feasible: can compute upper bounds and embed inbranch-and-bound toward exact decoding (Das et al., 2012)

But: AD3 local subproblems are quadratic (more involved than inprojected subgradient)
Still—very easy and efficient for logic and knapsack factors!

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

99 / 149

Projecting onto Hard Constraint Polytopes

XOR

OR

OR-OUT
KNAPSACK

Martins et al. (2011a): logic factors can be solved in O(K ) time
Almeida and Martins (2013): same for knapsack factors!

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

100 / 149

Structured Factors

What about structured factors?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

101 / 149

Structured Factors

What about structured factors?
Projected subgradient handles these quite wellcombinatorial machinery (Viterbi, Chu-Liu-Edmonds, Fulkerson-Ford,
Floyd-Warshall,...)
We cannot solve the AD3 subproblems with that machinery...

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

101 / 149

Structured Factors

What about structured factors?
Projected subgradient handles these quite wellcombinatorial machinery (Viterbi, Chu-Liu-Edmonds, Fulkerson-Ford,
Floyd-Warshall,...)
We cannot solve the AD3 subproblems with that machinery...
Or can we?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

101 / 149

Structured Factors

What about structured factors?
Projected subgradient handles these quite wellcombinatorial machinery (Viterbi, Chu-Liu-Edmonds, Fulkerson-Ford,
Floyd-Warshall,...)
We cannot solve the AD3 subproblems with that machinery...
Or can we?
Active set method: seek the support of the solution by adding/removing
components; very suitable for warm-starting (Nocedal and Wright, 1999)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

101 / 149

An Active Set Method for the AD3 Subproblem

q̄ s ← arg max θ s > q s +q̄ s ∈Qs

André Martins (Priberam/IT)

X(θ is + λis )> q is −i∈N(s)LP Decoders in NLPη X
2 i∈N(s)kq is − p i k2 

http://tiny.cc/lpdnlp

102 / 149

An Active Set Method for the AD3 Subproblem

q̄ s ← arg max θ s > q s +q̄ s ∈Qs

X(θ is + λis )> q is −i∈N(s)

η X
2 i∈N(s)kq is − p i k2 

Too many possible assignments: dimension of q s is O(exp(|N(s)|))André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

102 / 149

An Active Set Method for the AD3 Subproblem

q̄ s ← arg max θ s > q s +q̄ s ∈Qs

X(θ is + λis )> q is −i∈N(s)

η X
2 i∈N(s)kq is − p i k2 

Too many possible assignments: dimension of q s is O(exp(|N(s)|))Key result: there’s a sparse solution (only O(|N(s)|) nonzeros)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

102 / 149

An Active Set Method for the AD3 Subproblem

q̄ s ← arg max θ s > q s +q̄ s ∈Qs

X(θ is + λis )> q is −i∈N(s)

η X
2 i∈N(s)kq is − p i k2 

Too many possible assignments: dimension of q s is O(exp(|N(s)|))Key result: there’s a sparse solution (only O(|N(s)|) nonzeros)
Active set methods: seek the support of the solution by adding/removing
components; very suitable for warm-starting (Nocedal and Wright, 1999)
Only requirement: a local-max oracle (as in projected subgradient)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

102 / 149

An Active Set Method for the AD3 Subproblem

q̄ s ← arg max θ s > q s +q̄ s ∈Qs

X(θ is + λis )> q is −i∈N(s)

η X
2 i∈N(s)kq is − p i k2 

Too many possible assignments: dimension of q s is O(exp(|N(s)|))Key result: there’s a sparse solution (only O(|N(s)|) nonzeros)
Active set methods: seek the support of the solution by adding/removing
components; very suitable for warm-starting (Nocedal and Wright, 1999)
Only requirement: a local-max oracle (as in projected subgradient)More info: Martins et al. (2014)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

102 / 149

Runtime of AD3 vs PSDD (Parsing)AD3 (full)
Subgrad. (full)

800
600
400
200
00

200

400

600

800 1000 1200 1400 1600 1800
# iterations

average runtime (sec.)# oracle calls (normalized)

1000

0.20

Subgrad.
AD3
0.10

0.00
0

10

20
30
sentence length (words)

40

50

Caching and warm-starting the subproblems reduces drastically the
number of oracle calls—huge speed-ups!!
AD3 faster to achieve consensus (due to the quadratic penalty)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

103 / 149

What Kind of Local Decoding Do We Need?

Algorithm
Sum-Prod. BP (Pearl, 1988)
TRBP (Wainwright et al., 2005)
Norm-Product BP (Hazan and Shashua, 2010)
Max-Prod. BP (Pearl, 1988)
TRW-S (Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
Accelerated DD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

André Martins (Priberam/IT)

LP Decoders in NLP

Local Operation
marginals
marginals
marginals
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

http://tiny.cc/lpdnlp

104 / 149

Example: Potts Grid (20 × 20, 8 states)

A. Martins, M. Figueiredo, P. Aguiar, N. Smith, E. Xing (2014).
AD3 : Alternating Directions Dual Decomposition for MAP Inference in Graphical Models.
Journal of Machine Learning Research (to appear).

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

105 / 149

Example: Frame-Semantic Parsing
Dual Objective

Frame−Semantic Parsing
26.1

42.18

26

42.16

25.9

42.14

25.8

42.12
0

200 400 600 800 1000
Number of Iterations

61.4
61.2
61
60.8
60.6

20.4
20.3
20.2
200

400

600

800

20.1

100

66

MPLP

65

Subgrad.

64

AD3

200

300

400

500

63
200

400

600

800 1000

200

400

600

800 1000

Embedded in a branch-and-bound procedure for exact decoding
D. Das, A. Martins, N. Smith.
“An Exact DD Algorithm for Shallow Semantic Parsing with Constraints.”*SEM Workshop, 2012.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

106 / 149

Try It Yourself: AD3 Toolkit

Freely available at: http://www.ark.cs.cmu.edu/AD3
Implemented in C++, includes a Python wrapper (thanks to Andy
Mueller)
Implements MPLP, PSDD, AD3 for arbitrary factor graphs
Many built-in factors: logic, knapsack, dense, and some structured
factors
You can implement your own factor (only need to write a local MAP
decoder!)Toy examples included (parsing, coreference, Potts models)André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

107 / 149

Summing Up Dual Decomposition
Dual decomposition is a general optimization technique that splits thedual into several subproblems (one per factor) that must agree on
overlaps
This can be used to solve LP-MAP
We discussed three variants: subgradient (PSDD), accelerated
gradient (ADD), and alternating directions (AD3 )The algorithms are convergent and retrieve the true MAP if the graphhas no cycles; they also give certificates when the solution of
LP-MAP equals the MAP
For PSDD and AD3 only local maximizations are necessary; ADD
requires computing marginals

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

108 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

109 / 149

Applications

We’ll discuss three applications:
Turbo Parsing
Compressive Summarization
Joint Coreference Resolution and Quotation Attribution

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

110 / 149

Applications

We’ll discuss three applications:
Turbo Parsing
Compressive Summarization
Joint Coreference Resolution and Quotation Attribution

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

110 / 149

What is a Turbo Parser?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

111 / 149

What is a Turbo Parser?

A parser that runs inference in factor graphs, ignoring global
effects caused by loops (Martins et al., 2010)name inspired from turbo decoders (Berrou et al., 1993)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

111 / 149

What is a Turbo Parser?

A parser that runs inference in factor graphs, ignoring global
effects caused by loops (Martins et al., 2010)name inspired from turbo decoders (Berrou et al., 1993)
Next: we speed up turbo parsers via AD3 w/ active set

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

111 / 149

Recent Paper

André F. T. Martins, Miguel B. Almeida, Noah A. Smith.
“Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers.”
ACL 2013 Short Paper.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

112 / 149

An Important Distinction
A projective tree:

*

Logic

plays

a

minimal

role

here

A non-projective tree:*WelearnedAndré Martins (Priberam/IT)alessonin

LP Decoders in NLP

1987

about

volatility

http://tiny.cc/lpdnlp

113 / 149

An Important Distinction
A projective tree:

*

Logic

plays

a

minimal

role

here

A non-projective tree:*Welearnedalesson

in

1987

about

volatility

This talk: we allow non-projective trees.
Suitable for languages with flexible word order (Dutch, German, Czech,...)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

113 / 149

First-Order Scores for Arcs*We

learnedAndré Martins (Priberam/IT)alessonin

LP Decoders in NLP

1987

about

volatility

http://tiny.cc/lpdnlp

114 / 149

Second-Order Scores for Consecutive Siblings*We

learnedAndré Martins (Priberam/IT)alessonin

LP Decoders in NLP

1987

about

volatility

http://tiny.cc/lpdnlp

114 / 149

Second-Order Scores for Grandparents*

We

learnedAndré Martins (Priberam/IT)alessonin

LP Decoders in NLP

1987

about

volatility

http://tiny.cc/lpdnlp

114 / 149

Scores for Arbitrary Siblings*We

learnedAndré Martins (Priberam/IT)alessonin

LP Decoders in NLP

1987

about

volatility

http://tiny.cc/lpdnlp

114 / 149

Scores for Head Bigrams*

WelearnedAndré Martins (Priberam/IT)alessonin

LP Decoders in NLP

1987

about

volatility

http://tiny.cc/lpdnlp

114 / 149

Third-Order Scores for Grand-siblings*We

learnedalesson

in

1987

about

volatility

Used by Koo and Collins (2010) for projective parsing.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

114 / 149

Third-Order Scores for Tri-siblings*We

learnedalesson

in

1987

about

volatility

Used by Koo and Collins (2010) for projective parsing.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

114 / 149

Decoding

How to deal with all these parts?
Dynamic programming only available for the projective case...

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

115 / 149

Decoding

How to deal with all these parts?
Dynamic programming only available for the projective case...
Beyond arc-factored models, non-projective parsing is NP-hard(McDonald and Satta, 2007)
Need to embrace approximations!

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

115 / 149

Approximate Dependency Parsers

arc

consecutive siblings

grandparent

all siblings

tri-siblings

grand-siblings

McDonald et al. (2006)
Smith et al. (2008)
Martins et al. (2010)
Koo et al. (2010)
Martins et al. (2011)
Martins et al. (2013)

parserprojective + greedy
loopy BPLP solver
dual decomp.
AD3
AD3 & active set

André Martins (Priberam/IT)

AF
X
X
X
X
X
X

nonprojective archead bigram

directed path

CS
X
X
X
X
X

G

AS

X
X

X
X

X
X

X
X

LP Decoders in NLP

DP

HB

NPA

GS

TS

X

X

X
X

X
X

X

http://tiny.cc/lpdnlp

116 / 149

Factor Graph Representation

Variables nodes for dependency arcs, linked to a tree constraint
Head automata for consecutive siblings and grandparents (as inSmith and Eisner (2008); Koo et al. (2010))
Pairwise factors for arbitrary siblings (as Martins et al. (2011b))
Third-order head automata for grand-siblings and tri-siblings
Sequence model for head bigrams

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

117 / 149

Factor Graph Representation

Variables nodes for dependency arcs, linked to a tree constraint
Head automata for consecutive siblings and grandparents (as inSmith and Eisner (2008); Koo et al. (2010))
Pairwise factors for arbitrary siblings (as Martins et al. (2011b))
Third-order head automata for grand-siblings and tri-siblings
Sequence model for head bigrams
We solve the LP-MAP relaxation with AD3 .

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

117 / 149

Parsing Accuracies/Runtimes

SOTA accuracies for the largest non-projective datasets (CoNLL-2006 and
CoNLL-2008):

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

118 / 149

Extension: Broad-Coverage Semantic Parsing
Same idea applied to semantic role labeling.

Best results in the SemEval 2014 shared task:
André F. T. Martins and Mariana S. C. Almeida.
“Priberam: A Turbo Semantic Parser with Second Order Features.”
SemEval 2014.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

119 / 149

Applications

We’ll discuss three applications:
Turbo Parsing
Compressive Summarization
Joint Coreference Resolution and Quotation Attribution

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

120 / 149

Applications

We’ll discuss three applications:
Turbo Parsing
Compressive Summarization
Joint Coreference Resolution and Quotation Attribution

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

120 / 149

Recent Paper

Miguel B. Almeida and André F. T. Martins.
“Fast and Robust Compressive Summarization with Dual
Decomposition and Multi-Task Learning.”
ACL 2013.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

121 / 149

Multi-Document Summarization
Map a set of related documents to a brief summary.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

122 / 149

Multi-Document Summarization
Map a set of related documents to a brief summary.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

122 / 149

What Makes a Good Summary?

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

123 / 149

What Makes a Good Summary?

1André Martins (Priberam/IT)

conciseness

LP Decoders in NLP

http://tiny.cc/lpdnlp

123 / 149

What Makes a Good Summary?

André Martins (Priberam/IT)

1

conciseness2

informativeness

LP Decoders in NLP

http://tiny.cc/lpdnlp

123 / 149

What Makes a Good Summary?

André Martins (Priberam/IT)

1

conciseness2

informativeness3

grammaticality

LP Decoders in NLP

http://tiny.cc/lpdnlp

123 / 149

Extractive Summarization
Just extract the most salient sentences.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

124 / 149

Extractive Summarization
Just extract the most salient sentences.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

124 / 149

Extractive Summarization
Just extract the most salient sentences.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

124 / 149

What We Do: Compressive Summarization
Jointly extract and compress sentences.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

125 / 149

What We Do: Compressive Summarization
Jointly extract and compress sentences.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

125 / 149

What We Do: Compressive Summarization
Jointly extract and compress sentences.

For given summary size, easier to be informative, but harder to begrammatical.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

125 / 149

Compressive Summarization as Global Optimizationn
Indicator variables for every word of the nth sentence, z n := hzn,` iL`=1

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

126 / 149

Compressive Summarization as Global Optimizationn
Indicator variables for every word of the nth sentence, z n := hzn,` iL`=1

Summary length must not exceed the budget (B words)
Quality function rewards global informativeness (through g(z))...
... but also local grammaticality (through hn (z n )):maximizeg(z) +NX

hn (z n )

n=1

s.t.

Ln
N X
X

zn,` ≤ B.

n=1 `=1

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

126 / 149

Grammaticality: Sentence Compression Model
Inspired by Knight and Marcu (2000)’s word deletion model

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

127 / 149

Grammaticality: Sentence Compression Model
Inspired by Knight and Marcu (2000)’s word deletion model
Our model factors over dependency arcs:$

The

leaderAndré Martins (Priberam/IT)of moderate Kashmiri separatists warned Thursday that ...

LP Decoders in NLP

http://tiny.cc/lpdnlp

127 / 149

Grammaticality: Sentence Compression Model
Inspired by Knight and Marcu (2000)’s word deletion model
Our model factors over dependency arcs:$

The

leaderof moderate Kashmiri separatists warned Thursday that ...

Goal: maximize sum of arc scores, allowing only deletion of subtrees.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

127 / 149

Grammaticality: Sentence Compression Model
Inspired by Knight and Marcu (2000)’s word deletion model
Our model factors over dependency arcs:$

The

leaderof moderate Kashmiri separatists warned Thursday that ...

Goal: maximize sum of arc scores, allowing only deletion of subtrees.
A structured factor, locally decodable with dynamic programming.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

127 / 149

Informativeness: Coverage Model

Inspired by extractive max-coverage models (Filatova and Hatzivassiloglou,
2004; Yih et al., 2007; Gillick et al., 2008; Lin and Bilmes, 2010)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

128 / 149

Informativeness: Coverage Model

Inspired by extractive max-coverage models (Filatova and Hatzivassiloglou,
2004; Yih et al., 2007; Gillick et al., 2008; Lin and Bilmes, 2010)
Extract a list of concepts from the original documents
Define relevance scores for each concept (linear feature-basedmodel)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

128 / 149

Informativeness: Coverage Model

Inspired by extractive max-coverage models (Filatova and Hatzivassiloglou,
2004; Yih et al., 2007; Gillick et al., 2008; Lin and Bilmes, 2010)
Extract a list of concepts from the original documents
Define relevance scores for each concept (linear feature-basedmodel)
Define g(z) as sum of scores for each concept in the summary

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

128 / 149

Graphical Model for Our Compressive Summarizer

BudgetAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

129 / 149

Graphical Model for Our Compressive Summarizer

Budget$Talks with Kashmiri

Sentences

separatists began

last

$

of moderate Kashmiri separatists warned Thursday that ...

The

André Martins (Priberam/IT)

leaderyear ...

LP Decoders in NLP

http://tiny.cc/lpdnlp

129 / 149

Graphical Model for Our Compressive Summarizer

Budget$Talks with Kashmiri separatists began

Sentences$

The

André Martins (Priberam/IT)

leaderlastyear ...

of moderate Kashmiri separatists warned Thursday that ...

LP Decoders in NLP

http://tiny.cc/lpdnlp

129 / 149

Graphical Model for Our Compressive Summarizer
Concept tokens

Budget$Talks with Kashmiri separatists began

Sentences$

The

André Martins (Priberam/IT)

leaderlastyear ...

of moderate Kashmiri separatists warned Thursday that ...

LP Decoders in NLP

http://tiny.cc/lpdnlp

129 / 149

Graphical Model for Our Compressive Summarizer
Concept tokens"Kashmiri separatists"

Concept type$

Talks with Kashmiri separatists began

Sentences$

The

André Martins (Priberam/IT)

leaderlast

Budgetyear ...

of moderate Kashmiri separatists warned Thursday that ...

LP Decoders in NLP

http://tiny.cc/lpdnlp

129 / 149

Graphical Model for Our Compressive Summarizer
Concept tokens"Kashmiri separatists"

Concept type$

Talks with Kashmiri separatists began

Sentences$The

leaderlast

Budgetyear ...

of moderate Kashmiri separatists warned Thursday that ...

1

We use dual decomposition (AD3 ) for solving a linear relaxation

2

We apply a fast rounding procedure to obtain a valid summary

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

129 / 149

Graphical Model for Our Compressive Summarizer
Concept tokens"Kashmiri separatists"

Concept type$

Talks with Kashmiri separatists began

Sentences$The

leaderlast

Budgetyear ...

of moderate Kashmiri separatists warned Thursday that ...

1

We use dual decomposition (AD3 ) for solving a linear relaxation

2

We apply a fast rounding procedure to obtain a valid summary

Multi-task learning: user-generated data (Simple English Wikipedia)
along with manual abstracts and compressive summaries
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

129 / 149

Results on TAC-2008 Dataset
Better informativeness (without sacrificing grammaticality):
Gillick et al. (2008)
Berg-Kirkpatrick et al. (2011)
Woodsend and Lapata (2012)
Single-task AD3

11.03
11.71
11.37
11.88

Multi-task AD3

12.30
ROUGE-2 Recall

Averaged runtimes per summarization problem (10 documents):
SolverILP Exact, GLPK
LP-Relax., GLPK
AD3 (1,000 its.)
Extractive (ILP)

André Martins (Priberam/IT)

Runtime (sec.)
10.394
2.265
0.406
0.265

LP Decoders in NLPROUGE-2
12.40
12.38
12.30
11.16

http://tiny.cc/lpdnlp

130 / 149

Applications

We’ll discuss three applications:
Turbo Parsing
Compressive Summarization
Joint Coreference Resolution and Quotation Attribution

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

131 / 149

Applications

We’ll discuss three applications:
Turbo Parsing
Compressive Summarization
Joint Coreference Resolution and Quotation Attribution

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

131 / 149

Recent Paper

Mariana S. C. Almeida, Miguel B. Almeida and André F. T. Martins.
“A Joint Model for Quotation Attribution and Coreference
Resolution.”
EACL 2014.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

132 / 149

Why Jointly?
Coreference resolution and quotation attribution may benefit frombeing treated as a joint task.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

133 / 149

Why Jointly?
Coreference resolution and quotation attribution may benefit frombeing treated as a joint task.
A speaker doesn’t refer to himself as he:
Rivals carp at “the principle of Pilson,” as NBC’s Arthur Watson once
put it – “he’s always expounding that rights are too high, then he’s
going crazy.” But the 49-year-old Mr. Pilson is hardly a man to ignore
the numbers.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

133 / 149

Why Jointly?
Coreference resolution and quotation attribution may benefit frombeing treated as a joint task.
A speaker doesn’t refer to himself as he:
Rivals carp at “the principle of Pilson,” as NBC’s Arthur Watson once
put it – “he’s always expounding that rights are too high, then he’s
going crazy.” But the 49-year-old Mr. Pilson is hardly a man to ignore
the numbers.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

133 / 149

Why Jointly?
Coreference resolution and quotation attribution may benefit frombeing treated as a joint task.
A speaker doesn’t refer to himself as he:
Rivals carp at “the principle of Pilson,” as NBC’s Arthur Watson once
put it – “he’s always expounding that rights are too high, then he’s
going crazy.” But the 49-year-old Mr. Pilson is hardly a man to ignore
the numbers.

Two consecutive quotes are often from co-referent speakers:
English novelist Dorothy L. Sayers described ringing as a “passion thatfinds its satisfaction in mathematical completeness and mechanicalperfection.”
Ringers, she added, are “filled with the solemn intoxication that comesof intricate ritual faultlessly performed.”

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

133 / 149

Why Jointly?
Coreference resolution and quotation attribution may benefit frombeing treated as a joint task.
A speaker doesn’t refer to himself as he:
Rivals carp at “the principle of Pilson,” as NBC’s Arthur Watson once
put it – “he’s always expounding that rights are too high, then he’s
going crazy.” But the 49-year-old Mr. Pilson is hardly a man to ignore
the numbers.

Two consecutive quotes are often from co-referent speakers:
English novelist Dorothy L. Sayers described ringing as a “passion thatfinds its satisfaction in mathematical completeness and mechanicalperfection.”
Ringers, she added, are “filled with the solemn intoxication that comesof intricate ritual faultlessly performed.”

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

133 / 149

Coreference Tree (Denis and Baldridge, 2008;
Fernandes et al., 2012; Durrett and Klein, 2013)

Clusters of co-referent mentions (entities) correspond to subtrees
coming out from the root node.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

134 / 149

Coreference Tree (Denis and Baldridge, 2008;
Fernandes et al., 2012; Durrett and Klein, 2013)

Clusters of co-referent mentions (entities) correspond to subtrees
coming out from the root node.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

134 / 149

From Coreference to Quotation-Coreference Trees(Almeida et al., 2014)

Include mention nodes and quotation nodes
Quotation nodes have to be leaves
Subtrees coming out from the root induce entity clusters along with
their quotes: entity-based quotation attribution

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

135 / 149

From Coreference to Quotation-Coreference Trees(Almeida et al., 2014)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

136 / 149

From Coreference to Quotation-Coreference Trees(Almeida et al., 2014)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

136 / 149

Beyond Arc Scores
The simplest coreference models (e.g., the surface model of Durrett andKlein (2013)) are arc-factored
Exact decoding can be performed in a greedy mannerAndré Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

137 / 149

Beyond Arc Scores
The simplest coreference models (e.g., the surface model of Durrett andKlein (2013)) are arc-factored
Exact decoding can be performed in a greedy manner
However: in our approach, an arc factored model would be equivalent to
do coreference resolution and quotation attribution independently...

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

137 / 149

Beyond Arc Scores
The simplest coreference models (e.g., the surface model of Durrett andKlein (2013)) are arc-factored
Exact decoding can be performed in a greedy manner
However: in our approach, an arc factored model would be equivalent to
do coreference resolution and quotation attribution independently...
To do things jointly, we add extra scores for:A speaker being mentioned inside a quotation
Consecutive quotes having the same speakers

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

137 / 149

Beyond Arc Scores
The simplest coreference models (e.g., the surface model of Durrett andKlein (2013)) are arc-factored
Exact decoding can be performed in a greedy manner
However: in our approach, an arc factored model would be equivalent to
do coreference resolution and quotation attribution independently...
To do things jointly, we add extra scores for:A speaker being mentioned inside a quotation
Consecutive quotes having the same speakers
These scores require knowing if pairs of nodes are in the same subtree.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

137 / 149

Logic Program
Arc variables: each node (except the root) has exactly one parent
j−1
Xai→j = 1,∀j 6= 0i=0Path variables: paths propagate through arcs
πi→∗ i = 1,∀i,πi→∗ k =_(ai→j ∧ πj→∗ k ),

∀i, k

i<j≤k

Pair variables: nodes k and ` are in the same subtree if they have acommon ancestor which is not the rootpk,` =_(πi→∗ k ∧ πi→∗ ` ),∀k, l.

i6=0

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

138 / 149

Experiments
Datasets:
WSJ portion of the Ontonotes (597 documents); same splits as
CoNLL 2011 shared task
Quotation annotations of the PARC dataset (Pareti, 2012; O’Keefeet al., 2012)
Coreference evaluation metrics: average between MUC, B3 , CEAFe
Quotation evaluation metrics:
Representative speaker match (RSM): # matches torepresentative (non-pronominal) mention of the gold speaker’s entity
Entity cluster F1 (ECF1 ): F1 score between the predicted and gold
speaker entity (sets of mentions)

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

139 / 149

Results
Coreference Resolution:
Durrett and Klein (2013) (surface)
Quote/Coref independent
Joint System

MUC F1
58.87
57.89
58.78

BCUB F1
62.74
62.50
63.79

CEAFE F1
45.46
45.48
45.50

Avg.
55.7
55.3
56.0

Quotation attribution:
QuoteOnly
QuoteAfterCoref
Quote/Coref independent
Joint System

André Martins (Priberam/IT)

LP Decoders in NLP

RSM
49.4%
64.6%
74.7%
76.6%

ECF1
41.2%
70.0%
73.7%
74.1%

http://tiny.cc/lpdnlp

140 / 149

Outline
1

Structured Prediction and Factor Graphs

2

Integer Linear Programming

3

Message-Passing Algorithms
Sum-Product
Max-Product4

Dual Decomposition

5

Applications

6

Conclusions

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

141 / 149

Conclusions
Many structured problems in NLP are NP-hard or expensive(constrained models, diversity, combination of structured models)
Often they can be approximately decoded via Linear Programming(e.g., by relaxing an ILP)
The structure inherent to these problems can be represented with afactor graphMessage-passing and dual decomposition algorithms can solve theseLPs efficiently, exploiting the structure of the graph
Conceptually: approximate global decoding by invoking only local
decoders (local maximizations, marginals, max-marginals, QPs, ...)
AD3 is faster than the subgradient algorithm both in theory and inpractice, and requires the same local decoders
SOTA results in several applications (turbo parsing, summarization,
joint coref and quotation attribution)
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

142 / 149

Thank you!

The syntactic/semantic parser and AD3 are freely available at:
http://www.ark.cs.cmu.edu/TurboParser
http://www.ark.cs.cmu.edu/AD3

lti

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

143 / 149

Acknowledgments
Fundação para a Ciência e Tecnologia, grants
PEst-OE/EEI/LA0008/2011 and PTDC/EEI-SII/2312/2012.
Fundação para a Ciência e Tecnologia and Information andCommunication Technologies Institute (Portugal/USA), through the
CMU-Portugal Program.
Priberam: QREN/POR Lisboa (Portugal), EU/FEDER programme,
Discooperio project, contract 2011/18501.
Priberam: QREN/POR Lisboa (Portugal), EU/FEDER programme,Intelligo project, contract 2012/24803.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

144 / 149

References I
Almeida, M. B. and Martins, A. F. T. (2013). Fast and robust compressive summarization with dual decomposition andmulti-task learning. In Proc. of the Annual Meeting of the Association for Computational Linguistics.
Almeida, M. S. C., Almeida, M. B., and Martins, A. F. T. (2014). A joint model for quotation attribution and coreference
resolution. In Proc. of the Annual Meeting of the European Chapter of the Association for Computational Linguistics.
Auli, M. and Lopez, A. (2011). A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG
Supertagging and Parsing. In Proc. of Annual Meeting of the Association for Computational Linguistics.
Berg-Kirkpatrick, T., Gillick, D., and Klein, D. (2011). Jointly learning to extract and compress. In Proc. of Annual Meeting of
the Association for Computational Linguistics.
Berrou, C., Glavieux, A., and Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding. In Proc. ofInternational Conference on Communications, volume 93, pages 1064–1070.
Bertsekas, D., Hager, W., and Mangasarian, O. (1999). Nonlinear programming. Athena Scientific.
Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2011). Distributed Optimization and Statistical Learning via theAlternating Direction Method of Multipliers. Now Publishers.
Burkett, D. and Klein, D. (2012). Fast inference in phrase extraction models with belief propagation. In Proc. of the North
American Chapter of the Association for Computational Linguistics, pages 29–38. Association for Computational Linguistics.
Chang, Y.-W. and Collins, M. (2011). Exact decoding of phrase-based translation models through lagrangian relaxation. In
Proc. of Empirical Methods for Natural Language Processing.
Clarke, J. and Lapata, M. (2008). Global Inference for Sentence Compression An Integer Linear Programming Approach.
Journal of Artificial Intelligence Research, 31:399–429.
Dantzig, G. and Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1):101–111.
Dantzig, G. B. (1947). Maximization of a linear function of variables subject to linear inequalities. Published in T.C. Koopmans(ed.): Activity Analysis of Production and Allocation, New York-London 1951, pages 339–347.
Das, D., Martins, A. F. T., and Smith, N. A. (2012). An Exact Dual Decomposition Algorithm for Shallow Semantic Parsing
with Constraints. In Proc. of First Joint Conference on Lexical and Computational Semantics (*SEM).
Denis, P. and Baldridge, J. (2008). Specialized models and ranking for coreference resolution. In Proceedings of the Conferenceon Empirical Methods in Natural Language Processing, pages 660–669. Association for Computational Linguistics.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

145 / 149

References II
Dreyer, M. and Eisner, J. (2009). Graphical models over multiple strings. In Proc. of Empirical Methods in Natural Language
Processing, pages 101–110. Association for Computational Linguistics.
Duchi, J., Tarlow, D., Elidan, G., and Koller, D. (2007). Using combinatorial optimization within max-product belief
propagation. Advances in Neural Information Processing Systems, 19.
Durrett, G. and Klein, D. (2013). Easy victories and uphill battles in coreference resolution. In Proceedings of the 2013
Conference on Empirical Methods in Natural Language Processing.
Eckstein, J. and Bertsekas, D. (1992). On the Douglas-Rachford splitting method and the proximal point algorithm for maximal
monotone operators. Mathematical Programming, 55(1):293–318.
Eisner, J. (1996). Three new probabilistic models for dependency parsing: An exploration. In Proc. of International Conference
on Computational Linguistics, pages 340–345.
Everett III, H. (1963). Generalized Lagrange multiplier method for solving problems of optimum allocation of resources.
Operations Research, 11(3):399–417.
Fernandes, E. R., dos Santos, C. N., and Milidiú, R. L. (2012). Latent structure perceptron with feature induction forunrestricted coreference resolution. In Joint Conference on EMNLP and CoNLL-Shared Task, pages 41–48. Association for
Computational Linguistics.
Filatova, E. and Hatzivassiloglou, V. (2004). A formal model for information selection in multi-sentence text extraction. In Proc.
of International Conference on Computational Linguistics.
Gabay, D. and Mercier, B. (1976). A dual algorithm for the solution of nonlinear variational problems via finite element
approximation. Computers and Mathematics with Applications, 2(1):17–40.
Gillick, D., Favre, B., and Hakkani-Tur, D. (2008). The icsi summarization system at tac 2008. In Proc. of Text Understanding
Conference.
Globerson, A. and Jaakkola, T. (2008). Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations.
Neural Information Processing Systems, 20.
Glowinski, R. and Le Tallec, P. (1989). Augmented Lagrangian and operator-splitting methods in nonlinear mechanics. Society
for Industrial Mathematics.
Glowinski, R. and Marroco, A. (1975). Sur l’approximation, par éléments finis d’ordre un, et la résolution, parpenalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires. Rev. Franc. Automat. Inform. Rech. Operat.,
9:41–76.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

146 / 149

References III
Hazan, T. and Shashua, A. (2010). Norm-product belief propagation: Primal-dual message-passing for approximate inference.
IEEE Transactions on Information Theory, 56(12):6294–6316.
Johnson, J. (2008). Equivalence of Entropy Regularization and Relative-Entropy Proximal Method. Unpublished manuscript.
Jojic, V., Gould, S., and Koller, D. (2010). Accelerated dual decomposition for MAP inference. In International Conference ofMachine Learning.
Kantorovich, L. V. (1940). A new method of solving of some classes of extremal problems. In Dokl. Akad. Nauk SSSR,
volume 28, pages 211–214.
Karp, R. M. (1972). Reducibility among combinatorial problems. Springer.
Khachiyan, L. G. (1980). Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical
Physics, 20(1):53–72.
Knight, K. and Marcu, D. (2000). Statistics-based summarization—step one: Sentence compression. In AAAI/IAAI.
Koller, D. and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. The MIT Press.
Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on PatternAnalysis and Machine Intelligence, 28:1568–1583.
Komodakis, N., Paragios, N., and Tziritas, G. (2007). MRF optimization via dual decomposition: Message-passing revisited. In
Proc. of International Conference on Computer Vision.
Koo, T. and Collins, M. (2010). Efficient third-order dependency parsers. In Proc. of Annual Meeting of the Association for
Computational Linguistics, pages 1–11.
Koo, T., Globerson, A., Carreras, X., and Collins, M. (2007). Structured prediction models via the matrix-tree theorem. In
Empirical Methods for Natural Language Processing.
Koo, T., Rush, A. M., Collins, M., Jaakkola, T., and Sontag, D. (2010). Dual decomposition for parsing with non-projective
head automata. In Proc. of Empirical Methods for Natural Language Processing.
Lauritzen, S. (1996). Graphical Models. Clarendon Press, Oxford.
Lin, H. and Bilmes, J. (2010). Multi-document summarization via budgeted maximization of submodular functions. In Proc. ofAnnual Meeting of the North American chapter of the Association for Computational Linguistics.
MacKay, D. (2003). Information Theory, Inference, and Learning Algorithms, volume 7. Cambridge University Press.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

147 / 149

References IV
Martins, A. F. T. and Almeida, M. S. C. (2014). Priberam: A turbo semantic parser with second order features. In Proc. of theInternational Workshop on Semantic Evaluations (SemEval); task 8: Broad-Coverage Semantic Dependency Parsing.
Martins, A. F. T., Figueiredo, M. A. T., Aguiar, P. M. Q., Smith, N. A., and Xing, E. P. (2011a). An Augmented LagrangianApproach to Constrained MAP Inference. In Proc. of International Conference on Machine Learning.
3

Martins, A. F. T., Figueiredo, M. A. T., Aguiar, P. M. Q., Smith, N. A., and Xing, E. P. (2014). AD : Alternating Directions
Dual Decomposition for MAP Inference in Graphical Models. Journal of Machine Learning Research (to appear).
Martins, A. F. T. and Smith, N. A. (2009). Summarization with a Joint Model for Sentence Extraction and Compression. In
North American Chapter of the Association for Computational Linguistics: Workshop on Integer Linear Programming for
NLP.
Martins, A. F. T., Smith, N. A., Aguiar, P. M. Q., and Figueiredo, M. A. T. (2011b). Dual Decomposition with Many
Overlapping Components. In Proc. of Empirical Methods for Natural Language Processing.
Martins, A. F. T., Smith, N. A., Xing, E. P., Figueiredo, M. A. T., and Aguiar, P. M. Q. (2010). Turbo Parsers: Dependency
Parsing by Approximate Variational Inference. In Proc. of Empirical Methods for Natural Language Processing.
McAllester, D., Collins, M., and Pereira, F. (2008). Case-factor diagrams for structured probabilistic modeling. Journal ofComputer and System Sciences, 74(1):84–96.
McDonald, R. (2006). Discriminative sentence compression with soft syntactic constraints. In Proc. of Annual Meeting of theEuropean Chapter of the Association for Computational Linguistics.
McDonald, R. and Satta, G. (2007). On the complexity of non-projective data-driven dependency parsing. In Proc. ofInternational Conference on Parsing Technologies.
McDonald, R. T., Pereira, F., Ribarov, K., and Hajic, J. (2005). Non-projective dependency parsing using spanning tree
algorithms. In Proc. of Empirical Methods for Natural Language Processing.
Nesterov, Y. (2005). Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152.
Nivre, J., Hall, J., Nilsson, J., Eryiǧit, G., and Marinov, S. (2006). Labeled pseudo-projective dependency parsing with support
vector machines. In Procs. of International Conference on Natural Language Learning.
Nocedal, J. and Wright, S. (1999). Numerical optimization. Springer verlag.

André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

148 / 149

References V
O’Keefe, T., Pareti, S., Curran, J. R., Koprinska, I., and Honnibal, M. (2012). A sequence labelling approach to quote
attribution. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing andComputational Natural Language Learning, pages 790–799. Association for Computational Linguistics.
Pareti, S. (2012). A database of attribution relations. In LREC, pages 3213–3217.
Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.
Richardson, M. and Domingos, P. (2006). Markov logic networks. Machine Learning, 62(1):107–136.
Roth, D. and Yih, W. (2004). A linear programming formulation for global inference in natural language tasks. In International
Conference on Natural Language Learning.
Rush, A. and Collins, M. (2012). A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural
Language Processing. Journal of Artificial Intelligence Research, 45:305–362.
Rush, A., Sontag, D., Collins, M., and Jaakkola, T. (2010). On dual decomposition and linear programming relaxations fornatural language processing. In Proc. of Empirical Methods for Natural Language Processing.
Rush, A. M. and Collins, M. (2011). Exact decoding of syntactic translation models through lagrangian relaxation. In Proc. ofAnnual Meeting on Association for Computational Linguistics.
Smith, D. and Eisner, J. (2008). Dependency parsing by belief propagation. In Proc. of Empirical Methods for Natural Language
Processing.
Smith, N. A. (2011). Linguistic Structure Prediction, volume 13 of Synthesis Lectures on Human Language Technologies.
Morgan and Claypool.
Wainwright, M. and Jordan, M. (2008). Graphical Models, Exponential Families, and Variational Inference. Now Publishers.
Wainwright, M. J., Jaakkola, T., and Willsky, A. (2005). A new class of upper bounds on the log partition function. IEEE
Transactions on Information Theory, 51(7):2313–2335.
Woodsend, K. and Lapata, M. (2012). Multiple aspect summarization using integer linear programming. In Proc. of Empirical
Methods in Natural Language Processing.
Yedidia, J. S., Freeman, W. T., and Weiss, Y. (2001). Generalized belief propagation. In Neural Information Processing Systems.
Yih, W.-t., Goodman, J., Vanderwende, L., and Suzuki, H. (2007). Multi-document summarization by maximizing informative
content-words. In Proc. of International Joint Conference on Artifical Intelligence.
André Martins (Priberam/IT)

LP Decoders in NLP

http://tiny.cc/lpdnlp

149 / 149