Abstract | ||
---|---|---|
The task of selecting and ordering infor- mation appears in multiple contexts in text generation and summarization. For in- stance, methods for title generation con- struct a headline by selecting and order- ing words from the input text. In this pa- per, we investigate decoding methods that simultaneously optimize selection and or- dering preferences. We formalize decod- ing as a task of nding an acyclic path in a directed weighted graph. Since the problem is NP-hard, nding an exact so- lution is challenging. We describe a novel decoding method based on a randomized color-coding algorithm. We prove bounds on the number of color-coding iterations necessary to guarantee any desired likeli- hood of nding the correct solution. Our experiments show that the randomized de- coder is an appealing alternative to a range of decoding algorithms for selection-and- ordering problems, including beam search and Integer Linear Programming. |
Year | Venue | Field |
---|---|---|
2007 | HLT-NAACL | Automatic summarization,Graph,Headline,Text generation,Computer science,Beam search,Theoretical computer science,Integer programming,Artificial intelligence,Decoding methods,Machine learning |
DocType | Citations | PageRank |
Conference | 8 | 0.62 |
References | Authors | |
11 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pawan Deshpande | 1 | 63 | 4.19 |
Regina Barzilay | 2 | 3869 | 254.27 |
David R. Karger | 3 | 19367 | 2233.64 |