Randomized Decoding for Selection-and-Ordering Problems

Proceedings of NAACL HLT 2007, pages 444–451, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Randomized Decoding for Selection-and-Ordering Problems Pawan Deshpande, Regina Barzilay and David R. Karger Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {pawand,regina,karger}@csail.mit.edu 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 finding an acyclic path in a directed weighted graph. Since the problem is NP-hard, finding 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 finding 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. 1 Introduction The task of selecting and ordering information ap- pears in multiple contexts in text generation and summarization. For instance, a typical multidocu- ment summarization system creates a summary by selecting a subset of input sentences and ordering them into a coherent text. Selection and ordering at the word level is commonly employed in lexical re- alization. For instance, in the task of title generation, the headline is constructed by selecting and ordering words from the input text. Decoding is an essential component of the selection-and-ordering process. Given selection and ordering preferences, the task is to find a sequence of elements that maximally satisfies these preferences. One possible approach for finding such a solution is to decompose it into two tasks: first, select a set of words based on individual selection preferences, and then order the selected units into a well-formed sequence. Although the modularity of this approach is appealing, the decisions made in the selection step cannot be retracted. Therefore, we cannot guarantee that selected units can be ordered in a meaningful way, and we may end up with a suboptimal output. In this paper, we investigate decoding methods that simultaneously optimize selection and order- ing preferences. We formalize decoding as find- ing a path in a directed weighted graph.1 The vertices in the graph represent units with associ- ated selection scores, and the edges represent pair- wise ordering preferences. The desired solution is the highest-weighted acyclic path of a prespecified length. The requirement for acyclicity is essential because in a typical selection-and-ordering problem, a well-formed output does not include any repeated units. For instance, a summary of multiple docu- ments should not contain any repeated sentences. 1We assume that the scoring function is local; that is, it is computed by combining pairwise scores. In fact, the majority of models that are used to guide ordering (i.e., bigrams) are local scoring functions. …

Content truncated to 500 words