名寄せの定量評価と逐次検定について

こんにちは、技術本部 Nayoseグループでバックエンドエンジニアをしている上田です。

普段はデータの名寄せサービスを開発しています。Sansanの名寄せというのは、こちらのページに記載のとおり、別々のデータとして存在する同じ会社や人物のデータをひとまとめにグルーピングすることを言います。

大抵はWebアプリケーション開発をしていますが、企画段階や技術検証フェーズでは仮説検証をすることもあります。今回はそのフェーズで行った、名寄せアルゴリズムを定量評価する際に利用する統計的仮説検定の話を紹介したいと思います。

なお、本記事はSansan Advent Calendar 2023の12日目の記事です。

名寄せの評価

業務では新しい名寄せアルゴリズムを開発することがあります。
アルゴリズム開発の基本戦略は、ユーザーが取り込んだ名刺と、マスターとして存在する会社データを同じ会社としてグルーピングできたら正解、別の会社のデータを紐づけてしまったら不正解と定義して、その正解率を高めるアルゴリズムを採用するというものです。

正解率を算出する1つの手法は、事前に決めた手順で名寄せ対象のデータセットを準備し、アルゴリズムをかけた後、目視で正誤を確認する方法です。
正解率を評価する際は、求められた正解率が、本番適用したい水準よりも高いかどうかを仮説検定で評価することがあります。

例えば、本番適用水準の正解率を0.95とします。このとき、有意水準0.05、検出力0.80で帰無仮説p=0.95、対立仮説p>0.95の片側検定をするという要領です。
仮説検定については、以下の記事にも解説がありますのでよければご覧ください。
buildersbox.corp-sansan.com

固定サンプルサイズ検定の課題

ここで一つ問題があります。評価する正解率のもとになる名寄せ対象データセットを何件用意するか？という問題です。

前述の仮説検定の場合、母比率の差の検定となるためR言語の power.prop.test()（マニュアル）という基本統計関数で簡単に求めることができます。
開発したアルゴリズムの真の正解率が仮に0.96の場合、実際に必要なサンプルサイズを求めると、5,313件*1となります。
5,000件のデータを目視で確認するのは非常にコストがかかるため、気軽には利用できない方法です。

少し状況を変えて、アルゴリズム開発の初期段階を想定してみます。
初期段階では、残念ながら正解率がそう高くなることはないです。例えば、100件のデータを見て、80件が正解だとします。この時の95%信頼区間は[0.72, 0.88]となるので、誤差込みで0.88くらいにはなりえる性能と言えそうです。
そこで、帰無仮説p=0.80、対立仮説p=0.90でサンプルサイズを求めると、157件となります。このケースではだいぶ少なくなりましたが、元々100件で見積もった経緯からすると、まだ多いです。

このように、サンプルサイズを固定して行う一般的な仮説検定には実務利用に対して課題があります。改めて課題を列挙しておきます。

サンプルサイズを事前に決めないといけない
そしてそれは非常に大きいサイズとなる
その大きなサンプルサイズに対して、全件を調査した後でなければ評価できない

よって、正誤判定にコストが掛かり、短いサイクルで反復的に仮説検定をしたいユースケースには不向きなことが多い手法です。

逐次検定の導入

逐次検定（Sequential Test）はこの課題を克服する一つの検定方法です。

逐次検定の歴史については、こちらの記事"Fully Sequential vs Group Sequential Tests"が参考になるので、DeepL翻訳をベースに引用して紹介します。

それ以前にも逐次検定の手順はいくつか応用されていたが、現代の逐次検定における最初の重要な開発は、第2次世界大戦中に起こった。1943年、当時コロンビア大学の統計研究グループの一員として働いていたAbraham Waldは、逐次確率比検定（SPRT）を開発した。
SPRTは、戦争中に生産されるさまざまな機器、車両、弾薬などの品質を保証するコストを削減することを目的としていた。工業試験の多くは、被検査品にとって破壊的であり、かなりの労力を要するため、検査品目の数を最小限に抑え、品目のバッチをクリアするか、不適格と宣言することが目標であった。
SPRTは、タイプIとタイプIIのエラーコントロールの点で、同等の設計の固定サンプル試験と比較して、必要な平均サンプルサイズを40-50％削減することに成功している。

このように、検査の回数を減らす目的で逐次検定が発展し、事前にサンプルサイズを決めて行う通常の仮説検定（固定水平検定; Fixed Horizen Test*2）と比較して半数もサンプルサイズを削減する成果が上がるとのことです。

一方で、以下のようにも指摘されています。

この成功の平均的な代償は、逐次検定が結論に達するまでの最大標本サイズの増加であり、等価な固定水平検定と比較して、任意の標本での統計的検出力が低下することを意味します。

つまり、平均してサンプルサイズを減らす代わりに検出力も低下する（帰無仮説が間違っているときにそれを棄却できない）トレードオフになっているということです。というのも、平均して減りますが、最悪のケースでは固定サンプルサイズを上回り、検定が終わらない可能性があるためです。
とはいえ、信頼性は多少犠牲にしつつも、サンプルサイズを小さくすることで意思決定を早くする効果があるため、利用価値のある検定方法です。

ここからは、単純なSPRTについてその効果を検証しつつ、そのデメリットを補完する群逐次検定（Group Sequential Test; GST）について紹介します。

SPRTの解説

仮説検定の最良検定を与えるネイマン・ピアソンの定理（Neyman–Pearson lemma）から、 $m$ 件の標本から計算される尤度比 $L_{m}$ を用いて次の検定を考えることができます。
まず、 $L_{m} < c_{1}$ なら帰無仮説を採択し、 $L_{m} > c_{2}$ なら対立仮説を採択し、そして、

$\displaystyle c_{1} < L_{m} < c_{2} \quad (m=1,2,\dots)$

が成り立つ限りは、帰無仮説、対立仮説いずれの仮説の採択も保留して、次の標本を観測し、再度検定します。そして、 $L_{m} < c_{1}$ になれば直ちに標本抽出をやめて帰無仮説を採択し、逆に $L_{m} > c_{2}$ になれば直ちに抽出をやめて対立仮説を採択するようにします。

1945年にA. Wald*3は上記の採択域の境界となる $c_{1}$ , $c_{2}$ の値の近似値を、この逐次検定における第一種、第二種の誤りの大きさである $\alpha$ , $\beta$ を用いてそれぞれ以下のとおり導きました。

$\displaystyle c_{1} \approx \frac{\beta}{1-\alpha}, \qquad c_{2} \approx \frac{1-\beta}{\alpha}$

この方法は、逐次確率比検定（Sequential Probability Ratio Test; SPRT）と呼ばれています。

名寄せの問題では正解、不正解の二値分類となるため、確率分布に二項分布*4を仮定します。通常のサンプルサイズと区別するために、抽出済みのサンプルサイズを $m$ とし、そのうち正解となった回数を $d_{m}$ とします。すると、尤度比は以下になります。

$\displaystyle L_{m} = \frac{{}_{m}C_{d_{m}} p_{1}^{d_{m}} q_{1}^{m - d_{m}}}{{}_{m}C_{d_{m}} p_{0}^{d_{m}} q_{0}^{m - d_{m}}} = \left( \frac{q_{1}}{q_{0}} \right)^{m} \left(\frac{p_{1}q_{0}}{p_{0}q_{1}} \right)^{d_{m}}$

ここで、 $p_{0}$ , $p_{1}$ はそれぞれ帰無仮説、対立仮説における母比率、 $q=1-p$ です。この式から、以下を得ます。

$\displaystyle \frac{L_{m+1}}{L_{m}} = \frac{q_{1}}{q_{0}} \left(\frac{p_{1}q_{0}}{p_{0}q_{1}} \right)^{d_{m+1}-d_{m}} \quad (m = 0, 1, 2, \dots)$

ただし、 $L_{0} = 1$ です。両辺の対数をとって変形すると、以下のような漸化式になります。

$\displaystyle \log{L_{m+1}} = \log{L_{m}} + \log \frac{q_{1}}{q_{0}} + X_{m+1} \log \left(\frac{p_{1}q_{0}}{p_{0}q_{1}} \right) \quad (m = 0, 1, 2, \dots)$

なお、 $X_{m+1} = d_{m+1} - d_{m}$ は $m+1$ 回目で成功したら+1、そうでなければ0になるような変数です。つまり、 $m+1$ 回目のベルヌーイ試行の結果と同一です。

この漸化式を用いると、SPRTによる検定は以下のフローで実現できます。

1. 1件サンプリングし、 $L_{1}$ を計算する。
2. $L_{1} < c_{1}$ なら帰無仮説を採択し、 $L_{1} > c_{2}$ なら対立仮説を採択して検定を終了する。
3. $c_{1} < L_{1} < c_{2}$ なら次の標本をサンプリングし、 $L_{2}$ を計算する。
4. （これを繰り返す）
5. $m$ 番目の標本をサンプリングし、1件サンプリングし、 $L_{m}$ を計算する。
6. $L_{m} < c_{1}$ なら帰無仮説を採択し、 $L_{m} > c_{2}$ なら対立仮説を採択して検定を終了する。
7. $c_{1} < L_{m} < c_{2}$ なら次の標本をサンプリングし、 $L_{m+1}$ を計算する。
8. （これを繰り返す）

シミュレーション

SPRTの効果を検証するために、シミュレーションしてみます。
名寄せの正解率を表す母比率（二項分布のパラメータ）pについて、帰無仮説p=0.95とし、対立仮説として以下4つを用意します。

1. 対立仮説p=0.96
2. 対立仮説p=0.94
3. 対立仮説p=0.99
4. 対立仮説p=0.90

それぞれについて、前項のSPRT漸化式を用い、各検定の終了回数の平均値と標準偏差、実際の検出力を算出します。シミュレーション条件は以下とします。

$\alpha$ （第一種の誤り）: 0.05
$\beta$ （第二種の誤り）: 0.20
シミュレーション回数: 10,000回
標本抽出回数 $m$ の上限: 片側検定における固定サンプルサイズ

最後の条件は、SPRTのシミュレーションを有限時間内で終わらせるための制約になります。通常の仮説検定におけるサンプルサイズよりも大きくなってしまった場合は、SPRTの恩恵は得られないため、その回数に達したらシミュレーションを打ち切ります。

結果は以下になりました。

表. SPRTシミュレーション結果
対立仮説	0.96	0.94	0.99	0.90
終了回数平均値	1,721	1,940	91	102
終了回数標準偏差	1,136	1,314	44	72
固定サンプルサイズ	5,313	6,426	224	343
削減率	64%	70%	59%	70%
検出力	0.7997	0.7888	0.8556	0.7880
固定サンプルサイズ超え割合	0.0174	0.0134	0.0279	0.0165

再現コードはこちらに公開しているので、ご参照ください。

この結果を見て分かることは以下です。

いずれの検定も固定サンプルサイズに対して、平均して60%~70%のサンプルサイズを削減できました
$+ 1 \sigma$ の場合でも40%~50%削減できました（対立仮説0.96の場合、 $1-(1,721+1,136)/5,313=0.46$ ）
一方で、固定サンプルサイズ以上になったシミュレーションが10,000回中、平均して188回（1.88%）発生しています
実際の検出力については、設定した0.80をやや下回るケースが過半数を占めました

このことから、大まかな判定（対立仮説0.99 or 0.90）においては100回程度の標本抽出で結論を出すことが可能であると期待でき、アルゴリズム開発の初期段階において、固定サンプルサイズ検定と比較して高速な評価を実現できそうです。

SPRTの欠点とGSTの台頭

冒頭で紹介したとおり、単純なSPRTには下記の欠点があります。

検定終了までの平均回数は小さいですが、最悪ケースで終わらない場合があります。これは、実務に存在する作業期限やデータ数に上限がある場合には使いづらくなります。
事前にサンプルサイズを見積もることができないため、作業時間の見積もりが困難です。
1件ずつのサンプリングが必要になるので、バッチ処理的に評価できません。

特に、人間を対象にする臨床試験の現場では、これらの欠点は致命的だったため、それらの欠点を補う群逐次検定（Group Sequential Test; GST）という新しい逐次検定の方法が開発されました。

GSTの特徴は以下です。

一度の検定で複数件のサンプルをまとめて評価可能（バッチ処理が可能）
予め検定の回数を設定できる（作業期限を考慮できる）
アルファ消費関数という仕組みが導入され、一般化可能性が高い

最初の2点は実務上非常に有益です。また、3点目も注目です。これは雑に言うと、結論を将来のデータについても適用しやすいというものです。

特に、ユーザーが入力するデータに基づいて意思決定したい状況においては、真の母集団というものは特定できません。あくまでも今手元にあるデータでしか判断できないです。より一般化可能性の高い手法であれば、今手元にあるデータで出した結論を将来手に入るユーザーデータについても適用しやすい、というのですから非常に望ましいです。
こういった特徴をもつGSTは、情報検索分野におけるオンライン評価やA/Bテストに応用されています*5。GSTの詳細やシミュレーション、実務への応用事例については、別の機会とさせてください。