Word alignment as a combinatorial task

Ondrej Bojar

UFAL MFF UK

Abstract

Computational linguists need to automatically find word-to-word corresponencies (word alignments) in large parallel texts, esp. for the purposes of training of machine translation systems. Methods used to date usually restrict the space of allowed word alignments to *functions* mapping one source word to many target words. Naturally, this restriction cannot always explain observed data. Unfortunately, allowing full M-N word alignments renders the task too complex.

The aim of my talk is to present the problem to experienced discrete mathematicians and ask them for help with the formalization of the task: the restrictions should be raised but there has to be a (low) polynomial algorithm to search for the best alignment.

Ultimately, I'm searching for a colleague interested in the topic to supervise or write a thesis (bachelor/masters). I can provide all necessary data and linguistic tools and I'd like to co-