# Natural Language Toolkit: IBM Model 5
#
# Copyright (C) 2001-2023 NLTK Project
# Author: Tah Wei Hoon <hoon.tw@gmail.com>
# URL: <https://www.nltk.org/>
# For license information, see LICENSE.TXT
"""
Translation model that keeps track of vacant positions in the target
sentence to decide where to place translated words.
Translation can be viewed as a process where each word in the source
sentence is stepped through sequentially, generating translated words
for each source word. The target sentence can be viewed as being made
up of ``m`` empty slots initially, which gradually fill up as generated
words are placed in them.
Models 3 and 4 use distortion probabilities to decide how to place
translated words. For simplicity, these models ignore the history of
which slots have already been occupied with translated words.
Consider the placement of the last translated word: there is only one
empty slot left in the target sentence, so the distortion probability
should be 1.0 for that position and 0.0 everywhere else. However, the
distortion probabilities for Models 3 and 4 are set up such that all
positions are under consideration.
IBM Model 5 fixes this deficiency by accounting for occupied slots
during translation. It introduces the vacancy function v(j), the number
of vacancies up to, and including, position j in the target sentence.
Terminology
-----------
:Maximum vacancy:
The number of valid slots that a word can be placed in.
This is not necessarily the same as the number of vacant slots.
For example, if a tablet contains more than one word, the head word
cannot be placed at the last vacant slot because there will be no
space for the other words in the tablet. The number of valid slots
has to take into account the length of the tablet.
Non-head words cannot be placed before the head word, so vacancies
to the left of the head word are ignored.
:Vacancy difference:
For a head word: (v(j) - v(center of previous cept))
Can be positive or negative.
For a non-head word: (v(j) - v(position of previously placed word))
Always positive, because successive words in a tablet are assumed to
appear to the right of the previous word.
Positioning of target words fall under three cases:
1. Words generated by NULL are distributed uniformly
2. For a head word t, its position is modeled by the probability
v_head(dv | max_v,word_class_t(t))
3. For a non-head word t, its position is modeled by the probability
v_non_head(dv | max_v,word_class_t(t))
dv and max_v are defined differently for head and non-head words.
The EM algorithm used in Model 5 is:
:E step: In the training data, collect counts, weighted by prior
probabilities.
- (a) count how many times a source language word is translated
into a target language word
- (b) for a particular word class and maximum vacancy, count how
many times a head word and the previous cept's center have
a particular difference in number of vacancies
- (b) for a particular word class and maximum vacancy, count how
many times a non-head word and the previous target word
have a particular difference in number of vacancies
- (d) count how many times a source word is aligned to phi number
of target words
- (e) count how many times NULL is aligned to a target word
:M step: Estimate new probabilities based on the counts from the E step
Like Model 4, there are too many possible alignments to consider. Thus,
a hill climbing approach is used to sample good candidates. In addition,
pruning is used to weed out unlikely alignments based on Model 4 scores.
Notations
---------
:i: Position in the source sentence
Valid values are 0 (for NULL), 1, 2, ..., length of source sentence
:j: Position in the target sentence
Valid values are 1, 2, ..., length of target sentence
:l: Number of words in the source sentence, excluding NULL
:m: Number of words in the target sentence
:s: A word in the source language
:t: A word in the target language
:phi: Fertility, the number of target words produced by a source word
:p1: Probability that a target word produced by a source word is
accompanied by another target word that is aligned to NULL
:p0: 1 - p1
:max_v: Maximum vacancy
:dv: Vacancy difference, Δv
The definition of v_head here differs from GIZA++, section 4.7 of
[Brown et al., 1993], and [Koehn, 2010]. In the latter cases, v_head is
v_head(v(j) | v(center of previous cept),max_v,word_class(t)).
Here, we follow appendix B of [Brown et al., 1993] and combine v(j) with
v(center of previous cept) to obtain dv:
v_head(v(j) - v(center of previous cept) | max_v,word_class(t)).
References
----------
Philipp Koehn. 2010. Statistical Machine Translation.
Cambridge University Press, New York.
Peter E Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and
Robert L. Mercer. 1993. The Mathematics of Statistical Machine
Translation: Parameter Estimation. Computational Linguistics, 19 (2),
263-311.
"""
import warnings
from collections import defaultdict
from math import factorial
from nltk.translate import AlignedSent, Alignment, IBMModel, IBMModel4
from nltk.translate.ibm_model import Counts, longest_target_sentence_length
[docs]class IBMModel5(IBMModel):
"""
Translation model that keeps track of vacant positions in the target
sentence to decide where to place translated words
>>> bitext = []
>>> bitext.append(AlignedSent(['klein', 'ist', 'das', 'haus'], ['the', 'house', 'is', 'small']))
>>> bitext.append(AlignedSent(['das', 'haus', 'war', 'ja', 'groß'], ['the', 'house', 'was', 'big']))
>>> bitext.append(AlignedSent(['das', 'buch', 'ist', 'ja', 'klein'], ['the', 'book', 'is', 'small']))
>>> bitext.append(AlignedSent(['ein', 'haus', 'ist', 'klein'], ['a', 'house', 'is', 'small']))
>>> bitext.append(AlignedSent(['das', 'haus'], ['the', 'house']))
>>> bitext.append(AlignedSent(['das', 'buch'], ['the', 'book']))
>>> bitext.append(AlignedSent(['ein', 'buch'], ['a', 'book']))
>>> bitext.append(AlignedSent(['ich', 'fasse', 'das', 'buch', 'zusammen'], ['i', 'summarize', 'the', 'book']))
>>> bitext.append(AlignedSent(['fasse', 'zusammen'], ['summarize']))
>>> src_classes = {'the': 0, 'a': 0, 'small': 1, 'big': 1, 'house': 2, 'book': 2, 'is': 3, 'was': 3, 'i': 4, 'summarize': 5 }
>>> trg_classes = {'das': 0, 'ein': 0, 'haus': 1, 'buch': 1, 'klein': 2, 'groß': 2, 'ist': 3, 'war': 3, 'ja': 4, 'ich': 5, 'fasse': 6, 'zusammen': 6 }
>>> ibm5 = IBMModel5(bitext, 5, src_classes, trg_classes)
>>> print(round(ibm5.head_vacancy_table[1][1][1], 3))
1.0
>>> print(round(ibm5.head_vacancy_table[2][1][1], 3))
0.0
>>> print(round(ibm5.non_head_vacancy_table[3][3][6], 3))
1.0
>>> print(round(ibm5.fertility_table[2]['summarize'], 3))
1.0
>>> print(round(ibm5.fertility_table[1]['book'], 3))
1.0
>>> print(round(ibm5.p1, 3))
0.033
>>> test_sentence = bitext[2]
>>> test_sentence.words
['das', 'buch', 'ist', 'ja', 'klein']
>>> test_sentence.mots
['the', 'book', 'is', 'small']
>>> test_sentence.alignment
Alignment([(0, 0), (1, 1), (2, 2), (3, None), (4, 3)])
"""
MIN_SCORE_FACTOR = 0.2
"""
Alignments with scores below this factor are pruned during sampling
"""
[docs] def __init__(
self,
sentence_aligned_corpus,
iterations,
source_word_classes,
target_word_classes,
probability_tables=None,
):
"""
Train on ``sentence_aligned_corpus`` and create a lexical
translation model, vacancy models, a fertility model, and a
model for generating NULL-aligned words.
Translation direction is from ``AlignedSent.mots`` to
``AlignedSent.words``.
:param sentence_aligned_corpus: Sentence-aligned parallel corpus
:type sentence_aligned_corpus: list(AlignedSent)
:param iterations: Number of iterations to run training algorithm
:type iterations: int
:param source_word_classes: Lookup table that maps a source word
to its word class, the latter represented by an integer id
:type source_word_classes: dict[str]: int
:param target_word_classes: Lookup table that maps a target word
to its word class, the latter represented by an integer id
:type target_word_classes: dict[str]: int
:param probability_tables: Optional. Use this to pass in custom
probability values. If not specified, probabilities will be
set to a uniform distribution, or some other sensible value.
If specified, all the following entries must be present:
``translation_table``, ``alignment_table``,
``fertility_table``, ``p1``, ``head_distortion_table``,
``non_head_distortion_table``, ``head_vacancy_table``,
``non_head_vacancy_table``. See ``IBMModel``, ``IBMModel4``,
and ``IBMModel5`` for the type and purpose of these tables.
:type probability_tables: dict[str]: object
"""
super().__init__(sentence_aligned_corpus)
self.reset_probabilities()
self.src_classes = source_word_classes
self.trg_classes = target_word_classes
if probability_tables is None:
# Get probabilities from IBM model 4
ibm4 = IBMModel4(
sentence_aligned_corpus,
iterations,
source_word_classes,
target_word_classes,
)
self.translation_table = ibm4.translation_table
self.alignment_table = ibm4.alignment_table
self.fertility_table = ibm4.fertility_table
self.p1 = ibm4.p1
self.head_distortion_table = ibm4.head_distortion_table
self.non_head_distortion_table = ibm4.non_head_distortion_table
self.set_uniform_probabilities(sentence_aligned_corpus)
else:
# Set user-defined probabilities
self.translation_table = probability_tables["translation_table"]
self.alignment_table = probability_tables["alignment_table"]
self.fertility_table = probability_tables["fertility_table"]
self.p1 = probability_tables["p1"]
self.head_distortion_table = probability_tables["head_distortion_table"]
self.non_head_distortion_table = probability_tables[
"non_head_distortion_table"
]
self.head_vacancy_table = probability_tables["head_vacancy_table"]
self.non_head_vacancy_table = probability_tables["non_head_vacancy_table"]
for n in range(0, iterations):
self.train(sentence_aligned_corpus)
[docs] def reset_probabilities(self):
super().reset_probabilities()
self.head_vacancy_table = defaultdict(
lambda: defaultdict(lambda: defaultdict(lambda: self.MIN_PROB))
)
"""
dict[int][int][int]: float. Probability(vacancy difference |
number of remaining valid positions,target word class).
Values accessed as ``head_vacancy_table[dv][v_max][trg_class]``.
"""
self.non_head_vacancy_table = defaultdict(
lambda: defaultdict(lambda: defaultdict(lambda: self.MIN_PROB))
)
"""
dict[int][int][int]: float. Probability(vacancy difference |
number of remaining valid positions,target word class).
Values accessed as ``non_head_vacancy_table[dv][v_max][trg_class]``.
"""
[docs] def train(self, parallel_corpus):
counts = Model5Counts()
for aligned_sentence in parallel_corpus:
l = len(aligned_sentence.mots)
m = len(aligned_sentence.words)
# Sample the alignment space
sampled_alignments, best_alignment = self.sample(aligned_sentence)
# Record the most probable alignment
aligned_sentence.alignment = Alignment(
best_alignment.zero_indexed_alignment()
)
# E step (a): Compute normalization factors to weigh counts
total_count = self.prob_of_alignments(sampled_alignments)
# E step (b): Collect counts
for alignment_info in sampled_alignments:
count = self.prob_t_a_given_s(alignment_info)
normalized_count = count / total_count
for j in range(1, m + 1):
counts.update_lexical_translation(
normalized_count, alignment_info, j
)
slots = Slots(m)
for i in range(1, l + 1):
counts.update_vacancy(
normalized_count, alignment_info, i, self.trg_classes, slots
)
counts.update_null_generation(normalized_count, alignment_info)
counts.update_fertility(normalized_count, alignment_info)
# M step: Update probabilities with maximum likelihood estimates
# If any probability is less than MIN_PROB, clamp it to MIN_PROB
existing_alignment_table = self.alignment_table
self.reset_probabilities()
self.alignment_table = existing_alignment_table # don't retrain
self.maximize_lexical_translation_probabilities(counts)
self.maximize_vacancy_probabilities(counts)
self.maximize_fertility_probabilities(counts)
self.maximize_null_generation_probabilities(counts)
[docs] def sample(self, sentence_pair):
"""
Sample the most probable alignments from the entire alignment
space according to Model 4
Note that Model 4 scoring is used instead of Model 5 because the
latter is too expensive to compute.
First, determine the best alignment according to IBM Model 2.
With this initial alignment, use hill climbing to determine the
best alignment according to a IBM Model 4. Add this
alignment and its neighbors to the sample set. Repeat this
process with other initial alignments obtained by pegging an
alignment point. Finally, prune alignments that have
substantially lower Model 4 scores than the best alignment.
:param sentence_pair: Source and target language sentence pair
to generate a sample of alignments from
:type sentence_pair: AlignedSent
:return: A set of best alignments represented by their ``AlignmentInfo``
and the best alignment of the set for convenience
:rtype: set(AlignmentInfo), AlignmentInfo
"""
sampled_alignments, best_alignment = super().sample(sentence_pair)
return self.prune(sampled_alignments), best_alignment
[docs] def prune(self, alignment_infos):
"""
Removes alignments from ``alignment_infos`` that have
substantially lower Model 4 scores than the best alignment
:return: Pruned alignments
:rtype: set(AlignmentInfo)
"""
alignments = []
best_score = 0
for alignment_info in alignment_infos:
score = IBMModel4.model4_prob_t_a_given_s(alignment_info, self)
best_score = max(score, best_score)
alignments.append((alignment_info, score))
threshold = IBMModel5.MIN_SCORE_FACTOR * best_score
alignments = [a[0] for a in alignments if a[1] > threshold]
return set(alignments)
[docs] def hillclimb(self, alignment_info, j_pegged=None):
"""
Starting from the alignment in ``alignment_info``, look at
neighboring alignments iteratively for the best one, according
to Model 4
Note that Model 4 scoring is used instead of Model 5 because the
latter is too expensive to compute.
There is no guarantee that the best alignment in the alignment
space will be found, because the algorithm might be stuck in a
local maximum.
:param j_pegged: If specified, the search will be constrained to
alignments where ``j_pegged`` remains unchanged
:type j_pegged: int
:return: The best alignment found from hill climbing
:rtype: AlignmentInfo
"""
alignment = alignment_info # alias with shorter name
max_probability = IBMModel4.model4_prob_t_a_given_s(alignment, self)
while True:
old_alignment = alignment
for neighbor_alignment in self.neighboring(alignment, j_pegged):
neighbor_probability = IBMModel4.model4_prob_t_a_given_s(
neighbor_alignment, self
)
if neighbor_probability > max_probability:
alignment = neighbor_alignment
max_probability = neighbor_probability
if alignment == old_alignment:
# Until there are no better alignments
break
alignment.score = max_probability
return alignment
[docs] def prob_t_a_given_s(self, alignment_info):
"""
Probability of target sentence and an alignment given the
source sentence
"""
probability = 1.0
MIN_PROB = IBMModel.MIN_PROB
slots = Slots(len(alignment_info.trg_sentence) - 1)
def null_generation_term():
# Binomial distribution: B(m - null_fertility, p1)
value = 1.0
p1 = self.p1
p0 = 1 - p1
null_fertility = alignment_info.fertility_of_i(0)
m = len(alignment_info.trg_sentence) - 1
value *= pow(p1, null_fertility) * pow(p0, m - 2 * null_fertility)
if value < MIN_PROB:
return MIN_PROB
# Combination: (m - null_fertility) choose null_fertility
for i in range(1, null_fertility + 1):
value *= (m - null_fertility - i + 1) / i
return value
def fertility_term():
value = 1.0
src_sentence = alignment_info.src_sentence
for i in range(1, len(src_sentence)):
fertility = alignment_info.fertility_of_i(i)
value *= (
factorial(fertility)
* self.fertility_table[fertility][src_sentence[i]]
)
if value < MIN_PROB:
return MIN_PROB
return value
def lexical_translation_term(j):
t = alignment_info.trg_sentence[j]
i = alignment_info.alignment[j]
s = alignment_info.src_sentence[i]
return self.translation_table[t][s]
def vacancy_term(i):
value = 1.0
tablet = alignment_info.cepts[i]
tablet_length = len(tablet)
total_vacancies = slots.vacancies_at(len(slots))
# case 1: NULL-aligned words
if tablet_length == 0:
return value
# case 2: head word
j = tablet[0]
previous_cept = alignment_info.previous_cept(j)
previous_center = alignment_info.center_of_cept(previous_cept)
dv = slots.vacancies_at(j) - slots.vacancies_at(previous_center)
max_v = total_vacancies - tablet_length + 1
trg_class = self.trg_classes[alignment_info.trg_sentence[j]]
value *= self.head_vacancy_table[dv][max_v][trg_class]
slots.occupy(j) # mark position as occupied
total_vacancies -= 1
if value < MIN_PROB:
return MIN_PROB
# case 3: non-head words
for k in range(1, tablet_length):
previous_position = tablet[k - 1]
previous_vacancies = slots.vacancies_at(previous_position)
j = tablet[k]
dv = slots.vacancies_at(j) - previous_vacancies
max_v = total_vacancies - tablet_length + k + 1 - previous_vacancies
trg_class = self.trg_classes[alignment_info.trg_sentence[j]]
value *= self.non_head_vacancy_table[dv][max_v][trg_class]
slots.occupy(j) # mark position as occupied
total_vacancies -= 1
if value < MIN_PROB:
return MIN_PROB
return value
# end nested functions
# Abort computation whenever probability falls below MIN_PROB at
# any point, since MIN_PROB can be considered as zero
probability *= null_generation_term()
if probability < MIN_PROB:
return MIN_PROB
probability *= fertility_term()
if probability < MIN_PROB:
return MIN_PROB
for j in range(1, len(alignment_info.trg_sentence)):
probability *= lexical_translation_term(j)
if probability < MIN_PROB:
return MIN_PROB
for i in range(1, len(alignment_info.src_sentence)):
probability *= vacancy_term(i)
if probability < MIN_PROB:
return MIN_PROB
return probability
[docs] def maximize_vacancy_probabilities(self, counts):
MIN_PROB = IBMModel.MIN_PROB
head_vacancy_table = self.head_vacancy_table
for dv, max_vs in counts.head_vacancy.items():
for max_v, trg_classes in max_vs.items():
for t_cls in trg_classes:
estimate = (
counts.head_vacancy[dv][max_v][t_cls]
/ counts.head_vacancy_for_any_dv[max_v][t_cls]
)
head_vacancy_table[dv][max_v][t_cls] = max(estimate, MIN_PROB)
non_head_vacancy_table = self.non_head_vacancy_table
for dv, max_vs in counts.non_head_vacancy.items():
for max_v, trg_classes in max_vs.items():
for t_cls in trg_classes:
estimate = (
counts.non_head_vacancy[dv][max_v][t_cls]
/ counts.non_head_vacancy_for_any_dv[max_v][t_cls]
)
non_head_vacancy_table[dv][max_v][t_cls] = max(estimate, MIN_PROB)
[docs]class Model5Counts(Counts):
"""
Data object to store counts of various parameters during training.
Includes counts for vacancies.
"""
[docs] def __init__(self):
super().__init__()
self.head_vacancy = defaultdict(
lambda: defaultdict(lambda: defaultdict(lambda: 0.0))
)
self.head_vacancy_for_any_dv = defaultdict(lambda: defaultdict(lambda: 0.0))
self.non_head_vacancy = defaultdict(
lambda: defaultdict(lambda: defaultdict(lambda: 0.0))
)
self.non_head_vacancy_for_any_dv = defaultdict(lambda: defaultdict(lambda: 0.0))
[docs] def update_vacancy(self, count, alignment_info, i, trg_classes, slots):
"""
:param count: Value to add to the vacancy counts
:param alignment_info: Alignment under consideration
:param i: Source word position under consideration
:param trg_classes: Target word classes
:param slots: Vacancy states of the slots in the target sentence.
Output parameter that will be modified as new words are placed
in the target sentence.
"""
tablet = alignment_info.cepts[i]
tablet_length = len(tablet)
total_vacancies = slots.vacancies_at(len(slots))
# case 1: NULL aligned words
if tablet_length == 0:
return # ignore zero fertility words
# case 2: head word
j = tablet[0]
previous_cept = alignment_info.previous_cept(j)
previous_center = alignment_info.center_of_cept(previous_cept)
dv = slots.vacancies_at(j) - slots.vacancies_at(previous_center)
max_v = total_vacancies - tablet_length + 1
trg_class = trg_classes[alignment_info.trg_sentence[j]]
self.head_vacancy[dv][max_v][trg_class] += count
self.head_vacancy_for_any_dv[max_v][trg_class] += count
slots.occupy(j) # mark position as occupied
total_vacancies -= 1
# case 3: non-head words
for k in range(1, tablet_length):
previous_position = tablet[k - 1]
previous_vacancies = slots.vacancies_at(previous_position)
j = tablet[k]
dv = slots.vacancies_at(j) - previous_vacancies
max_v = total_vacancies - tablet_length + k + 1 - previous_vacancies
trg_class = trg_classes[alignment_info.trg_sentence[j]]
self.non_head_vacancy[dv][max_v][trg_class] += count
self.non_head_vacancy_for_any_dv[max_v][trg_class] += count
slots.occupy(j) # mark position as occupied
total_vacancies -= 1
[docs]class Slots:
"""
Represents positions in a target sentence. Used to keep track of
which slot (position) is occupied.
"""
[docs] def __init__(self, target_sentence_length):
self._slots = [False] * (target_sentence_length + 1) # 1-indexed
[docs] def occupy(self, position):
"""
:return: Mark slot at ``position`` as occupied
"""
self._slots[position] = True
[docs] def vacancies_at(self, position):
"""
:return: Number of vacant slots up to, and including, ``position``
"""
vacancies = 0
for k in range(1, position + 1):
if not self._slots[k]:
vacancies += 1
return vacancies
def __len__(self):
return len(self._slots) - 1 # exclude dummy zeroeth element