# -*- coding: utf-8 -*-
# Natural Language Toolkit: RIBES Score
#
# Copyright (C) 2001-2015 NLTK Project
# Contributors: Katsuhito Sudoh, Liling Tan, Kasramvd, J.F.Sebastian
# Mark Byers, ekhumoro, P. Ortiz
# URL: <http://nltk.org/>
# For license information, see LICENSE.TXT
""" RIBES score implementation """
from __future__ import division
from itertools import islice
import math
from nltk.util import ngrams, choose
def sentence_ribes(references, hypothesis, alpha=0.25, beta=0.10):
"""
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.
http://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 http://www.kecl.ntt.co.jp/icl/lirg/ribes/ for the official script.
:param references: a list of reference sentences
:type reference: 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
"""
best_ribes = -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 = word_rank_alignment(reference, hypothesis)
nkt = kendall_tau(worder)
# Calculates the brevity penalty
bp = min(1.0, math.exp(1.0 - len(reference)/len(hypothesis)))
# Calculates the unigram precision, *p1*
p1 = len(worder) / len(hypothesis)
_ribes = nkt * (p1 ** alpha) * (bp ** beta)
if _ribes > best_ribes: # Keeps the best score.
best_ribes = _ribes
return best_ribes
def corpus_ribes(list_of_references, hypotheses, alpha=0.25, beta=0.10):
"""
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
"""
corpus_best_ribes = 0.0
# Iterate through each hypothesis and their corresponding references.
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):
"""
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.
for i,sublist in enumerate(ngrams(sentence, len(ngram))):
# Returns the index of the word when ngram matches.
if ngram == sublist:
return i
def word_rank_alignment(reference, hypothesis, character_based=False):
"""
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)
"""
worder = []
hyp_len = len(hypothesis)
# Stores a list of possible ngrams from the reference sentence.
# This is used for matching context window later in the algorithm.
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 word is not in the reference, continue.
if h_word not in reference:
continue
# If we can determine one-to-one word correspondence for unigrams that
# only appear once in both the reference and hypothesis.
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: # If searching the right context is possible.
# Retrieve the right context window.
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 ngram appears only once in both ref and hyp.
if num_times_in_ref == num_times_in_hyp == 1:
# Find the position of ngram that matched the reference.
pos = position_of_ngram(right_context_ngram, reference)
worder.append(pos) # Add the positions of the ngram.
break
if window <= i: # If searching the left context is possible.
# Retrieve the left context window.
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:
# Find the position of ngram that matched the reference.
pos = position_of_ngram(left_context_ngram, reference)
# Add the positions of the ngram.
worder.append(pos+ len(left_context_ngram) -1)
break
return worder
def find_increasing_sequences(worder):
"""
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)
"""
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):
"""
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
:type normalize: boolean
:return: The Kendall's Tau correlation coefficient.
:rtype: float
"""
worder_len = len(worder)
# Extract the groups of increasing/monotonic sequences.
increasing_sequences = find_increasing_sequences(worder)
# Calculate no. of increasing_pairs in *worder* list.
num_increasing_pairs = sum(choose(len(seq),2) for seq in increasing_sequences)
# Calculate no. of possible pairs.
num_possible_pairs = choose(worder_len, 2)
# Kendall's Tau computation.
tau = 2 * num_increasing_pairs / num_possible_pairs -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 spearman_rho(worder, normalize=True):
"""
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)
"""
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: # 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