Content deleted Content added
→Learning from a corpus: Dirac delta |
|||
| (19 intermediate revisions by 7 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 |
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 54 ⟶ 57:
* 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. For a detailed derivation of the algorithm, see <ref>{{Cite book |last=Koehn |first=Philipp |url=https://books.google.com/books?id=4v_Cx1wIMLkC&newbks=0&hl=en |title=Statistical Machine Translation |date=2010 |publisher=Cambridge University Press |isbn=978-0-521-87415-1 |language=en}}</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 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}
▲
In short, the EM algorithm goes as follows:<blockquote>INPUT. a corpus of English-foreign sentence pairs <math>\{(e^{(k)}, f^{(k)})\}_k</math>
Line 74 ⟶ 83:
=== 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 90 ⟶ 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.
▲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>
== Model 4 ==
Line 112 ⟶ 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 130 ⟶ 153:
== 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]]
| |||