Content deleted Content added
99Electrons (talk | contribs) added Category:IBM software using HotCat |
|||
| (44 intermediate revisions by 16 users not shown) | |||
Line 1:
{{short description|Sequence of models in statistical machine translation}}{{Confused|AI alignment}}
The '''IBM alignment models''' are a sequence of increasingly complex models used in [[statistical machine translation]] to train a translation model and an alignment model, starting with lexical translation probabilities and moving to reordering and word duplication.<ref name=":1">{{Cite journal |last1=Brown |first1=Peter F. |author-link1=Peter Fitzhugh Brown |last2=Pietra |first2=Vincent J. Della |last3=Pietra |first3=Stephen A. Della |last4=Mercer |first4=Robert L. |author-link4=Robert Mercer |date=1993-06-01 |title=The mathematics of statistical machine translation: parameter estimation |url=https://dl.acm.org/doi/10.5555/972470.972474 |journal=Comput. Linguist. |volume=19 |issue=2 |pages=263–311 |issn=0891-2017}}</ref><ref>{{cite web | url = http://www.statmt.org/survey/Topic/IBMModels | title = IBM Models | date = 11 September 2015 | publisher = SMT Research Survey Wiki | access-date = 26 October 2015}}</ref> They underpinned the majority of statistical machine translation systems for almost twenty years starting in the early 1990s, until [[neural machine translation]] began to dominate. These models offer principled probabilistic formulation and (mostly) tractable inference.<ref>{{cite web |author=Yarin Gal |author2=Phil Blunsom |date=12 June 2013 |title=A Systematic Bayesian Treatment of the IBM Alignment Models |url=http://mlg.eng.cam.ac.uk/yarin/PDFs/PY-IBM_presentation.pdf |archive-url=https://web.archive.org/web/20160304071924/http://mlg.eng.cam.ac.uk/yarin/PDFs/PY-IBM_presentation.pdf |archive-date=4 Mar 2016 |access-date=26 October 2015 |publisher=University of Cambridge}}</ref>
The IBM alignment models were published in parts in 1988<ref>{{Cite journal |last1=Brown |first1=P. |last2=Cocke |first2=J. |last3=Della Pietra |first3=S. |last4=Della Pietra |first4=V. |last5=Jelinek |first5=F. |last6=Mercer |first6=R. |last7=Roossin |first7=P. |date=1988 |title=A Statistical Approach to Language Translation |url=https://aclanthology.org/C88-1016/ |journal=Coling Budapest 1988 Volume 1: International Conference on Computational Linguistics}}</ref> and 1990,<ref>{{Cite journal |last1=Brown |first1=Peter F. |last2=Cocke |first2=John |last3=Della Pietra |first3=Stephen A. |last4=Della Pietra |first4=Vincent J. |last5=Jelinek |first5=Fredrick |last6=Lafferty |first6=John D. |last7=Mercer |first7=Robert L. |last8=Roossin |first8=Paul S. |date=1990 |title=A Statistical Approach to Machine Translation |url=https://aclanthology.org/J90-2002/ |journal=Computational Linguistics |volume=16 |issue=2 |pages=79–85}}</ref> and the entire series is published in 1993.<ref name=":1" /> Every author of the 1993 paper subsequently went to the hedge fund [[Renaissance Technologies]].<ref>{{Cite web |last=walutowyjohn |date=2013-01-28 |title=A Visionary Gift: Della Pietra Family Endows Biomedical Imaging Chair - SBU News |url=https://news.stonybrook.edu/alumni/a-visionary-gift-della-pietra-family-endows-biomedical-imaging-chair-2/ |access-date=2025-01-06 |website=Stony Brook University News |language=en-US}}</ref>
The original work on statistical machine translation at [[IBM]] proposed five models, and a model 6 was proposed later. The sequence of the six models can be summarized as:
Line 9 ⟶ 13:
* Model 5: fixed deficiency problem.
* Model 6: Model 4 combined with a [[Hidden Markov model|HMM]] alignment model in a log linear way
== Mathematical setup ==
The IBM alignment models translation as a conditional probability model. For each source-language ("foreign") sentence <math>f</math>, we generate both a target-language ("English") sentence <math>e</math> and an alignment <math>a</math>. The problem then is to find a good statistical model for <math>p(e, a|f)</math>, the probability that we would generate English language sentence <math>e</math> and an alignment <math>a</math> given a foreign sentence <math>f</math>.
The meaning of an alignment grows increasingly complicated as the model version number grew. See Model 1 for the most simple and understandable version.
== Model 1 ==
=== Word alignment ===
Given any foreign-English sentence pair <math>(e, f)</math>, an alignment for the sentence pair is a function of type <math>\{1, ., ..., l_e\} \to \{0, 1, ., ..., l_f\}</math>. That is, we assume that the English word at ___location <math>i</math> is "explained" by the foreign word at ___location <math>a(i)</math>. For example, consider the following pair of sentences <blockquote>It will surely rain tomorrow -- 明日 は きっと 雨 だ</blockquote>We can align some English words to corresponding Japanese words, but not everyone:<blockquote>it -> ?
will -> ?
surely -> きっと
rain -> 雨
tomorrow -> 明日</blockquote>This in general happens due to the different grammar and conventions of speech in different languages. English sentences require a subject, and when there is no subject available, it uses a [[dummy pronoun]] ''it''. Japanese verbs do not have different forms for future and present tense, and the future tense is implied by the noun 明日 (tomorrow). Conversely, the [[Topic marker|topic-marker]] は and the grammar word だ (roughly "to be") do not correspond to any word in the English sentence.
So, we can write the alignment as <blockquote>1-> 0; 2 -> 0; 3 -> 3; 4 -> 4; 5 -> 1</blockquote>where 0 means that there is no corresponding alignment.
Thus, we see that the alignment function is in general a function of type <math>\{1, ., ..., l_e\} \to \{0, 1, ., ..., l_f\}</math>.
Future models will allow one English world to be aligned with multiple foreign words.
=== Statistical model ===
Given the above definition of alignment, we can define the statistical model used by Model 1:
* Start with a "dictionary". Its entries are of form <math>t(e_i | f_j)</math>, which can be interpreted as saying "the foreign word <math>f_j</math> is translated to the English word <math>e_i</math> with probability <math>t(e_i | f_j)</math>".
* After being given a foreign sentence <math>f</math> with length <math>l_f</math>, we first generate an English sentence length <math>l_e</math> uniformly in a range <math>Uniform[1, 2, ..., N]</math>. In particular, it does not depend on <math>f</math> or <math>l_f</math>.
* Then, we generate an alignment uniformly in the set of all possible alignment functions <math>\{1, ., ..., l_e\} \to \{0, 1, ., ..., l_f\}</math>.
* Finally, for each English word <math>e_1, e_2, ... e_{l_e}</math>, generate each one independently of every other English word. For the word <math>e_i</math>, generate it according to <math>t(e_i|f_{a(i)})</math>.
Together, we have the probability<math display="block">p(e, a|f) = \frac{1/N}{(1+l_f)^{l_e}}\prod_{i=1}^{l_e} t(e_i | f_{a(i)})</math>IBM Model 1 uses very simplistic assumptions on the statistical model, in order to allow the following algorithm to have closed-form solution.
=== Learning from a corpus ===
If a dictionary is not provided at the start, but we have a corpus of English-foreign language pairs <math>\{(e^{(k)}, f^{(k)})\}_k</math> (without alignment information), then the model can be cast into the following form:
* fixed parameters: the foreign sentences <math>\{f^{(k)}\}_k</math>.
* learnable parameters: the entries of the dictionary <math>t(e_i | f_j)</math>.
* observable variables: the English sentences <math>\{e^{(k)}\}_k</math>.
* latent variables: the alignments <math>\{a^{(k)}\}_k</math>
In this form, this is exactly the kind of problem solved by [[expectation–maximization algorithm]]. Due to the simplistic assumptions, the algorithm has a closed-form, efficiently computable solution, which is the solution to the following equations:<math display="block">
\begin{cases}
\max_{t'} \sum_k \sum_i \sum_{a^{(k)}} t(a^{(k)} | e^{(k)}, f^{(k)}) \ln t(e_i^{(k)} | f_{a^{(k)}(i)}^{(k)}) \\
\sum_x t'(e_x | f_y) = 1 \quad \forall y
\end{cases}
</math>This can be solved by [[Lagrange multiplier|Lagrangian multipliers]], then simplified. For a detailed derivation of the algorithm, see <ref name=":0">{{Cite book |last=Koehn |first=Philipp |url=https://books.google.com/books?id=4v_Cx1wIMLkC |title=Statistical Machine Translation |date=2010 |publisher=Cambridge University Press |isbn=978-0-521-87415-1 |language=en |chapter=4. Word-Based Models}}</ref> chapter 4 and.<ref>{{Cite web |title=CS288, Spring 2020, Lectur 05: Statistical Machine Translation |url=https://cal-cs288.github.io/sp20/slides/cs288_sp20_05_statistical_translation_1up.pdf |url-status=live |archive-url=https://web.archive.org/web/20201024011801/https://cal-cs288.github.io/sp20/slides/cs288_sp20_05_statistical_translation_1up.pdf |archive-date=24 Oct 2020}}</ref>
In short, the EM algorithm goes as follows:<blockquote>INPUT. a corpus of English-foreign sentence pairs <math>\{(e^{(k)}, f^{(k)})\}_k</math>
INITIALIZE. matrix of translations probabilities <math>t(e_x | f_y)</math>.<blockquote>This could either be uniform or random. It is only required that every entry is positive, and for each <math>y</math>, the probability sums to one: <math>\sum_x t(e_x|f_y) = 1</math>.</blockquote>
LOOP. until <math>t(e_x | f_y)</math> converges:<blockquote><math>t(e_x | f_y) \leftarrow \frac{t(e_x|f_y)}{\lambda_y} \sum_{k, i, j}\frac{\delta(e_x, e_i^{(k)})\delta(f_y, f_{j}^{(k)})}{\sum_{j'}t(e_i^{(k)}|f_{j'}^{(k)})}</math>
<blockquote>where each <math>\lambda_y</math> is a normalization constant that makes sure each <math>\sum_x t(e_x|f_y) = 1</math>.</blockquote></blockquote>RETURN. <math>t(e_x | f_y)</math>.</blockquote>In the above formula, <math>\delta</math> is the [[Dirac delta function]] -- it equals 1 if the two entries are equal, and 0 otherwise. The index notation is as follows:<blockquote><math>k</math> ranges over English-foreign sentence pairs in corpus;
<math>i</math> ranges over words in English sentences;
<math>j</math> ranges over words in foreign language sentences;
<math>x</math> ranges over the entire vocabulary of English words in the corpus;
<math>y</math> ranges over the entire vocabulary of foreign words in the corpus.</blockquote>
=== Limitations ===
There are several limitations to the IBM model 1.<ref name=":0" />
* No fluency: Given any sentence pair <math>(e, f)</math>, any permutation of the English sentence is equally likely: <math>p(e|f) = p(e'|f)</math> for any permutation of the English sentence <math>e</math> into <math>e'</math>.
* No length preference: The probability of each length of translation is equal: <math>\sum_{e\text{ has length }l}p(e|f) = \frac 1N</math> for any <math>l \in \{1, 2, ..., N\}</math>.
*Does not explicitly model fertility: some foreign words tend to produce a fixed number of English words. For example, for German-to-English translation, ''ja'' is usually omitted, and ''zum'' is usually translated to one of ''to the, for the, to a, for a''.
== Model 2 ==
Model 2 allows alignment to be conditional on sentence lengths. That is, we have a probability distribution <math>p_a(j |i, l_e, l_f)</math>, meaning "the probability that English word <math>i</math> is aligned to foreign word <math>j</math>, when the English sentence is of length <math>l_e</math>, and the foreign sentence is of length <math>l_f</math>".
The rest of Model 1 is unchanged. With that, we have <math display="block">p(e, a|f) = {1/N}\prod_{i=1}^{l_e} t(e_i | f_{a(i)})p_a(a(i)|i, l_e, l_f)</math>The EM algorithm can still be solved in closed-form, giving the following algorithm:<math display="block">t(e_x | f_y) \leftarrow \frac{1}{\lambda_y} \sum_{k, i, j}\frac{t(e_{i}^{(k)}| f_{j}^{(k)})p_a(j | i, l_e, l_f) \delta(e_x, e_i^{(k)})\delta(f_y, f_{j}^{(k)})}{\sum_{j'}t(e_i^{(k)}|f_{j'}^{(k)})p_a(j' | i, l_e, l_f)}</math><math display="block">p_a(j|i, l_e, l_f) \leftarrow \frac{1}{\lambda_{i, l_e, l_f}} \sum_{k}\frac{t(e_{i}^{(k)}| f_{j}^{(k)})p_a(j | i, l_e, l_f) \delta(e_x, e_i^{(k)})\delta(f_y, f_{j}^{(k)})\delta(l_e, l_e^{(k)})\delta(l_f, l_f^{(k)})}{\sum_{j'}t(e_i^{(k)}|f_{j'}^{(k)})p_a(j' | i, l_e, l_f)}</math>where <math>\lambda</math> are still normalization factors. See section 4.4.1<ref name=":0" /> of for a derivation and an algorithm.
== Model 3 ==
The fertility problem is addressed in IBM Model 3. The fertility is modeled using probability distribution defined as:
Line 44 ⟶ 107:
The number of inserted words depends on sentence length. This is why the NULL token insertion is modeled as an additional step: the fertility step. It increases the IBM Model 3 translation process to four steps:
[[File:IBM models 03.jpg|none]]
The last step is called distortion instead of alignment because it is possible to produce the same translation with the same alignment in different ways. For example, in the above example, we have another way to get the same alignment:<ref>{{Cite conference | author = Wołk K., Marasek K. | year = 2014 | title = Polish-English Speech Statistical Machine Translation Systems for the IWSLT 2014 | arxiv = 1509.08874 | conference = Proceedings of the 11th International Workshop on Spoken Language Translation, Lake Tahoe, USA }}</ref>
* ja NULL nie pôjde tak <u>do do</u> domu
* I do not go <u>the to</u> house
* I do not go to the house
IBM Model 3 can be mathematically expressed as:
:<math>P(S\mid E,A)=\prod_{i=1}^{I} \Phi_i!n(\Phi \mid e_j)*\prod_{j=1}^{J}t(f_j \mid e_{a_j})*\prod_{j:a(j)\neq 0}^{J}d(j
where <math>\Phi_i</math> represents the fertility of <math>e_i</math>, each source word <math>s</math> is assigned a fertility distribution <math>n</math>, and <math>I</math> and <math>J</math> refer to the absolute lengths of the target and source sentences, respectively.<ref>FERNÁNDEZ, Pablo Malvar. Improving Word-to-word Alignments Using Morphological Information. 2008. PhD Thesis. San Diego State University.</ref>
See section 4.4.2<ref name=":0" /> of for a derivation and an algorithm.
== Model 4 ==
Line 66 ⟶ 135:
== Model 5 ==
IBM Model 5 reformulates IBM Model 4 by enhancing the alignment model with more training parameters in order to overcome the model deficiency.<ref>KNIGHT, Kevin. A statistical MT tutorial workbook. Manuscript prepared for the 1999 JHU Summer Workshop, 1999.</ref> During the translation in Model 3 and Model 4 there are no heuristics that would prohibit the placement of an output word in a position already taken. In Model 5 it is important to place words only in free positions. It is done by tracking the number of free positions and allowing placement only in such positions. The distortion model is similar to IBM Model 4, but it is based on free positions. If <math>v_j</math> denotes the number of free positions in the output, the IBM Model 5 distortion probabilities would be defined as:<ref
For the initial word in the cept: <math>d_1(v_j\lor B(e_j),v_{\odot i-1},v_{max})</math>
Line 72 ⟶ 141:
For additional words: <math>d_1(v_{j}-v_{\pi_{i,k-1}}\lor B(e_j),v_{max'})</math>
The alignment models that use first-order dependencies like the HMM or IBM Models 4 and 5 produce better results than the other alignment methods. The main idea of HMM is to predict the distance between subsequent source language positions. On the other hand, IBM Model 4 tries to predict the distance between subsequent target language positions. Since it was expected to achieve better alignment quality when using both types of such dependencies, HMM and Model 4 were combined in a log-linear manner in Model 6 as follows:<ref>{{cite web | url = http://people.cs.kuleuven.be/~ivan.vulic/Files/TASOA.pdf | author = Vulić I. | title = Term Alignment. State of the Art Overview | year = 2010 | publisher = Katholieke Universiteit Leuven |
:<math>p_6(f,a\lor e)= \frac{p_4(f,a\lor e)^\alpha*p_{HMM}(f,a\lor e)}{\sum_{a',f'} p_4(f',a'\lor e)^\alpha*p_{HMM}(f',a'\lor e)}</math>
Line 80 ⟶ 149:
:<math>p_6(f,a\lor e)=\frac{\prod_{k=1}^{K}p_k(f,a\lor e)^{\alpha_{k}}}{\sum_{a',f'}\prod_{k=1}^{K}p_k(f',a'\mid e)^{\alpha_{k}}}</math>
The log-linear combination is used instead of linear combination because the <math>P_r (f, a \mid e)</math> values are typically different in terms of their orders of magnitude for HMM and IBM Model 4.<ref>{{cite journal | last1 = Wołk | first1 = K. | title = Noisy-Parallel and Comparable Corpora Filtering Methodology for the Extraction of Bi-Lingual Equivalent Data at Sentence Level | journal = Computer Science | volume = 16 | year = 2015 | issue =
== References ==
{{reflist}}
== Further reading ==
* {{Cite journal |last=Knight |first=Kevin |date=1997-12-15 |title=Automating Knowledge Acquisition for Machine Translation |url=https://ojs.aaai.org/aimagazine/index.php/aimagazine/article/view/1323 |journal=AI Magazine |language=en |volume=18 |issue=4 |pages=81 |doi=10.1609/aimag.v18i4.1323 |issn=2371-9621}}
* Knight, Kevin. "[https://web.archive.org/web/20231223235443/http://www.snlp.de/prescher/teaching/2007/StatisticalNLP/bib/1999jhu.knight.pdf A statistical MT tutorial workbook]." ''Prepared for the 1999 JHU Summer Workshop''. 1999.
[[Category:Machine translation]]
| |||