October 9, 2008 - Roy Tromble

Title: Search and Learning for the Linear Ordering Problem with an Application to Machine Translation

Abstract:
The Linear Ordering Problem is a hard combinatorial optimization problem with applications in a number of disciplines. In this talk we will describe local search for the Linear Ordering Problem using permutation neighborhoods, and introduce a novel search procedure that improves on the state-of-the-art for greedy local search on a benchmark problem set. We will then move on to the problem of statistical machine translation. We will relate machine translation decoding to difficult combinatorial optimization problems and introduce a new model of word reordering using the linear ordering problem. This will lead to an interesting machine learning problem, which requires adaptation of standard learning algorithms. We will evaluate the learning methods on the task of German-English translation and show that the learned reordering models can help to significantly improve upon the translations of a standard decoder.