natural language toolkit ibm model 1 c 20012013 nltk project chin yee lee c lee32student unimelb edu au hengfeng li hengfeng12345gmail com ruxin hou r houstudent unimelb edu au calvin tanujaya lim c tanujayalimgmail com based on earlier version by will zhang wilzzhagmail com guan gui gguistudent unimelb edu au url https www nltk org for license information see license txt lexical translation model that ignores word order in ibm model 1 word order is ignored for simplicity as long as the word alignments are equivalent it doesn t matter where the word occurs in the source or target sentence thus the following three alignments are equally likely source je mange du jambon target i eat some ham alignment 0 0 1 1 2 2 3 3 source je mange du jambon target some ham eat i alignment 0 2 1 3 2 1 3 1 source du jambon je mange target eat i some ham alignment 0 3 1 2 2 0 3 1 note that an alignment is represented here as wordindexintarget wordindexinsource the em algorithm used in model 1 is e step in the training data count how many times a source language word is translated into a target language word weighted by the prior probability of the translation m step estimate the new probability of translation based on the counts from the expectation 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 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 ignores 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 ibm1 ibmmodel1bitext 5 printroundibm1 translationtable buch book 3 0 889 printroundibm1 translationtable das book 3 0 062 printroundibm1 translationtable buch none 3 0 113 printroundibm1 translationtable ja none 3 0 073 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 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 the following entry must be present translationtable see ibmmodel for the type and purpose of this table type probabilitytables dictstr object set userdefined probabilities e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimate 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 word t in the target sentence is aligned to word s in the source sentence 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 natural language toolkit ibm model 1 c 2001 2013 nltk project chin yee lee c lee32 student unimelb edu au hengfeng li hengfeng12345 gmail com ruxin hou r hou student unimelb edu au calvin tanujaya lim c tanujayalim gmail com based on earlier version by will zhang wilzzha gmail com guan gui ggui student unimelb edu au url https www nltk org for license information see license txt lexical translation model that ignores word order in ibm model 1 word order is ignored for simplicity as long as the word alignments are equivalent it doesn t matter where the word occurs in the source or target sentence thus the following three alignments are equally likely source je mange du jambon target i eat some ham alignment 0 0 1 1 2 2 3 3 source je mange du jambon target some ham eat i alignment 0 2 1 3 2 1 3 1 source du jambon je mange target eat i some ham alignment 0 3 1 2 2 0 3 1 note that an alignment is represented here as word_index_in_target word_index_in_source the em algorithm used in model 1 is e step in the training data count how many times a source language word is translated into a target language word weighted by the prior probability of the translation m step estimate the new probability of translation based on the counts from the expectation 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 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 ignores 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 ibm1 ibmmodel1 bitext 5 print round ibm1 translation_table buch book 3 0 889 print round ibm1 translation_table das book 3 0 062 print round ibm1 translation_table buch none 3 0 113 print round ibm1 translation_table ja none 3 0 073 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 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 the following entry must be present translation_table see ibmmodel for the type and purpose of this table type probability_tables dict str object set user defined probabilities e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimate 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 word t in the target sentence is aligned to word s in the source 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 prefer newer word in case of tie
import warnings
from collections import defaultdict

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


class IBMModel1(IBMModel):
    

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

        if probability_tables is None:
            self.set_uniform_probabilities(sentence_aligned_corpus)
        else:
            
            self.translation_table = probability_tables["translation_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):
        initial_prob = 1 / len(self.trg_vocab)
        if initial_prob < IBMModel.MIN_PROB:
            warnings.warn(
                "Target language vocabulary is too large ("
                + str(len(self.trg_vocab))
                + " words). "
                "Results may be less accurate."
            )

        for t in self.trg_vocab:
            self.translation_table[t] = defaultdict(lambda: initial_prob)

    def train(self, parallel_corpus):
        counts = Counts()
        for aligned_sentence in parallel_corpus:
            trg_sentence = aligned_sentence.words
            src_sentence = [None] + aligned_sentence.mots

            
            total_count = self.prob_all_alignments(src_sentence, trg_sentence)

            
            for t in trg_sentence:
                for s in src_sentence:
                    count = self.prob_alignment_point(s, t)
                    normalized_count = count / total_count[t]
                    counts.t_given_s[t][s] += normalized_count
                    counts.any_t_given_s[s] += normalized_count

        
        self.maximize_lexical_translation_probabilities(counts)

    def prob_all_alignments(self, src_sentence, trg_sentence):
        
        alignment_prob_for_t = defaultdict(lambda: 0.0)
        for t in trg_sentence:
            for s in src_sentence:
                alignment_prob_for_t[t] += self.prob_alignment_point(s, t)
        return alignment_prob_for_t

    def prob_alignment_point(self, s, t):
        
        return self.translation_table[t][s]

    def prob_t_a_given_s(self, alignment_info):
        
        prob = 1.0

        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]

        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 = []

        for j, trg_word in enumerate(sentence_pair.words):
            
            best_prob = max(self.translation_table[trg_word][None], 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]
                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)