The Mathematics of Statistical Machine Translation: Parameter Estimation

4.1 Model 1

1. What does IBM Model 1 assume?
   The length \(m\) has a small fixed probability \(\epsilon\); each French position connects to any of the \(l + 1\) English positions (including \(e_0\)) with equal probability; and the French word depends only on the English word it connects to: \(\Pr(\mathbf{f}, \mathbf{a} \mid \mathbf{e}) = \frac{\epsilon}{(l+1)^m} \prod_j t(f_j \mid e_{a_j})\). Word order doesn’t matter.
   • Brown et al., 1993, The Mathematics of Statistical Machine Translation (Computational Linguistics), §4.1
2. What trick makes EM exact and efficient for Model 1?
   The sum over all \((l+1)^m\) alignments of a product factorizes into a product of sums: \(\Pr(\mathbf{f} \mid \mathbf{e}) = \frac{\epsilon}{(l+1)^m} \prod_{j=1}^{m} \sum_{i=0}^{l} t(f_j \mid e_i)\). So expected counts take time proportional to \(l + m\) per word pair, not \((l+1)^m\).
   • Brown et al., 1993, The Mathematics of Statistical Machine Translation (Computational Linguistics), §4.1
3. Give the Model 1 expected count of \(f\) given \(e\) for one sentence pair.
   \(c(f \mid e; \mathbf{f}, \mathbf{e}) = \frac{t(f \mid e)}{t(f \mid e_0) + \ldots + t(f \mid e_l)} \times (\text{count of } f \text{ in } \mathbf{f}) \times (\text{count of } e \text{ in } \mathbf{e})\); new \(t(f \mid e)\) is the sum of these counts over the corpus, normalized over \(f\).
   • Brown et al., 1993, The Mathematics of Statistical Machine Translation (Computational Linguistics), §4.1
4. Why doesn’t the initialization of Model 1 matter?
   Its likelihood has a unique local maximum, so EM reaches the same solution from any starting point that avoids zeros (they started with all \(t(f \mid e)\) equal). Later models are initialized from earlier ones, so the final result doesn’t depend on the initial guess either.
   • Brown et al., 1993, The Mathematics of Statistical Machine Translation (Computational Linguistics), §4.1