acl acl2013 acl2013-332 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hajime Morita ; Ryohei Sasano ; Hiroya Takamura ; Manabu Okumura
Abstract: This study proposes a text summarization model that simultaneously performs sentence extraction and compression. We translate the text summarization task into a problem of extracting a set of dependency subtrees in the document cluster. We also encode obligatory case constraints as must-link dependency constraints in order to guarantee the readability of the generated summary. In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 21 (1 − e−1). Our experiments with the NTC(1IR − −A eCLIA test collections show that our approach outperforms a state-of-the-art algorithm.
Reference: text
sentIndex sentText sentNum sentScore
1 We translate the text summarization task into a problem of extracting a set of dependency subtrees in the document cluster. [sent-9, score-0.44]
2 We also encode obligatory case constraints as must-link dependency constraints in order to guarantee the readability of the generated summary. [sent-10, score-0.267]
3 In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 21 (1 − e−1). [sent-11, score-1.004]
4 1 Introduction Text summarization is often addressed as a task of simultaneously performing sentence extraction and sentence compression (Berg-Kirkpatrick et al. [sent-13, score-0.445]
5 Joint models of sentence extraction and compression have a great benefit in that they have a large degree of freedom as far as controlling redundancy goes. [sent-15, score-0.267]
6 Meanwhile, submodular maximization has recently been applied to the text summarization task, and the methods thereof have performed very well (Lin and Bilmes, 2010; Lin and Bilmes, 2011; Morita et al. [sent-29, score-0.732]
7 Formalizing summarization as a submodular maximization problem has an important benefit inthat the problem can be solved by using a greedy algorithm with a performance guarantee. [sent-31, score-0.824]
8 We therefore decided to formalize the task of simultaneously performing sentence extraction and compression as a submodular maximization problem. [sent-32, score-0.939]
9 The existing greedy algorithm for solving submodular maximization problems cannot work in the presence of such numerous constraints although monotone and nonmonotone submodular maximization with constraints other than budget constraints have been studied (Lee et al. [sent-36, score-1.655]
10 In this study, we avoid this difficulty by reducing the task to one of extracting dependency subtrees from sentences in the source documents. [sent-40, score-0.347]
11 The reduction replaces the difficulty of numerous linear constraints with another difficulty wherein two subtrees can share the same word to1023 Proce dingsS o f ita h,e B 5u1lgsta Arinan,u Aaulg Musete 4ti-n9g 2 o0f1 t3h. [sent-41, score-0.391]
12 Ac s2s0o1ci3a Atiosnso fcoirat Cio nm foprut Caotimonpaulta Lti nognuails Lti cnsg,u piasgteics 1023–1032, ken when they are selected from the same sentence, and as a result, the cost of the union of the two subtrees is not always the mere sum of their costs. [sent-43, score-0.642]
13 We can overcome this difficulty by tackling a new class of submodular maximization problem: a budgeted monotone nondecreasing submodular function maximization with a cost function, where the cost of an extraction unit varies depending on what other extraction units are selected. [sent-44, score-1.994]
14 We also propose a new greedy algorithm that solves this new class of maximization problem with a performance guarantee 12(1 e−1). [sent-46, score-0.38]
15 This property is suitable for summarization purposes, because the gain of adding a new sentence to a summary that already contains sufficient information should be small. [sent-55, score-0.34]
16 Therefore, many studies have formalized text summarization as a submodular maximization problem (Lin and Bilmes, 2010; Lin and Bilmes, 2011; Morita et ≤ + − ≤ − al. [sent-56, score-0.732]
17 To our knowledge, there is no study that addresses the joint task of simultaneously performing compression and extraction through an approximate submodular maximization with a performance guarantee. [sent-59, score-0.887]
18 (2009) proposed an algorithm that solves the submodular maximization problem under multiple linear constraints with a performance guarantee 1− e−1 in polynomial time. [sent-61, score-0.81]
19 (201 1) formulated a unified task of sentence extraction and sentence compression as an ILP. [sent-65, score-0.319]
20 1 Problem Definition Let V be the finite set of all valid subtrees in the source documents, where valid subtrees are defined to be the ones that can be regarded as grammatical sentences. [sent-68, score-0.9]
21 In this paper, we regard subtrees containing the root node of the sentence as valid. [sent-69, score-0.48]
22 Accordingly, V denotes a set of all rooted subtrees in all sentences. [sent-70, score-0.407]
23 A subtree contains a set of elements that are units in a dependency structure (e. [sent-71, score-0.27]
24 This means the cost of a subtree is the integer number of characters it contains. [sent-77, score-0.409]
25 V is partitioned into exclusive subsets B ofvalid subtrees, and each subset corresponds to the original sentence from which the valid subtrees derived. [sent-78, score-0.502]
26 However, the cost of a union of subtrees from different sentences is simply the sum of the costs of subtrees, while the cost of a union of subtrees from the same sentence is smaller than the sum of the costs. [sent-79, score-1.336]
27 (1) For example, if we∑ Badd a subtree t containing words {wa, wb, wc} to a summary that already covers {wwords {wa, wb, wd} fmromma ythe th same sentence, sth weo raddsdit {iownal cost of} }t f riso only c({wc}) eb en-cause wa a anddd wb are already tc oisv oernelyd1 . [sent-81, score-0.556]
28 The first requirement is that the union of valid subtrees is also a valid subtree. [sent-83, score-0.673]
29 The second requirement is that the union of subtrees and a single valid subtree have the same score and the same cost if they cover the same elements. [sent-84, score-1.011]
30 We will refer to the single valid subtree as the equivalent subtree of the union of subtrees. [sent-85, score-0.763]
31 These requirements enable us to represent sentence compression as the extraction of subtrees from a sentence. [sent-86, score-0.614]
32 This is because the requirements guarantee that the extracted subtrees represent a sentence. [sent-87, score-0.42]
33 U means the set of subtrees that are not extracted. [sent-96, score-0.347]
34 The algorithm iteratively adds to the current summary the element si that has the largest ratio of the objective function gain to the additional cost, unless adding it violates the budget constraint. [sent-97, score-0.507]
35 V implicitly constrains the model such that it can only select valid subtrees from a set of nodes and edges. [sent-102, score-0.45]
36 The performance guarantee oftheir algorithm is actually the same as ours, since Algorithm 1Modified greedy algorithm for budgeted submodular function maximization with a cost function . [sent-107, score-1.243]
37 3 Relation with Discrete Optimization We argue that our optimization problem can be regarded as an extraction of subtrees rooted at a given node from a directed graph, instead of from a tree. [sent-112, score-0.493]
38 However, while matroids are often used to represent constraints on submodular maximization problems (Conforti and Cornu ´ejols, 1984; Calinescu et al. [sent-116, score-0.714]
39 To our knowledge, this is the first study that gives a constant performance guarantee for the submodular maximization under greedoid (non-matroid) constraints. [sent-118, score-0.789]
40 1025 4 Joint Model of Extraction and Compression We will formalize the unified task of sentence compression and extraction as a budgeted monotone nondecreasing submodular function maximization with a cost function. [sent-128, score-1.401]
41 In this formalization, a valid subtree of a sentence represents a candidate of a compressed sentence. [sent-129, score-0.511]
42 We will refer to all valid subtrees of a given sentence as a valid set. [sent-130, score-0.605]
43 A valid set corresponds to all candidates of the compression of a sentence. [sent-131, score-0.277]
44 Since, from the requirements, the union of valid subtrees is also a valid subtree in the valid set, the model can extract one or more subtrees from one sentence, and generate a compressed sentence by merging those subtrees to generate an equivalent subtree. [sent-133, score-1.878]
45 Therefore, the joint model can extract an arbitrarily compressed sentence as a subtree without enumerating all candidates. [sent-134, score-0.443]
46 We can approximately solve the subtree extraction problem by using Algorithm 1. [sent-136, score-0.311]
47 On line 5 of the algorithm, the subtree extraction is performed as a local search that finds maximal density subtrees from the whole documents. [sent-137, score-0.872]
48 The maximal density subtree is a subtree that has the highest score per cost of subtree. [sent-138, score-0.888]
49 In this paper, we address the task of summarization of Japanese text by means of sentence compression and extraction. [sent-140, score-0.319]
50 In Japanese, syntactic subtrees that contain the root of the dependency tree of the original sentence often make grammatical sentences. [sent-141, score-0.466]
51 1 that a union of valid subtrees is a valid and equivalent tree is of- ten true for Japanese. [sent-143, score-0.704]
52 In this joint model, we generate a compressed sentence by extracting an arbitrary subtree from a dependency tree of a sentence. [sent-150, score-0.439]
53 The sentence generated by a subtree can be unnatural even though the subtree contains the root node of the sentence. [sent-152, score-0.673]
54 1 Objective Function We extract subtrees from sentences in order to solve the query-oriented summarization problem as a unified one consisting of sentence compression and extraction. [sent-162, score-0.666]
55 With such a similarity, sentence compression extracts nearly only the query terms and fails to contain important information. [sent-165, score-0.292]
56 The score function is supermodular as a score function of subtree extraction3, because the union of two subtrees can have extra word pairs that are not included in either subtree. [sent-170, score-0.941]
57 The behavior can be represented by a submodular objective function that reduces word scores depending on those already included in the summary. [sent-177, score-0.56]
58 Our positive reward for long sentences is represented as reward(S) = c(S) |S|, (3) where c(S) is the cost of summary S, and |S| is the − wnuhmerbeerc oSf) siesnttheenccoess tionf Ssu. [sent-181, score-0.355]
59 Let d be the damping rate, countS(w) be the number of sentences containing word w in summary S, words(S) be the set of words included in summary S, qsb(w) be the query relevance score of word w, and γ be a parameter that adjusts the rate of sentence compression. [sent-183, score-0.384]
60 It is also ad3The score is still submodular for the purpose of sentence extraction. [sent-186, score-0.508]
61 vantageous that the submodular maximization can deal with such objective functions. [sent-187, score-0.705]
62 Due to the nature of the objective function, we can use dynamic programming to effectively search for the subtree with the maximal density. [sent-189, score-0.41]
63 We will use a fast algorithm to find the maximal density subtree (MDS) of a given sentence for each cost in Algorithm 1. [sent-192, score-0.692]
64 That is, the gain function of adding a subtree to a summary can be represented as the sum of gains for words: g(t) = ∑{gainS(w) + freqt(w)c(w)γ}, ∑w∈t gainS(w) = qsb(w)dcountS(w) , where freqt(w) is the number of ws in subtree t, and gainS(w) is the gain of adding the word w to the summary S. [sent-195, score-1.069]
65 Our algorithm is based on dynamic programming, and it selects a subtree that maximizes the gain function per cost. [sent-196, score-0.472]
66 We extended this algorithm to work for submodular word gain functions that are not constant. [sent-199, score-0.556]
67 Let n be a node in the tree, a and b be child nodes of n, c(n) be the cost of n, mdsac be the MDS rooted at {mdscn(n), a and have cost c. [sent-204, score-0.383]
68 The valid subtrees rooted at n can be ob- tained by taking unions of n with one or both of t1 ∈ mdsa and t2 ∈ mdsb. [sent-209, score-0.551]
69 mdscn is the union that has∈ ∈th me largest gain over sthe union with the cost of c (by enumerating all the unions). [sent-210, score-0.569]
70 Next, let us consider the objective function that returns the sum of values of submodular word gain functions. [sent-212, score-0.706]
71 s∪u mbt dien-dicates a set of current maximal density subtrees among the combinations calculated before. [sent-225, score-0.524]
72 newt indicates a set of temporary maximal density subtrees for the combinations calculated from line 4 to 8. [sent-226, score-0.629]
73 subt[cost,ws] indicates a element of subt that has a cost cost and contains a set of words ws. [sent-227, score-0.436]
74 Line 1 sets subt to a set consisting of a subtree that indicates node n itself. [sent-229, score-0.438]
75 The algorithm calculates maximal density subtrees within combinations of the root node n and MDSs rooted at child nodes of n. [sent-230, score-0.753]
76 Line 3 iteratively adds MDSs rooted at a next child node to the combinations; the algorithm then calculates MDSs newt between subt and the MDSs of the child node. [sent-231, score-0.384]
77 The procedure from line 6 to 8 selects a subtree that has a larger gain from the temporary maximal subtree and the union of t and m. [sent-232, score-0.849]
78 When we treat word overlaps, we need to count Algorithm 2Algorithm for finding maximal density subtree for each cost: MDSs. [sent-236, score-0.447]
79 The right table enumerates the subtrees rooted at w2 in the left tree for all indices. [sent-238, score-0.438]
80 Lin and Bilmes (201 1) designed a monotone submodular function for query-oriented summarization. [sent-275, score-0.613]
81 They proposed a positive diversity reward function in order to define a monotone submodular objective function for generating a non-redundant summary. [sent-277, score-0.848]
82 The diversity reward gives a smaller gain for a biased summary, because it consists of gains based on three clusters and calculates a square root score with respect to each sentence. [sent-278, score-0.312]
83 The reward also contains a score for the similarity of a sentence to the query, for purposes of query-oriented summa- RecallLength# of nuggets Subtree extraction0. [sent-279, score-0.271]
84 In the coverage function min function limits the maximum gain α ∑i∈V wi,j, which is a small fraction α of the sim∑ilarity between a sentence j and the all source d∑ocuments. [sent-284, score-0.27]
85 7 Conclusions and Future Work We formalized a query-oriented summarization, which is a task in which one simultaneously performs sentence compression and extraction, as a new optimization problem: budgeted monotone nondecreasing submodular function maximization with a cost function. [sent-321, score-1.393]
86 2 % improvement over a state-of-the-art method using a submodular objective function. [sent-325, score-0.49]
87 Since our algorithm requires that the objective function is the sum of word score functions, our proposed method has a restriction that we cannot use an arbitrary monotone submodular function as the objective function for the summary. [sent-326, score-1.007]
88 S∗ is the optimal solution, cu(S) is the residual cost of − subtree u when S is already covered, and i∗ is the last step before the algorithm discards a subtree s ∈ S∗ or a part of the subtree s. [sent-331, score-1.003]
89 We can remove the subtree s0 from V without changing the approximate rate. [sent-333, score-0.27]
90 si is the i-th subtree obtained by line 5 of Algorithm 1. [sent-334, score-0.36]
91 Gi is the set obtained after adding subtree si to Gi−1 from the valid set Bi. [sent-335, score-0.426]
92 f(·) : 2V → R is a monotone submodular funcftio(·n). [sent-337, score-0.543]
93 We assume that there is an equivalent subtree with any union of subtrees in a valid set B: ∀t1 , t2, ∃te, te ≡ {t1, t2}. [sent-338, score-0.84]
94 Let B be a valid set, and union be a function that returns the union of subtrees. [sent-351, score-0.413]
95 Lemma 3 For a normalized monotone submodular f(·), for i= 1, . [sent-366, score-0.543]
96 Maximizing a monotone submodular function subject to a matroid constraint. [sent-383, score-0.659]
97 The weight-constrained maximum-density subtree problem and related problems in trees. [sent-400, score-0.27]
98 A note on the budgeted maximization on submodular functions. [sent-414, score-0.745]
99 Maximizing submodular set functions subject to multiple linear constraints. [sent-418, score-0.424]
100 Sentence compression as a component of a multi-document summarization system. [sent-501, score-0.267]
wordName wordTfidf (topN-words)
[('submodular', 0.424), ('subtrees', 0.347), ('subtree', 0.27), ('gi', 0.252), ('maximization', 0.215), ('compression', 0.174), ('cost', 0.139), ('mdss', 0.123), ('subt', 0.123), ('union', 0.12), ('monotone', 0.119), ('summary', 0.117), ('morita', 0.108), ('mds', 0.106), ('budgeted', 0.106), ('obligatory', 0.106), ('valid', 0.103), ('density', 0.103), ('reward', 0.099), ('summarization', 0.093), ('nuggets', 0.088), ('compressed', 0.086), ('gain', 0.078), ('ggi', 0.077), ('gii', 0.077), ('greedoid', 0.077), ('mdscn', 0.077), ('qsb', 0.077), ('ssii', 0.077), ('maximal', 0.074), ('guarantee', 0.073), ('bilmes', 0.072), ('function', 0.07), ('japanese', 0.07), ('newt', 0.068), ('query', 0.066), ('objective', 0.066), ('knp', 0.063), ('sbe', 0.063), ('krause', 0.063), ('ggii', 0.061), ('nondecreasing', 0.061), ('nugget', 0.061), ('pourpre', 0.061), ('kawahara', 0.06), ('rooted', 0.06), ('cu', 0.057), ('mitamura', 0.055), ('algorithm', 0.054), ('si', 0.053), ('sentence', 0.052), ('lin', 0.052), ('inequality', 0.05), ('kurohashi', 0.047), ('calinescu', 0.046), ('kulik', 0.046), ('matroid', 0.046), ('lemma', 0.045), ('node', 0.045), ('gf', 0.045), ('constraints', 0.044), ('aclia', 0.041), ('maxs', 0.041), ('guestrin', 0.041), ('unions', 0.041), ('extraction', 0.041), ('greedy', 0.038), ('asn', 0.038), ('sakai', 0.038), ('submodularity', 0.038), ('line', 0.037), ('root', 0.036), ('sum', 0.036), ('ntcir', 0.035), ('enumerating', 0.035), ('element', 0.035), ('tokyo', 0.034), ('calculates', 0.034), ('budget', 0.034), ('reconstructed', 0.034), ('simultaneously', 0.033), ('gains', 0.033), ('score', 0.032), ('let', 0.032), ('tree', 0.031), ('allowance', 0.031), ('cguri', 0.031), ('conforti', 0.031), ('cornu', 0.031), ('greedoids', 0.031), ('gvrii', 0.031), ('khuller', 0.031), ('matroids', 0.031), ('mdsn', 0.031), ('rfor', 0.031), ('tatsunori', 0.031), ('overlaps', 0.031), ('nc', 0.031), ('ilp', 0.03), ('wb', 0.03)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000001 332 acl-2013-Subtree Extractive Summarization via Submodular Maximization
Author: Hajime Morita ; Ryohei Sasano ; Hiroya Takamura ; Manabu Okumura
Abstract: This study proposes a text summarization model that simultaneously performs sentence extraction and compression. We translate the text summarization task into a problem of extracting a set of dependency subtrees in the document cluster. We also encode obligatory case constraints as must-link dependency constraints in order to guarantee the readability of the generated summary. In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 21 (1 − e−1). Our experiments with the NTC(1IR − −A eCLIA test collections show that our approach outperforms a state-of-the-art algorithm.
2 0.22355177 18 acl-2013-A Sentence Compression Based Framework to Query-Focused Multi-Document Summarization
Author: Lu Wang ; Hema Raghavan ; Vittorio Castelli ; Radu Florian ; Claire Cardie
Abstract: We consider the problem of using sentence compression techniques to facilitate queryfocused multi-document summarization. We present a sentence-compression-based framework for the task, and design a series of learning-based compression models built on parse trees. An innovative beam search decoder is proposed to efficiently find highly probable compressions. Under this framework, we show how to integrate various indicative metrics such as linguistic motivation and query relevance into the compression process by deriving a novel formulation of a compression scoring function. Our best model achieves statistically significant improvement over the state-of-the-art systems on several metrics (e.g. 8.0% and 5.4% improvements in ROUGE-2 respectively) for the DUC 2006 and 2007 summarization task. ,
3 0.2232631 333 acl-2013-Summarization Through Submodularity and Dispersion
Author: Anirban Dasgupta ; Ravi Kumar ; Sujith Ravi
Abstract: We propose a new optimization framework for summarization by generalizing the submodular framework of (Lin and Bilmes, 2011). In our framework the summarization desideratum is expressed as a sum of a submodular function and a nonsubmodular function, which we call dispersion; the latter uses inter-sentence dissimilarities in different ways in order to ensure non-redundancy of the summary. We consider three natural dispersion functions and show that a greedy algorithm can obtain an approximately optimal summary in all three cases. We conduct experiments on two corpora—DUC 2004 and user comments on news articles—and show that the performance of our algorithm outperforms those that rely only on submodularity.
4 0.16843782 157 acl-2013-Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning
Author: Miguel Almeida ; Andre Martins
Abstract: We present a dual decomposition framework for multi-document summarization, using a model that jointly extracts and compresses sentences. Compared with previous work based on integer linear programming, our approach does not require external solvers, is significantly faster, and is modular in the three qualities a summary should have: conciseness, informativeness, and grammaticality. In addition, we propose a multi-task learning framework to take advantage of existing data for extractive summarization and sentence compression. Experiments in the TAC2008 dataset yield the highest published ROUGE scores to date, with runtimes that rival those of extractive summarizers.
5 0.14321376 112 acl-2013-Dependency Parser Adaptation with Subtrees from Auto-Parsed Target Domain Data
Author: Xuezhe Ma ; Fei Xia
Abstract: In this paper, we propose a simple and effective approach to domain adaptation for dependency parsing. This is a feature augmentation approach in which the new features are constructed based on subtree information extracted from the autoparsed target domain data. To demonstrate the effectiveness of the proposed approach, we evaluate it on three pairs of source-target data, compared with several common baseline systems and previous approaches. Our approach achieves significant improvement on all the three pairs of data sets.
6 0.10711147 377 acl-2013-Using Supervised Bigram-based ILP for Extractive Summarization
7 0.084904477 126 acl-2013-Diverse Keyword Extraction from Conversations
8 0.084185772 50 acl-2013-An improved MDL-based compression algorithm for unsupervised word segmentation
9 0.080628812 13 acl-2013-A New Syntactic Metric for Evaluation of Machine Translation
10 0.073732942 129 acl-2013-Domain-Independent Abstract Generation for Focused Meeting Summarization
11 0.072836488 353 acl-2013-Towards Robust Abstractive Multi-Document Summarization: A Caseframe Analysis of Centrality and Domain
12 0.068371907 46 acl-2013-An Infinite Hierarchical Bayesian Model of Phrasal Translation
13 0.061131001 260 acl-2013-Nonconvex Global Optimization for Latent-Variable Models
14 0.057735372 225 acl-2013-Learning to Order Natural Language Texts
15 0.057234373 5 acl-2013-A Decade of Automatic Content Evaluation of News Summaries: Reassessing the State of the Art
16 0.056965783 285 acl-2013-Propminer: A Workflow for Interactive Information Extraction and Exploration using Dependency Trees
17 0.055970464 167 acl-2013-Generalizing Image Captions for Image-Text Parallel Corpus
18 0.053481564 291 acl-2013-Question Answering Using Enhanced Lexical Semantic Models
19 0.051001672 199 acl-2013-Integrating Multiple Dependency Corpora for Inducing Wide-coverage Japanese CCG Resources
20 0.050907262 34 acl-2013-Accurate Word Segmentation using Transliteration and Language Model Projection
topicId topicWeight
[(0, 0.158), (1, -0.007), (2, -0.03), (3, -0.048), (4, -0.03), (5, 0.025), (6, 0.117), (7, -0.058), (8, -0.135), (9, -0.097), (10, -0.028), (11, 0.025), (12, -0.137), (13, -0.045), (14, -0.061), (15, 0.139), (16, 0.172), (17, -0.053), (18, -0.005), (19, 0.068), (20, 0.027), (21, -0.038), (22, 0.004), (23, 0.028), (24, 0.013), (25, -0.025), (26, -0.016), (27, 0.023), (28, 0.026), (29, -0.021), (30, -0.02), (31, 0.081), (32, -0.088), (33, 0.046), (34, 0.041), (35, 0.011), (36, 0.007), (37, -0.046), (38, 0.029), (39, -0.05), (40, -0.084), (41, -0.03), (42, 0.034), (43, 0.024), (44, 0.007), (45, -0.06), (46, -0.063), (47, 0.037), (48, -0.011), (49, -0.07)]
simIndex simValue paperId paperTitle
same-paper 1 0.93515658 332 acl-2013-Subtree Extractive Summarization via Submodular Maximization
Author: Hajime Morita ; Ryohei Sasano ; Hiroya Takamura ; Manabu Okumura
Abstract: This study proposes a text summarization model that simultaneously performs sentence extraction and compression. We translate the text summarization task into a problem of extracting a set of dependency subtrees in the document cluster. We also encode obligatory case constraints as must-link dependency constraints in order to guarantee the readability of the generated summary. In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 21 (1 − e−1). Our experiments with the NTC(1IR − −A eCLIA test collections show that our approach outperforms a state-of-the-art algorithm.
2 0.85151881 333 acl-2013-Summarization Through Submodularity and Dispersion
Author: Anirban Dasgupta ; Ravi Kumar ; Sujith Ravi
Abstract: We propose a new optimization framework for summarization by generalizing the submodular framework of (Lin and Bilmes, 2011). In our framework the summarization desideratum is expressed as a sum of a submodular function and a nonsubmodular function, which we call dispersion; the latter uses inter-sentence dissimilarities in different ways in order to ensure non-redundancy of the summary. We consider three natural dispersion functions and show that a greedy algorithm can obtain an approximately optimal summary in all three cases. We conduct experiments on two corpora—DUC 2004 and user comments on news articles—and show that the performance of our algorithm outperforms those that rely only on submodularity.
3 0.83564466 157 acl-2013-Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning
Author: Miguel Almeida ; Andre Martins
Abstract: We present a dual decomposition framework for multi-document summarization, using a model that jointly extracts and compresses sentences. Compared with previous work based on integer linear programming, our approach does not require external solvers, is significantly faster, and is modular in the three qualities a summary should have: conciseness, informativeness, and grammaticality. In addition, we propose a multi-task learning framework to take advantage of existing data for extractive summarization and sentence compression. Experiments in the TAC2008 dataset yield the highest published ROUGE scores to date, with runtimes that rival those of extractive summarizers.
4 0.82403797 18 acl-2013-A Sentence Compression Based Framework to Query-Focused Multi-Document Summarization
Author: Lu Wang ; Hema Raghavan ; Vittorio Castelli ; Radu Florian ; Claire Cardie
Abstract: We consider the problem of using sentence compression techniques to facilitate queryfocused multi-document summarization. We present a sentence-compression-based framework for the task, and design a series of learning-based compression models built on parse trees. An innovative beam search decoder is proposed to efficiently find highly probable compressions. Under this framework, we show how to integrate various indicative metrics such as linguistic motivation and query relevance into the compression process by deriving a novel formulation of a compression scoring function. Our best model achieves statistically significant improvement over the state-of-the-art systems on several metrics (e.g. 8.0% and 5.4% improvements in ROUGE-2 respectively) for the DUC 2006 and 2007 summarization task. ,
5 0.70979619 377 acl-2013-Using Supervised Bigram-based ILP for Extractive Summarization
Author: Chen Li ; Xian Qian ; Yang Liu
Abstract: In this paper, we propose a bigram based supervised method for extractive document summarization in the integer linear programming (ILP) framework. For each bigram, a regression model is used to estimate its frequency in the reference summary. The regression model uses a variety ofindicative features and is trained discriminatively to minimize the distance between the estimated and the ground truth bigram frequency in the reference summary. During testing, the sentence selection problem is formulated as an ILP problem to maximize the bigram gains. We demonstrate that our system consistently outperforms the previous ILP method on different TAC data sets, and performs competitively compared to the best results in the TAC evaluations. We also conducted various analysis to show the impact of bigram selection, weight estimation, and ILP setup.
6 0.69464511 353 acl-2013-Towards Robust Abstractive Multi-Document Summarization: A Caseframe Analysis of Centrality and Domain
7 0.61488527 5 acl-2013-A Decade of Automatic Content Evaluation of News Summaries: Reassessing the State of the Art
8 0.57427204 129 acl-2013-Domain-Independent Abstract Generation for Focused Meeting Summarization
9 0.56292021 50 acl-2013-An improved MDL-based compression algorithm for unsupervised word segmentation
10 0.53328913 142 acl-2013-Evolutionary Hierarchical Dirichlet Process for Timeline Summarization
11 0.5131523 59 acl-2013-Automated Pyramid Scoring of Summaries using Distributional Semantics
12 0.48063126 225 acl-2013-Learning to Order Natural Language Texts
13 0.46909776 178 acl-2013-HEADY: News headline abstraction through event pattern clustering
14 0.4686172 260 acl-2013-Nonconvex Global Optimization for Latent-Variable Models
15 0.46651062 362 acl-2013-Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers
16 0.44136435 375 acl-2013-Using Integer Linear Programming in Concept-to-Text Generation to Produce More Compact Texts
17 0.43462965 319 acl-2013-Sequential Summarization: A New Application for Timely Updated Twitter Trending Topics
18 0.42246023 158 acl-2013-Feature-Based Selection of Dependency Paths in Ad Hoc Information Retrieval
19 0.39560017 23 acl-2013-A System for Summarizing Scientific Topics Starting from Keywords
20 0.39537194 334 acl-2013-Supervised Model Learning with Feature Grouping based on a Discrete Constraint
topicId topicWeight
[(0, 0.026), (6, 0.044), (11, 0.079), (15, 0.028), (16, 0.013), (24, 0.028), (26, 0.035), (28, 0.02), (35, 0.056), (42, 0.058), (48, 0.067), (70, 0.037), (72, 0.303), (88, 0.036), (90, 0.033), (95, 0.045)]
simIndex simValue paperId paperTitle
1 0.78843272 30 acl-2013-A computational approach to politeness with application to social factors
Author: Cristian Danescu-Niculescu-Mizil ; Moritz Sudhof ; Dan Jurafsky ; Jure Leskovec ; Christopher Potts
Abstract: We propose a computational framework for identifying linguistic aspects of politeness. Our starting point is a new corpus of requests annotated for politeness, which we use to evaluate aspects of politeness theory and to uncover new interactions between politeness markers and context. These findings guide our construction of a classifier with domain-independent lexical and syntactic features operationalizing key components of politeness theory, such as indirection, deference, impersonalization and modality. Our classifier achieves close to human performance and is effective across domains. We use our framework to study the relationship between po- liteness and social power, showing that polite Wikipedia editors are more likely to achieve high status through elections, but, once elevated, they become less polite. We see a similar negative correlation between politeness and power on Stack Exchange, where users at the top of the reputation scale are less polite than those at the bottom. Finally, we apply our classifier to a preliminary analysis of politeness variation by gender and community.
same-paper 2 0.78245854 332 acl-2013-Subtree Extractive Summarization via Submodular Maximization
Author: Hajime Morita ; Ryohei Sasano ; Hiroya Takamura ; Manabu Okumura
Abstract: This study proposes a text summarization model that simultaneously performs sentence extraction and compression. We translate the text summarization task into a problem of extracting a set of dependency subtrees in the document cluster. We also encode obligatory case constraints as must-link dependency constraints in order to guarantee the readability of the generated summary. In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 21 (1 − e−1). Our experiments with the NTC(1IR − −A eCLIA test collections show that our approach outperforms a state-of-the-art algorithm.
3 0.72483945 165 acl-2013-General binarization for parsing and translation
Author: Matthias Buchse ; Alexander Koller ; Heiko Vogler
Abstract: Binarization ofgrammars is crucial for improving the complexity and performance of parsing and translation. We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter. We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.
4 0.52318615 172 acl-2013-Graph-based Local Coherence Modeling
Author: Camille Guinaudeau ; Michael Strube
Abstract: We propose a computationally efficient graph-based approach for local coherence modeling. We evaluate our system on three tasks: sentence ordering, summary coherence rating and readability assessment. The performance is comparable to entity grid based approaches though these rely on a computationally expensive training phase and face data sparsity problems.
5 0.44456449 275 acl-2013-Parsing with Compositional Vector Grammars
Author: Richard Socher ; John Bauer ; Christopher D. Manning ; Ng Andrew Y.
Abstract: Natural language parsing has typically been done with small sets of discrete categories such as NP and VP, but this representation does not capture the full syntactic nor semantic richness of linguistic phrases, and attempts to improve on this by lexicalizing phrases or splitting categories only partly address the problem at the cost of huge feature spaces and sparseness. Instead, we introduce a Compositional Vector Grammar (CVG), which combines PCFGs with a syntactically untied recursive neural network that learns syntactico-semantic, compositional vector representations. The CVG improves the PCFG of the Stanford Parser by 3.8% to obtain an F1 score of 90.4%. It is fast to train and implemented approximately as an efficient reranker it is about 20% faster than the current Stanford factored parser. The CVG learns a soft notion of head words and improves performance on the types of ambiguities that require semantic information such as PP attachments.
6 0.44427249 155 acl-2013-Fast and Accurate Shift-Reduce Constituent Parsing
7 0.444267 123 acl-2013-Discriminative Learning with Natural Annotations: Word Segmentation as a Case Study
8 0.44356897 358 acl-2013-Transition-based Dependency Parsing with Selectional Branching
9 0.44287577 83 acl-2013-Collective Annotation of Linguistic Resources: Basic Principles and a Formal Model
10 0.44216254 225 acl-2013-Learning to Order Natural Language Texts
11 0.44113186 47 acl-2013-An Information Theoretic Approach to Bilingual Word Clustering
12 0.43994442 62 acl-2013-Automatic Term Ambiguity Detection
13 0.43907815 17 acl-2013-A Random Walk Approach to Selectional Preferences Based on Preference Ranking and Propagation
14 0.43874517 185 acl-2013-Identifying Bad Semantic Neighbors for Improving Distributional Thesauri
15 0.43822953 132 acl-2013-Easy-First POS Tagging and Dependency Parsing with Beam Search
16 0.43716973 318 acl-2013-Sentiment Relevance
17 0.43667009 82 acl-2013-Co-regularizing character-based and word-based models for semi-supervised Chinese word segmentation
18 0.4363915 7 acl-2013-A Lattice-based Framework for Joint Chinese Word Segmentation, POS Tagging and Parsing
19 0.43614322 280 acl-2013-Plurality, Negation, and Quantification:Towards Comprehensive Quantifier Scope Disambiguation
20 0.43440378 276 acl-2013-Part-of-Speech Induction in Dependency Trees for Statistical Machine Translation