Searching for grammaticality: Propagating dependencies in the Viterbi algorithm

In many text-to-text generation scenarios (for instance, summarisation), we encounter humanauthored sentences that could be composed by recycling portions of related sentences to form new sentences. In this paper, we couch the generation of such sentences as a search problem. We investigate a statistical sentence generation method which recombines words to form new sentences. We propose an extension to the Viterbi algorithm designed to improve the grammaticality of generated sentences. Within a statistical framework, the extension favours those partially generated strings with a probable dependency tree structure. Our preliminary evaluations show that our approach generates less fragmented text than a bigram baseline.