Paper: Randomized Decoding for Selection-and-Ordering Problems

ACL ID N07-1056
Title Randomized Decoding for Selection-and-Ordering Problems
Venue Human Language Technologies
Session Main Conference
Year 2007

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...