Fast and Robust Compressive Summarization
with Dual Decomposition and Multi-Task Learning
Miguel B. Almeida∗†
André F. T. Martins∗†
Priberam Labs, Alameda D. Afonso Henriques, 41, 2o , 1000-123 Lisboa, Portugal†
Instituto de Telecomunicações, Instituto Superior Técnico, 1049-001 Lisboa, Portugal{mba,atm}@priberam.pt∗

Abstract
We present a dual decomposition framework for multi-document summarization,using a model that jointly extracts andcompresses sentences. Compared withprevious work based on integer linear programming, our approach does not require
external solvers, is significantly faster, andis modular in the three qualities a summary should have: conciseness, informativeness, and grammaticality. In addition,
we propose a multi-task learning framework to take advantage of existing data
for extractive summarization and sentencecompression. Experiments in the TAC2008 dataset yield the highest published
ROUGE scores to date, with runtimes thatrival those of extractive summarizers.

1

Introduction

Automatic text summarization is a seminal problem in information retrieval and natural language
processing (Luhn, 1958; Baxendale, 1958; Edmundson, 1969). Today, with the overwhelming
amount of information available on the Web, thedemand for fast, robust, and scalable summarization systems is stronger than ever.
Up to now, extractive systems have been themost popular in multi-document summarization.
These systems produce a summary by extracting
a representative set of sentences from the original documents (Kupiec et al., 1995; Carbonell andGoldstein, 1998; Radev et al., 2000; Gillick et al.,2008). This approach has obvious advantages: it
reduces the search space by letting decisions be
made for each sentence as a whole (avoiding finegrained text generation), and it ensures a grammatical summary, assuming the original sentences are
well-formed. The typical trade-offs in these mod-els (maximizing relevance, and penalizing redundancy) lead to submodular optimization problems(Lin and Bilmes, 2010), which are NP-hard but approximable through greedy algorithms; learning ispossible with standard structured prediction algorithms (Sipos et al., 2012; Lin and Bilmes, 2012).
Probabilistic models have also been proposed tocapture the problem structure, such as determinantal point processes (Gillenwater et al., 2012).
However, extractive systems are rather limitedin the summaries they can produce. Long, partly
relevant sentences tend not to appear in the summary, or to block the inclusion of other sentences. This has motivated research in compressive summarization (Lin, 2003; Zajic et al., 2006;
Daumé, 2006), where summaries are formed bycompressed sentences (Knight and Marcu, 2000),
not necessarily extracts. While promising results
have been achieved by models that simultaneously
extract and compress (Martins and Smith, 2009;
Woodsend and Lapata, 2010; Berg-Kirkpatrick etal., 2011), there are still obstacles that need tobe surmounted for these systems to enjoy wide
adoption. All approaches above are based on integer linear programming (ILP), suffering fromslow runtimes, when compared to extractive systems. For example, Woodsend and Lapata (2012)
report 55 seconds on average to produce a summary; Berg-Kirkpatrick et al. (2011) report substantially faster runtimes, but fewer compressions
are allowed. Having a compressive summarizer
which is both fast and expressive remains an open
problem. A second inconvenience of ILP-based
approaches is that they do not exploit the modularity of the problem, since the declarative specification required by ILP solvers discards important
structural information. For example, such solvers
are unable to take advantage of efficient dynamic
programming routines for sentence compression(McDonald, 2006).

This paper makes progress in two fronts:• We derive a dual decomposition framework forextractive and compressive summarization (§2–3). Not only is this framework orders of magnitude more efficient than the ILP-based approaches, it also allows the three well-known
metrics of summaries—conciseness, informativeness, and grammaticality—to be treated separately in a modular fashion (see Figure 1). We
also contribute with a novel knapsack factor,
along with a linear-time algorithm for the corresponding dual decomposition subproblem.
• We propose multi-task learning (§4) as a principled way to train compressive summarizers,
using auxiliary data for extractive summarization and sentence compression. To this end,
we adapt the framework of Evgeniou and Pontil (2004) and Daumé (2007) to train structured
predictors that share some of their parts.
Experiments on TAC data (§5) yield state-of-theart results, with runtimes similar to that of extractive systems. To our best knowledge, this had
never been achieved by compressive summarizers.

2

Extractive Summarization

In extractive summarization, we are given a setof sentences D := {s1 , . . . , sN } belonging to one
or more documents, and the goal is to extract a
subset S ⊆ D that conveys a good summary of D
and whose total number of words does not exceed
a prespecified budget B.
We use an indicator vector y := hyn iN
n=1 to represent an extractive summary, where yn = 1 if
sn ∈ S, and yn = 0 otherwise. Let Ln be thenumber of words of the nth sentence. By designing a quality score function g : {0, 1}N → R, thiscan be cast as a global optimization problem witha knapsack constraint:
maximizeg(y)w.r.t. y ∈ {0, 1}NPN
s.t.
n=1 Ln yn ≤ B.

(1)

Intuitively, a good summary is one which selectssentences that individually convey “relevant” information, while collectively having small “redundancy.” This trade-off was explicitly modeled in early works through the notion of maximal marginal relevance (Carbonell and Goldstein, 1998; McDonald, 2007). An alternative

are coverage-based models (§2.1; Filatova andHatzivassiloglou, 2004; Yih et al., 2007; Gillick
et al., 2008), which seek a set of sentences thatcovers as many diverse “concepts” as possible; redundancy is automatically penalized since redundant sentences cover fewer concepts. Both models
can be framed under the framework of submodular
optimization (Lin and Bilmes, 2010), leading to
greedy algorithms that have approximation guarantees. However, extending these models to allow
for sentence compression (as will be detailed in§3) breaks the diminishing returns property, making submodular optimization no longer applicable.
2.1

Coverage-Based Summarization

Coverage-based extractive summarization can beformalized as follows. Let C(D) := {c1 , . . . , cM }be a set of relevant concept types which arepresent in the original documents D.1 Let σm be arelevance score assigned to the mth concept, andlet the set Im ⊆ {1, . . . , N } contain the indices ofthe sentences in which this concept occurs. Then,the following quality score function is defined:
g(y) =

PM

m=1 σm um (y),(2)

Wwhere um (y) := n∈Im yn is a Boolean functionthat indicates whether the mth concept is present
in the summary. Plugging this into Eq. 1, one obtains the following Boolean optimization problem:
maximizew.r.t.
s.t.

PM

m=1 σm umNy ∈ {0, 1} , u ∈ {0, 1}MW
um = n∈Im yn , ∀m ∈ [M ]PN
(3)n=1 Ln yn ≤ B,

where we used the notation [M ] := {1, . . . , M }.
This can be converted into an ILP and addressedwith off-the-shelf solvers (Gillick et al., 2008). A
drawback of this approach is that solving an ILP
exactly is NP-hard. Even though existing commercial solvers can solve most instances with a moderate speed, they still exhibit poor worst-case behaviour; this is exacerbated when there is the needto combine an extractive component with othermodules, as in compressive summarization (§3).
1
Previous work has modeled concepts as events (Filatova
and Hatzivassiloglou, 2004), salient words (Lin and Bilmes,2010), and word bigrams (Gillick et al., 2008). In the sequel,
we assume concepts are word k-grams, but our model canhandle other representations, such as phrases or predicateargument structures.

2.2

A Dual Decomposition Formulation

We next describe how the problem in Eq. 3 can beaddressed with dual decomposition, a class of optimization techniques that tackle the dual of combinatorial problems in a modular, extensible, andparallelizable manner (Komodakis et al., 2007;
Rush et al., 2010). In particular, we employ alternating directions dual decomposition (AD3 ;Martins et al., 2011a, 2012) for solving a linear relaxation of Eq. 3. AD3 resembles the subgradientbased algorithm of Rush et al. (2010), but it enjoys
a faster convergence rate. Both algorithms split
the original problem into several components,
and then iterate between solving independent local subproblems at each component and adjusting
multipliers to promote an agreement.2 The difference between the two methods is that the AD3 local subproblems, instead of requiring the computation of a locally optimal configuration, require
solving a local quadratic problem. Martins et al.
(2011b) provided linear-time solutions for several
logic constraints, with applications to syntax andframe-semantic parsing (Das et al., 2012). We will
see that AD3 can also handle budget and knapsackconstraints efficiently.
To tackle Eq. 3 with dual decomposition, we
split the coverage-based summarizer into the following M + 1 components (one per constraint):
1. For each of the M concepts in C(D), one
component for imposing the logic constraint
in Eq. 3. This corresponds to the OR - WITH OUTPUT factor described by Martins et al.
(2011b); the AD3 subproblem for the mth factor
can be solved in time O(|Im |).
2. Another component for the knapsack constraint. This corresponds to a (novel) KNAP SACK factor, whose AD3 subproblem is solvable in time O(N ). The actual algorithm is described in the appendix (Algorithm 1).3

3

Compressive Summarization

We now turn to compressive summarization,
which does not limit the summary sentences to beverbatim extracts from the original documents; in2
For details about dual decomposition and Lagrangian relaxation, see the recent tutorial by Rush and Collins (2012).
3
The AD3 subproblem in this case corresponds to computing an Euclidean projection onto the knapsack polytope(Eq. 11). Others addressed the related, but much harder, integer quadratic knapsack problem (McDonald, 2007).

stead, it allows the extraction of compressed sentences where some words can be deleted.
Formally, let us express each sentence of Dn
as a sequence of word tokens, sn := htn,` iL`=0 ,where tn,0 ≡ $ is a dummy symbol. We represent a compression of sn as an indicator vecn
tor z n := hzn,` iL`=0 , where zn,` = 1 if the `thword is included in the compression. By convention, the dummy symbol is included if and only if
the remaining compression is non-empty. A compressive summary can then be represented by anindicator vector z which is the concatenation of
N such vectors, z = hz 1 , . . . , z N i; each positionin this indicator vector is indexed by a sentencen ∈ [N ] and a word position ` ∈ {0} ∪ [Ln ].
Models for compressive summarization were
proposed by Martins and Smith (2009) and BergKirkpatrick et al. (2011) by combining extraction
and compression scores. Here, we follow the latter work, by combining a coverage score function
g with sentence-level compression score functions
h1 , . . . , hN . This yields the decoding problem:Pmaximize g(z) + N
n=1 hn (z n )w.r.t. z n ∈ {0, 1}Ln , ∀n ∈ [N ]PN PLns.t.
n=1`=1 zn,` ≤ B.
3.1

(4)

Coverage Model

We use a coverage function similar to Eq. 2, but
taking a compressive summary z as argument:P(5)g(z) = M
m=1 σm um (z),where we redefine um as follows. First, weparametrize each occurrence of the mth concept(assumed to be a k-gram) as a triple hn, `s , `e i,
where n indexes a sentence, `s indexes a start position within the sentence, and `e indexes the end
position. We denote by Tm the set of triples representing all occurrences of the mth concept in theoriginal text, and we associate an indicator variable zn,`s :`e to each member of this set. We thendefine um (z) via the following logic constraints:• A concept type is selected if some of its k-gram
tokens are selected:
W
um (y) := hn,`s ,`e i∈Tm zn,`s :`e .
(6)• A k-gram concept token is selected if all its
words are selected:Vezn,`s :`e := ``=`
z .
(7)
s n,`

Concept tokens"Kashmiri separatists"

Concept type

$

Talks

with Kashmiri separatists began

Sentences$The

leaderlast

Budgetyear ...

of moderate Kashmiri separatists warned Thursday that ...

Figure 1: Components of our compressive summarizer. Factors depicted in blue belong to the compression model, and aim to enforce grammaticality. The logic factors in red form the coverage component.
Finally, the budget factor, in green, is connected to the word nodes; it ensures that the summary fits theword limit. Shaded circles represent active variables while white circles represent inactive variables.
We set concept scores as σm := w · Φcov (D, cm ),where Φcov (D, cm ) is a vector of features (described in §3.5) and w the corresponding weights.
3.2

Compression Model

For the compression score function, we follow
Martins and Smith (2009) and decompose it as asum of local score functions ρn,` defined on dependency arcs:
P n(8)hn (z n ) := L`=1 ρn,` (zn,` , zn,π(`) ),where π(`) denotes the index of the word whichis the parent of the `th word in the dependency
tree (by convention, the root of the tree is thedummy symbol). To model the event that an
arc is “cut” by disconnecting a child from its
head, we define arc-deletion scores ρn,` (0, 1) :=w · Φcomp (sn , `, π(`)), where Φcomp is a feature
map, which is described in detail in §3.5. We set
ρn,` (0, 0) = ρn,` (1, 1) = 0, and ρn,` (1, 0) = −∞,to allow only the deletion of entire subtrees.
A crucial fact is that one can maximize Eq. 8
efficiently with dynamic programming (using theViterbi algorithm for trees); the total cost is linear
in Ln . We will exploit this fact in the dual decomposition framework described next.4
3.3

A Dual Decomposition Formulation

In previous work, the optimization problem in
Eq. 4 was converted into an ILP and fed to an offthe-shelf solver (Martins and Smith, 2009; BergKirkpatrick et al., 2011; Woodsend and Lapata,2012). Here, we employ the AD3 algorithm, in a
4

The same framework can be readily adapted to othercompression models that are efficiently decodable, such as
the semi-Markov model of McDonald (2006), which would
allow incorporating a language model for the compression.

similar manner as described in §2, but with an additional component for the sentence compressor,
and slight modifications in the other
P components.
We have the following N + M + M
m=1 |Tm | + 1
components in total, illustrated in Figure 1:
1. For each of the N sentences, one component
for the compression model. The AD3 quadratic
subproblem for this factor can be addressed bysolving a sequence of linear subproblems, as described by Martins et al. (2012). Each of thesesubproblems corresponds to maximizing an objective function of the same form as Eq. 8; thiscan be done in O(Ln ) time with dynamic programming, as discussed in §3.2.
2. For each of the M concept types in C(D),
one OR - WITH - OUTPUT factor for the logic constraint in Eq. 6. This is analogous to the one
described for the extractive case.
3. For each k-gram concept token in Tm , one
AND - WITH - OUTPUT factor that imposes theconstraint in Eq. 7. This factor was describedby Martins et al. (2011b) and its AD3 subproblem can be solved in time linear in k.
4. Another component linked to all the words imposing that at most B words can be selected;
this is done via a BUDGET factor, a particularcase of KNAPSACK. The runtime of this AD3
subproblem is linear in the number of words.
In addition, we found it useful to add a second
BUDGET factor limiting the number of sentencesthat can be selected to a prescribed value K. We
set K = 6 in our experiments.

3.4

Rounding Strategy

Recall that the problem in Eq. 4 is NP-hard, andthat AD3 is solving a linear relaxation. While
there are ways of wrapping AD3 in an exact searchalgorithm (Das et al., 2012), such strategies work
best when the solution of the relaxation has few
fractional components, which is typical of parsing and translation problems (Rush et al., 2010;
Chang and Collins, 2011), and attractive networks(Taskar et al., 2004). Unfortunately, this is not thecase in summarization, where concepts “compete”
with each other for inclusion in the summary, leading to frustrated cycles. We chose instead to adopt
a fast and simple rounding procedure for obtaining
a summary from a fractional solution.
The procedure works as follows. First, solve
the LP relaxation using AD3 , as described above.
This yields a solution z ∗ , where each component
lies in the unit interval [0, 1]. If these components
are all integer, then we have a certificate that thisis the optimal solution. Otherwise, we collect the∗ (“posK sentences with the highest values of zn,0teriors” on sentences), and seek the feasible summary which is the closest (in Euclidean distance)
to z ∗ , while only containing those sentences.
ThisPL
can be computed exactly in time O(B K
k=1 nk ),through dynamic programming.5
3.5

Features and Hard Constraints

As Berg-Kirkpatrick et al. (2011), we used
stemmed word bigrams as concepts, to which we
associate the following concept features (Φcov ):indicators for document counts, features indicating if each of the words in the bigram is a stopword, the earliest position in a document each concept occurs, as well as two and three-way conjunctions of these features.
For the compression model, we include the following arc-deletion features (Φcomp ):• the dependency label of the arc being deleted, as
well as its conjunction with the part-of-speech
tag of the head, of the modifier, and of both;• the dependency labels of the arc being deleted
and of its parent arc;
• the modifier tag, if the modifier is a function
word modifying a verb ;5
Briefly, if we link the roots of the K sentences to a superroot node, the problem above can be transformed into thatof finding the best configuration in the resulting binary tree
subject to a budget constraint. We omit details for space.

• a feature indicating whether the modifier or anyof its descendants is a negation word;• indicators of whether the modifier is a temporal
word (e.g., Friday) or a preposition pointing toa temporal word (e.g., on Friday).
In addition, we included hard constraints to prevent the deletion of certain arcs, following previous work in sentence compression (Clarke andLapata, 2008). We never delete arcs whose dependency label is SUB, OBJ, PMOD, SBAR, VC, or
PRD (this makes sure we preserve subjects and objects of verbs, arcs departing from prepositions orcomplementizers, and that we do not break verb
chains or predicative complements); arcs linking
to a conjunction word or siblings of such arcs (toprevent inconsistencies in handling coordinative
conjunctions); arcs linking verbs to other verbs,
to adjectives (e.g., make available), to verb particles (e.g., settle down), to the word that (e.g., saidthat), or to the word to if it is a leaf (e.g., allowed
to come); arcs pointing to negation words, cardinal
numbers, or determiners; and arcs connecting two
proper nouns or words within quotation marks.

4

Multi-Task Learning

We next turn to the problem of learning the modelfrom training data. Prior work in compressive
summarization has followed one of two strategies:
Martins and Smith (2009) and Woodsend and Lapata (2012) learn the extraction and compression
models separately, and then post-combine them,circumventing the lack of fully annotated data.
Berg-Kirkpatrick et al. (2011) gathered a small
dataset of manually compressed summaries, andtrained with full supervision. While the latterapproach is statistically more principled, it has
the disadvantage of requiring fully annotated data,
which is difficult to obtain in large quantities. On
the other hand, there is plenty of data containing manually written abstracts (from the DUC andTAC conferences) and user-generated text (fromWikipedia) that may provide useful weak supervision.
With this in mind, we put together a multi-task
learning framework for compressive summarization (which we name task #1). The goal is totake advantage of existing data for related tasks,
such as extractive summarization (task #2), andsentence compression (task #3). The three tasks
are instances of structured predictors (Bakır etTasksComp. summ. (#1)
Extr. summ. (#2)
Sent. comp. (#3)

FeaturesΦcov , Φcomp
Φcov
Φcomp

Decoder
AD3 (solve Eq. 4)
AD3 (solve Eq. 3)
dyn. prg. (max. Eq. 8)

Table 1: Features and decoders used for each task.
al., 2007), and for all of them we assume featurebased models that decompose over “parts”:• For the compressive summarization task, theparts correspond to concept features (§3.1) andto arc-deletion features (§3.2).
• For the extractive summarization task, there areparts for concept features only.
• For the sentence compression task, the parts
correspond to arc-deletion features only.
This is summarized in Table 1. Features forthe three tasks are populated into feature vectorsΦ1 (x, y), Φ2 (x, y), and Φ3 (x, y), respectively,
where hx, yi denotes a task-specific input-output
pair. We assume the feature vectors are all D dimensional, where we place zeros in entries corresponding to parts that are absent. Note that
this setting is very general and applies to arbitrary structured prediction problems (not just summarization), the only assumption being that someparts are shared between different tasks.
Next, we associate weight vectors v 1 , v 2 , v 3 ∈RD to each task, along with a “shared” vector w.
Each task makes predictions according to the rule:yb := arg max (w + v k ) · Φk (x, y),y(9)where k ∈ {1, 2, 3}. This setting is equivalent to the approach of Daumé (2007) for domain
adaptation, which consists in splitting each feature into task-component features and a sharedfeature; but here we do not duplicate features explicitly. To learn the weights, we regularize theweight vectors separately, and assume that eachtask has its own loss function Lk , so that the total
P3loss L is a weighted sum L(w, v 1 , v 2 , v 3 ) :=k=1 σk Lk (w + v k ). This yields the following
objective function to be minimized:
3

F (w, v 1 , v 2 , v 3 ) =X λk
λkwk2 +
kv k k2
2
2
k=1

+

1
N

3
X
k=1

σk Lk (w + v k ), (10)where λ and the λk ’s are regularization constants,
and N is the total number of training instances.6 In
our experiments (§5), we let the Lk ’s be structured
hinge losses (Taskar et al., 2003; Tsochantaridis etal., 2004), where the corresponding cost functions
are concept recall (for task #2), precision of arc
deletions (for task #3), and a combination thereof(for task #1).7 These losses were normalized, andwe set σk = N/Nk , where Nk is the number oftraining instances for the kth task. This ensures
all tasks are weighted evenly. We used the samerationale to set λ = λ1 = λ2 = λ3 , choosing thisvalue through cross-validation in the dev set.
We optimize Eq. 10 with stochastic subgradientdescent. This leads to update rules of the form˜ k (w + v k )w ← (1 − ηt λ)w − ηt σk ∇L˜ k (w + v k ),v j ← (1 − ηt λj )v j − ηt δjk σk ∇L˜ k are stochastic subgradients for the kth
where ∇L
task, that take only a single instance into account,and δjk = 1 if and only if j = k. Stochastic subgradients can be computed via cost-augmented decoding (see footnote 7).
Interestingly, Eq. 10 subsumes previous approaches to train compressive summarizers. The
limit λ → ∞ (keeping the λk ’s fixed) forces w →0, decoupling all the tasks. In this limit, inference
for task #1 (compressive summarization) is based
solely on the model learned from that task’s data,
recovering the approach of Berg-Kirkpatrick et al.
(2011). In the other extreme, setting σ1 = 0 simply ignores task #1’s training data. As a result, theoptimal v 1 will be a vector of zeros; since tasks#2 and #3 have no parts in common, the objective
will decouple into a sum of two independent terms
6
Note that, by substituting uk := w + v k and solving forw, the problem in Eq. 10 becomes that of minimizing the sumof the losses with a penalty for the (weighted) variance of thevectors {0, u1 , u2 , u3 }, regularizing the difference towards
their average, as in Evgeniou and Pontil (2004). This is similar to the hierarchical joint learning approach of Finkel andManning (2010), except that our goal is to learn a new task
(compressive summarization) instead of combining tasks.
7
Let Yk denote the output set for the kth task. Givena task-specific cost function ∆k : Yk × Yk → R,
and letting hxt , yt iTt=1 be the labeled dataset for thistask, the structured hinge loss takes the form Lk (uk ) :=P000
t maxy ∈Yk(uk · (Φk (xt , y ) − Φk (xt , yt )) + ∆k (y , yt )).
The inner maximization over y 0 is called the cost-augmented
decoding problem: it differs from Eq. 9 by the inclusionof the cost term ∆k (y 0 , yt ). Our costs decompose over themodel’s factors, hence any decoder for Eq. 9 can be used
for the maximization above: for tasks #1–#2, we solve a
relaxation by running AD3 without rounding, and for task #3
we use dynamic programming; see Table 1.

involving v 2 and v 3 , which is equivalent to training the two tasks separately and post-combining
the models, as Martins and Smith (2009) did.

5

Experiments

5.1

Experimental setup

We evaluated our compressive summarizers ondata from the Text Analysis Conference (TAC)
evaluations. We use the same splits as previous work (Berg-Kirkpatrick et al., 2011; Woodsend and Lapata, 2012): the non-update portionsof TAC-2009 for training and TAC-2008 for testing. In addition, we reserved TAC-2010 as a devset. The test partition contains 48 multi-document
summarization problems; each provides 10 related
news articles as input, and asks for a summarywith up to 100 words, which is evaluated against
four manually written abstracts. We ignored all
the query information present in the TAC datasets.
Single-Task Learning. In the single-task experiments, we trained a compressive summarizer on
the dataset disclosed by Berg-Kirkpatrick et al.
(2011), which contains manual compressive summaries for the TAC-2009 data. We trained a structured SVM with stochastic subgradient descent;
the cost-augmented inference problems are relaxed and solved with AD3 , as described in §3.3.8
We followed the procedure described in BergKirkpatrick et al. (2011) to reduce the number ofcandidate sentences: scores were defined for eachsentence (the sum of the scores of the concepts
they cover), and the best-scored sentences were
greedily selected up to a limit of 1,000 words. We
then tagged and parsed the selected sentences with
TurboParser.9 Our choice of a dependency parser
was motivated by our will for a fast system; in particular, TurboParser attains top accuracies at a rateof 1,200 words per second, keeping parsing times
below 1 second for each summarization problem.
Multi-Task Learning. For the multi-task experiments, we also used the dataset of BergKirkpatrick et al. (2011), but we augmented thetraining data with extractive summarization andsentence compression datasets, to help train the8
We use the AD3 implementation in http://www.
ark.cs.cmu.edu/AD3, setting the maximum number of
iterations to 200 at training time and 1000 at test time. We
extended the code to handle the knapsack and budget factors;
the modified code will be part of the next release (AD3 2.1).
9
http://www.ark.cs.cmu.edu/TurboParser

compressive summarizer. For extractive summarization, we used the DUC 2003 and 2004
datasets (a total of 80 multi-document summarization problems). We generated oracle extracts by
maximizing bigram recall with respect to the manual abstracts, as described in Berg-Kirkpatrick etal. (2011). For sentence compression, we adapted
the Simple English Wikipedia dataset of Woodsend and Lapata (2011), containing aligned sentences for 15,000 articles from the English andSimple English Wikipedias. We kept only the
4,481 sentence pairs corresponding to deletionbased compressions.
5.2

Results

Table 2 shows the results. The top rows referto three strong baselines: the ICSI-1 extractive
coverage-based system of Gillick et al. (2008),
which achieved the best ROUGE scores in the
TAC-2008 evaluation; the compressive summarizer of Berg-Kirkpatrick et al. (2011), denoted
BGK’11; and the multi-aspect compressive summarizer of Woodsend and Lapata (2012), denoted
WL’12. All these systems require ILP solvers.
The bottom rows show the results achieved by
our implementation of a pure extractive system(similar to the learned extractive summarizer ofBerg-Kirkpatrick et al., 2011); a system that postcombines extraction and compression components
trained separately, as in Martins and Smith (2009);
and our compressive summarizer trained as a single task, and in the multi-task setting.
The ROUGE and Pyramid scores show that thecompressive summarizers (when properly trained)
yield considerable benefits in content coverageover extractive systems, confirming the results ofBerg-Kirkpatrick et al. (2011). Comparing thetwo bottom rows, we see a clear benefit by training in the multi-task setting, with a consistent
gain in both coverage and linguistic quality. Our
ROUGE-2 score (12.30%) is, to our knowledge,
the highest reported on the TAC-2008 dataset,with little harm in grammaticality with respect toan extractive system that preserves the original
sentences. Figure 2 shows an example summary.
5.3

Runtimes

We conducted another set of experiments to compare the runtime of our compressive summarizer
based on AD3 with the runtimes achieved by
GLPK, the ILP solver used by Berg-Kirkpatrick etal. (2011). We varied the maximum number of it-System
ICSI-1
BGK’11WL’12
Extractive
Post-comb.
Single-task
Multi-task

R-2
11.03
11.71
11.37
11.16
11.07
11.88
12.30

R-SU4
13.96
14.47
14.47
14.07
13.85
14.86
15.18

Pyr
34.5†
41.3†
–
36.0
38.4
41.0
42.6

LQ
–
–
–
4.6
4.1
3.8
4.2

Table 2: Results for compressive summarization.
Shown are the ROUGE-2 and ROUGE SU-4 recalls with the default options from the ROUGE
toolkit (Lin, 2004); Pyramid scores (Nenkova andPassonneau, 2004); and linguistic quality scores,scored between 1 (very bad) to 5 (very good). For
Pyramid, the evaluation was performed by twoannotators, each evaluating half of the problems;
scores marked with † were computed by different
annotators and are not directly comparable. Linguistic quality was evaluated by two linguists; weshow the average of the reported scores.
SolverILP Exact
LP-Relax.
AD3 -5000
AD3 -1000
AD3 -200
Extractive (ILP)

Runtime (sec.)
10.394
2.265
0.952
0.406
0.159
0.265

ROUGE-2
12.40
12.38
12.38
12.30
12.15
11.16

Table 3: Runtimes of several decoders on a Intel
Core i7 processor @2.8 GHz, with 8GB RAM. For
each decoder, we show the average time taken tosolve a summarization problem in TAC-2008. The
reported runtimes of AD3 and LP-Relax include
the time taken to round the solution (§3.4), which
is 0.029 seconds on average.
erations of AD3 in {200, 1000, 5000}, and clocked
the time spent by GLPK to solve the exact ILPs
and their relaxations. Table 3 depicts the results.10
We see that our proposed configuration (AD3 1000) is orders of magnitude faster than the ILP
solver, and 5 times faster than its relaxed variant,while keeping similar accuracy levels.11 The gain
when the number of iterations in AD3 is increased
to 5000 is small, given that the runtime is more
10
Within dual decomposition algorithms, we verified experimentally that AD3 is substantially faster than the subgradient algorithm, which is consistent with previous findings(Martins et al., 2011b).
11
The runtimes obtained with the exact ILP solver seemslower than those reported by Berg-Kirkpatrick et al. (2011).
(around 1.5 sec. on average, according to their Fig. 3). We
conjecture that this difference is due to the restricted set of
subtrees that can be deleted by Berg-Kirkpatrick et al. (2011),
which greatly reduces their search space.

Japan dispatched four military ships to help Russia rescue seven crew members aboard a small submarine
trapped on the seabed in the Far East. The Russian
Pacific Fleet said the crew had 120 hours of oxygen
reserves on board when the submarine submerged at
midday Thursday (2300 GMT Wednesday) off the Kamchatka peninsula, the stretch of Far Eastern Russia facing the Bering Sea. The submarine, used in rescue,research and intelligence-gathering missions, became
stuck at the bottom of the Bay of Berezovaya off Russia’s Far East coast when its propeller was caught in afishing net. The Russian submarine had been tending
an underwater antenna mounted to the sea floor when it
became snagged on a wire helping to stabilize a ventilation cable attached to the antenna. Rescue crews lowered a British remote-controlled underwater vehicle to a
Russian mini-submarine trapped deep under the Pacific
Ocean, hoping to free the vessel and its seven trappedcrewmen before their air supply ran out.

Figure 2: Example summary from our compressive system. Removed text is grayed out.
than doubled; accuracy starts to suffer, however, if
the number of iterations is reduced too much. In
practice, we observed that the final rounding procedure was crucial, as only 2 out of the 48 test
problems had integral solutions (arguably becauseof the “repulsive” nature of the network, as hinted
in §3.4). For comparison, we also report in the bottom row the average runtime of the learned extractive baseline. We can see that our system’s runtime
is competitive with this baseline. To our knowledge, this is the first time a compressive summarizer achieves such a favorable accuracy/speed
tradeoff.

6

Conclusions

We presented a multi-task learning framework forcompressive summarization, leveraging data forrelated tasks in a principled manner. We decodewith AD3 , a fast and modular dual decomposition
algorithm which is orders of magnitude faster thanILP-based approaches. Results show that the stateof the art is improved in automatic and manual
metrics, with speeds close to extractive systems.
Our approach is modular and easy to extend.
For example, a different compression model could
incorporate rewriting rules to enable compressions that go beyond word deletion, as in Cohn
and Lapata (2008). Other aspects may be added
as additional components in our dual decomposition framework, such as query information(Schilder and Kondadadi, 2008), discourse con-

straints (Clarke and Lapata, 2007), or lexical preferences (Woodsend and Lapata, 2012). Our multitask approach may be used to jointly learn parameters for these aspects; the dual decomposition algorithm ensures that optimization remains
tractable even with many components.

A

Projection Onto Knapsack

This section describes a linear-time algorithm (Algorithm 1) for solving the following problem:
minimize kz − ak2
w.r.t. zn ∈ [0, 1], ∀n ∈ [N ],PNs.t.
n=1 Ln zn ≤ B,

(11)

where a ∈ RN and Ln ≥ 0, ∀n ∈ [N ]. This includes as special cases the problems of projecting
onto a budget constraint (Ln = 1, ∀n) and onto
the simplex (same, plus B = 1).
Let clip(t) := max{0, min{1, t}}. Algorithm 1starts by clipping a tounit interval; if that
Pthe
N
yields a z satisfying n=1 Ln zn ≤ B, we aredone.POtherwise, the solution of Eq. 11 must satisfy N
n=1 Ln zn = B. It can be shown from theKKT conditions that the solution is of the formzn∗ := clip(an + τ ∗ Ln ) for a constant τ ∗ lying in aparticular interval of split-points (line 11). To seek
this constant, we use an algorithm due to Pardalos
and Kovoor (1990) which iteratively shrinks thisinterval. The algorithm requires computing medians as a subroutine, which can be done in linear
time (Blum et al., 1973). The overall complexityin O(N ) (Pardalos and Kovoor, 1990).

Acknowledgments
We thank all reviewers for their insightful comments; Trevor Cohn for helpful discussions about
multi-task learning; Taylor Berg-Kirkpatrick foranswering questions about their summarizer andfor providing code; and Helena Figueira and Pedro
Mendes for helping with manual evaluation. This
work was partially supported by the EU/FEDER
programme, QREN/POR Lisboa (Portugal), under
the Discooperio project (contract 2011/18501),
and by a FCT grant PTDC/EEI-SII/2312/2012.

References
G. Bakır, T. Hofmann, B. Schölkopf, A. Smola,
B. Taskar, and S. Vishwanathan. 2007. Predicting
Structured Data. The MIT Press.

Algorithm 1 Projection Onto Knapsack.
N
1: input: a := han iN
n=1 , costs hLn in=1 , maximum cost B
2:
3: {Try to clip into unit interval:}
4: Set zn ← clip(an ) for n ∈ [N ]P
5: if Nn=1 Ln zn ≤ B then6:
Return z and stop.
7: end if
8:
9: {Run Pardalos and Kovoor (1990)’s algorithm:}
10: Initialize working set W ← {1, . . . , K}
11: Initialize set of split points:

P ← {−an /Ln , (1 − an )/Ln }N
n=1 ∪ {±∞}
12: Initialize τL ← −∞, τR ← ∞, stight ← 0, ξ ← 0.
13: while W 6= ∅ do
14:
Compute τ ← Median(P)P
15:
Set s ← stight + ξτ + n∈W Ln clip(an + τ Ln )16:
If s ≤ B, set τL ← τ ; if s ≥ B, set τR ← τ
17:Reduce set of split points: P ← P ∩ [τL , τR ]18:
Define the sets:
WL := {n ∈ W | (1 − an )/Ln < τL }WR := {n ∈ W | − an /Ln > τR }an
1 − an
WM := n ∈ W −≤ τL ∧
≥ τR
Ln
Ln
19:
Update working set: W ← W \ (WL ∪ WR ∪ WM )20:
Update tight-sum:PPstight ← stight + n∈WL Ln (1−an )− n∈WR Ln anP
21:
Update slack-sum: ξ ← ξ + n∈WM L2n
22: end whileP
23: Define τ ∗ ← (B − N
i=1 Li ai − stight )/ξ
24: Set zn ← clip(an + τ ∗ Ln ), ∀n ∈ [N ]25: output: z := hzn iN
n=1 .

P. B. Baxendale. 1958. Machine-made index for technical literature—an experiment. IBM Journal of Research Development, 2(4):354–361.
Taylor Berg-Kirkpatrick, Dan Gillick, and Dan Klein.
2011. Jointly learning to extract and compress. In
Proc. of Annual Meeting of the Association for Computational Linguistics.
Manuel Blum, Robert W Floyd, Vaughan Pratt,
Ronald L Rivest, and Robert E Tarjan. 1973. Timebounds for selection. Journal of Computer and System Sciences, 7(4):448–461.
J. Carbonell and J. Goldstein. 1998. The use of MMR,
diversity-based reranking for reordering documents
and producing summaries. In SIGIR.
Y.-W. Chang and M. Collins. 2011. Exact decoding ofphrase-based translation models through lagrangian
relaxation. In Proc. of Empirical Methods for Natural Language Processing.
James Clarke and Mirella Lapata. 2007. Modellingcompression with discourse constraints. In Proc. of
Empirical Methods in Natural Language Processing.
J. Clarke and M. Lapata. 2008. Global Inference for
Sentence Compression An Integer Linear Program-ming Approach. Journal of Artificial Intelligence
Research, 31:399–429.
T. Cohn and M. Lapata. 2008. Sentence compression
beyond word deletion. In Proc. COLING.
D. Das, A. F. T. Martins, and N. A. Smith. 2012. An
Exact Dual Decomposition Algorithm for Shallow
Semantic Parsing with Constraints. In Proc. of First
Joint Conference on Lexical and Computational Semantics (*SEM).
H. Daumé. 2006. Practical Structured Learning Techniques for Natural Language Processing. Ph.D. thesis, University of Southern California.
H. Daumé. 2007. Frustratingly easy domain adaptation. In Proc. of Annual Meeting of the Association
for Computational Linguistics.
H. P. Edmundson. 1969. New methods in automatic
extracting. Journal of the ACM, 16(2):264–285.
T. Evgeniou and M. Pontil. 2004. Regularized multi–
task learning. In Proc. of ACM SIGKDD International Conference on Knowledge Discovery andData Mining, pages 109–117. ACM.
Elena Filatova and Vasileios Hatzivassiloglou. 2004.
A formal model for information selection in multisentence text extraction. In Proc. of International
Conference on Computational Linguistics.
J.R. Finkel and C.D. Manning. 2010. Hierarchicaljoint learning: Improving joint parsing and namedentity recognition with non-jointly labeled data. In
Proc. of Annual Meeting of the Association for Computational Linguistics.
J. Gillenwater, A. Kulesza, and B. Taskar. 2012. Discovering diverse and salient threads in document
collections. In Proc. of Empirical Methods in Natural Language Processing.
Dan Gillick, Benoit Favre, and Dilek Hakkani-Tur.
2008. The icsi summarization system at tac 2008.
In Proc. of Text Understanding Conference.
K. Knight and D. Marcu. 2000. Statistics-basedsummarization—step one: Sentence compression.
In AAAI/IAAI.
N. Komodakis, N. Paragios, and G. Tziritas. 2007.
MRF optimization via dual decomposition:
Message-passing revisited. In Proc. of International
Conference on Computer Vision.

H. Lin and J. Bilmes. 2012. Learning mixtures of submodular shells with application to document summarization. In Proc. of Uncertainty in Artificial Intelligence.
C.-Y. Lin. 2003. Improving summarization performance by sentence compression-a pilot study. In theInt. Workshop on Inf. Ret. with Asian Languages.
Chin-Yew Lin. 2004. Rouge: A package for automatic evaluation of summaries. In Stan Szpakowicz
Marie-Francine Moens, editor, Text Summarization
Branches Out: Proceedings of the ACL-04 Workshop, pages 74–81, Barcelona, Spain, July.
H. P. Luhn. 1958. The automatic creation of literature
abstracts. IBM Journal of Research Development,2(2):159–165.
A. F. T. Martins and N. A. Smith. 2009. Summarization with a Joint Model for Sentence Extraction andCompression. In North American Chapter of the Association for Computational Linguistics: Workshop
on Integer Linear Programming for NLP.
A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar,
N. A. Smith, and E. P. Xing. 2011a. An Augmented Lagrangian Approach to Constrained MAP
Inference. In Proc. of International Conference on
Machine Learning.
A. F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and
M. A. T. Figueiredo. 2011b. Dual Decomposition
with Many Overlapping Components. In Proc. of
Empirical Methods for Natural Language Processing.
Andre F. T. Martins, Mario A. T. Figueiredo, Pedro
M. Q. Aguiar, Noah A. Smith, and Eric P. Xing.
2012. Alternating Directions Dual Decomposition.
Arxiv preprint arXiv:1212.6550.
R. McDonald. 2006. Discriminative sentence compression with soft syntactic constraints. In Proc. ofAnnual Meeting of the European Chapter of the Association for Computational Linguistics.
R. McDonald. 2007. A study of global inference algorithms in multi-document summarization. In ECIR.
A. Nenkova and R. Passonneau. 2004. Evaluating
content selection in summarization: The pyramidmethod. In Proceedings of NAACL, pages 145–152.

J. Kupiec, J. Pedersen, and F. Chen. 1995. A trainable
document summarizer. In SIGIR.

Panos M. Pardalos and Naina Kovoor. 1990. An algorithm for a singly constrained class of quadratic
programs subject to upper and lower bounds. Mathematical Programming, 46(1):321–328.

H. Lin and J. Bilmes. 2010. Multi-document summarization via budgeted maximization of submodular
functions. In Proc. of Annual Meeting of the North
American chapter of the Association for Computational Linguistics.

D. R. Radev, H. Jing, and M. Budzikowska. 2000.
Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation,and user studies. In the NAACL-ANLP Workshop on
Automatic Summarization.

A.M. Rush and M. Collins. 2012. A Tutorial on Dual
Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing. Journal of
Artificial Intelligence Research, 45:305–362.
A. Rush, D. Sontag, M. Collins, and T. Jaakkola. 2010.
On dual decomposition and linear programming relaxations for natural language processing. In Proc.
of Empirical Methods for Natural Language Processing.
Frank Schilder and Ravikumar Kondadadi. 2008. Fastsum: Fast and accurate query-based multi-document
summarization. In Proc. of Annual Meeting of the
Association for Computational Linguistics.
R. Sipos, P. Shivaswamy, and T. Joachims. 2012.
Large-margin learning of submodular summarization models.
B. Taskar, C. Guestrin, and D. Koller. 2003. Maxmargin Markov networks. In Proc. of Neural Information Processing Systems.
B. Taskar, V. Chatalbashev, and D. Koller. 2004.
Learning associative Markov networks. In Proc. ofInternational Conference of Machine Learning.
I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. 2004. Support vector machine learning for interdependent and structured output spaces. In Proc.
of International Conference of Machine Learning.
K. Woodsend and M. Lapata. 2010. Automatic generation of story highlights. In Proc. of Annual Meeting of the Association for Computational Linguistics, pages 565–574.
Kristian Woodsend and Mirella Lapata. 2011. Learning to simplify sentences with quasi-synchronous
grammar and integer programming. In Proc. of Empirical Methods in Natural Language Processing.
Kristian Woodsend and Mirella Lapata. 2012. Multiple aspect summarization using integer linear programming. In Proc. of Empirical Methods in Natural Language Processing.
Wen-tau Yih, Joshua Goodman, Lucy Vanderwende,and Hisami Suzuki. 2007. Multi-document summarization by maximizing informative content-words.
In Proc. of International Joint Conference on Artifical Intelligence.
D. Zajic, B. Dorr, J. Lin, and R. Schwartz. 2006.
Sentence compression as a component of a multidocument summarization system. In the ACL DUC
Workshop.