Seminar Announcement

Noah Fleming
Honours Thesis Project
Supervisor: Dr. Antonina Kolokolova

Complexity of Machine Translation: Restrictions and Approximations

Department of Computer Science
Thursday, April 2, 2015, 10:30 a.m., Room EN-2022

Abstract

A central task in statistical machine translation is the decoding problem: given a sentence in one language, find its most probable translation to another. There has been a number of probabilistic models of varying complexity developed for this problem, ranging from simpler models that might be tractable, but generally do not produce good translations, to more realistic, yet less tractable models.

We show that even for the simplest NP-hard model for decoding problem, computing a sentence which is similar enough to the optimal is intractable unless P=NP, where similarity is taken with respect to Hamming distance and edit distance. We then explore, in the context of parameterized complexity, what restrictions to these problems would allow for a tractable algorithm.