Approximation Strategies for Multi-Structure Sentence Compression

We begin with some notation. For an input sentence $S$ comprised of $n$ tokens including duplicates, we denote the set of tokens in $S$ by $T\triangleq \left\{t_i:1\le i\le n\right\}$. Let $C$ represent a compression of $S$ and let $x_i\in \left\{0,1\right\}$ denote an indicator variable whose value corresponds to whether token $t_i\in T$ is present in the compressed sentence $C$. In addition, we define bigram indicator variables $y_{ij}\in \left\{0,1\right\}$ to represent whether a particular order-preserving bigram²²Although Thadani and McKeown (2013) is not restricted to bigrams or order-preserving n-grams, we limit our discussion to this scenario as it also fits the assumptions of McDonald (2006) and the datasets of Clarke and Lapata (2006). $⟨t_i,t_j⟩$ from $S$ is present as a contiguous bigram in $C$ as well as dependency indicator variables $z_{ij}\in \left\{0,1\right\}$ corresponding to whether the dependency arc $t_i\to t_j$ is present in the dependency parse of $C$. The score for a given compression $C$ can now be defined to factor over its tokens, n-grams and dependencies as follows.

where ${\theta }_{\text{tok}}$, ${\theta }_{\text{bgr}}$ and ${\theta }_{\text{dep}}$ are feature-based scoring functions for tokens, bigrams and dependencies respectively. Specifically, each ${\theta }_v(\cdot )\equiv {𝐰}_v^{\top }{\mathit{\varphi }}_v(\cdot )$ where ${\mathit{\varphi }}_v(\cdot )$ is a feature map for a given variable type $v\in \left\{\text{tok, bgr, dep}\right\}$ and ${𝐰}_v$ is the corresponding vector of learned parameters.

The inference task involves recovering the highest scoring compression $C^{*}$ under a particular set of model parameters $𝐰$.

where the incidence vector $𝐱\triangleq {⟨x_i⟩}_{t_i\in T}$ represents an entire token configuration over $T$, with $𝐲$ and $𝐳$ defined analogously to represent configurations of bigrams and dependencies. ${𝜽}_v\triangleq ⟨{\theta }_v(\cdot )⟩$ denotes a corresponding vector of scores for each variable type $v$ under the current model parameters. In order to recover meaningful compressions by optimizing (2), the inference step must ensure:

1. 1.

   The configurations $𝐱$, $𝐲$ and $𝐳$ are consistent with each other, i.e., all configurations cover the same tokens.

2. 2.

   The structural configurations $𝐲$ and $𝐳$ are non-degenerate, i.e, the bigram configuration $𝐲$ represents an acyclic path while the dependency configuration $𝐳$ forms a tree.

These requirements naturally rule out simple approximate inference formulations such as search-based approaches for the joint objective.³³This work follows Thadani and McKeown (2013) in recovering non-projective trees for inference. However, recovering projective trees is tractable when a total ordering of output tokens is assumed. This will be addressed in future work. An ILP-based inference solution is demonstrated in Thadani and McKeown (2013) that makes use of linear constraints over the boolean variables $x_i$, $y_{ij}$ and $z_{ij}$ to guarantee consistency, as well as auxiliary real-valued variables and constraints representing the flow of commodities [31] in order to establish structure in $𝐲$ and $𝐳$. In the following section, we propose an alternative formulation that exploits the modularity of this joint objective.

Dual decomposition [26] and Lagrangian relaxation in general are often used for solving joint inference problems which are decomposable into individual subproblems linked by equality constraints [27, 44, 43, 13, 32, 11, 1]. This approach permits sub-problems to be solved separately using problem-specific efficient algorithms, while consistency over the structures produced is enforced through Lagrange multipliers via iterative optimization. Exact solutions are guaranteed when the algorithm converges on a consistent primal solution, although this convergence itself is not guaranteed and depends on the tightness of the underlying LP relaxation. The primary advantage of this technique is the ability to leverage the underlying structure of the problems in inference rather than relying on a generic ILP formulation while still often producing exact solutions.

The multi-structure inference problem described in the previous section seems in many ways to be a natural fit to such an approach since output scores factor over different types of structure that comprise the output compression. Even if ILP-based approaches perform reasonably at the scale of single-sentence compression problems, the exponential worst-case complexity of general-purpose ILPs will inevitably pose challenges when scaling up to (a) handle larger inputs, (b) use higher-order structural fragments, or (c) incorporate additional models.

Consider once more the optimization problem characterized by (2) The two structural problems that need to be solved in this formulation are the extraction of a maximum-weight acyclic subsequence of bigrams $𝐲$ from the lattice of all order-preserving bigrams from $S$ and the recovery of a maximum-weight directed subtree $𝐳$. Let $𝜶\left(𝐲\right)\in {\left\{0,1\right\}}^n$ denote the incidence vector of tokens contained in the n-gram sequence $𝐲$ and $𝜷\left(𝐳\right)\in {\left\{0,1\right\}}^n$ denote the incidence vector of words contained in the dependency tree $𝐳$. We can now rewrite the objective in (2) while enforcing the constraint that the words contained in the sequence $𝐲$ are the same as the words contained in the tree $𝐳$, i.e., $𝜶\left(𝐲\right)=𝜷\left(𝐳\right)$, by introducing a vector of Lagrange multipliers $𝝀\in {ℝ}^n$. In addition, the token configuration $𝐱$ can be rewritten in the form of a weighted combination of $𝜶\left(𝐲\right)$ and $𝜷\left(𝐳\right)$ to ensure its consistency with $𝐲$ and $𝐳$. This results in the following Lagrangian:

Finding the $𝐲$ and $𝐳$ that maximize this Lagrangian above yields a dual objective, and the dual problem corresponding to the primal objective specified in (2) is therefore the minimization of this objective over the Lagrange multipliers $𝝀$.

This can now be solved with the iterative subgradient algorithm illustrated in Algorithm 2.2. In each iteration $i$, the algorithm solves for ${𝐲}^{\left(i\right)}$ and ${𝐳}^{\left(i\right)}$ under ${𝝀}^{\left(i\right)}$, then generates ${𝝀}^{\left(i+1\right)}$ to penalize inconsistencies between $𝜶\left({𝐲}^{\left(i\right)}\right)$ and $𝜷\left({𝐳}^{\left(i\right)}\right)$. When $𝜶\left({𝐲}^{\left(i\right)}\right)=𝜷\left({𝐳}^{\left(i\right)}\right)$, the resulting primal solution is exact, i.e., ${𝐲}^{\left(i\right)}$ and ${𝐳}^{\left(i\right)}$ represent the optimal structures under (2). Otherwise, if the algorithm starts oscillating between a few primal solutions, the underlying LP must have a non-integral solution in which case approximation heuristics can be employed.⁴⁴ Heuristic approaches [26, 44], tightening [43] or branch and bound [11] can still be used to retrieve optimal solutions, but we did not explore these strategies here. The application of this Lagrangian relaxation strategy is contingent upon the existence of algorithms to solve the maximization subproblems for $f\left(𝐲,𝝀,\psi ,𝜽\right)$ and $g\left(𝐳,𝝀,\psi ,𝜽\right)$. The following sections discuss our approach to these problems.

[t] Subgradient-based joint inference {algorithmic}[1] \StatexInput: scores $𝜽$, ratio $\psi$, repetition limit $l_{\text{max}}$, iteration limit $i_{\text{max}}$, learning rate schedule $𝜼$ \StatexOutput: token configuration $𝐱$ \Statex\State${𝝀}^{\left(0\right)}\leftarrow {⟨0⟩}^n$ \State$M\leftarrow \mathrm{\varnothing },M_{\text{repeats}}\leftarrow \mathrm{\varnothing }$ \Foriteration \State$\widehat{𝐲}\leftarrow {\arg \max }_{𝐲}f\left(𝐲,𝝀,\psi ,𝜽\right)$ \State$\widehat{𝐳}\leftarrow {\arg \max }_{𝐳}g\left(𝐳,𝝀,\psi ,𝜽\right)$ \If$𝜶\left(\widehat{𝐲}\right)=𝜷\left(\widehat{𝐳}\right)$ \Return$𝜶\left(\widehat{𝐲}\right)$ \EndIf\If$𝜶\left(\widehat{𝐲}\right)\in M$ \State$M_{\text{repeats}}\leftarrow M_{\text{repeats}}\cup \left\{𝜶\left(\widehat{𝐲}\right)\right\}$ \EndIf\If$𝜷\left(\widehat{𝐳}\right)\in M$ \State$M_{\text{repeats}}\leftarrow M_{\text{repeats}}\cup \left\{𝜷\left(\widehat{𝐳}\right)\right\}$ \EndIf\Stateif $\left|M_{\text{repeats}}\right|\ge l_{\text{max}}$ then break \State$M\leftarrow M\cup \left\{𝜶\left(\widehat{𝐲}\right),𝜷\left(\widehat{𝐳}\right)\right\}$ \State${𝝀}^{\left(i+1\right)}\leftarrow {𝝀}^{\left(i\right)}-{\eta }_i\left(𝜶\left(\widehat{𝐲}\right)-𝜷\left(\widehat{𝐳}\right)\right)$ \EndFor\Return${\arg \max }_{𝐱\in {𝐌}_{\text{repeats}}}score\left(𝐱\right)$

McDonald (2006) provides a Viterbi-like dynamic programming algorithm to recover the highest-scoring sequence of order-preserving bigrams from a lattice, either in unconstrained form or with a specific length constraint. The latter requires a dynamic programming table $Q\left[i\right]\left[r\right]$ which represents the best score for a compression of length $r$ ending at token $i$. The table can be populated using the following recurrence:

where $R$ is the required number of output tokens and the scoring function is defined as

so as to solve $f\left(𝐲,𝝀,\psi ,𝜽\right)$ from (4). This approach requires $O\left(n^{2}R\right)$ time in order to identify the highest scoring sequence $𝐲$ and corresponding token configuration $𝜶\left(𝐲\right)$.

The maximum-weight non-projective subtree problem over general graphs is not as easily solved. Although the maximum spanning tree for a given token configuration can be recovered efficiently, Figure 1 illustrates that the maximum-scoring subtree is not necessarily found within it. The problem of recovering a maximum-weight subtree in a graph has been shown to be NP-hard even with uniform edge weights [29].

In order to produce a solution to this subproblem, we use an LP relaxation of the relevant portion of the ILP from Thadani and McKeown (2013) by omitting integer constraints over the token and dependency variables in $𝐱$ and $𝐳$ respectively. For simplicity, however, we describe the ILP version rather than the relaxed LP in order to motivate the constraints with their intended purpose rather than their effect in the relaxed problem. The objective for this LP is given by

where the vector of token scores is redefined as

in order to solve $g\left(𝐳,𝝀,\psi ,𝜽\right)$ from (4).

Linear constraints are introduced to produce dependency structures that are close to the optimal dependency trees. First, tokens in the solution must only be active if they have a single active incoming dependency edge. In addition, to avoid producing multiple disconnected subtrees, only one dependency is permitted to attach to the root pseudo-token.

In order to avoid cycles in the dependency tree, we include additional variables to establish single-commodity flow [31] between all pairs of tokens. These ${\gamma }_{ij}$ variables carry non-negative real values which must be consumed by active tokens that they are incident to.

These constraints ensure that cyclic structures are not possible in the non-relaxed ILP. In addition, they serve to establish connectivity for the dependency structure $𝐳$ since commodity can only originate in one location—at the pseudo-token root which has no incoming commodity variables. However, in order to enforce these properties on the output dependency structure, this acyclic, connected commodity structure must constrain the activation of the $z$ variables.

where $C_{\text{max}}$ is an arbitrary upper bound on the value of ${\gamma }_{ij}$ variables. Figure 2 illustrates how these commodity flow variables constrain the output of the ILP to be a tree. However, the effect of these constraints is diminished when solving an LP relaxation of the above problem.

In the LP relaxation, $x_i$ and $z_{ij}$ are redefined as real-valued variables in $\left[0,1\right]$, potentially resulting in fractional values for dependency and token indicators. As a result, the commodity flow network is able to establish connectivity but cannot enforce a tree structure, for instance, directed acyclic structures are possible and token indicators $x_i$ may be partially be assigned to the solution structure. This poses a challenge in implementing $𝜷\left(𝐳\right)$ which is needed to recover a token configuration from the solution of this subproblem.

We propose two alternative solutions to address this issue in the context of the joint inference strategy. The first is to simply use the relaxed token configuration identified by the LP in Algorithm 2.2, i.e., to set $𝜷\left(\widetilde{𝐳}\right)=\tilde{x}$ where $\widetilde{𝐱}$ and $\widetilde{𝐳}$ represent the real-valued counterparts of the incidence vectors $𝐱$ and $𝐳$. The viability of this approximation strategy is due to the following:

• •

  The relaxed LP is empirically fairly tight, yielding integral solutions 89% of the time on the compression datasets described in §3.

• •

  The bigram subproblem is guaranteed to return a well-formed integral solution which obeys the imposed compression rate, so we are assured of a source of valid—if non-optimal—solutions in line 13 of Algorithm 2.2.

We also consider another strategy that attempts to approximate a valid integral solution to the dependency subproblem. In order to do this, we first include an additional constraint in the relaxed LP which restrict the number of tokens in the output to a specific number of tokens $R$ that is given by an input compression rate.

The addition of this constraint to the relaxed LP reduces the rate of integral solutions drastically—from 89% to approximately 33%—but it serves to ensure that the resulting token configuration $\widetilde{𝐱}$ has at least as many non-zero elements as $R$, i.e., there are at least as many tokens activated in the LP solution as are required in a valid solution.

We then construct a subgraph $G\left(\widetilde{𝐳}\right)$ consisting of all dependency edges that were assigned non-zero values in the solution, assigning to each edge a score equal to the score of that edge in the LP as well as the score of its dependent word, i.e., each $z_{ij}$ in $G\left(\widetilde{𝐳}\right)$ is assigned a score of ${\theta }_{\text{dep}}\left(⟨t_i,t_j⟩\right)-{\lambda }_j+\left(1-\psi \right)\cdot {\theta }_{\text{tok}}\left(t_j\right)$. Since the commodity flow constraints in (9)–(11) ensure a connected $\widetilde{𝐳}$, it is therefore possible to recover a maximum-weight spanning tree from $G\left(\widetilde{𝐳}\right)$ using the Chu-Liu Edmonds algorithm [4, 14].⁵⁵ A detailed description of the Chu-Liu Edmonds algorithm for MSTs is available in McDonald et al. (2005). Although the runtime of this algorithm is cubic in the size of the input graph, it is fairly speedy when applied on relatively sparse graphs such as the solutions to the LP described above. The resulting spanning tree is a useful integral approximation of $\widetilde{𝐳}$ but, as mentioned previously, may contain more nodes than $R$ due to fractional values in $\widetilde{𝐱}$; we therefore repeatedly prune leaves with the lowest incoming edge weight in the current tree until exactly $R$ nodes remain. The resulting tree is assumed to be a reasonable approximation of the optimal integral solution to this LP.

The Chu-Liu Edmonds algorithm is also employed for another purpose: when the underlying LP for the joint inference problem is not tight—a frequent occurrence in our compression experiments—Algorithm 2.2 will not converge on a single primal solution and will instead oscillate between solutions that are close to the dual optimum. We identify this phenomenon by counting repeated solutions and, if they exceed some threshold $l_{\text{max}}$ with at least one repeated solution from either subproblem, we terminate the update procedure for Lagrange multipliers and instead attempt to identify a good solution from the repeating ones by scoring them under (2). It is straightforward to recover and score a bigram configuration $𝐲$ from a token configuration $𝜷\left(𝐳\right)$. However, scoring solutions produced by the dynamic program from §2.3 also requires the score over a corresponding parse tree; this can be recovered by constructing a dependency subgraph containing across only the tokens that are active in $𝜶\left(𝐲\right)$ and retrieving the maximum spanning tree for that subgraph using the Chu-Liu Edmonds algorithm.

The features used in this work are largely based on the features from Thadani and McKeown (2013).

• •

  ${\mathit{\varphi }}_{\text{tok}}$ contains features for part-of-speech (POS) tag sequences of length up to 3 around the token, features for the dependency label of the token conjoined with its POS, lexical features for verb stems and non-word symbols and morphological features that identify capitalized sequences, negations and words in parentheses.

• •

  ${\mathit{\varphi }}_{\text{bgr}}$ contains features for POS patterns in a bigram, the labels of dependency edges incident to it, its likelihood under a Gigaword language model (LM) and an indicator for whether it is present in the input sentence.

• •

  ${\mathit{\varphi }}_{\text{dep}}$ contains features for the probability of a dependency edge under a smoothed dependency grammar constructed from the Penn Treebank and various conjunctions of the following features: (a) whether the edge appears as a dependency or ancestral relation in the input parse (b) the directionality of the dependency (c) the label of the edge (d) the POS tags of the tokens incident to the edge and (e) the labels of their surrounding chunks and whether the edge remains within the chunk.

For the experiments in the following section, we trained models using a variant of the structured perceptron [10] which incorporates minibatches [50] for easy parallelization and faster convergence.⁶⁶ We used a minibatch size of 4 in all experiments. Overfitting was avoided by averaging parameters and monitoring performance against a held-out development set during training. All models were trained using variants of the ILP-based inference approach of Thadani and McKeown (2013). We followed Martins et al. (2009) in using LP-relaxed inference during learning, assuming algorithmic separability [28] for these problems.

We report results over the following systems grouped into three categories of models: tokens + n-grams, tokens + dependencies, and joint models.

• •

  3-LM: A reimplementation of the unsupervised ILP of Clarke and Lapata (2008) which infers order-preserving trigram variables parameterized with log-likelihood under an LM and a significance score for token variables inspired by Hori and Furui (2004), as well as various linguistically-motivated constraints to encourage fluency in output compressions.

• •

  DP: The bigram-based dynamic program of McDonald (2006) described in §2.3.⁹⁹For consistent comparisons with the other systems, our reimplementation does not include the $k$-best inference strategy presented in McDonald (2006) for learning with MIRA.

• •

  LP$\mathrm{\to }$MST: An approximate inference approach based on an LP relaxation of ILP-Dep. As discussed in §2.4, a maximum spanning tree is recovered from the output of the LP and greedily pruned in order to generate a valid integral solution while observing the imposed compression rate.

• •

  ILP-Dep: A version of the joint ILP of Thadani and McKeown (2013) without n-gram variables and corresponding features.

• •

  DP+LP$\mathrm{\to }$MST: An approximate joint inference approach based on Lagrangian relaxation that uses DP for the maximum weight subsequence problem and LP$\mathrm{\to }$MST for the maximum weight subtree problem.

• •

  DP+LP: Another Lagrangian relaxation approach that pairs DP with the non-integral solutions from an LP relaxation of the maximum weight subtree problem (cf. §2.4).

• •

  ILP-Joint: The full ILP from Thadani and McKeown (2013), which provides an upper bound on the performance of the proposed approximation strategies.

The learning rate schedule for the Lagrangian relaxation approaches was set as ${\eta }_i\triangleq \tau /\left(\tau +i\right)$,¹⁰¹⁰ $\tau$ was set to $100$ for aggressive subgradient updates. while the hyperparameter $\psi$ was tuned using the development split of each corpus.¹¹¹¹We were surprised to observe that performance improved significantly when $\psi$ was set closer to 1, thereby emphasizing token features in the dependency subproblem. The final values chosen were ${\psi }_{\text{BN}}=0.9$ and ${\psi }_{\text{NW}}=0.8$.

Tables 1 and 2 summarize the results from our compression experiments on the BN and NW corpora respectively. Starting with the n-gram approaches, the performance of 3-LM leads us to observe that the gains of supervised learning far outweigh the utility of higher-order n-gram factorization, which is also responsible for a significant increase in wall-clock time. In contrast, DP is an order of magnitude faster than all other approaches studied here although it is not competitive under parse-based measures such as RASP F${}_1\mathrm{\%}$ which is known to correlate with human judgments of grammaticality [5].

We were surprised by the strong performance of the dependency-based inference techniques, which yielded results that approached the joint model in both n-gram and parse-based measures. The exact ILP-Dep approach halves the runtime of ILP-Joint to produce compressions that have similar (although statistically distinguishable) scores. Approximating dependency-based inference with LP$\mathrm{\to }$MST yields similar performance for a further halving of runtime; however, the performance of this approach is notably worse.

Turning to the joint approaches, the strong performance of ILP-Joint is expected; less so is the relatively high but yet practically reasonable runtime that it requires. We note, however, that these ILPs are solved using a highly-optimized commercial-grade solver that can utilize all CPU cores¹²¹²16 cores in our experimental environment. while our approximation approaches are implemented as single-processed Python code without significant effort toward optimization. Comparing the two approximation strategies shows a clear performance advantage for DP+LP over DP+LP$\mathrm{\to }$MST: the latter approach entails slower inference due to the overhead of running the Chu-Liu Edmonds algorithm at every dual update, and furthermore, the error introduced by approximating an integral solution results in a significant decrease in dependency recall. In contrast, DP+LP directly optimizes the dual problem by using the relaxed dependency solution to update Lagrange multipliers and achieves the best performance on parse-based F${}_1$ outside of the slower ILP approaches. Convergence rates also vary for these two techniques: DP+LP has a lower rate of empirical convergence (15% on BN and 4% on NW) when compared to DP+LP$\mathrm{\to }$MST (19% on BN and 6% on NW).

Figure 3 shows the effect of input sentence length on inference time and performance for ILP-Joint and DP+LP over the NW test corpus.¹³¹³Similar results were observed for the BN test corpus. The timing results reveal that the approximation strategy is consistently faster than the ILP solver. The variation in RASP F${}_1$% with input size indicates the viability of a hybrid approach which could balance accuracy and speed by using ILP-Joint for smaller problems and DP+LP for larger ones.