charsim：調整に頼らない文字n-gram類似度
本記事では、いもすが提案する文字列類似度指標charsimを紹介します。生成モデルの回答や翻訳文などの評価対象（候補）を、比較の基準となる参照文と照合し、共通する表現の多さを測ります。一致した部分を加点しつつ、短い断片だけを抜き出した候補は内容の不足に応じて、同じ表現を繰り返して長くした候補は余分な部分に応じて減点します。
既存の指標では、単語の並びを照合するBLEU（Bilingual Evaluation Understudy）[1]と、文字の並びを照合するchrF（character n-gram F-score）[2]が代表的です。平滑化しないBLEUでは、評価に含めた長さの並びに一致が1つもなければ、短い一致が残っていてもスコアが0になります。1文ごとの評価ではこの問題が生じやすく、0になる値を補正する平滑化を使う場合は、その方法も選ぶ必要があります。chrFは短い一致も評価でき、余分な部分と不足する部分のどちらを重く減点するかを係数で指定します。
charsimは、連続する\(n\)文字のまとまりである文字n-gramを取り出し、候補と参照文に共通する出現回数を足し合わせます。この重なりから適合率と再現率を求め、小さい方をスコアにすることで、平滑化の方法や過不足の減点を調整する係数を選ばずに部分一致を評価します。n-gramの長さを表す次数\(n\)に応じて\(1/n\)の重みを付け、最大32-gramまでを数えます。長い一致も評価に含めながら、長いn-gram 1個あたりの加点を小さくする設計です。
主定義と長さの補正
候補\(t\)を1つ以上の参照文からなる参照集合\(\mathcal R\)と照合します。各参照文との重み付き重なりの平均を\(\bar M\)、候補の重み付き長さを\(L_t\)、参照文の重み付き長さの平均を\(\bar L_r\)とすると、主定義は次の式です。ここでは候補も参照文も空でない場合を扱います。
\[
\boxed{\;\operatorname{charsim}(t;\mathcal R)
= \frac{\bar M}{\max(L_t,\bar L_r)}=\min(P,R)\;}
\]
\[
P=\frac{\bar M}{L_t},\qquad R=\frac{\bar M}{\bar L_r}
\]
適合率\(P\)は候補側のどれだけが参照文と一致したか、再現率\(R\)は参照側のどれだけを候補が含んでいるかを表します。同じ重なりを大きい方の長さで割ると、2つの割合のうち小さい方が選ばれます。候補が平均参照長より短ければ再現率、長ければ適合率がスコアを決めるため、高いスコアを得るには、不足する部分と余分な部分の両方を減らす必要があります。
ここで使う重み付き長さは、文字数そのものではなく、次数\(n\)ごとのn-gram数に\(1/n\)を掛けて足した量です。例えば、1-gramの出現1個は1、2-gramの出現1個は\(1/2\)として数えます。重なりも同じ重みで数えるため、適合率と再現率は、重み付きのn-gram数に対する一致割合になります。具体的な数え方は§1、重み付き和は§2.2、平均の取り方は§3.1で定めます。
本記事では、重なりと参照長を平均してから正規化する「平均長版」を主定義にします。比較のため、参照文ごとに正規化してからスコアを平均する「基本形」も定義します（§2）。両者は平均と正規化の順序が異なり、参照文の長さがばらつくと値も変わります（§3.3）。単にcharsimと書くときは平均長版を指します。
対象とする問題と用途
charsimは、1文や短い文章を参照集合全体と照合する用途を想定しています。各参照文との重なりを平均するため、多くの参照文に共通する表現ほどスコアに反映されます。同じ参照集合に多数の候補を照合する場合は、参照側の情報を事前計算して再利用できます（§7.2）。
複数の正解のうちどれか1つに一致すればよい用途では、参照文ごとのスコアの最大値を使う方法が適しています。意味が同じでも表現が大きく異なる言い換えを評価したい場合は、文字列の一致を測るcharsimに加え、意味を評価する別の方法も必要です。
本記事では、定義から導ける性質と文字列の計算例を示し、簡略モデルで長さや一致の分布の影響を比較します。実データを用いた次数上限の影響の測定、既存指標との比較、人手評価との相関の検証は今後の課題です。
1. 記法
1.1. 入力
候補文字列を\(t\)、参照文を\(r\)、参照文の数を\(K\)とし、参照集合を\(\mathcal R=(r^{(1)},\dots,r^{(K)})\)と書きます。\(K\ge1\)を前提とし、参照文がない場合はスコアを定義しません。
参照集合では順序を区別せず、同じ文を複数回含められる多重集合として扱います。平均を取る際は、重複した文も別々に数えます。例えば、同じ文を2回含めると、その文は1回だけ含めた文の2倍の重みを持ちます。
文字の単位はUnicodeのコードポイントとし、文字列\(x\)の文字数を\(|x|\)と書きます。入力をそのまま照合するため、空白も1文字として数え、大文字と小文字を区別します。表記を統一する場合は前処理で行い、処理内容を評価条件に記載することを推奨します。
コードポイントは、Unicodeで文字などに割り当てられた番号です。見た目が1文字でも、複数のコードポイントで表されることがあります。例えば「が」を1つのコードポイントで表すと1文字、「か」と結合用の濁点に分けると2文字として数えます。こうした表現を揃えるUnicode正規化も、必要に応じて前処理で行います。
以降の式では、重なりや長さの記号から入力\(t\)と\(\mathcal R\)の引数を省略します。空文字列を含む場合のスコアは§3.1で定めます。
1.2. 文字n-gramと境界記号
次数\(n\)の文字n-gramは、連続する\(n\)文字からなる部分文字列です。charsimでは、入力の前後に境界記号を1個ずつ補ってから取り出します。境界記号を含むn-gramも照合することで、文頭や文末での一致を評価に加えます。
開始境界を^、終了境界を$と書くと、catは^cat$になります。2-gramは^c、ca、at、t$、3-gramは^ca、cat、at$です。同じn-gramが複数回現れた場合も、それぞれの出現を1個と数えます。
例えばcatとcatsでは、文頭を表す^cも、境界記号を含まないcaも一致します。文末のt$とs$は異なるため、一致として数えません。ここで使う^と$は説明用の表記であり、実装では入力中の文字と区別できる専用の値を使います。
境界記号はどの文字列にも補うため、記号だけの一致を加点すると、共通する文字がなくても重なりが生じます。これを防ぐため、境界記号だけからなるn-gramは除外します。空文字列では、^、$、^$がすべて除外されるため、どの次数でもn-gram数は0です。
文字列\(x\)の次数\(n\)のn-gram数を\(\ell_{x,n}\)と書きます。参照文\(r^{(i)}\)については、\(\ell_{r^{(i)},n}\)を\(\ell_{i,n}\)と略記します。1-gramでは元の文字を数えるため、\(\ell_{x,1}=|x|\)です。2-gram以上では、境界記号を含む文字列から取り出せる個数を数えます。
空でない文字列に境界記号を補うと、長さは\(|x|+2\)です。ここから連続する\(n\)文字を取り出せる位置は、\(2\le n\le|x|+2\)のとき\(|x|+3-n\)個あります。空文字列と1-gramの扱いを含めると、次の式になります。
\[
\ell_{x,n}=\begin{cases}
0 & (|x|=0)\\[2pt]
|x| & (|x|\gt 0,\ n=1)\\[2pt]
|x|+3-n & (|x|\gt 0,\ 2\le n\le |x|+2)\\[2pt]
0 & (n\gt |x|+2)
\end{cases}
\]
空でない文字列では、2-gramは境界に接する部分も数えるため、1-gramより1個多くなります。それ以降は次数を1つ上げるごとに1個ずつ減り、\(n\gt |x|+2\)では0になります。
1.3. n-gramの頻度と重なり
文字列\(x\)にn-gram \(g\)が現れる回数を\(c_x(g)\)とします。例えば、aaaにaaは2回現れるため、\(c_{\texttt{aaa}}(\texttt{aa})=2\)です。取り出す位置が重なっていても、別々の出現として数えます。\(g\)の長さから次数が分かるので、\(c_x\)に次数の添字は付けません。
2つの文字列\(x,y\)の重なりは、n-gramの種類ごとに出現回数の小さい方を求め、それらを足した値です。同じn-gramなら、文字列中の出現位置が異なっていても一致として数えます。以下の\(\sum_g\)は、指定した次数のn-gramについて、種類ごとに求めた値の和です。境界記号だけのものは含めません。
\[
\sum_g\min\bigl(c_x(g),c_y(g)\bigr)
\]
例えば、あるn-gramが候補に5回、参照文に2回現れた場合、その重なりは2個です。共通する出現回数だけを数えるため、候補での繰り返しを6回に増やしても、このn-gramによる加点は増えません。
2. 基本形
2.1. 各参照文との重なり
候補\(t\)と参照文\(r^{(i)}\)の次数\(n\)の重なりを、次のように定義します。
\[
m_{i,n}=\sum_g\min\bigl(c_{r^{(i)}}(g),c_t(g)\bigr)
\]
2.2. 次数をまたぐ重み付き和
各次数の重なりに\(1/n\)を掛け、次数上限\(N\)まで足すと、重み付き重なり\(M_i\)が得られます。正規化の分母に使う候補長\(L_t\)と参照長\(L_i\)も、n-gram数に同じ重みを掛けて求めます。
\[
\begin{aligned}
M_i &= \sum_{n=1}^{N}\frac{m_{i,n}}{n},\\
L_t &= \sum_{n=1}^{N}\frac{\ell_{t,n}}{n},\qquad
L_i = \sum_{n=1}^{N}\frac{\ell_{i,n}}{n}
\end{aligned}
\]
添字\(i\)は、\(i\)番目の参照文との重なりや、その参照文の長さを表します。候補とすべての参照文に共通の次数上限と重みを使うため、\(L_t\)は1回求めれば足ります。\(N\)の選び方は§2.5で定めます。
2.3. 長い方を基準とする正規化
参照文ごとのスコア\(s_i\)は、重み付き重なりを、候補と参照文の重み付き長さの大きい方で割った値です。両方が空の組は§3.1の規則で扱い、それ以外は次の式で求めます。
\[
s_i=\frac{M_i}{\max(L_t,L_i)}
\]
候補と参照文がともに空でなければ、適合率（precision）\(P_i\)と再現率（recall）\(R_i\)を次のように定義できます。適合率は候補側のn-gramのうち一致した割合、再現率は参照側のn-gramのうち一致した割合を、重み付きで求めた値です。
\[
P_i=\frac{M_i}{L_t},\qquad R_i=\frac{M_i}{L_i},\qquad
s_i=\min(P_i,R_i)
\]
候補が参照文より長ければ適合率、短ければ再現率がスコアになります。例えば、参照文の短い断片だけを含む候補では、候補内の一致割合が高くても、参照文をどれだけ含むかという再現率で減点されます。重なりはどちらの重み付き長さも超えないため、スコアは0以上1以下です。
各次数で\(m_{i,n}\le\ell_{t,n}\)かつ\(m_{i,n}\le\ell_{i,n}\)が成り立ちます。正の重み\(1/n\)を掛けて足しても、\(M_i\le\min(L_t,L_i)\)が保たれます。したがって、分母が正なら\(0\le s_i\le1\)です。両方が空の場合は\(s_i=1\)と定めます（§3.1）。
2.4. 複数参照の平均
基本形は、参照文ごとのスコアを平均した値です。
\[
\boxed{\;\operatorname{charsim}_{\mathrm{base}}(t;\mathcal R)
=\frac1K\sum_{i=1}^{K}s_i\;}
\]
長い参照文も短い参照文も、それぞれの長さで正規化したスコアを等しい重みで平均します。参照集合の\(K\)個の要素から1つを等確率で選び、その参照文とのスコアを求めたときの期待値にあたります。
2.5. 次数の打ち切りと完全一致
候補と参照文のうち、少なくとも1つが空でなければ、n-gramが存在する最大次数は最大文字数に2を足した値です。
\[
N'=\max\bigl(|t|,\max_i|r^{(i)}|\bigr)+2
\]
\(N'\)より大きい次数ではすべての項が0になるため、全次数の和も有限です。長い入力で全次数を計算するとn-gram数が増えるので、charsimでは計算量を抑えるため、次の上限で打ち切ります。
\[
N=\min(N',32)
\]
最大文字数が30以下なら全次数を使い、それより長ければ32で打ち切ります。上限を固定すると、取り出すn-gramの個数を入力長に比例する範囲に抑えられます（§7.5）。長めの一致も評価に含めるため、上限を32に設定します。
重み\(1/n\)と上限32を共通設定にすることで、評価データごとの調整を前提とせずに使える仕様にしています。実際の文字列を使う数値例と§7の実装手順も、この設定に従います。上限を変えた派生版でスコアがどう変わるかは、§5.7で説明します。
候補が参照文\(r^{(i)}\)と完全一致すれば、どの次数でも\(m_{i,n}=\ell_{t,n}=\ell_{i,n}\)となります。分子と分母が等しくなるため、1以上のどの次数で打ち切っても、その参照文とのスコア\(s_i\)は1です。
2.6. 基本形の性質と計算上の制約
基本形では分母\(\max(L_t,L_i)\)が参照文によって異なるため、一般には重なりを先に合計して1回で割ることはできません。各参照文の長さを評価に反映できる一方、計算でも参照文ごとの分母を扱う必要があります。平均長版では分母を共通にし、参照側の情報をまとめた表からスコアを求められます（§7.2）。
3. 主定義（平均長版）
3.1. 重なりと参照長の平均
平均長版では、各参照文との重なりと参照長をそれぞれ平均してから正規化します。次数\(n\)の平均重なりを\(\bar m_n\)、参照文の平均n-gram数を\(\bar\ell_{r,n}\)とします。
\[
\begin{aligned}
\bar m_n &= \frac1K\sum_{i=1}^{K}m_{i,n},\\
\bar\ell_{r,n} &= \frac1K\sum_{i=1}^{K}\ell_{i,n}
\end{aligned}
\]
平均した重なりとn-gram数にも\(1/n\)を掛け、次数をまたいで足します。こうして得られる\(\bar M\)と\(\bar L_r\)は、重み付き重なりと重み付き参照長の平均です。
\[
\begin{aligned}
\bar M &= \sum_{n=1}^{N}\frac{\bar m_n}{n},\\
\bar L_r &= \sum_{n=1}^{N}\frac{\bar\ell_{r,n}}{n}
\end{aligned}
\]
次数ごとの和と参照文ごとの平均は、順序を入れ替えても同じ値です。§2.2の\(M_i\)、\(L_i\)を先に求めれば、\(\bar M=\frac1K\sum_iM_i\)、\(\bar L_r=\frac1K\sum_iL_i\)として計算できます。
平均重なり\(\bar M\)を、候補長\(L_t\)と平均参照長\(\bar L_r\)の大きい方で割った値を主定義とします。両方の長さが正なら、適合率\(P\)と再現率\(R\)を定義でき、スコアはその小さい方に一致します。
\[
\boxed{\;\operatorname{charsim}(t;\mathcal R)
=\frac{\bar M}{\max(L_t,\bar L_r)}=\min(P,R)\;}
\]
\[
P=\frac{\bar M}{L_t},\qquad R=\frac{\bar M}{\bar L_r}
\]
§2.3の\(M_i\le L_t\)、\(M_i\le L_i\)を参照文について平均すると、\(\bar M\le L_t\)、\(\bar M\le\bar L_r\)となります。平均重なりは分母を超えないので、平均長版も0以上1以下です。
空文字列を含む場合は、次の規則で扱います。
- 候補とすべての参照文が空なら、スコアは1です。
- 候補の重み付き長さ\(L_t\)と平均参照長\(\bar L_r\)の片方だけが0なら、スコアは0です。
- 基本形では、候補と各参照文の組について、両方が空なら1、片方だけが空なら0としてから平均します。
参照文がない場合（\(K=0\)）は、空文字列を参照文に含む場合と区別し、スコアを定義しません。
3.2. 平均長を使う理由
平均長版を主定義にする理由は、平均参照長を基準に長さを補正でき、参照側の情報も1つの表にまとめて再利用できるためです。
- 重なりと参照長を同じ重みで平均するため、\(\bar M\le\bar L_r\)が保たれ、再現率を0以上1以下の一致割合として解釈できます。
- 分母は\(\max(L_t,\bar L_r)\)にまとまり、平均参照長より短い候補には再現率、長い候補には適合率を使って減点できます。
- 候補に現れるn-gramとその出現回数から平均重なりを求める表を、平均参照長とともに保存できます。同じ参照集合に多数の候補を照合する場合、各参照文のn-gramを毎回調べる必要がなくなります（§7.2）。
平均参照長を使うため、平均より長い参照文を加えると、再現率の分母も大きくなります。参照文の長さがばらつく場合の使い分けは§3.3、平均の代わりに中央値を使う案は§7.3で扱います。
3.3. 基本形との関係と適用条件
参照文の長さがすべて等しければ、基本形と平均長版は一致します。長さが異なる場合は、平均と正規化の順序がスコアに影響します。基本形は参照文ごとの長さを基準にし、平均長版は参照集合全体の平均長を基準にする、別の定義です。
すべての参照文で\(L_i=L_r\)なら、基本形の分母は共通の\(\max(L_t,L_r)\)です。分母が正なら分子だけを平均できるため、\(\operatorname{charsim}_{\mathrm{base}}=\bar M/\max(L_t,L_r)=\operatorname{charsim}\)となります。分母が0なら、どちらも空入力の規則により1です。
候補がすべての参照文以上の長さである場合も、分母がすべて\(L_t\)になるので一致します。
短い参照文と長い参照文が混在する例として、候補をa、参照集合を["a", "abcdefghij"]とします。基本形は約0.528、平均長版は約0.134です。基本形では、1つ目との完全一致のスコア1と、2つ目とのスコア約0.0569を平均します。平均長版では、重なりを平均した後、長い2つ目の参照文も含む平均参照長で割るため、スコアが低くなります。
短い正解と長い正解を、それぞれの長さで正規化して等しく重視したい場合は、基本形を検討してください。どれか1つに一致すればよい場合は、参照文ごとのスコア\(s_i\)の最大値を使う方法が適しています。この例なら、最大値は1です。
平均長版を使う際は、参照集合の平均長が、評価したい回答の長さを代表しているかを確認します。例えば短い要約と詳しい説明を同じ集合に入れると、平均長はどちらとも異なる中間の長さになります。極端に長い参照文が少数ある場合も平均長が引き上げられます。こうした回答を別の正解の種類として扱いたいなら、種類ごとに集合を分ける方が評価の目的に合います。
3.4. 文字の追加・削除・反復の計算例
参照文をcatの1つに固定し、候補をcat、ca、cats、catcatに変えて比較します。単一参照なので基本形と平均長版は一致します。まず、1文字不足したcaについて、重なりを数えるところからスコアを求めます。
境界記号を補った候補は^ca$、参照文は^cat$です。次数上限は\(N=5\)となります。共通する1-gramはcとa、2-gramは^cとca、3-gramは^caです。4-gram以上に一致はありません。単一参照なので、重なりの添字\(i\)を省略し、参照文のn-gram数を\(\ell_{r,n}\)と書きます。
| 次数\(n\) | 1 | 2 | 3 | 4 | 5 |
|---|
| 重なり\(m_n\) | 2 | 2 | 1 | 0 | 0 |
|---|
| \(m_n/n\) | 2 | 1 | \(1/3\) | 0 | 0 |
|---|
| 候補のn-gram数\(\ell_{t,n}\) | 2 | 3 | 2 | 1 | 0 |
|---|
| \(\ell_{t,n}/n\) | 2 | \(3/2\) | \(2/3\) | \(1/4\) | 0 |
|---|
| 参照文のn-gram数\(\ell_{r,n}\) | 3 | 4 | 3 | 2 | 1 |
|---|
| \(\ell_{r,n}/n\) | 3 | 2 | 1 | \(1/2\) | \(1/5\) |
|---|
重なりに\(1/n\)を掛けて足すと、\(\bar M=2+1+1/3=10/3\)です。表の\(\ell_{t,n}/n\)と\(\ell_{r,n}/n\)もそれぞれ横に足し、\(L_t=53/12\)、\(\bar L_r=67/10\)を得ます。候補の方が短いため、スコアの分母には\(\bar L_r\)を使います。
\[
\begin{aligned}
P &= \frac{10/3}{53/12}=\frac{40}{53}\approx0.755,\\
R &= \frac{10/3}{67/10}=\frac{100}{201}\approx0.498,\\
\operatorname{charsim}(\texttt{ca};[\texttt{cat}])
&=\min(P,R)\approx0.498
\end{aligned}
\]
候補側の重み付きn-gram数の約75%が一致していても、参照側の約50%しか含められていません。小さい方の再現率を採ることで、短い断片内での一致だけで高得点になるのを抑えられます。他の候補についても、スコアを小数第3位に丸めて次の表に示します。
| 候補\(t\) | 参照文との違い | スコアを決める値 | 次数上限\(N\) | charsim |
|---|
cat | 完全一致 | \(P=R=1\) | 5 | 1.000 |
ca | 1文字不足 | 再現率 | 5 | 0.498 |
cats | 1文字追加 | 適合率 | 6 | 0.592 |
catcat | 同じ語を2回反復 | 適合率 | 8 | 0.449 |
catsとcatcatは候補が長いため、適合率がスコアになります。catcatは参照文を含みますが、同じn-gramを繰り返しても参照側の出現回数を超えて加点されません。候補側の長さが増えるため、スコアは約0.449まで下がります。
4. 平均長版の振る舞い
4.1. スコアが1に近づく条件
候補の重み付き長さと平均参照長がともに正なら、スコアが1に近づくには、適合率\(\bar M/L_t\)と再現率\(\bar M/\bar L_r\)の両方が1に近いことが必要です。重み付きで数えた候補側のn-gramも、参照側のn-gramも、大半が一致している状態にあたります。
両方の割合が1に近ければ、候補の重み付き長さと平均参照長も近い値になります。高いスコアには、長さが近いことと、共通するn-gramが多いことの両方が必要です。
4.2. 候補が短い場合
候補の重み付き長さが平均参照長より小さい\(L_t\lt\bar L_r\)の場合、スコアは再現率\(\bar M/\bar L_r\)です。候補が参照文の一部と完全に一致していても、重なりは候補長を超えないため、スコアには次の上限があります。
\[
\operatorname{charsim}\le\frac{L_t}{\bar L_r}
\]
例えば、候補の重み付き長さが平均参照長の半分なら、スコアは最大でも0.5です。参照集合を固定すると、候補が短いほど、この上限も低くなります。短い断片内で文字がすべて一致していても、参照文の残りの部分を欠くため減点されます。
4.3. 候補が長い場合
\(L_t\gt \bar L_r\)なら、スコアは適合率\(\bar M/L_t\)です。重なりは平均参照長を超えないため、次の上限があります。
\[
\operatorname{charsim}\le\frac{\bar L_r}{L_t}
\]
候補の重み付き長さが平均参照長の2倍なら、スコアは最大でも0.5です。一致しないn-gramも候補長に数えるため、正の重なりの値を変えずに余分な部分を増やすと、分母が大きくなってスコアが下がります。参照文にある表現を含むことに加え、余分な部分が少ないことも評価できます。
4.4. 次数ごとの寄与
候補と各参照文の長さを固定すると、分母\(D=\max(L_t,\bar L_r)\)は定数です。\(D\gt0\)のとき、スコアを次数ごとの加点に分解できます。
\[
\operatorname{charsim}=\sum_{n=1}^{N}\frac{\bar m_n}{nD}
\]
各項の\(\bar m_n/(nD)\)を調べれば、短い断片と長い表現が、それぞれスコアにどれだけ寄与したかを確認できます。同じ長さの候補を比べる場合も、重なりの増減からスコアの差を計算できます。
ある次数の平均重なり\(\bar m_n\)だけが1増えれば、スコアは\(1/(nD)\)増えます。1つの参照文との重なり\(m_{i,n}\)だけが1増える場合は、平均を取るため増分は\(1/(KnD)\)です。文字数を変えずに編集すると、複数の次数で重なりが変わります。それぞれの増減を足せば、スコア全体の変化を求められます。
4.5. 完全一致からの変化
単一参照と候補が完全一致すればスコアは1です。文字を置き換えると、その位置を含むn-gramが変わりますが、残った一致は引き続き加点されます。高次の一致がなくなっても、低次に一致が残ればスコアは0になりません。
短い文字列では1文字の違いが大きく影響します。例えば、参照文をaに固定し、候補をaからbに変えると、共有文字がなくなるためスコアは1から0になります。
単一参照との比較でスコアが1になる条件は、比較に使うすべての次数で、n-gramの種類と出現回数が等しいことです。次数を打ち切ると、異なる文字列でもこの条件を満たすことがあります。元の文字列が完全に一致するかどうかは、文字列同士を直接比較して判定します。
4.6. 同じ断片の繰り返し
同じn-gram \(g\)が参照文に2回、候補に3回現れるなら、重なり\(\min(c_r(g),c_t(g))\)は2個です。候補の3回目の出現は、重なりには加えず、候補長には数えます。参照文にある回数を超えた反復は、このように適合率を下げる要因になります。一致として数える回数に上限を設ける点は、BLEUやchrFとも共通しています。
5. BLEU・chrFとの違い
BLEU・chrF・charsimを、長さの補正、次数ごとの値のまとめ方、複数参照の扱いから比較します。BLEUは平滑化を行わない原論文の定義を使います。chrFも原論文に従い、次数ごとの適合率と再現率をそれぞれ算術平均し、両者をF値にまとめる定義を基準にします[1, 2]。
5.1. 長さの過不足に対する補正
BLEUは、各次数の適合率を掛け合わせ、その個数に応じた根を取る幾何平均でまとめます。例えば4つの適合率なら、積の4乗根を取ります。さらに、候補の長さが基準となる参照長より短い場合に減点する係数（brevity penalty）を掛けます。余分な部分は適合率で、不足する部分はこの係数で減点する方法です。
chrFは適合率と再現率を、重み付き調和平均であるF値にまとめます。両方が高いときに高い値になる一方、片方が低ければスコアも下がります。重みを決める係数\(\beta\)が1なら両者を対等に扱い、1より大きければ再現率を重視します。F値の式と性質は§5.5で説明します。
charsimでは、長さの過剰も不足も\(\min(P,R)\)で扱います。BLEUのように不足を補正する別の係数を掛けず、chrFの\(\beta\)にあたる重みも使いません。過不足のどちらを重く減点するかを選ぶ作業がなくなります。
5.2. 文単位の評価と一致数0の扱い
BLEUの原論文では、複数の文からなる評価データ全体で一致数とn-gram数を合計し、各次数の適合率を求めます[1]。平滑化しない定義では、平均に含める適合率が1つでも0になると、幾何平均全体が0になります。1文では高次の一致が得られにくいため、文ごとの評価では平滑化の有無や方法が結果に影響します。
charsimでは、ある次数の一致数が0になっても、他の次数の加点は残ります。例えば§3.4のcaとcatでは、4-gramと5-gramが一致しなくても、1-gramから3-gramまでの重なりにより約0.498になります。短文でも、平滑化を加えずに部分一致を評価できます。
算術平均を使うchrFも、他の次数に一致があれば正のスコアになります。残った一致を加点できる点は、charsimとchrFに共通する性質です。
5.3. 複数参照の集約方法
BLEUは、各単語n-gramについて、参照文ごとの出現回数の最大値を上限として、候補側の一致数を数えます。そのため、異なる参照文にある一致を組み合わせて評価できます。
chrFの複数参照の扱いは実装によります。例えば、評価ライブラリーsacreBLEU[4]のv2.5.1の実装は、各候補に対してF値が最も高い参照文を選びます。
charsimは、各参照文との重なりと参照長を平均してから正規化します。基本形も参照別スコアを平均するため、どちらも参照集合全体との一致を評価します。
例えば、あるn-gramが候補に1回現れ、\(K\)個の参照文のうち1つだけに現れると、その平均重なりは\(1/K\)です。すべての参照文に現れれば1になります。参照文のうち何個に共通するかが加点に反映されるため、参照集合でよく使われる表現を重視できます。
5.4. 次数をまたぐ平均と重み付き和
chrFは、次数ごとに適合率と再現率を求め、その割合をそれぞれ等しい重みで平均します。charsimは、重なりとn-gram数に\(1/n\)を掛けて合計した後、適合率と再現率を求めます。割合を平均するchrFに対し、charsimでは個数を足してから割る点が異なります。
そのため、charsimで各次数がスコアに与える影響は、\(1/n\)だけでなく、取り出せるn-gramの個数にも依存します。同じ参照集合に同じ長さの候補を照合すれば分母が揃うので、スコアの差を次数ごとの加点に分けて調べられます（§4.4）。
5.5. 適合率・再現率の最小値とF値
ここでは適合率\(P\)と再現率\(R\)を共通にし、両者を1つのスコアにまとめる式だけを比較します。F値は、係数\(\beta\gt0\)を使って次のように求めます。少なくとも片方の割合が0なら、F値を0とします。
\[
F_\beta=\frac{(1+\beta^2)PR}{\beta^2P+R}
\]
F値は\(P\)と\(R\)の間に収まります。したがって、同じ\(P,R\)なら、charsimの\(\min(P,R)\)はF値以下です。
\[
\min(P,R)\le F_\beta\le\max(P,R)\qquad(\beta\gt 0)
\]
\(P,R\gt0\)のとき、F値の逆数は次の式で表せます。
\[
\frac1{F_\beta}=\frac{1}{1+\beta^2}\frac1P+
\frac{\beta^2}{1+\beta^2}\frac1R
\]
右辺は\(1/P\)と\(1/R\)の重み付き平均なので、両者の間に収まります。逆数を取ると、本文の不等式が得られます。少なくとも片方が0の場合も、\(F_\beta=0\)という規則から同じ不等式が成り立ちます。
例えば\(P=1\)、\(R=0.5\)なら、\(\beta=1\)のF値は約0.67、\(\min(P,R)\)は0.5です。最小値を使うと、低い方の割合がスコアの上限になり、高い方で補うことができません。余分な部分と不足する部分の両方を減らす、というcharsimの設計に対応します。
実際の文字列を評価するときは、境界記号や次数の集約方法も\(P,R\)に影響します。charsimとchrFの最終スコアを比べるには、それぞれの方法で\(P,R\)を計算する必要があります。
5.6. 文字単位の評価と次数上限
charsimとchrFは文字n-gramを使うため、単語へ分割するトークナイザーを必要としません。綴りの一部が変わっても、残った部分文字列の一致を数えられます。chrF++は文字n-gramに単語1-gramと2-gramを加え、単語単位の一致や隣接関係も評価します[3]。
BLEUの原論文では単語4-gram、chrFの原論文では文字6-gramまでを使っています[1, 2]。ここで比較する設定では、BLEUの幾何平均もchrFの算術平均も、各次数を等しい重みで扱います。
同じ次数でも、単語n-gramと文字n-gramでは照合する範囲が異なります。例えば、ドイツ語の「Lebensversicherung」は1語で18文字あり、単語1-gramには全体が入りますが、文字6-gramには一部しか入りません。単語n-gramを使う場合は、日本語の分かち書きなど、語の区切り方も結果に影響します。
charsimは文字32-gramまでを含め、chrFの文字6-gramより長い表現も直接照合します。同時に\(1/n\)の重みを付けることで、長いn-gram 1個あたりの加点を抑えます。長い一致を評価対象に含めつつ、短い一致に大きな重みを残す組み合わせです。
5.7. 高次の重みと次数上限への感度
次数上限を細かく調整する負担を減らすため、charsimは重なりの加算と\(1/n\)の重み付けを組み合わせます。一致が0の次数を加えても、低次の一致による加点は残ります。また、一様重みで同じ個数を足す場合より、高次の重なりと長さの寄与を小さくできます。
重み付けの違いを見るため、各次数のn-gram数を同じと仮定します。上限32では、次数4を超える項が重み付きn-gram数に占める割合は、一様重みで約88%、\(1/n\)重みで約49%です。各上限での割合は、重みの和から計算できます。
上限\(N\)に対して、次数\(N_0\)を超える項の重みの割合を求めます。\(1/n\)重みでは\(1-H_{N_0}/H_N\)、一様重みでは\(1-N_0/N\)です。ここで\(H_N=\sum_{n=1}^{N}1/n\)は調和数です。表では\(N_0=4\)として計算し、百分率を整数に丸めています。
| 次数4を超える項の重みの割合 | 上限8 | 上限16 | 上限32 | 上限64 |
|---|
| \(1/n\)重み | 23% | 38% | 49% | 56% |
|---|
| 一様重み | 50% | 75% | 88% | 94% |
|---|
この仮定では、\(1/n\)重みでも次数5以上の合計が約半分を占めます。スコアが上限の変更にどれだけ影響されるかは、重みだけでなく、その次数に実際にいくつ一致があるかで決まります。上限を広げても変化が小さいのは、追加する重なりと分母の増分が元の分母に比べて小さい場合や、両者が元のスコアと同じ比率で増える場合です。スコアの変化量を式で求めると、その関係を確認できます。
上限\(N\)での分子を\(A_N\)、分母を\(D_N\)、スコアを\(S_N=A_N/D_N\)とします。\(N_0\)から\(N_1\)へ上限を広げたときの増分を\(\Delta A=A_{N_1}-A_{N_0}\)、\(\Delta D=D_{N_1}-D_{N_0}\)とすると、\(D_{N_0}\gt 0\)のもとで次の式が成り立ちます。
\[
S_{N_1}-S_{N_0}
=\frac{\Delta A-S_{N_0}\Delta D}{D_{N_0}+\Delta D}
\]
分子を\(A_{N_0}+\Delta A\)、分母を\(D_{N_0}+\Delta D\)として、\(S_{N_1}-S_{N_0}\)を通分すると得られます。\(\Delta A=S_{N_0}\Delta D\)ならスコアは変わりません。高次の一致がなく\(\Delta A=0\)なら、\(S_{N_1}=S_{N_0}D_{N_0}/D_{N_1}\)です。
例えば、追加する次数に一致がなく、分母だけが10%増えるなら、スコアは元の\(1/1.1\)、約91%になります。入力の文字列が同じでも、数える次数を増やすと重み付き長さが増え、スコアが下がる例です。一方、候補とすべての参照文が完全一致していれば、分子と分母が同じだけ増えるため、上限を変えても1です。
長い定型句やソースコードが一致する場合も、高次を加えると分子と分母の両方が増えます。上限を変えた派生版を使う場合は、同じデータでスコアや候補の順位への影響を確認し、上限の値を評価条件に記載します。
6. 簡略モデルによる比較
ここでは文字列からn-gramを取り出す代わりに、一致数を仮定してスコアを計算します。§6.1〜§6.3では各次数に同じ一致率を仮定し、長さを補正する式の違いを調べます。§6.4では一致する文字数を揃え、一致が分散する場合と連続する場合を比べます。いずれも、式の働きを調べるための簡略モデルです。
6.1. 長さと一致率の設定
単一参照の文字数を\(\lambda\gt0\)、候補の文字数を\(\hat\lambda\gt0\)とします。空の候補のスコアは0とし、それ以外を次のモデルで扱います。
長さの補正式だけを比べるため、単語と文字の単位の違い、境界記号、次数によるn-gram数の違いを省略します。各次数のn-gram数を候補側で\(\hat\lambda\)、参照側で\(\lambda\)と置きます。短い方にあるn-gramのうち、割合\(p\)が一致すると仮定すると、重なりは次の値です。
\[
m_n=p\min(\hat\lambda,\lambda),\qquad 0\lt p\le1
\]
各次数の重なりとn-gram数が共通なので、適合率と再現率も次数によらず同じです。charsimでは重み付きの合計を割りますが、分子と分母の\(\sum_n1/n\)が相殺されるため、次の\(P,R\)になります。
\[
P=\frac{p\min(\hat\lambda,\lambda)}{\hat\lambda},\qquad
R=\frac{p\min(\hat\lambda,\lambda)}{\lambda}
\]
この\(P,R\)を各指標の式に代入します。chrFのモデルでは、再現率を重視する\(\beta=2\)を使います。
\[
\begin{aligned}
S_{\mathrm{charsim}}&=\min(P,R),\\
S_{\mathrm{chrF}}&=\frac{5PR}{4P+R},\\
S_{\mathrm{BLEU}}&=P\,\mathrm{BP}
\end{aligned}
\]
BLEUのbrevity penaltyにあたる\(\mathrm{BP}\)は、候補が参照文より短いときだけ1未満になります。
\[
\mathrm{BP}=\begin{cases}
1 & (\hat\lambda\ge\lambda),\\
\exp(1-\lambda/\hat\lambda) & (0\lt \hat\lambda\lt \lambda)
\end{cases}
\]
BLEUでは、次数ごとの適合率がすべて\(P\)なので、幾何平均も\(P\)です。chrFでも、算術平均から同じ\(P,R\)が得られます。charsimでは重みの和が相殺されるため、このモデルでは3つとも次数上限に依存しません。
6.2. スコアが最大になる長さ
このモデルでは、3つとも候補長と参照長が等しい\(\hat\lambda=\lambda\)で最大値\(p\)を取ります。charsimの式は次のように簡約できます。
\[
S_{\mathrm{charsim}}
=p\,\frac{\min(\hat\lambda,\lambda)}{\max(\hat\lambda,\lambda)}
\]
候補を参照文より短くすると再現率が、長くすると適合率が低下します。3つの指標で最大値を取る候補長は共通ですが、そこから長さを増減させたときの減点量は異なります。
6.3. 長さの過剰と不足への減点
参照長\(\lambda=100\)、一致率\(p=0.8\)として、参照長から同じ文字数だけずれた候補を比較します。\(\beta=2\)のchrFは再現率を重視するため、長すぎる候補より短すぎる候補を強く減点します。30文字ずれた場合のスコアは、候補長70で約0.60、130で約0.75です。
図1：候補長とスコアの関係（\(\lambda=100,\ p=0.8\)）
青色の破線はcharsim、オレンジ色の実線はBLEU、緑色の実線はchrFのモデルです。赤色の破線は、頂点から左右へ同じ傾きで下がる比較用の補助線です。候補長100以上ではBLEUとcharsimが重なります。
BLEUのモデルは、短い側にbrevity penaltyが働きます。候補長20では約0.015、30では約0.078となり、大きな不足を強く減点します。長い側では適合率だけで決まるため、charsimと同じ\(p\lambda/\hat\lambda\)になります。
charsimのモデルは、候補長が参照長の半分でも2倍でも\(p/2\)となります。長さの比を逆数にしてもスコアが変わらないため、比率に対して対称です。一方、同じ文字数だけ増減させた場合の減点量は異なり、候補長70では0.56、130では約0.62です。
長い側と短い側のスコアの偏りを比べるため、候補長50〜150の整数値をスコアで重み付けして平均した重心\(\bar\mu\)を求めます。同じ文字数だけ長い候補と短い候補が同じスコアなら、重心は100です。長い側のスコアが高いほど、重心は大きい方へずれます。
\[
\bar\mu_{\mathrm{chrF}}\approx103.3,\quad
\bar\mu_{\mathrm{BLEU}}\approx102.7,\quad
\bar\mu_{\mathrm{charsim}}\approx101.5
\]
候補長\(j\)でのモデルのスコアを\(S(j)\)とすると、重心は\(\bar\mu=\sum_{j=50}^{150}jS(j)/\sum_{j=50}^{150}S(j)\)です。候補長の範囲は参照長100を中心に揃えています。数値は§7.4の計算・図生成スクリプトで再計算でき、小数第1位に丸めています。
この範囲では、3つとも長い側の候補に高いスコアを与えるため、重心が100を超えます。charsimのずれは約1.5文字で、3つの中では最も小さくなります。この値は長短へのスコアの偏りを表し、最大スコアを取る候補長はいずれも100です（§6.2）。
6.4. 連続した一致への加点と次数の重み
回答の冒頭にある定型句だけを長くコピーした候補では、その箇所に長いn-gramの一致が集中します。一致する文字数が同じでも、短い一致が分散する候補より高次の加点が増えるため、次数の重みが評価に影響します。この差を調べるため、連続した一致のスコアを分散した一致のスコアで割り、\(1/n\)重みと一様重みで比べます。
候補と参照文の文字数をともに\(\lambda\)に固定し、文字の一致率を\(q\)（\(0\lt q\le1\)）とします。モデル上の1-gramの一致数を\(q\lambda\)に揃え、2-gram以上の一致数を次の2通りで与えます。
- 分散した一致：各位置が独立に確率\(q\)で一致すると考え、一致数の期待値を\(m_n=q^n\lambda\)で近似します。
- 連続ブロック：長さ\(b=q\lambda\)の部分だけが連続して一致すると考え、\(m_n=\max(b-n+1,0)\)と置きます。
境界記号や異なる位置間の偶然の一致は数えません。分散モデルでは、\(n\)文字が連続して一致する確率\(q^n\)に、取り出せる位置の数を掛けます。位置の数は\(n\le\lambda\)なら\(\lambda-n+1\)ですが、ここでは\(\lambda\)で近似します。同じ長さと重みを使う2つのモデルでは分母が共通なので、重み付き重なりの比がスコアの比になります。
次数の重みを\(w_n\)とすると、連続ブロックのスコアを分散した一致のスコアで割った比\(B_N\)は、次の式で求められます。
\[
B_N=\frac{\sum_{n=1}^{N}w_n\max(q\lambda-n+1,0)}
{\sum_{n=1}^{N}w_nq^n\lambda}
\]
\(w_n=1/n\)と\(w_n=1\)を比較します。一様重みの場合も、charsimと同じく重なり数を足してから正規化します。次数ごとの割合を平均するchrFとの比較は§6.1〜§6.3で扱い、ここでは重みの違いだけを調べます。
\(\lambda=100\)、\(q=0.8\)とすると、次数上限32でのスコア比は、一様重みで約5.2倍、charsimと同じ\(1/n\)重みで約1.8倍です。上限を100まで広げると、それぞれ約8.1倍と約2.0倍になります。
図2：一致の分布と次数の重み付け（\(\lambda=100,\ q=0.8\)）
横軸は次数上限、縦軸は連続ブロックのスコアを分散した一致のスコアで割った比です。青色の\(1/n\)重みでは、オレンジ色の一様重みより、この比が小さくなります。値は本文の2つの重なりモデルから計算しています。
この条件では、\(1/n\)重みでも連続一致の方が高いスコアになりますが、一様重みほど差は広がりません。長いn-gramの加点を小さくすることで、連続する表現の一致を評価しつつ、同じ文字数の一致が1か所に集中したときの加点を抑えられます。
連続一致への加点を残しつつ、その影響を抑えられることが、\(1/n\)を選ぶ理由の1つです。定型句のコピーだけに評価が偏るのを抑えたい用途に合います。長い連続一致そのものを重視する用途では、高次の寄与を小さくすることが不利にもなります。
7. 実装メモ
7.1. 基本的な計算手順
参照文がない場合と空文字列を含む場合は、§3.1の規則に従って処理します。通常の計算では、§2.5の\(N'\)から次数上限\(N=\min(N',32)\)を求め、候補と各参照文に境界記号を補います。重み付き重なり\(M_i\)と長さ\(L_t,L_i\)を0で初期化し、\(n=1\)から\(N\)まで次の処理を繰り返します。
- 候補と各参照文からn-gramを取り出し、種類ごとの出現回数を記録した頻度表を作ります。境界記号だけのn-gramは除きます。
- 候補と各参照文の頻度表から、\(m_{i,n}=\sum_g\min(c_{r^{(i)}}(g),c_t(g))\)を求めます。
- 各頻度表の出現回数を合計し、候補と参照文のn-gram数\(\ell_{t,n}\)、\(\ell_{i,n}\)を求めます。
- 重なり\(m_{i,n}\)とn-gram数\(\ell_{t,n}\)、\(\ell_{i,n}\)にそれぞれ\(1/n\)を掛け、対応する\(M_i\)、\(L_t\)、\(L_i\)に加えます。\(L_t\)への加算は、参照文ごとに繰り返さず、各次数で1回だけ行います。
すべての次数を処理したら、基本形では\(M_i/\max(L_t,L_i)\)を参照文ごとに求めて平均します。平均長版では\(M_i\)と\(L_i\)をそれぞれ平均し、\(\bar M/\max(L_t,\bar L_r)\)を求めます。
7.2. 参照集合を固定した事前計算
同じ参照集合で多数の候補を評価する場合、平均長版では参照側の情報を1つの表にまとめられます。各n-gram \(g\)について、候補での出現回数\(m\)に対する平均重なり\(F_g(m)\)を事前計算します。
\[
F_g(m)=\frac1K\sum_{i=1}^{K}\min\bigl(c_{r^{(i)}}(g),m\bigr)
\]
例えば、参照文が2つあり、あるn-gram \(g\)が片方に2回、もう片方には現れないとします。候補での出現回数が1回なら\(F_g(1)=(1+0)/2=0.5\)、2回以上なら\(F_g(m)=(2+0)/2=1\)です。この対応を保存すれば、候補での出現回数から平均重なりを直接取り出せます。
候補を評価するときは、各n-gramの出現回数を数え、対応する\(F_g\)の値を種類ごとに足します。各参照文とひとつひとつ照合する処理を、この表の参照に置き換えられます。参照文が多く、同じ参照集合を繰り返し使う場合に有効です。
\[
\bar m_n=\sum_gF_g\bigl(c_t(g)\bigr),\qquad
\bar M=\sum_{n=1}^{N}\frac{\bar m_n}{n}
\]
\(F_g\)の表は、\(g\)が1回以上、2回以上現れる参照文の数を順に足して作れます。平均参照長\(\bar L_r\)も保存しておけば、新しい候補について求める量は\(\bar M\)と\(L_t\)だけです。保存した\(\bar L_r\)と合わせ、\(\bar M/\max(L_t,\bar L_r)\)を計算します。
\(\min(c,m)=\sum_{a=1}^{m}\mathbf1[c\ge a]\)という等式を使います。\(\mathbf1\)は、条件を満たすとき1、それ以外は0になる指示関数です。\(g\)が1回以上現れる参照文の数、2回以上現れる参照文の数、と順に足していきます。\(m\)回以上現れる参照文の数まで足した和を\(K\)で割ると、\(F_g(m)\)になります。
表には\(F_g(0)=0\)を含め、参照側の最大出現回数まで記録すれば十分です。それを超える\(m\)では最後の値を使い、どの参照文にもないn-gramは0として扱います。
次数32まで事前計算した表は、短い候補にも使えます。実際の次数上限\(N=\min(N',32)\)が32未満なら、\(N\)を超える次数では候補にも参照文にもn-gramがなく、項は0です。したがって、32まで足す実装でも同じ値になり、候補の長さに合わせて表を作り直す必要はありません。
7.3. 平均長と中央値による正規化の違い
極端に長い参照文の影響を減らす案として、平均の代わりに中央値を使う方法があります。重み付き参照長\(L_i\)を小さい順に並べ、中央の値を基準にすれば、分母は\(\max(L_t,\operatorname{median}_iL_i)\)です。
分子を平均のままにすると、平均重なりが中央値を超えることがあるため、中央値で割った比を再現率として解釈できなくなります。主定義では重なりと参照長の両方を平均し、再現率を0以上1以下の一致割合として解釈できるようにしています。
7.4. 空入力と動作確認
§3.1の規則は、割り算の前に条件分岐で処理します。\(K=0\)は未定義なので、エラーまたは欠損値を返します。次の表に、動作確認用の入力と期待するスコアを示します。小数は小数第3位に丸めています。
| 候補 | 参照集合 | 平均長版 | 基本形 |
|---|
"cat" | ["cat"] | 1 | 1 |
"a" | ["b"] | 0 | 0 |
"" | [""] | 1 | 1 |
"" | ["a"] | 0 | 0 |
"a" | [""] | 0 | 0 |
"" | ["", "a"] | 0 | 0.5 |
"ca" | ["cat"] | 0.498 | 0.498 |
"a" | ["a", "abcdefghij"] | 0.134 | 0.528 |
"a" | [] | 未定義 | 未定義 |
候補が空で、参照集合が["", "a"]の場合は、2つの定義の違いを確認できます。平均長版は平均参照長が正なので0、基本形は空同士の1と片方だけが空の0を平均して0.5です。
入力に^や$が含まれる場合も確認してください。入力中のこれらの文字は、通常の文字として数えます。境界記号と混同して除外すると、定義とは異なる値になります。
§3の数値例と§6のモデル計算は、計算・図生成スクリプトで再計算できます。Python 3の標準ライブラリーだけで動作し、直接実行すると日英両方の図も生成します。
7.5. 計算量と打ち切り
文字数\(L\)の1文から取り出せるn-gramは、各次数で\(O(L)\)個なので、次数\(N\)までで\(O(NL)\)個です。全次数を使うと\(N=O(L)\)となり、個数は\(O(L^2)\)に増えます。32で打ち切れば\(O(32L)\)、つまり文字数に比例する個数に抑えられます。参照文が複数ある場合は、それぞれの文字数に応じた個数のn-gramを前処理します。
実際の処理時間には、n-gramの保存方法とハッシュ値の計算方法も影響します。上限を32に固定すると、n-gram 1個の長さも32以下に収まります。ハッシュ表の操作が平均定数時間で済む実装なら、n-gramの生成・集計にかかる平均的な時間は、文の文字数に比例します。
n-gram 1個を取り出すたびに\(n\)文字をコピーしてハッシュ値を計算すると、時間は\(O(N^2L)\)、全次数では\(O(L^3)\)に達します。上限32を固定し、辞書操作が平均定数時間で済む実装なら、期待計算時間は\(O(L)\)です。
次数上限も変数として扱う場合は、各n-gramを定数時間で更新できる表現と辞書操作を仮定すれば、生成・集計を期待\(O(NL)\)時間で処理できます。ハッシュ値を識別子にする場合は、衝突によって異なるn-gramを同一視しないための処理も必要です。
8. 設計上の限界
charsimのスコアを評価に使う際は、文字列の一致で分かる範囲と、参照集合・前処理への依存を考慮します。
- 意味が同じでも、共通する文字列が少ない言い換えは低いスコアになります。意味の一致まで評価する用途では、人による確認や意味を評価する別の方法を併用します。
- 語順を評価できるのは、n-gramに含まれる範囲です。1-gramは文字の並び順を区別せず、単語を並べ替えても、各単語の内部にある部分文字列の一致は残ります。
- 次数上限32では、それより長いn-gramを直接照合できません。上限内でも\(1/n\)重みが高次の加点を小さくするため、長い定型句やコードの一致そのものを重視する用途では、目的に合うかを確認します。
- 参照集合や前処理が変わると、同じ候補でもスコアが変わります。候補同士を比較する際は、この2つを揃えます。言語やタスクをまたぐ比較でも、評価条件の違いを考慮します。
9. まとめ
charsimは、文字n-gramの一致を足し合わせ、適合率と再現率の小さい方をスコアにします。短文の部分一致を平滑化なしに評価し、長さの過不足も同じ式で減点できるため、評価時に平滑化の方法や適合率と再現率の重みを選ぶ必要がありません。
重み\(1/n\)と次数上限32は、長い一致も数えながら、その加点と計算量を抑えるための設定です。次数上限を変えると、重なりだけでなく正規化に使う長さも変わります。派生版を使う場合は、実際の評価データでスコアや候補の順位への影響を確認します。
主定義の平均長版は、参照集合全体との一致を評価し、参照側の情報を保存して繰り返し使う用途に適しています。採用時には、参照集合の平均長が評価したい回答を代表するかを確認します。各参照文の長さを基準にしたい場合は基本形、どれか1つとの一致を評価したい場合は最大値、異なる種類の正解を扱う場合は集合ごとの評価を選べます。
10. 参考文献
比較対象のBLEU、chrF、chrF++と、実装上の参照先であるsacreBLEUの文献です。
- [1] Kishore Papineni, Salim Roukos, Todd Ward, Wei-Jing Zhu, "BLEU: a Method for Automatic Evaluation of Machine Translation," ACL, 2002.
- [2] Maja Popović, "chrF: character n-gram F-score for automatic MT evaluation," WMT, 2015.
- [3] Maja Popović, "chrF++: words helping character n-grams," WMT, 2017.
- [4] Matt Post, "A Call for Clarity in Reporting BLEU Scores," WMT, 2018. （sacreBLEU）
いもすの関連論文として、文字n-gramに基づく評価手法を検討した次の2本があります[5, 6]。このうち翻訳評価の研究とは、重なりの数え方が共通し、長さの補正方法が異なります。
- [5] 今城健太郎, 平野正徳, 鈴木脩司, 三上裕明, "pfgen-bench: 日本語事前学習モデルのための文章生成性能評価ベンチマーク," Jxiv, 2024. 質問への回答を評価するベンチマークの提案です。流暢さを測るFluency指標では、候補に現れる文字n-gramについて、参照回答群での出現頻度を足し合わせています。本記事の\(\min(c_r,c_t)\)による重なりとは、出現回数の扱いが異なります。
- [6] 今城健太郎, 平野正徳, "高精度翻訳モデルのための自動評価手法の検討," Jxiv, 2026. n-gramが\(i\)回以上現れるかを0または1で表す二値特徴量\(f_{w,i}\)を使い、多数の参照訳との重なりを評価しています。長さの補正は参照訳の文字数の中央値を使う別の係数で行い、本記事の\(\max(L_t,\bar L_r)\)による正規化とは異なります。
最終更新日: 2026年10月26日