| Randomized Decoding for Selection-and-Ordering Problems (2008) | |||||||||||||||
Abstract | |||||||||||||||
| The task of selecting and ordering information appears in multiple contexts in text generation and summarization. For instance, methods for title generation construct a headline by selecting and ordering words from the input text. In this paper, we investigate decoding methods that simultaneously optimize selection and ordering preferences. We formalize decoding as a task of finding an acyclic path in a directed weighted graph. Since the problem is NP-hard, finding an exact solution 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 likelihood of finding the correct solution. Our experiments show that the randomized decoder is an appealing alternative to a range of decoding algorithms for selection-andordering problems, including beam search and Integer Linear Programming. 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||