emnlp emnlp2013 emnlp2013-65 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chen Li ; Fei Liu ; Fuliang Weng ; Yang Liu
Abstract: Joint compression and summarization has been used recently to generate high quality summaries. However, such word-based joint optimization is computationally expensive. In this paper we adopt the ‘sentence compression + sentence selection’ pipeline approach for compressive summarization, but propose to perform summary guided compression, rather than generic sentence-based compression. To create an annotated corpus, the human annotators were asked to compress sentences while explicitly given the important summary words in the sentences. Using this corpus, we train a supervised sentence compression model using a set of word-, syntax-, and documentlevel features. During summarization, we use multiple compressed sentences in the integer linear programming framework to select . salient summary sentences. Our results on the TAC 2008 and 2011 summarization data sets show that by incorporating the guided sentence compression model, our summarization system can yield significant performance gain as compared to the state-of-the-art.
Reference: text
sentIndex sentText sentNum sentScore
1 hle inul , fyualn igaln@gh Abstract Joint compression and summarization has been used recently to generate high quality summaries. [sent-4, score-1.081]
2 In this paper we adopt the ‘sentence compression + sentence selection’ pipeline approach for compressive summarization, but propose to perform summary guided compression, rather than generic sentence-based compression. [sent-6, score-1.41]
3 Using this corpus, we train a supervised sentence compression model using a set of word-, syntax-, and documentlevel features. [sent-8, score-0.935]
4 Our results on the TAC 2008 and 2011 summarization data sets show that by incorporating the guided sentence compression model, our summarization system can yield significant performance gain as compared to the state-of-the-art. [sent-11, score-1.703]
5 1 Introduction Automatic summarization can be broadly divided into two categories: extractive and abstractive summarization. [sent-12, score-0.451]
6 Extractive summarization focuses on selecting the salient sentences from the document collection and concatenating them to form a summary; while abstractive summarization is generally considered more difficult, involving sophisticated techniques for meaning representation, content planlwte. [sent-13, score-0.76]
7 , and the “true abstractive summarization remains a researcher’s dream” (Radev et al. [sent-17, score-0.358]
8 These compressive summaries often contain more information than sentence-based extractive summaries since they can remove insignificant sentence constituents and make space for more salient information that is otherwise dropped due to the summary length constraint. [sent-20, score-0.555]
9 One is a pipeline approach, where sentence-based extractive summarization is followed or proceeded by sentence compression (Knight and Marcu, 2000; Lin, 2003; Zajic et al. [sent-22, score-1.332]
10 Another line of work uses joint compression and summarization. [sent-25, score-0.818]
11 One popular approach for such joint compression and summarization is via integer linear programming (ILP). [sent-28, score-1.186]
12 In this study, we use the pipeline compression and summarization method because of its computational efficiency. [sent-30, score-1.127]
13 Prior work using such pipeline methods simply uses generic sentence-based com- pression for each sentence in the documents, no matter whether compression is done before or after summary sentence extraction. [sent-31, score-1.245]
14 hc o2d0s1 i3n A Nsastoucria lti Loan fgoura Cgoem Ppruotcaetsiosin agl, L piang eusis 4t9ic0s–50 , mary guided compression combined with ILP-based sentence selection for summarization in this paper. [sent-34, score-1.441]
15 We expect such “guided” sentence compression is beneficial for the pipeline compression and summarization task. [sent-38, score-2.02]
16 In addition, previous research on joint modeling for compression and summarization suggested that the labeled extraction and compression data sets would be helpful for learning a better joint model (Daum ´e, 2006; Martins and Smith, 2009). [sent-39, score-1.935]
17 We hope that our work on this guided compression will also be of benefit to the future joint modeling studies. [sent-40, score-1.038]
18 Using our created compression data, we train a supervised compression model using a variety of word-, sentence-, and document-level features. [sent-41, score-1.636]
19 During summarization, we generate multiple compression candidates for each sentence, and use the ILP framework to select compressed summary sentences. [sent-42, score-1.063]
20 In addition, we also propose to apply a preselection step to select some important sentences, which can both speed up the summarization system and improve performance. [sent-43, score-0.366]
21 Our results show that by incorporating a guided sentence compression model, our summarization system can yield significant performance gain as compared to the state-of-the-art reported results. [sent-45, score-1.419]
22 Compared to the abstractive counterpart, extractive summarization has received considerable attention due to its clear problem formulation to extract a set of salient and non-redundant sentences from the given document set. [sent-47, score-0.585]
23 The extractive summary sentence selection problem can also be formulated in an optimization framework. [sent-52, score-0.35]
24 Compressive summarization receives increasing attention in recent years, since it offers a viable step towards abstractive summarization. [sent-60, score-0.376]
25 The compressed summaries can be generated through a joint model of the sentence selection and compression processes, or through a pipeline approach that integrates a generic sentence compression model with a summary sentence pre-selection or post-selection step. [sent-61, score-2.33]
26 Many studies explore the joint sentence compression and selection setting. [sent-62, score-0.977]
27 Martins and Smith (2009) jointly perform sentence extraction and compression by solving an ILP problem; Berg-Kirkpatrick et al. [sent-63, score-0.908]
28 (2012) incorporate semantic role information in the ILP model; Chali and Hasan (2012) investigate three strategies in compressive summarization: compression before extraction, after extraction, or joint compression and extraction in one global optimization framework. [sent-67, score-1.702]
29 Qian and Liu (2013) propose a graph-cut based method that improves the speed of joint compression and summarization. [sent-69, score-0.818]
30 The pipeline approach, where sentence-based extractive summarization is followed or proceeded by sentence compression, is also popular. [sent-70, score-0.535]
31 Knight and Marcu (2000) utilize the noisy channel and decision tree method to perform sentence compression; Lin (2003) shows that pure syntactic-based compression may not improve the system performance; Zajic et al. [sent-71, score-0.915]
32 (2013) design a series of learning-based compression models built on parse trees, and integrate them in query-focused multi-document summarization. [sent-73, score-0.797]
33 Prior studies often rely heavily on the generic sentence compression approaches (McDonald, 2006; Nomoto, 2007; Clarke and Lapata, 2008; Thadani and McKeown, 2013) for compressing the sentences in the documents, yet a generic compression system may not be the best fit for the summarization purpose. [sent-74, score-2.203]
34 In this paper, we adopt the pipeline-based compressive summarization framework, but propose a novel guided compression method that is catered to the summarization task. [sent-75, score-1.657]
35 We train a supervised guided compression model to produce n-best compressions for each sentence, and use an ILP formulation to select the best set of summary sentences. [sent-77, score-1.394]
36 3 Guided Compression Corpus The goal of guided sentence compression is to create compressed sentences that are grammatically correct and contain the important information that we would like to preserve in the final summary. [sent-79, score-1.252]
37 Following the compression literature (Clarke and Lapata, 2008), the compression task is defined as a word 492 hTORoehruiengre sinart asflet eSnareskniat wdewna. [sent-80, score-1.594]
38 deletion problem, that is, the human annotators (and also automatic compression systems) are allowed to only remove words from the original sentence to form a compression. [sent-82, score-0.935]
39 The key difference between our proposed guided compression with generic sentence compression is that, we provide guidance to the human compression process by specifying a set of “important words” that we wish to keep for each sentence. [sent-83, score-2.808]
40 We expect this kind of summary oriented compression would benefit the ultimate summarization task. [sent-84, score-1.198]
41 For generic sentence compression, there may be multiple ‘good’ human compressions for this sentence, such as those listed in the table. [sent-86, score-0.358]
42 Without guidance, a human annotator (or automatic system) is likely to use option A or B; however, if “18 hours” appears in the summary, then we want to provide this guidance in the compression process, hence option C may be the best compression choice. [sent-87, score-1.633]
43 This guided compression therefore avoids removing the salient words that are important to the final summary. [sent-88, score-1.059]
44 To generate the guided compression corpus, we use the TAC 2010 data set1 that was used for the multi-document summarization task. [sent-89, score-1.301]
45 Since annotating all the sentences in this data set is time consuming and some sentences are not very important for the summarization task, we choose a set of sentences that are highly related to the human abstracts for annotation. [sent-92, score-0.447]
46 A sentence was compressed by 3 human annotatorsand we select the shortest candidate as the goldstandard compression for each sentence. [sent-108, score-1.046]
47 For our compression corpus, which contains 1,150 sentences and their guided compressions, the average compression rate, as measured by the percentage of dropped words, is about 50%. [sent-113, score-1.871]
48 This com- pression ratio is higher compared to other generic sentence compression corpora, in which the word deletion rate ranges from 24% to 34% depending on different text genres and annotation guidelines (Clarke and Lapata, 2008; Liu and Liu, 2009). [sent-114, score-1.005]
49 4 Summarization System Our summarization system consists of three key components: we train a supervised guided compression model using our created compression data, with a variety of features. [sent-116, score-2.162]
50 then we use this model to generate n-best compressions for each sentence; we feed the multiple compressed sentences to the ILP framework to select the best summary sentences. [sent-117, score-0.458]
51 In addition, we propose a sentence pre-selection step that can both speed up the summarization system and improve the performance. [sent-118, score-0.42]
52 In this paper, we employ the CRF-based compression approach due to its proved performance and its flexibility to integrate different levels of discriminative features. [sent-121, score-0.812]
53 Under this framework, sentence compression is formulated as a sequence labeling problem, where each word is labeled as either “0” (retained) or “1” (removed). [sent-122, score-0.893]
54 Some of the above features were employed in related sentence compression studies (Nomoto, 2007; Liu and Liu, 2013). [sent-147, score-0.912]
55 During summarization, we apply the model to a given sentence to generate its n-best guided compressions and use them in the following summarization step. [sent-151, score-0.784]
56 2 Summary Sentence Selection The sentence selection process is similar to the standard sentence-based extractive summarization, except that the input to the selection module is a list of compressed sentences in our work. [sent-153, score-0.44]
57 Many extractive summarization approaches can be applied for this purpose. [sent-154, score-0.377]
58 First, since we use multiple compressions for one sentence, we need to introduce an additional constraint: for each sentence, only one of the n-best compressions may be included in the summary. [sent-163, score-0.368]
59 (2) represents our additional constraint, which requires that for each sentence j,only one candidate compression will be chosen. [sent-170, score-0.913]
60 This kind of selection step has been used in previous ILP-based summarization systems (Berg-Kirkpatrick et al. [sent-180, score-0.346]
61 To train the SVR model, the target value for each sentence is the ROUGE-2 score between the sentence and the four human abstracts (this same value is used for sentence selection in corpus annotation (Section 3)). [sent-185, score-0.391]
62 Using this model, we can predict a salience score (Vj in Eq 1) for each sentence and only select the top n sentences and supply them to the compression and summarization steps. [sent-189, score-1.272]
63 In particular, we used the TAC 2010 data set for creating the guided compression corpus and training the SVR pre-selection model, the TAC 2009 data set as development set for parameter tuning, and the TAC 2008 and 2011 data sets as the test set for reporting the final summarization results. [sent-199, score-1.301]
64 We compare our pipeline summarization system against three recent studies, which have reported some of the highest published results on this task. [sent-200, score-0.352]
65 We use the SVR-based approach to preselect a set of sentences from the document set; these sentences are further fed to the guided compression module that produces n-best compressions for each 8http://www. [sent-213, score-1.341]
66 “Our System” uses the SVR-based sentence pre-selection + guided compression + ILP-based summary sentence selection. [sent-225, score-1.326]
67 “Our System w/ Generic Comp” uses the pre-selection + generic compression + ILP summary sentence selection setting. [sent-226, score-1.116]
68 That is, all of the sentences in the documents (excluding those containing less than 5 words) are compressed and used in the ILPbased summary sentence selection module. [sent-249, score-0.412]
69 We can see that although sentence pre-selection removes some sentences from consideration in the later summarization step, it actually significantly improves system performance. [sent-250, score-0.442]
70 When applying the pre-selection step, fewer sentences are used in the compression and summarization, this means we are able to use more compression candidates for each sentence (considering the complexity of ILP module). [sent-256, score-1.762]
71 Without pre-selection, we used the 100-best candidates generated from the compression model; with pre-selection, we are able to increase the number to 200-best candidate compressions and still maintain reasonable computational cost. [sent-258, score-1.033]
72 This suggests that in the important sentences (those are kept after pre-selection), there is more summary related information and thus the compression model keeps more words in them (lower compression ratio). [sent-263, score-1.751]
73 Without the pre-selection step, the scores are less stable in regard to the changing of the m value, since the large amount of sentences plus a high volume of the compression candidates may incur huge computational cost to the ILP solver. [sent-277, score-0.869]
74 In general, we also notice that given more compression candidates, the R-2 score is still improving, as indicated by Figure 1. [sent-279, score-0.797]
75 The improved performance of ‘with pre-selection’ over ‘without pre-selection’ is partly because fewer sentences are used and thus we are able to increase the number of compression candidates for these sentences in the ILP sentence extraction module. [sent-280, score-1.02]
76 In order to illustrate the contribution of our summary-guided sentence compression component, we train a generic sentence compression model and use this in our compression and summarization pipeline. [sent-282, score-2.945]
77 The generic compression model was trained using the Edinburgh sentence compression corpus (Clarke and Lapata, 2008), which contains 1370 sentences collected from news articles. [sent-283, score-1.792]
78 Each sentence has 3 compressions and we choose the shortest compression as the reference. [sent-285, score-1.077]
79 The average compression rate of this corpus is about 28%, lower than that in our summary guided compression data. [sent-286, score-1.931]
80 Results of our system using the generic compression model (with sentence pre-selection) are shown in the last row of Table 3 and Table 4. [sent-289, score-0.977]
81 We can see that the system with this generic compression model performs # Compression Candidates # Compression Candidates Figure 1: R-2 scores of the two systems (without and with the sentence pre-selection step) when using different number of compressions for each sentence. [sent-290, score-1.161]
82 worse than ours, and is also inferior to the TAC best performing system on both data sets, which signifies the importance of our proposed summary guided sentence compression approach. [sent-291, score-1.252]
83 We can also see there is a difference in the compression ratio in the system generated compressions when using different compression corpora to train the compression models. [sent-292, score-2.632]
84 The resulting compression ratio patterns are consistent with those in the training data, that is, using our guided compression corpus our system compressed sentences more aggressively. [sent-293, score-1.994]
85 Since we use a supervised compression model, we further consider the relationship between the summarization performance and the number of sentence pairs used for training the guided compression model. [sent-295, score-2.22]
86 In the compression step, we generate only the 1-best compression candidate in order to remove the im498 pact caused by the downstream summary sentence selection module. [sent-298, score-1.871]
87 As seen from Figure 2, increasing the compression training data generally improves summarization performance, although there are also fluTcAtCua 2t0i0on8s. [sent-299, score-1.081]
88 a512tes250 4T0A C602 018 01 20 # Sentence Pairs in the Training Set Figure 2: ROUGE-2 scores when using different number of sentences to train the guided compression model. [sent-302, score-1.073]
89 6 Conclusion and Future Work In this paper, we propose a pipeline summariza- tion approach that combines a novel guided compression model with ILP-based summary sentence selection. [sent-303, score-1.276]
90 We create a guided compression corpus, where the human annotators were explicitly informed about the important summary words during the compression annotation. [sent-304, score-1.973]
91 We then train a supervised compression model to capture the guided compression process using a set of word-, sentence-, and document-level features. [sent-305, score-1.856]
92 We conduct experiments on the TAC 2008 and 2011 summarization data sets and show that by incorporating the guided sentence compression model, our summarization system can yield significant performance gain as compared to the state-of-the-art. [sent-306, score-1.703]
93 , 2007), improve the readability of the sentences generated from the guided compression system, and report results using multiple evaluation metrics (Nenkova et al. [sent-308, score-1.057]
94 Fast and robust compressive summarization with dual decomposition and multi-task learning. [sent-323, score-0.356]
95 On the effectiveness of using sentence compression models for queryfocused multi-document summarization. [sent-332, score-0.893]
96 Global inference for sentence compression an integer linear programming approach. [sent-336, score-0.977]
97 Improving summarization performance by sentence compression - A pilot study. [sent-373, score-1.177]
98 The pyramid method: Incorporating human content selection variation in summarization evaluation. [sent-408, score-0.344]
99 A sentence compression based framework to query-focused multidocument summarization. [sent-449, score-0.893]
100 Multi-candidate reduction: Sentence compression as a tool for document summarization tasks. [sent-462, score-1.117]
wordName wordTfidf (topN-words)
[('compression', 0.797), ('summarization', 0.284), ('guided', 0.22), ('compressions', 0.184), ('tac', 0.174), ('ilp', 0.134), ('summary', 0.117), ('compressed', 0.099), ('sentence', 0.096), ('extractive', 0.093), ('abstractive', 0.074), ('compressive', 0.072), ('guiding', 0.07), ('generic', 0.062), ('gillick', 0.061), ('summaries', 0.059), ('pipeline', 0.046), ('selection', 0.044), ('salient', 0.042), ('svr', 0.041), ('martins', 0.04), ('sentences', 0.04), ('depth', 0.038), ('integer', 0.038), ('salience', 0.037), ('liu', 0.037), ('clarke', 0.037), ('document', 0.036), ('nenkova', 0.036), ('sjk', 0.035), ('candidates', 0.032), ('chali', 0.031), ('nomoto', 0.031), ('pression', 0.031), ('submodular', 0.031), ('thadani', 0.031), ('zajic', 0.031), ('qian', 0.03), ('lapata', 0.03), ('programming', 0.029), ('jk', 0.028), ('abstracts', 0.027), ('supervised', 0.026), ('woodsend', 0.026), ('annotators', 0.026), ('module', 0.024), ('compressing', 0.024), ('preselection', 0.024), ('sdf', 0.024), ('succinctness', 0.024), ('xjk', 0.024), ('guidance', 0.023), ('lin', 0.023), ('kathleen', 0.023), ('system', 0.022), ('sbar', 0.022), ('yang', 0.022), ('rouge', 0.022), ('joint', 0.021), ('ani', 0.021), ('knight', 0.021), ('kupiec', 0.02), ('aker', 0.02), ('almeida', 0.02), ('galanis', 0.02), ('turner', 0.02), ('candidate', 0.02), ('studies', 0.019), ('ratio', 0.019), ('ci', 0.019), ('fei', 0.019), ('andre', 0.019), ('xian', 0.019), ('select', 0.018), ('concept', 0.018), ('step', 0.018), ('bigrams', 0.018), ('daum', 0.018), ('informativeness', 0.017), ('bosch', 0.017), ('linear', 0.017), ('mckeown', 0.017), ('conjunction', 0.017), ('crf', 0.017), ('marcu', 0.017), ('dropped', 0.017), ('proceeded', 0.016), ('human', 0.016), ('train', 0.016), ('formulation', 0.016), ('documents', 0.016), ('overlaps', 0.016), ('stopwords', 0.016), ('yoshikawa', 0.016), ('hasan', 0.016), ('grammaticality', 0.016), ('wb', 0.015), ('vj', 0.015), ('extraction', 0.015), ('discriminative', 0.015)]
simIndex simValue paperId paperTitle
same-paper 1 1.000002 65 emnlp-2013-Document Summarization via Guided Sentence Compression
Author: Chen Li ; Fei Liu ; Fuliang Weng ; Yang Liu
Abstract: Joint compression and summarization has been used recently to generate high quality summaries. However, such word-based joint optimization is computationally expensive. In this paper we adopt the ‘sentence compression + sentence selection’ pipeline approach for compressive summarization, but propose to perform summary guided compression, rather than generic sentence-based compression. To create an annotated corpus, the human annotators were asked to compress sentences while explicitly given the important summary words in the sentences. Using this corpus, we train a supervised sentence compression model using a set of word-, syntax-, and documentlevel features. During summarization, we use multiple compressed sentences in the integer linear programming framework to select . salient summary sentences. Our results on the TAC 2008 and 2011 summarization data sets show that by incorporating the guided sentence compression model, our summarization system can yield significant performance gain as compared to the state-of-the-art.
2 0.53896296 149 emnlp-2013-Overcoming the Lack of Parallel Data in Sentence Compression
Author: Katja Filippova ; Yasemin Altun
Abstract: A major challenge in supervised sentence compression is making use of rich feature representations because of very scarce parallel data. We address this problem and present a method to automatically build a compression corpus with hundreds of thousands of instances on which deletion-based algorithms can be trained. In our corpus, the syntactic trees of the compressions are subtrees of their uncompressed counterparts, and hence supervised systems which require a structural alignment between the input and output can be successfully trained. We also extend an existing unsupervised compression method with a learning module. The new system uses structured prediction to learn from lexical, syntactic and other features. An evaluation with human raters shows that the presented data harvesting method indeed produces a parallel corpus of high quality. Also, the supervised system trained on this corpus gets high scores both from human raters and in an automatic evaluation setting, significantly outperforming a strong baseline. 1 Introduction and related work Sentence compression is a paraphrasing task where the goal is to generate sentences shorter than given while preserving the essential content. A robust compression system would be useful for mobile devices as well as a module in an extractive summarization system (Mani, 2001). Although a compression may differ lexically and structurally from the source sentence, to date most systems are extractive and proceed by deleting words from the 1481 input (Knight & Marcu, 2000; Dorr et al., 2003; Turner & Charniak, 2005; Clarke & Lapata, 2008; Berg-Kirkpatrick et al., 2011, inter alia). To decide which words, dependencies or phrases can be dropped, (i) rule-based approaches (Grefenstette, 1998; Jing & McKeown, 2000; Dorr et al., 2003; Zajic et al., 2007), (ii) supervised models trained on parallel data (Knight & Marcu, 2000; Turner & Charniak, 2005; McDonald, 2006; Gillick & Favre, 2009; Galanis & Androutsopoulos, 2010, inter alia) and (iii) unsupervised methods which make use of statistics collected from non-parallel data (Hori & Furui, 2004; Zajic et al., 2007; Clarke & Lapata, 2008; Filippova & Strube, 2008) have been investigated. Since it is infeasible to manually devise a set of accurate deletion rules with high coverage, recent research has been devoted to developing statistical methods and possibly augmenting them with a few linguistic rules to improve output readability (Clarke & Lapata, 2008; Nomoto, 2009). Supervised models. A major problem for supervised deletion-based systems is very limited amount of parallel data. Many approaches make use of a small portion of the Ziff-Davis corpus which has about 1K sentence-compression pairs1 . Other main sources of training data are the two manually crafted compression corpora from the University of Edinburgh (“written” and “spoken”, each approx. 1.4K pairs). Galanis & Androutsopoulos (201 1) attempt at getting more parallel data by applying a deletionbased compressor together with an automatic para1The method of Galley & McKeown (2007) could benefit from a larger number of sentences. Proce Sdeiantgtlse o,f W thaesh 2i0n1gt3o nC,o UnSfeAre,n 1c8e- o2n1 E Omctpoibriecra 2l0 M13et.h ?oc d2s0 i1n3 N Aastusorcaila Ltiaon g fuoarg Ceo Pmrpoucetastsi on ga,l p Laignegsu 1is4t8ic1s–1491, phraser and generating multiple alternative compressions. To our knowledge, this extended data set has not yet been used for successful training of compression systems. Scarce parallel data makes it hard to go beyond a small set of features and explore lexicalization. For example, Knight & Marcu (2000) only induce nonlexicalized CFG rules, many of which occurred only once in the training data. The features of McDonald (2006) are formulated exclusively in terms of syntactic categories. Berg-Kirkpatrick et al. (201 1) have as few as 13 features to decide whether a constituent can be dropped. Galanis & Androutsopoulos (2010) use many features when deciding which branches of the input dependency tree can be pruned but require a reranker to select most fluent compressions from a pool of candidates generated in the pruning phase, many of which are ungrammatical. Even further data limitations exist for the algorithms which operate on syntactic trees and reformulate the compression task as a tree pruning one (Nomoto, 2008; Filippova & Strube, 2008; Cohn & Lapata, 2009; Galanis & Androutsopoulos, 2010, inter alia). These methods are sensitive to alignment errors, their performance degrades if the syntactic structure of the compression is very different from that of the input. For example, see Nomoto’s 2009 analysis of the poor performance of the T3 system of Cohn & Lapata (2009) when retrained on a corpus of loosely similar RSS feeds and news. Unsupervised models. Few approaches require no training data at all. The model of Hori & Furui (2004) combines scores estimated from monolingual corpora to generate compressions of transcribed speech. Adopting an integer linear programming (ILP) framework, Clarke & Lapata (2008) use hand-crafted syntactic constraints and an ngram language model, trained on uncompressed sentences, to find best compressions. The model of Filippova & Strube (2008) also uses ILP but the problem is formulated over dependencies and not ngrams. Conditional probabilities and word counts collected from a large treebank are combined in an ad hoc manner to assess grammatical importance and informativeness of dependencies. Similarly, Woodsend & Lapata (2010) formulate an ILP problem to gener- ate news story highlights using precomputed scores. 1482 Again, an ad hoc combination of the scores learned independently of the task is used in the objective function. Contributions of this paper. Our work is motivated by the obvious need for a large parallel corpus of sentences and compressions on which extractive systems can be trained. Furthermore, we want the compressions in the corpus to be structurally very close to the input. Ideally, in every pair, the compression should correspond to a subtree of the input. To this end, our contributions are three-fold: • • We describe an automatic procedure of constructing a parallel corpus ocf p 250,000 ese onften cocen-compression pairs such that the dependency tree of the compression is a subtree of the source tree. An evaluation with human raters demonstrates high quality of the parallel data in terms of readability and informativeness. We successfully apply the acquired data to train a neo svueclc supervised compression system ow thraicinh produces readable and informative compressions without employing a separate reranker. In particular, we start with the unsupervised method of Filippova & Strube (2008) and replace the ad hoc edge weighting with a linear function over a rich feature representation. The parameter vector is learned from our corpus specifically for the compression task using structured prediction (Collins, 2002). The new system significantly outperforms the baseline and hence provides further evidence for the utility of the parallel data. • We demonstrate that sparse lexical features are very eusmeofunls tfroart ese tnhtaetn spcea compression, aunreds st aharet a large parallel corpus is a requirement for applying them successfully. The compression framework we adopt and the unsupervised baseline are introduced in Section 2, the training algorithm for learning edge weights from parallel data is described in Section 3. In Section 4 we explain how to obtain the data and present an evaluation of its quality. In Section 5 we compare the baseline with our system and report the results of an experiment with humans as well as the results of an automatic evaluation. 2 Framework and baseline We adopt the unsupervised compression framework of Filippova & Strube (2008) as our baseline and extend it to a supervised structured prediction problem. In the experiments reported by Filippova & Strube (2008), the system was evaluated on the Edinburgh corpora. It achieved an F-score (Riezler et al., 2003) higher than reported by other systems on the same data under an aggressive compression rate and thus presents a competitive baseline. Tree pruning as optimization. In this framework, compressions are obtained by deleting edges of the source dependency structure so that (1) the retained edges form a valid syntactic tree, and (2) their total edge weight is maximized. The objective function is defined over set X = {xe, e ∈ E} of binary variables, corresponding {tox t,hee s∈et EE} o off t bhiesource edges, subject to the structural and length constraints, ×× = f(X) Xxe w(e) (1) Xe∈E Here, w(e) denotes the weight of edge e. This constrained optimization problem is solved under the tree structure and length constraints using ILP. If xe is resolved to 1, the respective edge is retained, otherwise it is deleted. The tree structure constraints enforce at most one parent for every node and structure connectivity (i.e., no disconnected subtrees). Given that length(node(e)) denotes the length of the node to which edge e points and α is the maximum permitted length for the compression, the length constraint is simply Xxe Xe∈E length(node(e)) ≤ α (2) Word limit is used in the original paper, whereas we use character length which is more appropriate for system comparisons (Napoles et al., 2011). If uniform weights are used in Eq. (1), the optimal solution would correspond to a subtree covering as many edges as possible while keeping the compression length under given limit. The solution to the surface realization problem (Belz et al., 2011) is standard: the words in the compression subtree are put in the same order they are found in the source. 1483 Due to space limitations, we refer the reader to (Filippova & Strube, 2008) for a detailed description on the method. Essential for the present discussion is that source dependency trees are transformed to dependency graphs in that (1) auxiliary, determiner, preposition, negation and possessive nodes are collapsed with their heads; (2) prepositions replace labels on the edges to their arguments; (3) the dummy root node is connected with every inflected verb. Figures 1(a)-1(b) illustrate most of the transformations. The transformations are deterministic and reversible, they can be implemented in a single top-down tree traversal2. The set E of edges in Eq. (1) is thus the set of edges of the transformed dependency graph, like in Fig. 1(b). A benefit of the transformations is that function words and negation appear in the compression if and only if their head words are present. Hence no separate constraints are required to en- × sure that negation or a determiner is preserved. The dummy root node makes constraint formulation easier and also allows for the generation of compressions from any finite clause of the source. The described pruning optimization framework is used both for the unsupervised baseline and for our supervised system. The difference between the baseline and our system is in how edge weights, w(e)’s in Eq. (1), are instantiated. Baseline edge weights. The precomputed edge weights reflect syntactic importance as well as informativeness of the nodes they point to. Given edge e from head node h to node n, the edge weight is the product of the syntactic and the informativeness weights, w(e) = wsynt(e) winfo(e) (3) The syntactic weight is defined as wsynt(e) = P(label(e) |lemma(h)) (4) For example, verb kill may have multiple arguments realized with dependency labels subj, dobj, in, etc. However, these argument labels are not equally likely, e.g., P(subj|kill) > P(in|kill) . When forced to prune an edge, t|hkiel system iwno|kuillld) prefer to keep 2Some of the transformations are comparable to what is implemented in the Stanford parser (de Marneffe et al., 2006). pspos prepnspoub j ro tdetamodc ompnsuabujxpas prep doebtjamodprep oabmjod ro tBritan’sMinsrto ryotfsoufbDjef nrsoeotsaysBritsha(bm)ocadcTosrmoaplndsifeor smubwejdagsrkapihledroadisnidaemoidnablast outheinr amiondAfghanistan ro tBritshamodrao stoldiersubjwas kiledinin a blastin Afghanistan Britain ’s Ministry of Defense says a British soldier was killed in a roadside blast in southern Afghanistan (a) Source dependency tree (c) Tree of extracted headline A British soldier was killed in a blast in Afghanistan detamodsubajuxpassrootpreppodbejtpreppobj A British soldier was killed in a blast in Afghanistan (d) Tree of extracted headline with transformations undone Figure 1: Source, transformed and extracted trees given headline British soldier killed in Afghanistan the subject edge over the preposition-in edge since it contributes more weight to the objective function. The informativeness score is inspired by Wood- send & Lapata (2012) and is defined as winfo(e) =PPhaeartdicl iene((lleemmmmaa((nn)))) (5) This weight tells us how likely it is that a word from an article appears in the headline. For exam- ple, given two edges one of which points to verb say and another one to verb kill, the latter would be preferred over the former because kill is more “headliny” than say. When collecting counts for the syntactic and informativeness scores, we used 9M news articles crawled from the Internet, much more than Filippova & Strube (2008). As a result our estimates are probably more accurate than theirs. Although both wsynt and winfo have a meaningful interpretation, there is no guarantee that product is the best way to combine the two when assigning edge weights. Also, it is unclear how to integrate other signals, such as distance to the root, node length or information about the siblings, which pre1484 sumably all play a role in determining the overall edge importance. 3 Learning edge weights Our supervised system differs from the unsupervised baseline in that instead of relying on precomputed scores, we define edge weight w(e) in Eq. (1) with a linear function over a feature representation, w(e) = w · f(e) (6) Here f(e) is a vector of binary variables for every feature from the set of all possible but very infrequent features in the training set. f(e) has 1for every feature extracted for edge e and zero otherwise. Table 1 gives an overview of the feature types we use (edge e points from head h to node n). Note that syntactic, structural and semantic features are closed-class. For all the structural features but char length, seven is used as maximum possible value; all possible character lengths are bucketed into six classes. All the features are local for a given edge, contextual information is included about – syntacticlabel(e); for e* to h, label(e*); pos(h); pos(n) structural depth(n); #children(n); #children(h); char length(n); #words in(n) semantic NE tag(h); NE tag(n); is negated(n) lexical lemma(n); lemma(h)-label(e); for e* to n’s siblings, lemma(h)-label(e*) Table 1: Types of features extracted for edge e from h to n the head and the target nodes, and the siblings as well as the children of the latter. The negation feature is only applicable to verb nodes which contain a negative particle, like not, after the tree transformations. Lexical features which combine lemmas and syntactic labels are inspired by the unsupervised baseline and are very sparse. In what follows, our assumption is that we have a compression corpus at our disposal where for every input sentence there is a correct “oracle” compression such that its transformed parse tree matches a subtree of the transformed input graph. Given such a corpus, we can apply structured prediction methods to learn the parameter vector w. In our study we employ an averaged variant of online structured perceptron (Collins, 2002). In the context of sentence fusion, a similar dependency structure pruning framework and a similar learning approach was adopted by Elsner & Santhanam (201 1). At every iteration, for every input graph, we find the optimal solution with ILP under the current parameter vector w. The maximum permitted compression length is set to be the same as the length of the oracle compression. Since the oracle compression is a subtree of the input graph, it represents a feasible solution for ILP. The parameter vector is updated if there is a mismatch between the predicted and the oracle sets of edges for all the features with a non-zero net count. More formally, given an input graph with the set of edges E, oracle compression C ⊂ E and compression Ct ⊆ E predicted at itera- tCion ⊂ ⊂t , t ahen parameter update ⊆vec Etor p raetd ti + 1d aist given by wt+1 = wt+ e∈XC\Ct f(e) −X f(e) X e∈XCt\C (7) w is averaged over all the wt’s so that features whose weight fluctuated a lot during training are penalized (Freund & Shapire, 1999). 1485 Of course, training a model with a large number of features, such as a lexicalized model, is only possible if there is a large compression corpus where the dependency tree of the compression is a subtree of the source sentence. In the next section we introduce our method of getting a sufficient amount of such data. 4 Acquiring parallel data automatically In this section we explain how we obtained a parallel corpus of sentences and compressions. The underlying idea is to harvest news articles from the Internet where the headline appears to be similar to the first sentence and use it to find an extractive compression of the sentence. Collecting headline-sentence pairs. Using a news crawler, we collected a corpus of news articles in English from the Internet. Similarly to previous work (Dolan et al., 2004; Wubben et al., 2009; Bejan & Harabagiu, 2010, inter alia), the Google News service3 was used to identify news. From every article, the headline and the first sentence, which are known to be semantically similar (Dorr et al., 2003), were extracted. Predictably, very few headlines are extractive compressions of the first sentence, therefore simply looking for pairs where the headline is a subsequence of the words from the first sentence would not solve the problem of getting a large amount of parallel data. Importantly, headlines are syntactically quite different from “normal” sentences. For example, they may have no main verb, omit determiners and appear incomplete, making it hard for a supervised deletion-based system to learn useful rules. Moreover, we observed poor parsing accuracy for headlines which would make syntactic annotations for headlines hardly useful. Thus, instead oftaking the headline as it is, we use it to find a proper extractive compression of the sen3http : / /news .google . com, Jan-Dec 2012. tence by matching lemmas of content words (nouns, verbs, adjectives, adverbs) and coreference IDs of entities from the headline with those of the sentence. The exact procedure is as follows (H, S and T stand for headline, sentence and transformed graph of the sentence): PREPROCESSING H and S are preprocessed in a standard way: tokenized, lemmatized, PoS and NE tagged. Additionally, S is parsed with a dependency parser (Nivre, 2006) and transformed as described in Section 2 to obtain T. Finally, pronominal anaphora is resolved in S. Recall that S is the first sentence, so the antecedent must be located in a preceding, higher-level clause. FILTERING To restrict the corpus to grammatical and informative headlines, we implemented a cascade of filters. Pair (H, S) is discarded if any of the questions in Table 2 is answered positively. Is H a question? Is H or S too short? (less than four word tokens) Is H about as long as S? (min ratio: 1.5) Does H lack a verb? Does H begin with a verb? Is there a noun, verb, adj, adv lemma from H not found in S? Are the noun, verb, adj, adv lemmas from H found in S in a different order? Table 2: Filters applied to candidate pair (H , S) MATCHING Given the content words of H, a subset of nodes in T is selected based on lemma or coreference identity of the main (head) word in the nodes. For example, the main word of a collapsed node in T, which covers two words was killed, is killed; was is its child attached with label aux in the untransformed parse tree. This node is marked if H contains word killed or killing because of the lemma identity. In some cases there are multiple possible matches. For example, given S Barack Obama said he will attend G20 and H mentioning Obama, both Barack Obama and he nodes are marked in T. Once all the nodes in T which match content words and entities from H are identified, a minimum subtree covering these nodes is found such that every word or entity from H occurs as many times in T as in 1486 H. So if H mentions Obama only once, then either Barack Obama or he must be covered by the subtree but not both. This minimum subtree corresponds to an extractive headline, H*, which we generate by ordering the surface forms of all the words in the subtree nodes by their offsets in S. Finally, the character length of H* is compared with the length of H. If H* is much longer than H, the pair (H S) is discarded (max ratio 1.5). As an illustration to the procedure, consider the example from Figure 1 with the extracted headline and its tree presented in Figure 1(c). Given the headline British soldier killed in Afghanistan, the extracted headline would be A British soldier was killed in a blast in Afghanistan. The lemmas british, soldier, kill, afghanistan from the headline match the nodes British, a soldier, was killed, in Afghanistan in the transformed graph. The node in a blast is added because it is on the path from was killed to in Afghanistan. Of course, it is possible to determinis- , tically undo the transformations in order to obtain a standard dependency tree. In this case the extracted headline would still correspond to a subtree of the input (compare Fig. 1(d) with Fig. 1(a)). Also note that a similar procedure can be implemented for constituency parses. The resulting corpus consists of 250K tuples (S T H H*), Appendix provides more examples of source sentences, original headlines and extracted headlines. We did not attempt to tune the values for minimum/maximum length and ratio lower thresholds may have produced comparable results. , , , – Evaluating data quality. The described procedure produces a comparatively large compression corpus but how good are automatically constructed compressions? To answer this question, we randomly selected 50 tuples from the corpus and set up an experiment with human raters to validate and assess data quality in terms of readability4 and informativeness5 which are standard measures of compression quality (Clarke & Lapata, 2006). Raters were asked to read a sentence and a compression (original H or extracted H* headline) and then rate the compression on two five-point scales. Three rat- ings were collected for every item. Table 3 gives 4Also called grammaticality and fluency. 5Also called importance and representativeness. average ratings with standard deviation. AVG read AVG info ORIG. HEADLINE4.36 (0.75)3.86 (0.79) EXTR. HEADLINE 4.26 (1.01) 3.70 (1.04) Table 3: Results for two kinds of headlines In terms of readability and informativeness the extracted headlines are comparable with humanwritten ones: at 95% confidence there is no statistically significant difference between the two. Encouraged by the results of the validation experiment we proceeded to our next question: Can a supervised compression system be successfully trained on this corpus? 5 System evaluation and discussion From the corpus of 250K tuples we used 100K to get pairs of extracted headlines and sentences for training (on the development set we did not observe much improvement from using more training data), 250 for development and the rest for testing. We ran the learning algorithm for 20 iterations, checking the performance on the development set. Features which applied to less than 20 edges were pruned, the size of the feature set is about 28K. 5.1 Evaluation with humans 50 pairs of original headlines and sentences (different from the data validation set in Sec. 4) were randomly selected for an evaluation with humans from the test data. As in the data quality validation experiment, we asked raters to assess the readability and informativeness of proposed compressions for the unsupervised system, our system and humanwritten headlines. The latter provide us with upper bounds on the evaluation criteria. Three ratings per item per parameter were collected. To get comparable results, the unsupervised and our systems used the same compression rate: for both, the requested maximum length was set to the length of the headline. Table 4 summarizes the results. The results indicate that the trained model significantly outperforms the unsupervised system, getting particularly good marks for readability. The differ- ence in readability between our system and original headlines is not statistically significant. Note that 1487 O U RNISRGU. SPY H.S ETYAESMDTLEIMNE4A43V. 376G0 6† read32A4.V. 571G20 † i‡nfo Table 4: Results for the systems and original headline: † and ‡ stand for significantly better than Unsupervised and Our system at 95% confidence, respectively the unsupervised baseline is also capable of generating readable compressions but does a much poorer job in selecting most important information. Our trained model successfully learned to optimize both scores. We refer the reader to Appendix for input and compression examples. Note that the ratings for the human-written headlines in this experiment are slightly different from the ratings in the data validation experiment because a different data sample was used. 5.2 Automatic evaluation Our automatic evaluation had the goal of explicitly addressing two relevant questions related to our claims about (1) the benefits of having a large parallel corpus and (2) employing a supervised approach with a rich feature representation. 1. Our primary motivation for collecting parallel data has been that having access to sparse lexical features, which considerably increase the feature space, would benefit compression systems. But is it really the case for sentence compression? Can a comparable performance be achieved with a closed, moderately sized set of dense, non-lexical features? If yes, then a large compression corpus is probably not needed. Furthermore, to demonstrate that a large corpus is not only sufficient but also necessary to learn weights for thousands of features, we need to compare the performance of the system when trained on the full data set and a small portion of it. 2. The syntactic and informativeness scores in Eq. (3) were calculated over millions of news articles and do provide us with meaninful statistics (see Sec. 2). Is there any benefit in replacing those scores with weights learned for their feature counterparts? Recall that one of our feature types in Table 1 is the concatenation of lemma(h) (parent lemma) and label(e) which relies on the same information as wsynt = P(label(e) |lemma(h)). The feature counterpart bofe winfo dmemfinae(dh i))n. Eq. (5) aislemma(n)–the lemma of the node to which edge points. How would the supervised system perform against the unsupervised one, if it only extracted features of these two types? To answer these questions, we sampled 1,000 tuples from the unused test data and measured F1 score (Riezler et al., 2003) by comparing the trees of the generated compression and the “correct”, extracted headline. The systems we compared are the unsupervised baseline (UNSUP. SYSTEM) and the supervised model trained on three kinds of feature sets: (1) SYNT-INFO FEATURES, corresponding to the supervised training of the unsupervised baseline model (i.e., lemma(h)-label(e) and lemma(n)); (2) NON-LEX FEATURES, corresponding to a dense, non-lexical feature representation (i.e., all the feature types from Table 1 excluding the three involving lemmas); (3) ALL FEATURES (same as OUR SYSTEM). Additionally, we trained the system on 10% of the data–10K as opposed to 100K tuples, ALL FEATURES ( 10K)–for 20 iterations ignoring features which applied to less than three edges6. As before, the same compression rate was used for all the systems. The results are summarized in Table 5. SANUYL ONSLTUF-LEPI.NASXTFYUOFSRE TAE STAMU(1R0ESK)F1578249s1c.0o364re#f12a7tN,u4835r.1A29e30s. Table 5: Results for the unsupervised baseline and the supervised system trained on three kinds of feature sets Clearly, having more features, lexicalized and unlexicalized, is important: there is a significant im6Recall from the beginning of the section that for the full (100K) training set the threshold was set to 20 with no tuning. For the 10K training set, we tried values of two, three, five and varied the number of iterations. The result we report is the highest we could get for 10K. 1488 provement in going beyond the closed set of 330 non-lexical features to all, from 79.6 to 84.3 points. Moreover, successful training requires a large corpus since the performance of the system degrades if only 10K training instances are used. Note that this number already exceeds all the existing compression corpora taken together. Hence, sparse lexical features are useful for compression and a large parallel corpus is a requirement for successful supervised training. Concerning our second question, learning feature weights from the data produces significantly better results than the hand-crafted way of making use of the same information, even if a much larger data set is used to collect statistics. We observed a dramatic increase from 52.3 to 75.0 points. Thus, we may conclude that training with dense and sparse features directly from data definitely improves the performance of the dependency pruning system. 5.3 Discussion It is important to note that the data we used is challenging: first sentences in news articles tend to be long, in fact longer than other news sentences, which implies less reliable syntactic analysis and noisier input to the syntax-based systems. In the test set we used for the evaluation with humans, the mean sentence length is 165 characters. The average compression rate in characters is 0.46 0. 16 which is quite iaogng rraetsesiv ine7 c. hRareaccatlel rtsha ist we u6se ±d 0th.1e6 very same framework for the unsupervised baseline and our system as well as the same compression rate. All the preprocessing errors affect both systems equally and the comparison of the two is fair. Predictably, wrong syntactic parses significantly increase chances of an ungrammatical compression, and parser errors seem to be a major source of readability deficiencies. A property of the described compression framework is that a desired compression length is expected to be provided by the user. This can be seen both as a strength and as a weakness, depending on the application. In a scenario where mobile devices with a limited screen size are used, or in a summarization scenario where a total summary length is ± provided (see the DUC/TAC guidelines8), being able 7We follow the standard terminology where smaller values imply shorter compressions. 8http : / /www .nist .gov/t ac / to specify a length is definitely an advantage. However, one can also think of other applications where the user does not have a strict length constraint but wants the text to be somewhat shorter. In this case, a reranker which compares compressions generated for a range of possible lengths can be employed to find a single compression (e.g., mean edge weight in the solution or a language model-based score). 6 Conclusions We have addressed a major problem for supervised extractive compression models the lack of a large parallel corpus. To this end, we presented a method to automatically build such a corpus from web documents available on the Internet. An evaluation with humans demonstrates that the quality of the corpus is high the compressions are grammatical and informative. We also significantly improved a competitive unsupervised method achieving high readability and informativeness scores by incorpo– – rating thousands of features and learning the feature weights from our corpus. This result further confirms the practical utility of the automatically obtained data. We have shown that employing lexical features is important for sentence compression, and that our supervised module can successfully learn their weights from the corpus. To our knowledge, we are the first to empirically demonstrate that sparse features are useful for compression and that a large parallel corpus is a requirement for a successful learning of their weights. We believe that other supervised deletion-based systems can benefit from our work. Acknowledgements: The authors are thankful to the EMNLP reviewers for their feedback and suggestions. Appendix The appendix presents examples of source sentences (S), original headlines (H), extracted headlines (H*), unsupervised baseline (U) and our system (O) compressions. 1489 References Bejan, C. & S. Harabagiu (2010). Unsupervised event coreference resolution with rich linguistic features. In Proc. of ACL-10, pp. 1412–1422. Belz, A., M. White, D. Espinosa, E. Kow, D. Hogan & A. Stent (201 1). The first surface realization shared task: Overview and evaluation results. In Proc. of ENLG-11, pp. 217–226. Berg-Kirkpatrick, T., D. Gillick & D. Klein (201 1). Jointly learning to extract and compress. In Proc. of ACL-11. Clarke, J. & M. Lapata (2006). Models for sentence compression: A comparison across domains, training requirements and evaluation measures. In Proc. of COLING-ACL-06, pp. 377–385. Clarke, J. & M. Lapata (2008). Global inference for sentence compression: An integer linear programming approach. Journal of Artificial Intelligence Research, 3 1:399–429. Cohn, T. & M. Lapata (2009). Sentence compres- sion as tree transduction. Journal of Artificial Intelligence Research, 34:637–674. Collins, M. (2002). Discriminative training methods for Hidden Markov Models: Theory and experiments with perceptron algorithms. In Proc. of EMNLP-02, pp. 1–8. de Marneffe, M.-C., B. MacCartney & C. D. Manning (2006). Generating typed dependency parses from phrase structure parses. In Proc. of LREC06, pp. 449–454. Dolan, B., C. Quirk & C. Brokett (2004). Unsupervised construction oflarge paraphrase corpora: Exploiting massively parallel news sources. In Proceedings of the 20th International Conference on Computational Linguistics, Geneva, Switzerland, 23–27 August 2004, pp. 350–356. Dorr, B., D. Zajic & R. Schwartz (2003). Hedge trimmer: A parse-and-trim approach to headline generation. In Proceedings of the Text Summarization Workshop at HLT-NAACL-03, Edmonton, Alberta, Canada, 2003, pp. 1–8. SCountry star Sara Evans has married former University of Alabama quarterback Jay Barker. H H* U O Country star Sara Evans marries Country star Sara Evans has married Sara Evans has married Jay Barker Sara Evans has married Jay Barker H H* U O Intel to build car batteries Intel would be building car batteries would be building the company said Intel would be building car batteries SIntel would be building car batteries, expanding its business beyond its core strength, the company said in a statement SA New Orleans Saints team spokesman says tight end Jeremy Shockey was taken to a hospital but is doing fine. H H* U O Spokesman: Shockey taken to hospital, doing fine spokesman says Jeremy Shockey was taken to a hospital but is doing fine A New Orleans Saints team spokesman says Jeremy Shockey was taken tight end Jeremy Shockey was taken to a hospital but is doing fine SPresident Obama declared a major disaster exists in the State of Florida and ordered Federal aid to supplement H H* U O State and beginning President President President President local recovery efforts in the area struck by severe storms, flooding, tornadoes, and straight-line winds on May 17, 2009, and continuing. Obama declares major disaster exists in the State of Florida Obama declared a major disaster exists in the State of Florida Obama declared a major disaster exists and ordered Federal aid Obama declared a major disaster exists in the State of Florida H H* U O mounting loan defaults. Regulators shut down small Florida bank Regulators shut down a small Florida bank shut down bringing the number of failures Regulators shut down a small Florida bank SRegulators Friday shut down a small Florida bank, bringing to 119 the number of US bank failures this year amid SThree men were arrested Wednesday night and Dayton police said their arrests are in connection to a west Dayton H H* U O bank robbery. 3 men arrested in connection with Bank robbery Three men were arrested are in connection to a bank robbery were arrested and Dayton police said their arrests are Three men were arrested and police said their arrests are SThe government and the social partners will resume the talks on the introduction of the so-called crisis tax, H H* U O which will be levied on all salaries, pensions and incomes over HRK 3,000. Government, social partners to resume talks on introduction of “crisis” tax. The government and the social partners will resume the talks on the introduction of the crisis tax The government will resume the talks on the introduction of the crisis tax which will be levied The government and the social partners will resume the talks on the introduction of the crisis tax SEngland star David Beckham may have the chance to return to AC Milan after the Italian club’s coach said H H* U O he was open to his move on Sunday. Beckham has chance of returning to Milan David Beckham may have the chance to return to AC Milan David Beckham may have the chance to return said star was David Beckham may have the chance to return to AC Milan SEastern Health and its insurance company have accepted liability for some patients involved in the breast cancer H H* U O testing scandal, according to a statement released Friday afternoon. Eastern Health accepts liability for some patients Eastern Health have accepted liability for some patients Health have accepted liability according to a statement Eastern Health have accepted liability for some patients SFrontier Communications Corp., a provider of phone, TV and Internet services, said Thursday H H* U it has started a cash tender offer to purchase up to $700 million of its notes. Frontier Communications starts tender offer for up to $700 million of notes Frontier Communications has started a tender offer to purchase $700 million of its notes Frontier Communications said Thursday a provider has started a tender offer OFrontier Communications has started a tender offe1r4 to9 p0urchase $700 million of its notes Elsner, M. & D. Santhanam (201 1). Learning to fuse disparate sentences. In Proceedings of the Workshop on Monolingual Text-to-text Generation, Prtland, OR, June 24 2011, pp. 54–63. Filippova, K. & M. Strube (2008). Dependency tree based sentence compression. In Proc. of INLG08, pp. 25–32. Freund, Y. & R. E. Shapire (1999). Large margin classification using the perceptron algorithm. Machine Learning, 37:277–296. Galanis, D. & I. Androutsopoulos (2010). An extractive supervised two-stage method for sentence compression. In Proc. of NAACL-HLT-10, pp. 885–893. Galanis, D. & I. Androutsopoulos (201 1). A new sentence compression dataset and its use in an abstractive generate-and-rank sentence compressor. In Proc. of UCNLG+Eval-11, pp. 1–1 1. Galley, M. & K. R. McKeown (2007). Lexicalized Markov grammars for sentence compression. In Proc. of NAACL-HLT-07, pp. 180–187. Gillick, D. & B. Favre (2009). A scalable global model for summarization. In ILP for NLP-09, pp. 10–18. Grefenstette, G. (1998). Producing intelligent telegraphic text reduction to provide an audio scanning service for the blind. In Working Notes of the Workshop on Intelligent Text Summarization, Palo Alto, Cal., 23 March 1998, pp. 111–1 17. Hori, C. & S. Furui (2004). Speech summarization: An approach through word extraction and a method for evaluation. IEEE Transactions on Information and Systems, E87-D(1): 15–25. Jing, H. & K. McKeown (2000). Cut and paste based text summarization. In Proc. of NAACL-00, pp. 178–185. Knight, K. & D. Marcu (2000). Statistics-based summarization – step one: Sentence compression. In Proc. of AAAI-00, pp. 703–71 1. Mani, I. (2001). Automatic Summarization. Amsterdam, Philadelphia: John Benjamins. 1491 McDonald, R. (2006). Discriminative sentence compression with soft syntactic evidence. In Proc. of EACL-06, pp. 297–304. Napoles, C., C. Callison-Burch, J. Ganitkevitch & B. Van Durme (201 1). Paraphrastic sentence compression with a character-based metric: Tightening without deletion. In Proceedings of the Workshop on Monolingual Text-to-text Generation, Prtland, OR, June 24 2011, pp. 84–90. Nivre, J. (2006). Springer. Inductive Dependency Parsing. Nomoto, T. (2008). A generic sentence trimmer with CRFs. In Proc. of ACL-HLT-08, pp. 299–307. Nomoto, T. (2009). A comparison of model free versus model intensive approaches to sentence compression. In Proc. of EMNLP-09, pp. 391–399. Riezler, S., T. H. King, R. Crouch & A. Zaenen (2003). Statistical sentence condensation using ambiguity packing and stochastic disambiguation methods for Lexical-Functional Grammar. In Proc. of HLT-NAACL-03, pp. 118–125. Turner, J. & E. Charniak (2005). Supervised and unsupervised learning for sentence compression. In Proc. of ACL-05, pp. 290–297. Woodsend, K. & M. Lapata (2010). Automatic generation of story highlights. In Proc. of ACL-10, pp. 565–574. Woodsend, K. & M. Lapata (2012). Multiple aspect summarization using Integer Linear Programming. In Proc. of EMNLP-12, pp. 233–243. Wubben, S., A. van den Bosch, E. Krahmer & E. Marsi (2009). Clustering and matching headlines for automatic paraphrase acquisition. In Proc. of ENLG-09, pp. 122–125. Zajic, D., B. J. Dorr, J. Lin & R. Schwartz (2007). Multi-candidate reduction: Sentence compression as a tool for document summarization tasks. Information Processing & Management, Special Issue on Text Summarization, 43(6): 1549–1570.
3 0.36949798 85 emnlp-2013-Fast Joint Compression and Summarization via Graph Cuts
Author: Xian Qian ; Yang Liu
Abstract: Extractive summarization typically uses sentences as summarization units. In contrast, joint compression and summarization can use smaller units such as words and phrases, resulting in summaries containing more information. The goal of compressive summarization is to find a subset of words that maximize the total score of concepts and cutting dependency arcs under the grammar constraints and summary length constraint. We propose an efficient decoding algorithm for fast compressive summarization using graph cuts. Our approach first relaxes the length constraint using Lagrangian relaxation. Then we propose to bound the relaxed objective function by the supermodular binary quadratic programming problem, which can be solved efficiently using graph max-flow/min-cut. Since finding the tightest lower bound suffers from local optimality, we use convex relaxation for initialization. Experimental results on TAC2008 dataset demonstrate our method achieves competitive ROUGE score and has good readability, while is much faster than the integer linear programming (ILP) method.
Author: Tengfei Ma ; Hiroshi Nakagawa
Abstract: Document summarization is an important task in the area of natural language processing, which aims to extract the most important information from a single document or a cluster of documents. In various summarization tasks, the summary length is manually defined. However, how to find the proper summary length is quite a problem; and keeping all summaries restricted to the same length is not always a good choice. It is obviously improper to generate summaries with the same length for two clusters of documents which contain quite different quantity of information. In this paper, we propose a Bayesian nonparametric model for multidocument summarization in order to automatically determine the proper lengths of summaries. Assuming that an original document can be reconstructed from its summary, we describe the ”reconstruction” by a Bayesian framework which selects sentences to form a good summary. Experimental results on DUC2004 data sets and some expanded data demonstrate the good quality of our summaries and the rationality of the length determination.
5 0.12928079 174 emnlp-2013-Single-Document Summarization as a Tree Knapsack Problem
Author: Tsutomu Hirao ; Yasuhisa Yoshida ; Masaaki Nishino ; Norihito Yasuda ; Masaaki Nagata
Abstract: Recent studies on extractive text summarization formulate it as a combinatorial optimization problem such as a Knapsack Problem, a Maximum Coverage Problem or a Budgeted Median Problem. These methods successfully improved summarization quality, but they did not consider the rhetorical relations between the textual units of a source document. Thus, summaries generated by these methods may lack logical coherence. This paper proposes a single document summarization method based on the trimming of a discourse tree. This is a two-fold process. First, we propose rules for transforming a rhetorical structure theorybased discourse tree into a dependency-based discourse tree, which allows us to take a tree- . trimming approach to summarization. Second, we formulate the problem of trimming a dependency-based discourse tree as a Tree Knapsack Problem, then solve it with integer linear programming (ILP). Evaluation results showed that our method improved ROUGE scores.
6 0.11894923 48 emnlp-2013-Collective Personal Profile Summarization with Social Networks
8 0.084803723 147 emnlp-2013-Optimized Event Storyline Generation based on Mixture-Event-Aspect Model
9 0.074129216 179 emnlp-2013-Summarizing Complex Events: a Cross-Modal Solution of Storylines Extraction and Reconstruction
10 0.060070708 160 emnlp-2013-Relational Inference for Wikification
11 0.05797815 198 emnlp-2013-Using Soft Constraints in Joint Inference for Clinical Concept Recognition
12 0.05565457 49 emnlp-2013-Combining Generative and Discriminative Model Scores for Distant Supervision
13 0.040429767 114 emnlp-2013-Joint Learning and Inference for Grammatical Error Correction
14 0.039908599 69 emnlp-2013-Efficient Collective Entity Linking with Stacking
15 0.033270117 77 emnlp-2013-Exploiting Domain Knowledge in Aspect Extraction
16 0.030809538 24 emnlp-2013-Application of Localized Similarity for Web Documents
17 0.030235857 40 emnlp-2013-Breaking Out of Local Optima with Count Transforms and Model Recombination: A Study in Grammar Induction
18 0.029877005 39 emnlp-2013-Boosting Cross-Language Retrieval by Learning Bilingual Phrase Associations from Relevance Rankings
19 0.028247861 93 emnlp-2013-Harvesting Parallel News Streams to Generate Paraphrases of Event Relations
20 0.027945813 53 emnlp-2013-Cross-Lingual Discriminative Learning of Sequence Models with Posterior Regularization
topicId topicWeight
[(0, -0.147), (1, 0.051), (2, -0.036), (3, 0.219), (4, -0.141), (5, -0.054), (6, 0.545), (7, -0.327), (8, 0.102), (9, 0.019), (10, 0.179), (11, 0.01), (12, 0.166), (13, -0.033), (14, -0.102), (15, -0.056), (16, -0.046), (17, -0.091), (18, 0.044), (19, 0.004), (20, 0.066), (21, 0.07), (22, 0.065), (23, -0.073), (24, -0.072), (25, -0.055), (26, -0.022), (27, 0.066), (28, -0.101), (29, 0.124), (30, 0.043), (31, -0.123), (32, -0.065), (33, 0.091), (34, 0.037), (35, 0.141), (36, 0.051), (37, -0.05), (38, -0.008), (39, -0.006), (40, -0.061), (41, -0.011), (42, -0.04), (43, -0.027), (44, -0.004), (45, 0.016), (46, 0.086), (47, 0.069), (48, 0.066), (49, 0.051)]
simIndex simValue paperId paperTitle
same-paper 1 0.9724642 65 emnlp-2013-Document Summarization via Guided Sentence Compression
Author: Chen Li ; Fei Liu ; Fuliang Weng ; Yang Liu
Abstract: Joint compression and summarization has been used recently to generate high quality summaries. However, such word-based joint optimization is computationally expensive. In this paper we adopt the ‘sentence compression + sentence selection’ pipeline approach for compressive summarization, but propose to perform summary guided compression, rather than generic sentence-based compression. To create an annotated corpus, the human annotators were asked to compress sentences while explicitly given the important summary words in the sentences. Using this corpus, we train a supervised sentence compression model using a set of word-, syntax-, and documentlevel features. During summarization, we use multiple compressed sentences in the integer linear programming framework to select . salient summary sentences. Our results on the TAC 2008 and 2011 summarization data sets show that by incorporating the guided sentence compression model, our summarization system can yield significant performance gain as compared to the state-of-the-art.
2 0.86822522 149 emnlp-2013-Overcoming the Lack of Parallel Data in Sentence Compression
Author: Katja Filippova ; Yasemin Altun
Abstract: A major challenge in supervised sentence compression is making use of rich feature representations because of very scarce parallel data. We address this problem and present a method to automatically build a compression corpus with hundreds of thousands of instances on which deletion-based algorithms can be trained. In our corpus, the syntactic trees of the compressions are subtrees of their uncompressed counterparts, and hence supervised systems which require a structural alignment between the input and output can be successfully trained. We also extend an existing unsupervised compression method with a learning module. The new system uses structured prediction to learn from lexical, syntactic and other features. An evaluation with human raters shows that the presented data harvesting method indeed produces a parallel corpus of high quality. Also, the supervised system trained on this corpus gets high scores both from human raters and in an automatic evaluation setting, significantly outperforming a strong baseline. 1 Introduction and related work Sentence compression is a paraphrasing task where the goal is to generate sentences shorter than given while preserving the essential content. A robust compression system would be useful for mobile devices as well as a module in an extractive summarization system (Mani, 2001). Although a compression may differ lexically and structurally from the source sentence, to date most systems are extractive and proceed by deleting words from the 1481 input (Knight & Marcu, 2000; Dorr et al., 2003; Turner & Charniak, 2005; Clarke & Lapata, 2008; Berg-Kirkpatrick et al., 2011, inter alia). To decide which words, dependencies or phrases can be dropped, (i) rule-based approaches (Grefenstette, 1998; Jing & McKeown, 2000; Dorr et al., 2003; Zajic et al., 2007), (ii) supervised models trained on parallel data (Knight & Marcu, 2000; Turner & Charniak, 2005; McDonald, 2006; Gillick & Favre, 2009; Galanis & Androutsopoulos, 2010, inter alia) and (iii) unsupervised methods which make use of statistics collected from non-parallel data (Hori & Furui, 2004; Zajic et al., 2007; Clarke & Lapata, 2008; Filippova & Strube, 2008) have been investigated. Since it is infeasible to manually devise a set of accurate deletion rules with high coverage, recent research has been devoted to developing statistical methods and possibly augmenting them with a few linguistic rules to improve output readability (Clarke & Lapata, 2008; Nomoto, 2009). Supervised models. A major problem for supervised deletion-based systems is very limited amount of parallel data. Many approaches make use of a small portion of the Ziff-Davis corpus which has about 1K sentence-compression pairs1 . Other main sources of training data are the two manually crafted compression corpora from the University of Edinburgh (“written” and “spoken”, each approx. 1.4K pairs). Galanis & Androutsopoulos (201 1) attempt at getting more parallel data by applying a deletionbased compressor together with an automatic para1The method of Galley & McKeown (2007) could benefit from a larger number of sentences. Proce Sdeiantgtlse o,f W thaesh 2i0n1gt3o nC,o UnSfeAre,n 1c8e- o2n1 E Omctpoibriecra 2l0 M13et.h ?oc d2s0 i1n3 N Aastusorcaila Ltiaon g fuoarg Ceo Pmrpoucetastsi on ga,l p Laignegsu 1is4t8ic1s–1491, phraser and generating multiple alternative compressions. To our knowledge, this extended data set has not yet been used for successful training of compression systems. Scarce parallel data makes it hard to go beyond a small set of features and explore lexicalization. For example, Knight & Marcu (2000) only induce nonlexicalized CFG rules, many of which occurred only once in the training data. The features of McDonald (2006) are formulated exclusively in terms of syntactic categories. Berg-Kirkpatrick et al. (201 1) have as few as 13 features to decide whether a constituent can be dropped. Galanis & Androutsopoulos (2010) use many features when deciding which branches of the input dependency tree can be pruned but require a reranker to select most fluent compressions from a pool of candidates generated in the pruning phase, many of which are ungrammatical. Even further data limitations exist for the algorithms which operate on syntactic trees and reformulate the compression task as a tree pruning one (Nomoto, 2008; Filippova & Strube, 2008; Cohn & Lapata, 2009; Galanis & Androutsopoulos, 2010, inter alia). These methods are sensitive to alignment errors, their performance degrades if the syntactic structure of the compression is very different from that of the input. For example, see Nomoto’s 2009 analysis of the poor performance of the T3 system of Cohn & Lapata (2009) when retrained on a corpus of loosely similar RSS feeds and news. Unsupervised models. Few approaches require no training data at all. The model of Hori & Furui (2004) combines scores estimated from monolingual corpora to generate compressions of transcribed speech. Adopting an integer linear programming (ILP) framework, Clarke & Lapata (2008) use hand-crafted syntactic constraints and an ngram language model, trained on uncompressed sentences, to find best compressions. The model of Filippova & Strube (2008) also uses ILP but the problem is formulated over dependencies and not ngrams. Conditional probabilities and word counts collected from a large treebank are combined in an ad hoc manner to assess grammatical importance and informativeness of dependencies. Similarly, Woodsend & Lapata (2010) formulate an ILP problem to gener- ate news story highlights using precomputed scores. 1482 Again, an ad hoc combination of the scores learned independently of the task is used in the objective function. Contributions of this paper. Our work is motivated by the obvious need for a large parallel corpus of sentences and compressions on which extractive systems can be trained. Furthermore, we want the compressions in the corpus to be structurally very close to the input. Ideally, in every pair, the compression should correspond to a subtree of the input. To this end, our contributions are three-fold: • • We describe an automatic procedure of constructing a parallel corpus ocf p 250,000 ese onften cocen-compression pairs such that the dependency tree of the compression is a subtree of the source tree. An evaluation with human raters demonstrates high quality of the parallel data in terms of readability and informativeness. We successfully apply the acquired data to train a neo svueclc supervised compression system ow thraicinh produces readable and informative compressions without employing a separate reranker. In particular, we start with the unsupervised method of Filippova & Strube (2008) and replace the ad hoc edge weighting with a linear function over a rich feature representation. The parameter vector is learned from our corpus specifically for the compression task using structured prediction (Collins, 2002). The new system significantly outperforms the baseline and hence provides further evidence for the utility of the parallel data. • We demonstrate that sparse lexical features are very eusmeofunls tfroart ese tnhtaetn spcea compression, aunreds st aharet a large parallel corpus is a requirement for applying them successfully. The compression framework we adopt and the unsupervised baseline are introduced in Section 2, the training algorithm for learning edge weights from parallel data is described in Section 3. In Section 4 we explain how to obtain the data and present an evaluation of its quality. In Section 5 we compare the baseline with our system and report the results of an experiment with humans as well as the results of an automatic evaluation. 2 Framework and baseline We adopt the unsupervised compression framework of Filippova & Strube (2008) as our baseline and extend it to a supervised structured prediction problem. In the experiments reported by Filippova & Strube (2008), the system was evaluated on the Edinburgh corpora. It achieved an F-score (Riezler et al., 2003) higher than reported by other systems on the same data under an aggressive compression rate and thus presents a competitive baseline. Tree pruning as optimization. In this framework, compressions are obtained by deleting edges of the source dependency structure so that (1) the retained edges form a valid syntactic tree, and (2) their total edge weight is maximized. The objective function is defined over set X = {xe, e ∈ E} of binary variables, corresponding {tox t,hee s∈et EE} o off t bhiesource edges, subject to the structural and length constraints, ×× = f(X) Xxe w(e) (1) Xe∈E Here, w(e) denotes the weight of edge e. This constrained optimization problem is solved under the tree structure and length constraints using ILP. If xe is resolved to 1, the respective edge is retained, otherwise it is deleted. The tree structure constraints enforce at most one parent for every node and structure connectivity (i.e., no disconnected subtrees). Given that length(node(e)) denotes the length of the node to which edge e points and α is the maximum permitted length for the compression, the length constraint is simply Xxe Xe∈E length(node(e)) ≤ α (2) Word limit is used in the original paper, whereas we use character length which is more appropriate for system comparisons (Napoles et al., 2011). If uniform weights are used in Eq. (1), the optimal solution would correspond to a subtree covering as many edges as possible while keeping the compression length under given limit. The solution to the surface realization problem (Belz et al., 2011) is standard: the words in the compression subtree are put in the same order they are found in the source. 1483 Due to space limitations, we refer the reader to (Filippova & Strube, 2008) for a detailed description on the method. Essential for the present discussion is that source dependency trees are transformed to dependency graphs in that (1) auxiliary, determiner, preposition, negation and possessive nodes are collapsed with their heads; (2) prepositions replace labels on the edges to their arguments; (3) the dummy root node is connected with every inflected verb. Figures 1(a)-1(b) illustrate most of the transformations. The transformations are deterministic and reversible, they can be implemented in a single top-down tree traversal2. The set E of edges in Eq. (1) is thus the set of edges of the transformed dependency graph, like in Fig. 1(b). A benefit of the transformations is that function words and negation appear in the compression if and only if their head words are present. Hence no separate constraints are required to en- × sure that negation or a determiner is preserved. The dummy root node makes constraint formulation easier and also allows for the generation of compressions from any finite clause of the source. The described pruning optimization framework is used both for the unsupervised baseline and for our supervised system. The difference between the baseline and our system is in how edge weights, w(e)’s in Eq. (1), are instantiated. Baseline edge weights. The precomputed edge weights reflect syntactic importance as well as informativeness of the nodes they point to. Given edge e from head node h to node n, the edge weight is the product of the syntactic and the informativeness weights, w(e) = wsynt(e) winfo(e) (3) The syntactic weight is defined as wsynt(e) = P(label(e) |lemma(h)) (4) For example, verb kill may have multiple arguments realized with dependency labels subj, dobj, in, etc. However, these argument labels are not equally likely, e.g., P(subj|kill) > P(in|kill) . When forced to prune an edge, t|hkiel system iwno|kuillld) prefer to keep 2Some of the transformations are comparable to what is implemented in the Stanford parser (de Marneffe et al., 2006). pspos prepnspoub j ro tdetamodc ompnsuabujxpas prep doebtjamodprep oabmjod ro tBritan’sMinsrto ryotfsoufbDjef nrsoeotsaysBritsha(bm)ocadcTosrmoaplndsifeor smubwejdagsrkapihledroadisnidaemoidnablast outheinr amiondAfghanistan ro tBritshamodrao stoldiersubjwas kiledinin a blastin Afghanistan Britain ’s Ministry of Defense says a British soldier was killed in a roadside blast in southern Afghanistan (a) Source dependency tree (c) Tree of extracted headline A British soldier was killed in a blast in Afghanistan detamodsubajuxpassrootpreppodbejtpreppobj A British soldier was killed in a blast in Afghanistan (d) Tree of extracted headline with transformations undone Figure 1: Source, transformed and extracted trees given headline British soldier killed in Afghanistan the subject edge over the preposition-in edge since it contributes more weight to the objective function. The informativeness score is inspired by Wood- send & Lapata (2012) and is defined as winfo(e) =PPhaeartdicl iene((lleemmmmaa((nn)))) (5) This weight tells us how likely it is that a word from an article appears in the headline. For exam- ple, given two edges one of which points to verb say and another one to verb kill, the latter would be preferred over the former because kill is more “headliny” than say. When collecting counts for the syntactic and informativeness scores, we used 9M news articles crawled from the Internet, much more than Filippova & Strube (2008). As a result our estimates are probably more accurate than theirs. Although both wsynt and winfo have a meaningful interpretation, there is no guarantee that product is the best way to combine the two when assigning edge weights. Also, it is unclear how to integrate other signals, such as distance to the root, node length or information about the siblings, which pre1484 sumably all play a role in determining the overall edge importance. 3 Learning edge weights Our supervised system differs from the unsupervised baseline in that instead of relying on precomputed scores, we define edge weight w(e) in Eq. (1) with a linear function over a feature representation, w(e) = w · f(e) (6) Here f(e) is a vector of binary variables for every feature from the set of all possible but very infrequent features in the training set. f(e) has 1for every feature extracted for edge e and zero otherwise. Table 1 gives an overview of the feature types we use (edge e points from head h to node n). Note that syntactic, structural and semantic features are closed-class. For all the structural features but char length, seven is used as maximum possible value; all possible character lengths are bucketed into six classes. All the features are local for a given edge, contextual information is included about – syntacticlabel(e); for e* to h, label(e*); pos(h); pos(n) structural depth(n); #children(n); #children(h); char length(n); #words in(n) semantic NE tag(h); NE tag(n); is negated(n) lexical lemma(n); lemma(h)-label(e); for e* to n’s siblings, lemma(h)-label(e*) Table 1: Types of features extracted for edge e from h to n the head and the target nodes, and the siblings as well as the children of the latter. The negation feature is only applicable to verb nodes which contain a negative particle, like not, after the tree transformations. Lexical features which combine lemmas and syntactic labels are inspired by the unsupervised baseline and are very sparse. In what follows, our assumption is that we have a compression corpus at our disposal where for every input sentence there is a correct “oracle” compression such that its transformed parse tree matches a subtree of the transformed input graph. Given such a corpus, we can apply structured prediction methods to learn the parameter vector w. In our study we employ an averaged variant of online structured perceptron (Collins, 2002). In the context of sentence fusion, a similar dependency structure pruning framework and a similar learning approach was adopted by Elsner & Santhanam (201 1). At every iteration, for every input graph, we find the optimal solution with ILP under the current parameter vector w. The maximum permitted compression length is set to be the same as the length of the oracle compression. Since the oracle compression is a subtree of the input graph, it represents a feasible solution for ILP. The parameter vector is updated if there is a mismatch between the predicted and the oracle sets of edges for all the features with a non-zero net count. More formally, given an input graph with the set of edges E, oracle compression C ⊂ E and compression Ct ⊆ E predicted at itera- tCion ⊂ ⊂t , t ahen parameter update ⊆vec Etor p raetd ti + 1d aist given by wt+1 = wt+ e∈XC\Ct f(e) −X f(e) X e∈XCt\C (7) w is averaged over all the wt’s so that features whose weight fluctuated a lot during training are penalized (Freund & Shapire, 1999). 1485 Of course, training a model with a large number of features, such as a lexicalized model, is only possible if there is a large compression corpus where the dependency tree of the compression is a subtree of the source sentence. In the next section we introduce our method of getting a sufficient amount of such data. 4 Acquiring parallel data automatically In this section we explain how we obtained a parallel corpus of sentences and compressions. The underlying idea is to harvest news articles from the Internet where the headline appears to be similar to the first sentence and use it to find an extractive compression of the sentence. Collecting headline-sentence pairs. Using a news crawler, we collected a corpus of news articles in English from the Internet. Similarly to previous work (Dolan et al., 2004; Wubben et al., 2009; Bejan & Harabagiu, 2010, inter alia), the Google News service3 was used to identify news. From every article, the headline and the first sentence, which are known to be semantically similar (Dorr et al., 2003), were extracted. Predictably, very few headlines are extractive compressions of the first sentence, therefore simply looking for pairs where the headline is a subsequence of the words from the first sentence would not solve the problem of getting a large amount of parallel data. Importantly, headlines are syntactically quite different from “normal” sentences. For example, they may have no main verb, omit determiners and appear incomplete, making it hard for a supervised deletion-based system to learn useful rules. Moreover, we observed poor parsing accuracy for headlines which would make syntactic annotations for headlines hardly useful. Thus, instead oftaking the headline as it is, we use it to find a proper extractive compression of the sen3http : / /news .google . com, Jan-Dec 2012. tence by matching lemmas of content words (nouns, verbs, adjectives, adverbs) and coreference IDs of entities from the headline with those of the sentence. The exact procedure is as follows (H, S and T stand for headline, sentence and transformed graph of the sentence): PREPROCESSING H and S are preprocessed in a standard way: tokenized, lemmatized, PoS and NE tagged. Additionally, S is parsed with a dependency parser (Nivre, 2006) and transformed as described in Section 2 to obtain T. Finally, pronominal anaphora is resolved in S. Recall that S is the first sentence, so the antecedent must be located in a preceding, higher-level clause. FILTERING To restrict the corpus to grammatical and informative headlines, we implemented a cascade of filters. Pair (H, S) is discarded if any of the questions in Table 2 is answered positively. Is H a question? Is H or S too short? (less than four word tokens) Is H about as long as S? (min ratio: 1.5) Does H lack a verb? Does H begin with a verb? Is there a noun, verb, adj, adv lemma from H not found in S? Are the noun, verb, adj, adv lemmas from H found in S in a different order? Table 2: Filters applied to candidate pair (H , S) MATCHING Given the content words of H, a subset of nodes in T is selected based on lemma or coreference identity of the main (head) word in the nodes. For example, the main word of a collapsed node in T, which covers two words was killed, is killed; was is its child attached with label aux in the untransformed parse tree. This node is marked if H contains word killed or killing because of the lemma identity. In some cases there are multiple possible matches. For example, given S Barack Obama said he will attend G20 and H mentioning Obama, both Barack Obama and he nodes are marked in T. Once all the nodes in T which match content words and entities from H are identified, a minimum subtree covering these nodes is found such that every word or entity from H occurs as many times in T as in 1486 H. So if H mentions Obama only once, then either Barack Obama or he must be covered by the subtree but not both. This minimum subtree corresponds to an extractive headline, H*, which we generate by ordering the surface forms of all the words in the subtree nodes by their offsets in S. Finally, the character length of H* is compared with the length of H. If H* is much longer than H, the pair (H S) is discarded (max ratio 1.5). As an illustration to the procedure, consider the example from Figure 1 with the extracted headline and its tree presented in Figure 1(c). Given the headline British soldier killed in Afghanistan, the extracted headline would be A British soldier was killed in a blast in Afghanistan. The lemmas british, soldier, kill, afghanistan from the headline match the nodes British, a soldier, was killed, in Afghanistan in the transformed graph. The node in a blast is added because it is on the path from was killed to in Afghanistan. Of course, it is possible to determinis- , tically undo the transformations in order to obtain a standard dependency tree. In this case the extracted headline would still correspond to a subtree of the input (compare Fig. 1(d) with Fig. 1(a)). Also note that a similar procedure can be implemented for constituency parses. The resulting corpus consists of 250K tuples (S T H H*), Appendix provides more examples of source sentences, original headlines and extracted headlines. We did not attempt to tune the values for minimum/maximum length and ratio lower thresholds may have produced comparable results. , , , – Evaluating data quality. The described procedure produces a comparatively large compression corpus but how good are automatically constructed compressions? To answer this question, we randomly selected 50 tuples from the corpus and set up an experiment with human raters to validate and assess data quality in terms of readability4 and informativeness5 which are standard measures of compression quality (Clarke & Lapata, 2006). Raters were asked to read a sentence and a compression (original H or extracted H* headline) and then rate the compression on two five-point scales. Three rat- ings were collected for every item. Table 3 gives 4Also called grammaticality and fluency. 5Also called importance and representativeness. average ratings with standard deviation. AVG read AVG info ORIG. HEADLINE4.36 (0.75)3.86 (0.79) EXTR. HEADLINE 4.26 (1.01) 3.70 (1.04) Table 3: Results for two kinds of headlines In terms of readability and informativeness the extracted headlines are comparable with humanwritten ones: at 95% confidence there is no statistically significant difference between the two. Encouraged by the results of the validation experiment we proceeded to our next question: Can a supervised compression system be successfully trained on this corpus? 5 System evaluation and discussion From the corpus of 250K tuples we used 100K to get pairs of extracted headlines and sentences for training (on the development set we did not observe much improvement from using more training data), 250 for development and the rest for testing. We ran the learning algorithm for 20 iterations, checking the performance on the development set. Features which applied to less than 20 edges were pruned, the size of the feature set is about 28K. 5.1 Evaluation with humans 50 pairs of original headlines and sentences (different from the data validation set in Sec. 4) were randomly selected for an evaluation with humans from the test data. As in the data quality validation experiment, we asked raters to assess the readability and informativeness of proposed compressions for the unsupervised system, our system and humanwritten headlines. The latter provide us with upper bounds on the evaluation criteria. Three ratings per item per parameter were collected. To get comparable results, the unsupervised and our systems used the same compression rate: for both, the requested maximum length was set to the length of the headline. Table 4 summarizes the results. The results indicate that the trained model significantly outperforms the unsupervised system, getting particularly good marks for readability. The differ- ence in readability between our system and original headlines is not statistically significant. Note that 1487 O U RNISRGU. SPY H.S ETYAESMDTLEIMNE4A43V. 376G0 6† read32A4.V. 571G20 † i‡nfo Table 4: Results for the systems and original headline: † and ‡ stand for significantly better than Unsupervised and Our system at 95% confidence, respectively the unsupervised baseline is also capable of generating readable compressions but does a much poorer job in selecting most important information. Our trained model successfully learned to optimize both scores. We refer the reader to Appendix for input and compression examples. Note that the ratings for the human-written headlines in this experiment are slightly different from the ratings in the data validation experiment because a different data sample was used. 5.2 Automatic evaluation Our automatic evaluation had the goal of explicitly addressing two relevant questions related to our claims about (1) the benefits of having a large parallel corpus and (2) employing a supervised approach with a rich feature representation. 1. Our primary motivation for collecting parallel data has been that having access to sparse lexical features, which considerably increase the feature space, would benefit compression systems. But is it really the case for sentence compression? Can a comparable performance be achieved with a closed, moderately sized set of dense, non-lexical features? If yes, then a large compression corpus is probably not needed. Furthermore, to demonstrate that a large corpus is not only sufficient but also necessary to learn weights for thousands of features, we need to compare the performance of the system when trained on the full data set and a small portion of it. 2. The syntactic and informativeness scores in Eq. (3) were calculated over millions of news articles and do provide us with meaninful statistics (see Sec. 2). Is there any benefit in replacing those scores with weights learned for their feature counterparts? Recall that one of our feature types in Table 1 is the concatenation of lemma(h) (parent lemma) and label(e) which relies on the same information as wsynt = P(label(e) |lemma(h)). The feature counterpart bofe winfo dmemfinae(dh i))n. Eq. (5) aislemma(n)–the lemma of the node to which edge points. How would the supervised system perform against the unsupervised one, if it only extracted features of these two types? To answer these questions, we sampled 1,000 tuples from the unused test data and measured F1 score (Riezler et al., 2003) by comparing the trees of the generated compression and the “correct”, extracted headline. The systems we compared are the unsupervised baseline (UNSUP. SYSTEM) and the supervised model trained on three kinds of feature sets: (1) SYNT-INFO FEATURES, corresponding to the supervised training of the unsupervised baseline model (i.e., lemma(h)-label(e) and lemma(n)); (2) NON-LEX FEATURES, corresponding to a dense, non-lexical feature representation (i.e., all the feature types from Table 1 excluding the three involving lemmas); (3) ALL FEATURES (same as OUR SYSTEM). Additionally, we trained the system on 10% of the data–10K as opposed to 100K tuples, ALL FEATURES ( 10K)–for 20 iterations ignoring features which applied to less than three edges6. As before, the same compression rate was used for all the systems. The results are summarized in Table 5. SANUYL ONSLTUF-LEPI.NASXTFYUOFSRE TAE STAMU(1R0ESK)F1578249s1c.0o364re#f12a7tN,u4835r.1A29e30s. Table 5: Results for the unsupervised baseline and the supervised system trained on three kinds of feature sets Clearly, having more features, lexicalized and unlexicalized, is important: there is a significant im6Recall from the beginning of the section that for the full (100K) training set the threshold was set to 20 with no tuning. For the 10K training set, we tried values of two, three, five and varied the number of iterations. The result we report is the highest we could get for 10K. 1488 provement in going beyond the closed set of 330 non-lexical features to all, from 79.6 to 84.3 points. Moreover, successful training requires a large corpus since the performance of the system degrades if only 10K training instances are used. Note that this number already exceeds all the existing compression corpora taken together. Hence, sparse lexical features are useful for compression and a large parallel corpus is a requirement for successful supervised training. Concerning our second question, learning feature weights from the data produces significantly better results than the hand-crafted way of making use of the same information, even if a much larger data set is used to collect statistics. We observed a dramatic increase from 52.3 to 75.0 points. Thus, we may conclude that training with dense and sparse features directly from data definitely improves the performance of the dependency pruning system. 5.3 Discussion It is important to note that the data we used is challenging: first sentences in news articles tend to be long, in fact longer than other news sentences, which implies less reliable syntactic analysis and noisier input to the syntax-based systems. In the test set we used for the evaluation with humans, the mean sentence length is 165 characters. The average compression rate in characters is 0.46 0. 16 which is quite iaogng rraetsesiv ine7 c. hRareaccatlel rtsha ist we u6se ±d 0th.1e6 very same framework for the unsupervised baseline and our system as well as the same compression rate. All the preprocessing errors affect both systems equally and the comparison of the two is fair. Predictably, wrong syntactic parses significantly increase chances of an ungrammatical compression, and parser errors seem to be a major source of readability deficiencies. A property of the described compression framework is that a desired compression length is expected to be provided by the user. This can be seen both as a strength and as a weakness, depending on the application. In a scenario where mobile devices with a limited screen size are used, or in a summarization scenario where a total summary length is ± provided (see the DUC/TAC guidelines8), being able 7We follow the standard terminology where smaller values imply shorter compressions. 8http : / /www .nist .gov/t ac / to specify a length is definitely an advantage. However, one can also think of other applications where the user does not have a strict length constraint but wants the text to be somewhat shorter. In this case, a reranker which compares compressions generated for a range of possible lengths can be employed to find a single compression (e.g., mean edge weight in the solution or a language model-based score). 6 Conclusions We have addressed a major problem for supervised extractive compression models the lack of a large parallel corpus. To this end, we presented a method to automatically build such a corpus from web documents available on the Internet. An evaluation with humans demonstrates that the quality of the corpus is high the compressions are grammatical and informative. We also significantly improved a competitive unsupervised method achieving high readability and informativeness scores by incorpo– – rating thousands of features and learning the feature weights from our corpus. This result further confirms the practical utility of the automatically obtained data. We have shown that employing lexical features is important for sentence compression, and that our supervised module can successfully learn their weights from the corpus. To our knowledge, we are the first to empirically demonstrate that sparse features are useful for compression and that a large parallel corpus is a requirement for a successful learning of their weights. We believe that other supervised deletion-based systems can benefit from our work. Acknowledgements: The authors are thankful to the EMNLP reviewers for their feedback and suggestions. Appendix The appendix presents examples of source sentences (S), original headlines (H), extracted headlines (H*), unsupervised baseline (U) and our system (O) compressions. 1489 References Bejan, C. & S. Harabagiu (2010). Unsupervised event coreference resolution with rich linguistic features. In Proc. of ACL-10, pp. 1412–1422. Belz, A., M. White, D. Espinosa, E. Kow, D. Hogan & A. Stent (201 1). The first surface realization shared task: Overview and evaluation results. In Proc. of ENLG-11, pp. 217–226. Berg-Kirkpatrick, T., D. Gillick & D. Klein (201 1). Jointly learning to extract and compress. In Proc. of ACL-11. Clarke, J. & M. Lapata (2006). Models for sentence compression: A comparison across domains, training requirements and evaluation measures. In Proc. of COLING-ACL-06, pp. 377–385. Clarke, J. & M. Lapata (2008). Global inference for sentence compression: An integer linear programming approach. Journal of Artificial Intelligence Research, 3 1:399–429. Cohn, T. & M. Lapata (2009). Sentence compres- sion as tree transduction. Journal of Artificial Intelligence Research, 34:637–674. Collins, M. (2002). Discriminative training methods for Hidden Markov Models: Theory and experiments with perceptron algorithms. In Proc. of EMNLP-02, pp. 1–8. de Marneffe, M.-C., B. MacCartney & C. D. Manning (2006). Generating typed dependency parses from phrase structure parses. In Proc. of LREC06, pp. 449–454. Dolan, B., C. Quirk & C. Brokett (2004). Unsupervised construction oflarge paraphrase corpora: Exploiting massively parallel news sources. In Proceedings of the 20th International Conference on Computational Linguistics, Geneva, Switzerland, 23–27 August 2004, pp. 350–356. Dorr, B., D. Zajic & R. Schwartz (2003). Hedge trimmer: A parse-and-trim approach to headline generation. In Proceedings of the Text Summarization Workshop at HLT-NAACL-03, Edmonton, Alberta, Canada, 2003, pp. 1–8. SCountry star Sara Evans has married former University of Alabama quarterback Jay Barker. H H* U O Country star Sara Evans marries Country star Sara Evans has married Sara Evans has married Jay Barker Sara Evans has married Jay Barker H H* U O Intel to build car batteries Intel would be building car batteries would be building the company said Intel would be building car batteries SIntel would be building car batteries, expanding its business beyond its core strength, the company said in a statement SA New Orleans Saints team spokesman says tight end Jeremy Shockey was taken to a hospital but is doing fine. H H* U O Spokesman: Shockey taken to hospital, doing fine spokesman says Jeremy Shockey was taken to a hospital but is doing fine A New Orleans Saints team spokesman says Jeremy Shockey was taken tight end Jeremy Shockey was taken to a hospital but is doing fine SPresident Obama declared a major disaster exists in the State of Florida and ordered Federal aid to supplement H H* U O State and beginning President President President President local recovery efforts in the area struck by severe storms, flooding, tornadoes, and straight-line winds on May 17, 2009, and continuing. Obama declares major disaster exists in the State of Florida Obama declared a major disaster exists in the State of Florida Obama declared a major disaster exists and ordered Federal aid Obama declared a major disaster exists in the State of Florida H H* U O mounting loan defaults. Regulators shut down small Florida bank Regulators shut down a small Florida bank shut down bringing the number of failures Regulators shut down a small Florida bank SRegulators Friday shut down a small Florida bank, bringing to 119 the number of US bank failures this year amid SThree men were arrested Wednesday night and Dayton police said their arrests are in connection to a west Dayton H H* U O bank robbery. 3 men arrested in connection with Bank robbery Three men were arrested are in connection to a bank robbery were arrested and Dayton police said their arrests are Three men were arrested and police said their arrests are SThe government and the social partners will resume the talks on the introduction of the so-called crisis tax, H H* U O which will be levied on all salaries, pensions and incomes over HRK 3,000. Government, social partners to resume talks on introduction of “crisis” tax. The government and the social partners will resume the talks on the introduction of the crisis tax The government will resume the talks on the introduction of the crisis tax which will be levied The government and the social partners will resume the talks on the introduction of the crisis tax SEngland star David Beckham may have the chance to return to AC Milan after the Italian club’s coach said H H* U O he was open to his move on Sunday. Beckham has chance of returning to Milan David Beckham may have the chance to return to AC Milan David Beckham may have the chance to return said star was David Beckham may have the chance to return to AC Milan SEastern Health and its insurance company have accepted liability for some patients involved in the breast cancer H H* U O testing scandal, according to a statement released Friday afternoon. Eastern Health accepts liability for some patients Eastern Health have accepted liability for some patients Health have accepted liability according to a statement Eastern Health have accepted liability for some patients SFrontier Communications Corp., a provider of phone, TV and Internet services, said Thursday H H* U it has started a cash tender offer to purchase up to $700 million of its notes. Frontier Communications starts tender offer for up to $700 million of notes Frontier Communications has started a tender offer to purchase $700 million of its notes Frontier Communications said Thursday a provider has started a tender offer OFrontier Communications has started a tender offe1r4 to9 p0urchase $700 million of its notes Elsner, M. & D. Santhanam (201 1). Learning to fuse disparate sentences. In Proceedings of the Workshop on Monolingual Text-to-text Generation, Prtland, OR, June 24 2011, pp. 54–63. Filippova, K. & M. Strube (2008). Dependency tree based sentence compression. In Proc. of INLG08, pp. 25–32. Freund, Y. & R. E. Shapire (1999). Large margin classification using the perceptron algorithm. Machine Learning, 37:277–296. Galanis, D. & I. Androutsopoulos (2010). An extractive supervised two-stage method for sentence compression. In Proc. of NAACL-HLT-10, pp. 885–893. Galanis, D. & I. Androutsopoulos (201 1). A new sentence compression dataset and its use in an abstractive generate-and-rank sentence compressor. In Proc. of UCNLG+Eval-11, pp. 1–1 1. Galley, M. & K. R. McKeown (2007). Lexicalized Markov grammars for sentence compression. In Proc. of NAACL-HLT-07, pp. 180–187. Gillick, D. & B. Favre (2009). A scalable global model for summarization. In ILP for NLP-09, pp. 10–18. Grefenstette, G. (1998). Producing intelligent telegraphic text reduction to provide an audio scanning service for the blind. In Working Notes of the Workshop on Intelligent Text Summarization, Palo Alto, Cal., 23 March 1998, pp. 111–1 17. Hori, C. & S. Furui (2004). Speech summarization: An approach through word extraction and a method for evaluation. IEEE Transactions on Information and Systems, E87-D(1): 15–25. Jing, H. & K. McKeown (2000). Cut and paste based text summarization. In Proc. of NAACL-00, pp. 178–185. Knight, K. & D. Marcu (2000). Statistics-based summarization – step one: Sentence compression. In Proc. of AAAI-00, pp. 703–71 1. Mani, I. (2001). Automatic Summarization. Amsterdam, Philadelphia: John Benjamins. 1491 McDonald, R. (2006). Discriminative sentence compression with soft syntactic evidence. In Proc. of EACL-06, pp. 297–304. Napoles, C., C. Callison-Burch, J. Ganitkevitch & B. Van Durme (201 1). Paraphrastic sentence compression with a character-based metric: Tightening without deletion. In Proceedings of the Workshop on Monolingual Text-to-text Generation, Prtland, OR, June 24 2011, pp. 84–90. Nivre, J. (2006). Springer. Inductive Dependency Parsing. Nomoto, T. (2008). A generic sentence trimmer with CRFs. In Proc. of ACL-HLT-08, pp. 299–307. Nomoto, T. (2009). A comparison of model free versus model intensive approaches to sentence compression. In Proc. of EMNLP-09, pp. 391–399. Riezler, S., T. H. King, R. Crouch & A. Zaenen (2003). Statistical sentence condensation using ambiguity packing and stochastic disambiguation methods for Lexical-Functional Grammar. In Proc. of HLT-NAACL-03, pp. 118–125. Turner, J. & E. Charniak (2005). Supervised and unsupervised learning for sentence compression. In Proc. of ACL-05, pp. 290–297. Woodsend, K. & M. Lapata (2010). Automatic generation of story highlights. In Proc. of ACL-10, pp. 565–574. Woodsend, K. & M. Lapata (2012). Multiple aspect summarization using Integer Linear Programming. In Proc. of EMNLP-12, pp. 233–243. Wubben, S., A. van den Bosch, E. Krahmer & E. Marsi (2009). Clustering and matching headlines for automatic paraphrase acquisition. In Proc. of ENLG-09, pp. 122–125. Zajic, D., B. J. Dorr, J. Lin & R. Schwartz (2007). Multi-candidate reduction: Sentence compression as a tool for document summarization tasks. Information Processing & Management, Special Issue on Text Summarization, 43(6): 1549–1570.
3 0.76871091 85 emnlp-2013-Fast Joint Compression and Summarization via Graph Cuts
Author: Xian Qian ; Yang Liu
Abstract: Extractive summarization typically uses sentences as summarization units. In contrast, joint compression and summarization can use smaller units such as words and phrases, resulting in summaries containing more information. The goal of compressive summarization is to find a subset of words that maximize the total score of concepts and cutting dependency arcs under the grammar constraints and summary length constraint. We propose an efficient decoding algorithm for fast compressive summarization using graph cuts. Our approach first relaxes the length constraint using Lagrangian relaxation. Then we propose to bound the relaxed objective function by the supermodular binary quadratic programming problem, which can be solved efficiently using graph max-flow/min-cut. Since finding the tightest lower bound suffers from local optimality, we use convex relaxation for initialization. Experimental results on TAC2008 dataset demonstrate our method achieves competitive ROUGE score and has good readability, while is much faster than the integer linear programming (ILP) method.
Author: Tengfei Ma ; Hiroshi Nakagawa
Abstract: Document summarization is an important task in the area of natural language processing, which aims to extract the most important information from a single document or a cluster of documents. In various summarization tasks, the summary length is manually defined. However, how to find the proper summary length is quite a problem; and keeping all summaries restricted to the same length is not always a good choice. It is obviously improper to generate summaries with the same length for two clusters of documents which contain quite different quantity of information. In this paper, we propose a Bayesian nonparametric model for multidocument summarization in order to automatically determine the proper lengths of summaries. Assuming that an original document can be reconstructed from its summary, we describe the ”reconstruction” by a Bayesian framework which selects sentences to form a good summary. Experimental results on DUC2004 data sets and some expanded data demonstrate the good quality of our summaries and the rationality of the length determination.
5 0.37350383 48 emnlp-2013-Collective Personal Profile Summarization with Social Networks
Author: Zhongqing Wang ; Shoushan LI ; Fang Kong ; Guodong Zhou
Abstract: Personal profile information on social media like LinkedIn.com and Facebook.com is at the core of many interesting applications, such as talent recommendation and contextual advertising. However, personal profiles usually lack organization confronted with the large amount of available information. Therefore, it is always a challenge for people to find desired information from them. In this paper, we address the task of personal profile summarization by leveraging both personal profile textual information and social networks. Here, using social networks is motivated by the intuition that, people with similar academic, business or social connections (e.g. co-major, co-university, and cocorporation) tend to have similar experience and summaries. To achieve the learning process, we propose a collective factor graph (CoFG) model to incorporate all these resources of knowledge to summarize personal profiles with local textual attribute functions and social connection factors. Extensive evaluation on a large-scale dataset from LinkedIn.com demonstrates the effectiveness of the proposed approach. 1
6 0.32994097 174 emnlp-2013-Single-Document Summarization as a Tree Knapsack Problem
8 0.21394494 198 emnlp-2013-Using Soft Constraints in Joint Inference for Clinical Concept Recognition
9 0.20054364 179 emnlp-2013-Summarizing Complex Events: a Cross-Modal Solution of Storylines Extraction and Reconstruction
10 0.1859878 147 emnlp-2013-Optimized Event Storyline Generation based on Mixture-Event-Aspect Model
11 0.15644346 28 emnlp-2013-Automated Essay Scoring by Maximizing Human-Machine Agreement
12 0.15627903 189 emnlp-2013-Two-Stage Method for Large-Scale Acquisition of Contradiction Pattern Pairs using Entailment
13 0.15228808 114 emnlp-2013-Joint Learning and Inference for Grammatical Error Correction
14 0.14478721 66 emnlp-2013-Dynamic Feature Selection for Dependency Parsing
15 0.14153716 49 emnlp-2013-Combining Generative and Discriminative Model Scores for Distant Supervision
16 0.13960348 203 emnlp-2013-With Blinkers on: Robust Prediction of Eye Movements across Readers
17 0.13234536 132 emnlp-2013-Mining Scientific Terms and their Definitions: A Study of the ACL Anthology
18 0.13144319 129 emnlp-2013-Measuring Ideological Proportions in Political Speeches
19 0.12968108 160 emnlp-2013-Relational Inference for Wikification
20 0.11925901 58 emnlp-2013-Dependency Language Models for Sentence Completion
topicId topicWeight
[(3, 0.069), (12, 0.191), (18, 0.018), (22, 0.052), (30, 0.078), (31, 0.016), (50, 0.018), (51, 0.133), (66, 0.031), (71, 0.025), (75, 0.037), (77, 0.024), (95, 0.157), (96, 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 0.7659865 65 emnlp-2013-Document Summarization via Guided Sentence Compression
Author: Chen Li ; Fei Liu ; Fuliang Weng ; Yang Liu
Abstract: Joint compression and summarization has been used recently to generate high quality summaries. However, such word-based joint optimization is computationally expensive. In this paper we adopt the ‘sentence compression + sentence selection’ pipeline approach for compressive summarization, but propose to perform summary guided compression, rather than generic sentence-based compression. To create an annotated corpus, the human annotators were asked to compress sentences while explicitly given the important summary words in the sentences. Using this corpus, we train a supervised sentence compression model using a set of word-, syntax-, and documentlevel features. During summarization, we use multiple compressed sentences in the integer linear programming framework to select . salient summary sentences. Our results on the TAC 2008 and 2011 summarization data sets show that by incorporating the guided sentence compression model, our summarization system can yield significant performance gain as compared to the state-of-the-art.
2 0.75988382 85 emnlp-2013-Fast Joint Compression and Summarization via Graph Cuts
Author: Xian Qian ; Yang Liu
Abstract: Extractive summarization typically uses sentences as summarization units. In contrast, joint compression and summarization can use smaller units such as words and phrases, resulting in summaries containing more information. The goal of compressive summarization is to find a subset of words that maximize the total score of concepts and cutting dependency arcs under the grammar constraints and summary length constraint. We propose an efficient decoding algorithm for fast compressive summarization using graph cuts. Our approach first relaxes the length constraint using Lagrangian relaxation. Then we propose to bound the relaxed objective function by the supermodular binary quadratic programming problem, which can be solved efficiently using graph max-flow/min-cut. Since finding the tightest lower bound suffers from local optimality, we use convex relaxation for initialization. Experimental results on TAC2008 dataset demonstrate our method achieves competitive ROUGE score and has good readability, while is much faster than the integer linear programming (ILP) method.
3 0.72004122 1 emnlp-2013-A Constrained Latent Variable Model for Coreference Resolution
Author: Kai-Wei Chang ; Rajhans Samdani ; Dan Roth
Abstract: Coreference resolution is a well known clustering task in Natural Language Processing. In this paper, we describe the Latent Left Linking model (L3M), a novel, principled, and linguistically motivated latent structured prediction approach to coreference resolution. We show that L3M admits efficient inference and can be augmented with knowledge-based constraints; we also present a fast stochastic gradient based learning. Experiments on ACE and Ontonotes data show that L3M and its constrained version, CL3M, are more accurate than several state-of-the-art approaches as well as some structured prediction models proposed in the literature.
4 0.65327621 110 emnlp-2013-Joint Bootstrapping of Corpus Annotations and Entity Types
Author: Hrushikesh Mohapatra ; Siddhanth Jain ; Soumen Chakrabarti
Abstract: Web search can be enhanced in powerful ways if token spans in Web text are annotated with disambiguated entities from large catalogs like Freebase. Entity annotators need to be trained on sample mention snippets. Wikipedia entities and annotated pages offer high-quality labeled data for training and evaluation. Unfortunately, Wikipedia features only one-ninth the number of entities as Freebase, and these are a highly biased sample of well-connected, frequently mentioned “head” entities. To bring hope to “tail” entities, we broaden our goal to a second task: assigning types to entities in Freebase but not Wikipedia. The two tasks are synergistic: knowing the types of unfamiliar entities helps disambiguate mentions, and words in mention contexts help assign types to entities. We present TMI, a bipartite graphical model for joint type-mention inference. TMI attempts no schema integration or entity resolution, but exploits the above-mentioned synergy. In experiments involving 780,000 people in Wikipedia, 2.3 million people in Freebase, 700 million Web pages, and over 20 professional editors, TMI shows considerable annotation accuracy improvement (e.g., 70%) compared to baselines (e.g., 46%), especially for “tail” and emerging entities. We also compare with Google’s recent annotations of the same corpus with Freebase entities, and report considerable improvements within the people domain.
5 0.61313176 198 emnlp-2013-Using Soft Constraints in Joint Inference for Clinical Concept Recognition
Author: Prateek Jindal ; Dan Roth
Abstract: This paper introduces IQPs (Integer Quadratic Programs) as a way to model joint inference for the task of concept recognition in clinical domain. IQPs make it possible to easily incorporate soft constraints in the optimization framework and still support exact global inference. We show that soft constraints give statistically significant performance improvements when compared to hard constraints.
7 0.59773976 114 emnlp-2013-Joint Learning and Inference for Grammatical Error Correction
8 0.5933336 149 emnlp-2013-Overcoming the Lack of Parallel Data in Sentence Compression
9 0.58985668 48 emnlp-2013-Collective Personal Profile Summarization with Social Networks
10 0.57625228 56 emnlp-2013-Deep Learning for Chinese Word Segmentation and POS Tagging
11 0.57342154 179 emnlp-2013-Summarizing Complex Events: a Cross-Modal Solution of Storylines Extraction and Reconstruction
12 0.57150292 194 emnlp-2013-Unsupervised Relation Extraction with General Domain Knowledge
13 0.56851101 69 emnlp-2013-Efficient Collective Entity Linking with Stacking
14 0.56811571 86 emnlp-2013-Feature Noising for Log-Linear Structured Prediction
16 0.56577784 160 emnlp-2013-Relational Inference for Wikification
17 0.56390584 174 emnlp-2013-Single-Document Summarization as a Tree Knapsack Problem
18 0.56363684 107 emnlp-2013-Interactive Machine Translation using Hierarchical Translation Models
20 0.56143945 143 emnlp-2013-Open Domain Targeted Sentiment