natural language toolkit ibm model 2 c 20012013 nltk project s chin yee lee hengfeng li ruxin hou calvin tanujaya lim url https www nltk org for license information see license txt lexical translation model that considers word order ibm model 2 improves on model 1 by accounting for word order an alignment probability is introduced ai j l m which predicts a source word position given its aligned target word s position the em algorithm used in model 2 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 count how many times a particular position in the source sentence is aligned to a particular position in the target sentence m step estimate new probabilities based on the counts from the e step 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 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 263311 lexical translation model that considers word order bitext bitext appendalignedsent klein ist das haus the house is small bitext appendalignedsent das haus ist ja gro the house is big bitext appendalignedsent das buch ist ja klein the book is small bitext appendalignedsent das haus the house bitext appendalignedsent das buch the book bitext appendalignedsent ein buch a book ibm2 ibmmodel2bitext 5 printroundibm2 translationtable buch book 3 1 0 printroundibm2 translationtable das book 3 0 0 printroundibm2 translationtable buch none 3 0 0 printroundibm2 translationtable ja none 3 0 0 printroundibm2 alignmenttable1122 3 0 939 printroundibm2 alignmenttable1222 3 0 0 printroundibm2 alignmenttable2245 3 1 0 testsentence bitext2 testsentence words das buch ist ja klein testsentence mots the book is small testsentence alignment alignment0 0 1 1 2 2 3 2 4 3 train on sentencealignedcorpus and create a lexical translation model and an alignment model translation direction is from alignedsent mots to alignedsent words param sentencealignedcorpus sentencealigned parallel corpus type sentencealignedcorpus listalignedsent param iterations number of iterations to run training algorithm type iterations int param probabilitytables 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 translationtable alignmenttable see ibmmodel for the type and purpose of these tables type probabilitytables dictstr object get translation probabilities from ibm model 1 run more iterations of training for model 1 since it is faster than model 2 set userdefined probabilities ai j l m 1 l1 for all i j l m e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimates computes the probability of all possible word alignments expressed as a marginal distribution over target words t each entry in the return value represents the contribution to the total alignment probability by the target word t to obtain probabilityalignment srcsentence trgsentence simply sum the entries in the return value return probability of t for all s in srcsentence rtype dictstr float probability that position j in trgsentence is aligned to position i in the srcsentence probability of target sentence and an alignment given the source sentence determines the best word alignment for one sentence pair from the corpus that the model was trained on the best alignment will be set in sentencepair when the method returns in contrast with the internal implementation of ibm models the word indices in the alignment are zero indexed not oneindexed param sentencepair a sentence in the source language and its counterpart sentence in the target language type sentencepair alignedsent initialize trgword to align with the null token data object to store counts of various parameters during training includes counts for alignment natural language toolkit ibm model 2 c 2001 2013 nltk project s chin yee lee hengfeng li ruxin hou calvin tanujaya lim url https www nltk org for license information see license txt lexical translation model that considers word order ibm model 2 improves on model 1 by accounting for word order an alignment probability is introduced a i j l m which predicts a source word position given its aligned target word s position the em algorithm used in model 2 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 count how many times a particular position in the source sentence is aligned to a particular position in the target sentence m step estimate new probabilities based on the counts from the e step 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 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 lexical translation model that considers word order bitext bitext append alignedsent klein ist das haus the house is small bitext append alignedsent das haus ist ja groß the house is big bitext append alignedsent das buch ist ja klein the book is small bitext append alignedsent das haus the house bitext append alignedsent das buch the book bitext append alignedsent ein buch a book ibm2 ibmmodel2 bitext 5 print round ibm2 translation_table buch book 3 1 0 print round ibm2 translation_table das book 3 0 0 print round ibm2 translation_table buch none 3 0 0 print round ibm2 translation_table ja none 3 0 0 print round ibm2 alignment_table 1 1 2 2 3 0 939 print round ibm2 alignment_table 1 2 2 2 3 0 0 print round ibm2 alignment_table 2 2 4 5 3 1 0 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 2 4 3 train on sentence_aligned_corpus and create a lexical translation model and an alignment model 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 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 see ibmmodel for the type and purpose of these tables type probability_tables dict str object get translation probabilities from ibm model 1 run more iterations of training for model 1 since it is faster than model 2 set user defined probabilities a i j l m 1 l 1 for all i j l m 1 indexed e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimates computes the probability of all possible word alignments expressed as a marginal distribution over target words t each entry in the return value represents the contribution to the total alignment probability by the target word t to obtain probability alignment src_sentence trg_sentence simply sum the entries in the return value return probability of t for all s in src_sentence rtype dict str float probability that position j in trg_sentence is aligned to position i in the src_sentence probability of target sentence and an alignment given the source sentence skip the dummy zeroeth element determines the best word alignment for one sentence pair from the corpus that the model was trained on the best alignment will be set in sentence_pair when the method returns in contrast with the internal implementation of ibm models the word indices in the alignment are zero indexed not one indexed param sentence_pair a sentence in the source language and its counterpart sentence in the target language type sentence_pair alignedsent initialize trg_word to align with the null token data object to store counts of various parameters during training includes counts for alignment
import warnings
from collections import defaultdict

from nltk.translate import AlignedSent, Alignment, IBMModel, IBMModel1
from nltk.translate.ibm_model import Counts


class IBMModel2(IBMModel):
    

    def __init__(self, sentence_aligned_corpus, iterations, probability_tables=None):
        
        super().__init__(sentence_aligned_corpus)

        if probability_tables is None:
            
            
            
            ibm1 = IBMModel1(sentence_aligned_corpus, 2 * iterations)
            self.translation_table = ibm1.translation_table
            self.set_uniform_probabilities(sentence_aligned_corpus)
        else:
            
            self.translation_table = probability_tables["translation_table"]
            self.alignment_table = probability_tables["alignment_table"]

        for n in range(0, iterations):
            self.train(sentence_aligned_corpus)

        self.align_all(sentence_aligned_corpus)

    def set_uniform_probabilities(self, sentence_aligned_corpus):
        
        l_m_combinations = set()
        for aligned_sentence in sentence_aligned_corpus:
            l = len(aligned_sentence.mots)
            m = len(aligned_sentence.words)
            if (l, m) not in l_m_combinations:
                l_m_combinations.add((l, m))
                initial_prob = 1 / (l + 1)
                if initial_prob < IBMModel.MIN_PROB:
                    warnings.warn(
                        "A source sentence is too long ("
                        + str(l)
                        + " words). Results may be less accurate."
                    )

                for i in range(0, l + 1):
                    for j in range(1, m + 1):
                        self.alignment_table[i][j][l][m] = initial_prob

    def train(self, parallel_corpus):
        counts = Model2Counts()
        for aligned_sentence in parallel_corpus:
            src_sentence = [None] + aligned_sentence.mots
            trg_sentence = ["UNUSED"] + aligned_sentence.words  
            l = len(aligned_sentence.mots)
            m = len(aligned_sentence.words)

            
            total_count = self.prob_all_alignments(src_sentence, trg_sentence)

            
            for j in range(1, m + 1):
                t = trg_sentence[j]
                for i in range(0, l + 1):
                    s = src_sentence[i]
                    count = self.prob_alignment_point(i, j, src_sentence, trg_sentence)
                    normalized_count = count / total_count[t]

                    counts.update_lexical_translation(normalized_count, s, t)
                    counts.update_alignment(normalized_count, i, j, l, m)

        
        self.maximize_lexical_translation_probabilities(counts)
        self.maximize_alignment_probabilities(counts)

    def maximize_alignment_probabilities(self, counts):
        MIN_PROB = IBMModel.MIN_PROB
        for i, j_s in counts.alignment.items():
            for j, src_sentence_lengths in j_s.items():
                for l, trg_sentence_lengths in src_sentence_lengths.items():
                    for m in trg_sentence_lengths:
                        estimate = (
                            counts.alignment[i][j][l][m]
                            / counts.alignment_for_any_i[j][l][m]
                        )
                        self.alignment_table[i][j][l][m] = max(estimate, MIN_PROB)

    def prob_all_alignments(self, src_sentence, trg_sentence):
        
        alignment_prob_for_t = defaultdict(lambda: 0.0)
        for j in range(1, len(trg_sentence)):
            t = trg_sentence[j]
            for i in range(0, len(src_sentence)):
                alignment_prob_for_t[t] += self.prob_alignment_point(
                    i, j, src_sentence, trg_sentence
                )
        return alignment_prob_for_t

    def prob_alignment_point(self, i, j, src_sentence, trg_sentence):
        
        l = len(src_sentence) - 1
        m = len(trg_sentence) - 1
        s = src_sentence[i]
        t = trg_sentence[j]
        return self.translation_table[t][s] * self.alignment_table[i][j][l][m]

    def prob_t_a_given_s(self, alignment_info):
        
        prob = 1.0
        l = len(alignment_info.src_sentence) - 1
        m = len(alignment_info.trg_sentence) - 1

        for j, i in enumerate(alignment_info.alignment):
            if j == 0:
                continue  
            trg_word = alignment_info.trg_sentence[j]
            src_word = alignment_info.src_sentence[i]
            prob *= (
                self.translation_table[trg_word][src_word]
                * self.alignment_table[i][j][l][m]
            )

        return max(prob, IBMModel.MIN_PROB)

    def align_all(self, parallel_corpus):
        for sentence_pair in parallel_corpus:
            self.align(sentence_pair)

    def align(self, sentence_pair):
        
        best_alignment = []

        l = len(sentence_pair.mots)
        m = len(sentence_pair.words)

        for j, trg_word in enumerate(sentence_pair.words):
            
            best_prob = (
                self.translation_table[trg_word][None]
                * self.alignment_table[0][j + 1][l][m]
            )
            best_prob = max(best_prob, IBMModel.MIN_PROB)
            best_alignment_point = None
            for i, src_word in enumerate(sentence_pair.mots):
                align_prob = (
                    self.translation_table[trg_word][src_word]
                    * self.alignment_table[i + 1][j + 1][l][m]
                )
                if align_prob >= best_prob:
                    best_prob = align_prob
                    best_alignment_point = i

            best_alignment.append((j, best_alignment_point))

        sentence_pair.alignment = Alignment(best_alignment)


class Model2Counts(Counts):
    

    def __init__(self):
        super().__init__()
        self.alignment = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: 0.0)))
        )
        self.alignment_for_any_i = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: 0.0))
        )

    def update_lexical_translation(self, count, s, t):
        self.t_given_s[t][s] += count
        self.any_t_given_s[s] += count

    def update_alignment(self, count, i, j, l, m):
        self.alignment[i][j][l][m] += count
        self.alignment_for_any_i[j][l][m] += count