natural language toolkit ribes score c 20012023 nltk project contributors katsuhito sudoh liling tan kasramvd j f sebastian mark byers ekhumoro p ortiz url https www nltk org for license information see license txt ribes score implementation import math from itertools import islice from nltk util import choose ngrams def sentenceribesreferences hypothesis alpha0 25 beta0 10 bestribes 1 0 calculates ribes for each reference and returns the best score for reference in references collects the worder from the ranked correlation alignments worder wordrankalignmentreference hypothesis nkt kendalltauworder calculates the brevity penalty bp min1 0 math exp1 0 lenreference lenhypothesis calculates the unigram precision p1 p1 lenworder lenhypothesis ribes nkt p1alpha bpbeta if ribes bestribes keeps the best score bestribes ribes return bestribes def corpusribeslistofreferences hypotheses alpha0 25 beta0 10 corpusbestribes 0 0 iterate through each hypothesis and their corresponding references for references hypothesis in ziplistofreferences hypotheses corpusbestribes sentenceribesreferences hypothesis alpha beta return corpusbestribes lenhypotheses def positionofngramngram sentence iterates through the ngrams in sentence for i sublist in enumeratengramssentence lenngram returns the index of the word when ngram matches if ngram sublist return i def wordrankalignmentreference hypothesis characterbasedfalse worder hyplen lenhypothesis stores a list of possible ngrams from the reference sentence this is used for matching context window later in the algorithm refngrams hypngrams for n in range1 lenreference 1 for ng in ngramsreference n refngrams appendng for ng in ngramshypothesis n hypngrams appendng for i hword in enumeratehypothesis if word is not in the reference continue if hword not in reference continue if we can determine onetoone word correspondence for unigrams that only appear once in both the reference and hypothesis elif hypothesis counthword reference counthword 1 worder appendreference indexhword else maxwindowsize maxi hyplen i 1 for window in range1 maxwindowsize if i window hyplen if searching the right context is possible retrieve the right context window rightcontextngram tupleislicehypothesis i i window 1 numtimesinref refngrams countrightcontextngram numtimesinhyp hypngrams countrightcontextngram if ngram appears only once in both ref and hyp if numtimesinref numtimesinhyp 1 find the position of ngram that matched the reference pos positionofngramrightcontextngram reference worder appendpos add the positions of the ngram break if window i if searching the left context is possible retrieve the left context window leftcontextngram tupleislicehypothesis i window i 1 numtimesinref refngrams countleftcontextngram numtimesinhyp hypngrams countleftcontextngram if numtimesinref numtimesinhyp 1 find the position of ngram that matched the reference pos positionofngramleftcontextngram reference add the positions of the ngram worder appendpos lenleftcontextngram 1 break return worder def findincreasingsequencesworder items iterworder a b none nextitems none result b while b is not none a b b nextitems none if b is not none and a 1 b result appendb else if lenresult 1 yield tupleresult result b def kendalltauworder normalizetrue worderlen lenworder with worderlen 2 chooseworderlen 2 will be 0 as we divide by this it will give a zerodivisionerror to avoid this we can just return the lowest possible score if worderlen 2 tau 1 else extract the groups of increasingmonotonic sequences increasingsequences findincreasingsequencesworder calculate no of increasingpairs in worder list numincreasingpairs sumchooselenseq 2 for seq in increasingsequences calculate no of possible pairs numpossiblepairs chooseworderlen 2 kendall s tau computation tau 2 numincreasingpairs numpossiblepairs 1 if normalize if normalized the tau output falls between 0 0 to 1 0 return tau 1 2 else otherwise the tau outputs falls between 1 0 to 1 0 return tau def spearmanrhoworder normalizetrue worderlen lenworder sumdsquare sumwi i 2 for wi i in zipworder rangeworderlen rho 1 sumdsquare chooseworderlen 1 3 if normalize if normalized the rho output falls between 0 0 to 1 0 return rho 1 2 else otherwise the rho outputs falls between 1 0 to 1 0 return rho natural language toolkit ribes score c 2001 2023 nltk project contributors katsuhito sudoh liling tan kasramvd j f sebastian mark byers ekhumoro p ortiz url https www nltk org for license information see license txt ribes score implementation the ribes rank based intuitive bilingual evaluation score from hideki isozaki tsutomu hirao kevin duh katsuhito sudoh and hajime tsukada 2010 automatic evaluation of translation quality for distant language pairs in proceedings of emnlp https www aclweb org anthology d d10 d10 1092 pdf the generic ribes scores used in shared task e g workshop for asian translation wat uses the following ribes calculations ribes kendall_tau alpha p1 beta bp please note that this re implementation differs from the official ribes implementation and though it emulates the results as describe in the original paper there are further optimization implemented in the official ribes script users are encouraged to use the official ribes script instead of this implementation when evaluating your machine translation system refer to https www kecl ntt co jp icl lirg ribes for the official script param references a list of reference sentences type references list list str param hypothesis a hypothesis sentence type hypothesis list str param alpha hyperparameter used as a prior for the unigram precision type alpha float param beta hyperparameter used as a prior for the brevity penalty type beta float return the best ribes score from one of the references rtype float calculates ribes for each reference and returns the best score collects the worder from the ranked correlation alignments calculates the brevity penalty calculates the unigram precision p1 keeps the best score this function calculates ribes for a system output hypothesis with multiple references and returns best score among multi references and individual scores the scores are corpus wise i e averaged by the number of sentences c f ribes version 1 03 1 code different from bleu s micro average precision ribes calculates the macro average precision by averaging the best ribes score for each pair of hypothesis and its corresponding references hyp1 it is a guide to action which ensures that the military always obeys the commands of the party ref1a it is a guide to action that ensures that the military will forever heed party commands ref1b it is the guiding principle which guarantees the military forces always being under the command of the party ref1c it is the practical guide for the army always to heed the directions of the party hyp2 he read the book because he was interested in world history ref2a he was interested in world history because he read the book list_of_references ref1a ref1b ref1c ref2a hypotheses hyp1 hyp2 round corpus_ribes list_of_references hypotheses 4 0 3597 param references a corpus of lists of reference sentences w r t hypotheses type references list list list str param hypotheses a list of hypothesis sentences type hypotheses list list str param alpha hyperparameter used as a prior for the unigram precision type alpha float param beta hyperparameter used as a prior for the brevity penalty type beta float return the best ribes score from one of the references rtype float iterate through each hypothesis and their corresponding references this function returns the position of the first instance of the ngram appearing in a sentence note that one could also use string as follows but the code is a little convoluted with type casting back and forth char_pos join sent join sent index join ngram word_pos char_pos count another way to conceive this is return next i for i ng in enumerate ngrams sentence len ngram if ng ngram param ngram the ngram that needs to be searched type ngram tuple param sentence the list of tokens to search from type sentence list str iterates through the ngrams in sentence returns the index of the word when ngram matches this is the word rank alignment algorithm described in the paper to produce the worder list i e a list of word indices of the hypothesis word orders w r t the list of reference words below is h0 r0 example from the isozaki et al 2010 paper note the examples are indexed from 1 but the results here are indexed from 0 ref str he was interested in world history because he read the book split hyp str he read the book because he was interested in world history split word_rank_alignment ref hyp 7 8 9 10 6 0 1 2 3 4 5 the h1 r1 example from the paper note the 0th index ref john hit bob yesterday split hyp bob hit john yesterday split word_rank_alignment ref hyp 2 1 0 3 here is the h2 r2 example from the paper note the 0th index here too ref the boy read the book split hyp the book was read by the boy split word_rank_alignment ref hyp 3 4 2 0 1 param reference a reference sentence type reference list str param hypothesis a hypothesis sentence type hypothesis list str stores a list of possible ngrams from the reference sentence this is used for matching context window later in the algorithm if word is not in the reference continue if we can determine one to one word correspondence for unigrams that only appear once in both the reference and hypothesis if searching the right context is possible retrieve the right context window if ngram appears only once in both ref and hyp find the position of ngram that matched the reference add the positions of the ngram if searching the left context is possible retrieve the left context window find the position of ngram that matched the reference add the positions of the ngram given the worder list this function groups monotonic 1 sequences worder 7 8 9 10 6 0 1 2 3 4 5 list find_increasing_sequences worder 7 8 9 10 0 1 2 3 4 5 param worder the worder list output from word_rank_alignment param type list int calculates the kendall s tau correlation coefficient given the worder list of word alignments from word_rank_alignment using the formula tau 2 num_increasing_pairs num_possible_pairs 1 note that the no of increasing pairs can be discontinuous in the worder list and each each increasing sequence can be tabulated as choose len seq 2 no of increasing pairs e g worder 7 8 9 10 6 0 1 2 3 4 5 number_possible_pairs choose len worder 2 round kendall_tau worder normalize false 3 0 236 round kendall_tau worder 3 0 382 param worder the worder list output from word_rank_alignment type worder list int param normalize flag to indicate normalization to between 0 0 and 1 0 type normalize boolean return the kendall s tau correlation coefficient rtype float with worder_len 2 choose worder_len 2 will be 0 as we divide by this it will give a zerodivisionerror to avoid this we can just return the lowest possible score extract the groups of increasing monotonic sequences calculate no of increasing_pairs in worder list calculate no of possible pairs kendall s tau computation if normalized the tau output falls between 0 0 to 1 0 otherwise the tau outputs falls between 1 0 to 1 0 calculates the spearman s rho correlation coefficient given the worder list of word alignment from word_rank_alignment using the formula rho 1 sum d 2 choose len worder 1 3 given that d is the sum of difference between the worder list of indices and the original word indices from the reference sentence using the h0 r0 and h5 r5 example from the paper worder 7 8 9 10 6 0 1 2 3 4 5 round spearman_rho worder normalize false 3 0 591 round spearman_rho worder 3 0 205 param worder the worder list output from word_rank_alignment param type list int if normalized the rho output falls between 0 0 to 1 0 otherwise the rho outputs falls between 1 0 to 1 0
import math
from itertools import islice

from nltk.util import choose, ngrams


def sentence_ribes(references, hypothesis, alpha=0.25, beta=0.10):
    
    best_ribes = -1.0
    
    for reference in references:
        
        worder = word_rank_alignment(reference, hypothesis)
        nkt = kendall_tau(worder)

        
        bp = min(1.0, math.exp(1.0 - len(reference) / len(hypothesis)))

        
        p1 = len(worder) / len(hypothesis)

        _ribes = nkt * (p1**alpha) * (bp**beta)

        if _ribes > best_ribes:  
            best_ribes = _ribes

    return best_ribes


def corpus_ribes(list_of_references, hypotheses, alpha=0.25, beta=0.10):
    
    corpus_best_ribes = 0.0
    
    for references, hypothesis in zip(list_of_references, hypotheses):
        corpus_best_ribes += sentence_ribes(references, hypothesis, alpha, beta)
    return corpus_best_ribes / len(hypotheses)


def position_of_ngram(ngram, sentence):
    
    
    for i, sublist in enumerate(ngrams(sentence, len(ngram))):
        
        if ngram == sublist:
            return i


def word_rank_alignment(reference, hypothesis, character_based=False):
    
    worder = []
    hyp_len = len(hypothesis)
    
    
    ref_ngrams = []
    hyp_ngrams = []
    for n in range(1, len(reference) + 1):
        for ng in ngrams(reference, n):
            ref_ngrams.append(ng)
        for ng in ngrams(hypothesis, n):
            hyp_ngrams.append(ng)
    for i, h_word in enumerate(hypothesis):
        
        if h_word not in reference:
            continue
        
        
        elif hypothesis.count(h_word) == reference.count(h_word) == 1:
            worder.append(reference.index(h_word))
        else:
            max_window_size = max(i, hyp_len - i + 1)
            for window in range(1, max_window_size):
                if i + window < hyp_len:  
                    
                    right_context_ngram = tuple(islice(hypothesis, i, i + window + 1))
                    num_times_in_ref = ref_ngrams.count(right_context_ngram)
                    num_times_in_hyp = hyp_ngrams.count(right_context_ngram)
                    
                    if num_times_in_ref == num_times_in_hyp == 1:
                        
                        pos = position_of_ngram(right_context_ngram, reference)
                        worder.append(pos)  
                        break
                if window <= i:  
                    
                    left_context_ngram = tuple(islice(hypothesis, i - window, i + 1))
                    num_times_in_ref = ref_ngrams.count(left_context_ngram)
                    num_times_in_hyp = hyp_ngrams.count(left_context_ngram)
                    if num_times_in_ref == num_times_in_hyp == 1:
                        
                        pos = position_of_ngram(left_context_ngram, reference)
                        
                        worder.append(pos + len(left_context_ngram) - 1)
                        break
    return worder


def find_increasing_sequences(worder):
    
    items = iter(worder)
    a, b = None, next(items, None)
    result = [b]
    while b is not None:
        a, b = b, next(items, None)
        if b is not None and a + 1 == b:
            result.append(b)
        else:
            if len(result) > 1:
                yield tuple(result)
            result = [b]


def kendall_tau(worder, normalize=True):
    
    worder_len = len(worder)
    
    
    
    if worder_len < 2:
        tau = -1
    else:
        
        increasing_sequences = find_increasing_sequences(worder)
        
        num_increasing_pairs = sum(choose(len(seq), 2) for seq in increasing_sequences)
        
        num_possible_pairs = choose(worder_len, 2)
        
        tau = 2 * num_increasing_pairs / num_possible_pairs - 1
    if normalize:  
        return (tau + 1) / 2
    else:  
        return tau


def spearman_rho(worder, normalize=True):
    
    worder_len = len(worder)
    sum_d_square = sum((wi - i) ** 2 for wi, i in zip(worder, range(worder_len)))
    rho = 1 - sum_d_square / choose(worder_len + 1, 3)

    if normalize:  
        return (rho + 1) / 2
    else:  
        return rho