Statistical machine translation

The basic idea

• The best translation of a sentence maximizes faithfulness to the source language sentence and fluency in the target language.
• The noisy channel model (the source language sentence S is viewed as a corrupted version of some target language sentence T, which we are trying to discover):
  T = argmax P(T|S) = argmax P(S|T) P(T) / P(S) = argmax P(S|T) P(T)
  the product of a translation model and a language model for the target language.

The translation model

• Word-based and phrase-based translation
• Translation probability: φ(s_j|t_i), probability of generating S word (phrase) j from T word (phrase) i
• Distortion probability: probability of a given distance between the end of the S phrase (word) generated by T phrase (word) i-1 and the beginning of the S phrase (word) generated by T phrase (word) i
  d(a_i - b_i-1) = α^{|a_i - b_i-1 - 1|}
  (we need to estimate α)
• Translation model
  P(S|T) = Π_i φ(s_i|t_i) d(a_i - b_i-1)
• Training the φs and α requires dealing with the alignment problem

Word alignment

• IBM Model 1
  • Assume each S word is translation of a single T word (or the NULL word).
  • Given a word alignment A and word translation probabilities φ(s_j|t_i)
    P(S|T,A) = Π_j φ(s_j|t_aj)
  • The probability of choosing an S length J and choosing one of the alignments with T of length I, assuming equal likelihood of all alignments:
    P(A|T) = ε/(I + 1)^J
  • The probability of generating S via a particular alignment:
    P(S,A|T) = P(S|T,A) × P(A|T) = ε/(I + 1)^J Π_j φ(s_j|t_aj)
  • Summing over all alignments, we get the total probability of generating S:
    P(S|T) = Σ_A P(S|T,A) × P(A|T) = Σ_A ε/(I + 1)^J Π_j φ(s_j|t_aj)
  • Best alignment Â:
    Â = argmax_A P(S,A|T) = argmax_aj φ(s_j|t_aj), 1 < j < J
  • Training
    • Sentence alignment
    • Probability of an alignment A:
      P(A|S,T) = P(A,S|T) / Σ_A P(A,S|T)
    • Using the EM algorithm to estimate the φ parameters
      • Given current φs, compute probability of each alignment
      • Using weighted sum of alignments to re-estimate φs
  • Other IBM models
    • Fertility: number of source words corresponding to a target word
    • Parameters:
      • word-word translation probabilities (as before)
      • n(2|the): probability that the has fertility 2
      • d(2,4,6,7): probability that target word 2 aligns with source word 4 when the lengths of target and source sentences are 6 and 7
      • p1: probability of generating a spurious source word (corresponding to NULL) each time a source word is generated corresponding to a target word

Decoding

• Multi-stack beam search (separate stack for each number of translated source words)
• State in search space: a partial translation
• Expanding a state: translating a new source word (phrase), only using possible translations
• Goodness function: current goodness ("cost") (product of translation, distortion, language model probabilities so far) + future goodness ("cost") (estimate of maximum probability for translating remaining sentence, ignoring distortion)

© 2008. Indiana University and Michael Gasser. www.cs.indiana.edu/classes/B651/smt.html 2008-03-26