これはあくあたん工房 GW Advent Calendar4日目の記事です．
こんにちは，taxioです．最近MLベースの自然言語処理の勉強をしていて，Transformerとその関連の論文を読んでtf2.0でゴリゴリ実装したりしていました1．今回はそんな機械翻訳などの評価値としてよく使われるBLEU2とその平滑化手法について書いていきます．
BLEUのおさらい
BLEUとはKishore Papineni, Salim Roukos and Todd Ward, et al, BLEU: a Method for Automatic Evaluation of Machine Translation, ACL'02にて紹介された手法です．次の式に沿って，n-gramによって正解文章と機械翻訳が生成した文章を比較し数値化していきます．
BLEU = BP * exp(\sum_{n=1}^{N} w_n log P_n)
$P_n$はn-gram精度のことで，以下の式で表されます．
P_n = \frac{Count_{clip}(ngram_{Ref})}{Count(ngram_{MT})}
$Count(ngram_{MT})$は機械翻訳のn-gramの数のことで，$Count_{clip}(ngram_{Ref})$は機械翻訳と参照訳3に共通するn-gramの数のことです．
例えば，次のような機械翻訳と参照訳があったとします．
機械翻訳 : the the the the the the the.
参照訳1: The cat is on the mat.
参照訳2: There is a cat on the mat.
unigram(1-gram)を考えていきます．
まず，機械翻訳の文章から生成されるunigramの数は7なので，$Count(ngram_{MT})=7$となります．次に，参照訳のunigramとの一致を考えていくのですが普通に一致をとってしまった場合，参照訳のどちらにも「the」という単語が入っているため，一致度は$\frac{7}{7}$となってしまいます．これでは頻出単語を並べただけの文章のスコアが不自然に高くなってしまうので，BLEUでは参照訳で一度一致した候補語は使わないという制約を与えます．すると，一致度$P_1$は$\frac{2}{7}$となります．
$BP$(Brevity Penalty)は機械翻訳が参照訳より短い場合にペナルティを課す係数です．
$c$を機械翻訳の長さ，$r$を機械翻訳の長さに一番近い参照訳の長さとすると，
BP = \left\{
\begin{array}{ll}
1 & (c > r) \\
e^{1 - \frac{r}{c}} & (c \leq r)
\end{array}
\right.
となります．
機械翻訳の方が長い場合は何もせずとも自然にスコアは下がっていくため，BPは1となっています．
$w_n$は各n-gramに関する$P_n$に対する重みで，
\sum_{n=1}^{N} w_n = 1
となるように設定します．
論文中では$N=4$，$w_n=\frac{1}{N}$がベースラインであると紹介されており，実際$N=4$で使われているのをよく見かけます4．つまり，全ての$w_n$が等しい場合，算術平均であるため，
BLEU = BP * exp(\sum_{n=1}^{N} \frac{1}{N} log P_n)
と，他の記事でもよく見る形になります．
これをさらに変形すると，
BLEU = BP * (\prod_{n=1}^{N} P_n)^{\frac{1}{N}}
となり，非常に見やすい形になります．
BLEUの問題点
はい，ここから本題です．
このBLEUの評価値は，各$P_n$を掛け合わせるため，少々困った問題が起きます．それは高いオーダーでのn-gramの不一致によるスコアの急減少です5．例えば，$n=1,2,3$まである程度一致が見つかっていたのに，$n=4$の時に一致が0だとBLEUの値も0になってしまうという感じです．そのため，これを平滑化する手法が色々な論文で紹介されています．
import nltk
mt = ['This', 'is', 'an', 'fruit']
ref1 = ['This', 'is', 'an', 'apple']
ref2 = ['There', 'is', 'an', 'apple']
print(nltk.translate.bleu_score.sentence_bleu([ref1, ref2], mt))
# 8.636168555094496e-78
nltkライブラリ6ではn-gramの一致が0の場合，warningを出して代わりにsys.float_info.minを使っているので0にはなってません7．
Smooth BLEU
今回はBoxing Chen and Colin Cherry, A Systematic Comparison of Smoothing Techniques for Sentence-Level BLEU, ACL'14という論文で紹介されている平滑化手法について書いていきます．
ここからは便宜上，機械翻訳と参照訳の共通のn-gramの数を$m_n$，機械翻訳のn-gramの数を$l_n$として解説していきます．
手法1
$m_n$が0個なら小さい値$\epsilon$を足し合わせる手法です．nltkではmethod1というメソッドで実装されています．論文では$\epsilon$は経験的に決まると書いてあり，ライブラリのデフォルト値は0.1です．
手法2
Chin-Yew Lin and Franz Josef Och, Automatic Evaluation of Machine Translation Quality Using Longest Common Subsequence and Skip-Bigram Statistics, ACL'04で紹介された手法です．
$n>1$において，各$m_n$，$l_n$に1を足して計算します．
nltkではmethod2というメソッドで実装されていますが，こちらはn>1ではなくn=1から足し合わせの対象にしているようです．
手法3
NIST (National Institute of Standards and Technology)が提供しているmteval-v13aに実装されている手法です．
invcnt = 1
for n in 1 to N
if m_n = 0
invcnt = invcnt * 2
m_n = 1 / invcnt
endif
endfor
$m_n$が0だと$invcnt$を足していきます．定数はn-gramの一致が0の場合が多いほど$\frac{1}{2}$ずつ小さくなっていきます．
nltkではmethod3というメソッドで実装されています．
手法4
この論文で新規に紹介された手法です．先程の手法3の$invcnt$の更新を2倍ではなく，
invcnt = invcnt * \frac{K}{ln(len(T))}
とします．$K$は適当な平滑化係数で，$len(T)$は機械翻訳の文字列の長さ(単語数)です．こうすることで，短い文章の方が有利になってしまう点に対応しています．
nltkではmethod4というメソッド実装されています．$K$は経験的に決まり，ライブラリのデフォルト値は5となっています．
手法5
この論文で新規に紹介された手法です．
m'_0 = m_1 + 1\\
m'_n = \frac{m'_{n-1} + m_n + m_{n+1}}{3}
$m_n$の前後の値を使って平滑化しています．$m_N$を計算するために，n-gramは$N+1$まで算出します．
nltkではmethod5というメソッドで実装されています．
手法6
p^0_n = p_{n-1} * \frac{p_{n-1}}{p_{n-2}} \\
p_n = \frac{m_n + \alpha p^0_n}{l_n + \alpha} \\
BP = exp(1 - \beta \frac{r}{c})
$n > 2$において，それより前の値を使用して$P_n$を計算します．また，$BP$を計算する際，参照訳の全長と最良の翻訳の全長との比で計算される$\beta$を掛け合わせています8．
nltkではmethod6というメソッドで実装さていますが，どうやら$BP$の計算に関してはサポートしていないようです．$\alpha$は経験的に決まり，ライブラリのデフォルト値は5となっています．
手法7
この論文で新規に紹介された手法です．
先程の手法4で$P_n$を算出したあとに，さらに手法5でもう一度平滑化します．nltkではmethod7というメソッドで実装されています．
で，どれがいいの？
この論文では手法7が一番人間との評価に近いとされていました．ちなみにTransformerの公開実装では手法3が使われているような気がします．TensorflowのNMT Tutorialであるtensorflow/nmtでは手法2が使われています．
平滑化した方がいいというのは分かりますが，どれがいいのかはよく分からないですね．というかSoTA競ってるのに評価手法を統一しなくていいのでしょうか...？
最後に
BLEUの平滑化手法について書いていきました．
元々はBLEUでの評価の実装をしている際，nltkの実装が自分の知っているものと少し違うという違和感と，なんか内部のコメントに論文のリンクがあるという理由で調べ始めました．この記事を書くために関連論文を調べている最中もBLEUの平滑化について記述のある論文が紹介できないほど見つかりました．自然言語処理って勉強すればするほど新知識が出てきますね．
まだまだ勉強の身ですので，間違っていたり情報が古かったりした場合は指摘していただけるとありがたいです．