natural language toolkit ibm model 3 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 translation model that considers how a word can be aligned to multiple words in another language ibm model 3 improves on model 2 by directly modeling the phenomenon where a word in one language may be translated into zero or more words in another this is expressed by the fertility probability nphi source word if a source word translates into more than one word it is possible to generate sentences that have the same alignment in multiple ways this is modeled by a distortion step the distortion probability dji l m predicts a target word position given its aligned source word s position the distortion probability replaces the alignment probability of model 2 the fertility probability is not applicable for null target words that align to null are assumed to be distributed uniformly in the target sentence the existence of these words is modeled by p1 the probability that a target word produced by a real source word requires another target word that is produced by null the em algorithm used in model 3 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 target sentence is aligned to a particular position in the source sentence c count how many times a source word is aligned to phi number of target words d count how many times null is aligned to a target word m step estimate new probabilities based on the counts from the e step because there are too many possible alignments only the most probable ones are considered first the best alignment is determined using prior probabilities then a hill climbing approach is used to find other good candidates 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 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 translation model that considers how a word can be aligned to multiple words in another language bitext bitext appendalignedsent klein ist das haus the house is small bitext appendalignedsent das haus war ja gro the house was big bitext appendalignedsent das buch ist ja klein the book is small bitext appendalignedsent ein haus ist klein a house is small bitext appendalignedsent das haus the house bitext appendalignedsent das buch the book bitext appendalignedsent ein buch a book bitext appendalignedsent ich fasse das buch zusammen i summarize the book bitext appendalignedsent fasse zusammen summarize ibm3 ibmmodel3bitext 5 printroundibm3 translationtable buch book 3 1 0 printroundibm3 translationtable das book 3 0 0 printroundibm3 translationtable ja none 3 1 0 printroundibm3 distortiontable1122 3 1 0 printroundibm3 distortiontable1222 3 0 0 printroundibm3 distortiontable2245 3 0 75 printroundibm3 fertilitytable2 summarize 3 1 0 printroundibm3 fertilitytable1 book 3 1 0 printroundibm3 p1 3 0 054 testsentence bitext2 testsentence words das buch ist ja klein testsentence mots the book is small testsentence alignment alignment0 0 1 1 2 2 3 none 4 3 train on sentencealignedcorpus and create a lexical translation model a distortion model a fertility model and a model for generating nullaligned words 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 fertilitytable p1 distortiontable see ibmmodel for the type and purpose of these tables type probabilitytables dictstr object get translation and alignment probabilities from ibm model 2 set userdefined probabilities dictintintintint float probabilityj i l m values accessed as distortiontablejilm dj i l m 1 m for all i j l m simple initialization taken from giza sample the alignment space record the most probable alignment e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimates if any probability is less than minprob clamp it to minprob probability of target sentence and an alignment given the source sentence combine null insertion probability compute combination m nullfertility choose nullfertility combine fertility probabilities combine lexical and distortion probabilities data object to store counts of various parameters during training includes counts for distortion natural language toolkit ibm model 3 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 translation model that considers how a word can be aligned to multiple words in another language ibm model 3 improves on model 2 by directly modeling the phenomenon where a word in one language may be translated into zero or more words in another this is expressed by the fertility probability n phi source word if a source word translates into more than one word it is possible to generate sentences that have the same alignment in multiple ways this is modeled by a distortion step the distortion probability d j i l m predicts a target word position given its aligned source word s position the distortion probability replaces the alignment probability of model 2 the fertility probability is not applicable for null target words that align to null are assumed to be distributed uniformly in the target sentence the existence of these words is modeled by p1 the probability that a target word produced by a real source word requires another target word that is produced by null the em algorithm used in model 3 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 target sentence is aligned to a particular position in the source sentence c count how many times a source word is aligned to phi number of target words d count how many times null is aligned to a target word m step estimate new probabilities based on the counts from the e step because there are too many possible alignments only the most probable ones are considered first the best alignment is determined using prior probabilities then a hill climbing approach is used to find other good candidates 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 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 translation model that considers how a word can be aligned to multiple words in another language 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 ibm3 ibmmodel3 bitext 5 print round ibm3 translation_table buch book 3 1 0 print round ibm3 translation_table das book 3 0 0 print round ibm3 translation_table ja none 3 1 0 print round ibm3 distortion_table 1 1 2 2 3 1 0 print round ibm3 distortion_table 1 2 2 2 3 0 0 print round ibm3 distortion_table 2 2 4 5 3 0 75 print round ibm3 fertility_table 2 summarize 3 1 0 print round ibm3 fertility_table 1 book 3 1 0 print round ibm3 p1 3 0 054 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 train on sentence_aligned_corpus and create a lexical translation model a distortion model 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 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 distortion_table see ibmmodel for the type and purpose of these tables type probability_tables dict str object get translation and alignment probabilities from ibm model 2 set user defined probabilities dict int int int int float probability j i l m values accessed as distortion_table j i l m d j i l m 1 m for all i j l m simple initialization taken from giza sample the alignment space record the most probable alignment e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimates if any probability is less than min_prob clamp it to min_prob don t retrain probability of target sentence and an alignment given the source sentence exclude null combine null insertion probability compute combination m null_fertility choose null_fertility combine fertility probabilities combine lexical and distortion probabilities data object to store counts of various parameters during training includes counts for distortion
import warnings
from collections import defaultdict
from math import factorial

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


class IBMModel3(IBMModel):
    

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

        if probability_tables is None:
            
            ibm2 = IBMModel2(sentence_aligned_corpus, iterations)
            self.translation_table = ibm2.translation_table
            self.alignment_table = ibm2.alignment_table
            self.set_uniform_probabilities(sentence_aligned_corpus)
        else:
            
            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.distortion_table = probability_tables["distortion_table"]

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

    def reset_probabilities(self):
        super().reset_probabilities()
        self.distortion_table = defaultdict(
            lambda: defaultdict(
                lambda: defaultdict(lambda: defaultdict(lambda: self.MIN_PROB))
            )
        )
        

    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 / m
                if initial_prob < IBMModel.MIN_PROB:
                    warnings.warn(
                        "A target sentence is too long ("
                        + str(m)
                        + " words). Results may be less accurate."
                    )
                for j in range(1, m + 1):
                    for i in range(0, l + 1):
                        self.distortion_table[j][i][l][m] = initial_prob

        
        self.fertility_table[0] = defaultdict(lambda: 0.2)
        self.fertility_table[1] = defaultdict(lambda: 0.65)
        self.fertility_table[2] = defaultdict(lambda: 0.1)
        self.fertility_table[3] = defaultdict(lambda: 0.04)
        MAX_FERTILITY = 10
        initial_fert_prob = 0.01 / (MAX_FERTILITY - 4)
        for phi in range(4, MAX_FERTILITY):
            self.fertility_table[phi] = defaultdict(lambda: initial_fert_prob)

        self.p1 = 0.5

    def train(self, parallel_corpus):
        counts = Model3Counts()
        for aligned_sentence in parallel_corpus:
            l = len(aligned_sentence.mots)
            m = len(aligned_sentence.words)

            
            sampled_alignments, best_alignment = self.sample(aligned_sentence)
            
            aligned_sentence.alignment = Alignment(
                best_alignment.zero_indexed_alignment()
            )

            
            total_count = self.prob_of_alignments(sampled_alignments)

            
            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
                    )
                    counts.update_distortion(normalized_count, alignment_info, j, l, m)

                counts.update_null_generation(normalized_count, alignment_info)
                counts.update_fertility(normalized_count, alignment_info)

        
        
        existing_alignment_table = self.alignment_table
        self.reset_probabilities()
        self.alignment_table = existing_alignment_table  

        self.maximize_lexical_translation_probabilities(counts)
        self.maximize_distortion_probabilities(counts)
        self.maximize_fertility_probabilities(counts)
        self.maximize_null_generation_probabilities(counts)

    def maximize_distortion_probabilities(self, counts):
        MIN_PROB = IBMModel.MIN_PROB
        for j, i_s in counts.distortion.items():
            for i, src_sentence_lengths in i_s.items():
                for l, trg_sentence_lengths in src_sentence_lengths.items():
                    for m in trg_sentence_lengths:
                        estimate = (
                            counts.distortion[j][i][l][m]
                            / counts.distortion_for_any_j[i][l][m]
                        )
                        self.distortion_table[j][i][l][m] = max(estimate, MIN_PROB)

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

        probability = 1.0
        MIN_PROB = IBMModel.MIN_PROB

        
        null_fertility = alignment_info.fertility_of_i(0)
        probability *= pow(p1, null_fertility) * pow(p0, m - 2 * null_fertility)
        if probability < MIN_PROB:
            return MIN_PROB

        
        for i in range(1, null_fertility + 1):
            probability *= (m - null_fertility - i + 1) / i
            if probability < MIN_PROB:
                return MIN_PROB

        
        for i in range(1, l + 1):
            fertility = alignment_info.fertility_of_i(i)
            probability *= (
                factorial(fertility) * self.fertility_table[fertility][src_sentence[i]]
            )
            if probability < MIN_PROB:
                return MIN_PROB

        
        for j in range(1, m + 1):
            t = trg_sentence[j]
            i = alignment_info.alignment[j]
            s = src_sentence[i]

            probability *= (
                self.translation_table[t][s] * self.distortion_table[j][i][l][m]
            )
            if probability < MIN_PROB:
                return MIN_PROB

        return probability


class Model3Counts(Counts):
    

    def __init__(self):
        super().__init__()
        self.distortion = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: 0.0)))
        )
        self.distortion_for_any_j = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: 0.0))
        )

    def update_distortion(self, count, alignment_info, j, l, m):
        i = alignment_info.alignment[j]
        self.distortion[j][i][l][m] += count
        self.distortion_for_any_j[i][l][m] += count