Using Dynamic Programming to Help Search for Reorderings

19. Juli 2010


One often wishes to find an optimal ordering of a collection of objects, with respect to some scoring function. Classic examples include the Traveling Salesperson Problem and the Linear Ordering Problem, as well as applications in machine translation and computational biology. Unfortunately such problems are NP-hard.

One heuristic approach is to make a series of greedy or stochastic moves that "locally" improve the score of an initial guess. In this talk, I will show how to expand the notion of "locality" and consider a combinatorially large neighborhood of possible moves at each step, using dynamic programming to optimize or sample over this neighborhood. The relevant algorithms are derived from well-known algorithms for parsing with finite-state and context-free grammars. As an application, I will show improvements on machine translation from learning how to reorder the words of the input sentence.

Jason Eisner enjoys designing methods that statistically discover and exploit linguistic structure. His 60+ papers have introduced a variety of algorithms and formalisms used in parsing, machine translation, computational phonology, and computational morphology, as well as unsupervised and semi-supervised learning methods for these and other tasks. He has broad interests in computer science, machine learning, linguistics, and cognitive science.