Conformal Predictionによるしきい値調整

背景

しきい値は、多くの場合「なんとなく良さそう」という経験的な決め方になりがち
- 0.9以上ならpositiveと判定する、など
Conformal Predictionを使うと、しきい値の決め方に統計的な保証を持たせられる
しきい値調整という実務に絞って、Conformal Predictionの考え方を整理する

しきい値をどう決めるか、という問題

経験的なしきい値選定（パーセンタイル法）

よくあるやり方は、キャリブレーション用データ（学習には使っていないホールドアウトデータ）に対してモデルのスコアを計算し、その分布から「これくらいなら安全」というパーセンタイル点をしきい値にする方法
例えば、negativeサンプルのスコアを集めて、その99パーセンタイル点をしきい値にする、というやり方
直感的で実装も簡単だが、以下のような弱点がある
- そのパーセンタイル値が、本番データでも本当に同じ意味を持つのか（同じ誤り率になるのか）の保証がない
- キャリブレーションデータの件数が少ないと、パーセンタイル自体の推定がぶれる

経験的な方法の弱点

「99パーセンタイル」という言葉は、キャリブレーションデータの中では正確でも、未来の新しいデータに対して「エラー率が1%以下になる」ことを保証しない
特にサンプル数が少ない場合、単純な分位点の推定には誤差が乗る
この誤差を統計的に補正し、有限サンプルでも成り立つ保証を与えるのがConformal Prediction

Conformal Predictionとは

モデルの中身に依存しない（モデルフリーな）枠組みで、予測に対して統計的に妥当な保証を与える手法
「分布によらない（distribution-free）」という特徴があり、スコアの分布がどんな形であっても、同じ手順で保証が成り立つ
唯一の前提は、キャリブレーションデータと将来のテストデータが交換可能（exchangeable、i.i.d.なデータもこれに含まれる）であること

交換可能性（exchangeability）とは

i.i.d.（独立同分布）は、交換可能性の一種
i.i.d.なら必ず交換可能だが、逆は成り立たない（交換可能でも、i.i.d.とは限らない）
交換可能性とは、$n$個のデータ$(x_1, \ldots, x_n)$の同時分布が、順番を入れ替えても変わらないという性質のこと

$$ P(x_1, \ldots, x_n) = P(x_{\pi(1)}, \ldots, x_{\pi(n)}) $$

$\pi$は、$1, \ldots, n$のどんな並べ替え（順列）でもよい
i.i.d.より緩い条件なので、データ同士に依存があっても交換可能性は満たされる場合がある

以下は、独立ではないが交換可能な例である。

非復元抽出（sampling without replacement）: 母集団からデータを1件ずつ取り出すとき、取り出したデータを母集団に戻さずに、次の抽出を行う方法
- 例: トランプ52枚から1枚引いて、それを戻さずに次の1枚を引く
- 対義語は復元抽出（sampling with replacement）で、こちらは毎回母集団に戻してから次を引く（同じデータが何度でも選ばれうる）
- 非復元抽出では、各データの抽出結果はお互いに影響し合う（1枚目でハートのAを引いたら、2枚目でハートのAが出る確率は0になる）ため、独立ではない
- しかし、母集団自体は変わらないので、どの順番で引いても「その$n$枚の組み合わせが出る確率」は同じになる。これが「独立ではないが交換可能」という状態

Conformal Predictionの証明で重要なのは、「キャリブレーションデータ$n$件＋テストデータ1件」を合わせた$n+1$件が交換可能でありさえすればよい、という点である。i.i.d.である必要はなく、より緩い条件で足りるというのが、この手法の強みの1つ。

Nonconformity score（非適合度スコア）

Conformal Predictionでは、まずモデルの出力を「どれだけ普通と違うか（適合していないか）」を表すスコアに変換する
分類の場合、以下のようなスコアがよく使われる

$$ s(x, y) = 1 - \hat{p}(y \mid x) $$

$\hat{p}(y \mid x)$は、モデルが出力する「入力$x$に対してラベル$y$である確率」
正解ラベルの予測確率が低いほど、このスコアは大きくなる（＝モデルの予測と実際のラベルが「適合していない」）

Conformal Predictionによるしきい値の求め方

キャリブレーションデータでのスコア計算

キャリブレーションデータ$n$件それぞれについて、正解ラベルに対するnonconformity score $s_1, \ldots, s_n$を計算する

有限サンプル補正つき分位点

以下は、目標エラー率$\alpha$（例えば5%）に対応する分位点$\hat{q}$の求め方である。

$$ \hat{q} = \text{Quantile}\left(\{s_1, \ldots, s_n\}; \ \frac{\lceil (n+1)(1-\alpha) \rceil}{n}\right) $$

単純に$(1-\alpha)$分位点を取るのではなく、$\frac{\lceil (n+1)(1-\alpha) \rceil}{n}$という、少しだけ大きい分位点を取っているのがポイント
この補正が、サンプル数$n$が有限であっても保証が成り立つようにするための調整になっている
$n$が大きくなるほど、この補正値は$(1-\alpha)$に近づいていく
同じことだが、$\hat{q}$は「$s_1, \ldots, s_n$を小さい順に並べたとき、$k = \lceil (n+1)(1-\alpha) \rceil$番目に小さい値」と言い換えられる
次の具体例では、この言い換えの方で計算する
注意点として、この分位点は一般的な補間つきの分位点（線形補間など）とは一致しない。値と値の間を補間せず、$k$番目の値をそのまま使う（段階的な）分位点である点がポイント

しきい値としての解釈

新しい入力$x$に対して、nonconformity scoreが$\hat{q}$以下となるラベルだけを予測集合に含める、というのが本来のConformal Predictionの出力（予測集合）
二値分類でFA（誤検知）を抑えたい、という文脈に絞ると、これは「予測確率が、ある値以上ならpositiveとする」という単一のしきい値の形に単純化できる
つまり、経験的なパーセンタイル法とほぼ同じ計算をしているが、分位点の取り方に前述の有限サンプル補正が入っている点が異なる

具体例：二値分類でのしきい値計算

迷惑メール判定（positive = 迷惑メール）を例に、実際に手で計算してみる
目標: 本当は迷惑メールではない（negative）メールを誤って迷惑メール判定してしまう率を、20%以下に抑えたい（$\alpha = 0.2$）
キャリブレーションデータとして、本当はnegativeだと分かっている9件のメールを用意し、それぞれモデルが出す「迷惑メールである確率」を集める

以下は、9件のキャリブレーションデータのスコア（迷惑メール確率）を小さい順に並べたものである。

$$ 0.02,\ 0.05,\ 0.05,\ 0.08,\ 0.10,\ 0.12,\ 0.15,\ 0.22,\ 0.31 $$

$n = 9$、$\alpha = 0.2$なので、$k = \lceil (n+1)(1-\alpha) \rceil = \lceil 10 \times 0.8 \rceil = \lceil 8 \rceil = 8$
つまり、9件のスコアのうち小さい方から8番目の値を$\hat{q}$として使う
8番目の値は$0.22$なので、$\hat{q} = 0.22$

これで、しきい値が$0.22$と決まった。新しく届いた3通のメールに対して、モデルが出す迷惑メール確率がそれぞれ$0.10$・$0.25$・$0.40$だったとすると、以下のように判定する。

$0.10 \leq 0.22$ → negativeと判定（受信）
$0.25 > 0.22$ → positiveと判定（迷惑メール扱い）
$0.40 > 0.22$ → positiveと判定（迷惑メール扱い）

補正の効果を確認するために、同じ9件のスコアに対して、補正なしの単純な80パーセンタイル（線形補間）を計算すると、以下のようになる。

$$ \text{Quantile}_{0.8}^{\text{naive}} = 0.178 $$

補正なしだと$0.178$、Conformal Predictionの補正ありだと$0.22$と、後者の方が少し大きい（＝positive判定に慎重になる）しきい値になる
サンプル数$n=9$が少ないため、この差が目立って出ている。$n$が大きくなるほど、この2つの値は近づいていく
この差こそが、有限サンプルでも「$\alpha=0.2$以下」という保証を成り立たせるための補正分

FARとFRRを両方Conformal Predictionで保証する

ここまではFA（誤って受理してしまう率、FAR）だけを抑える例だったが、逆側のエラーであるFRR（本来positiveなのに誤って拒否してしまう率）も同時に考えたいことがある
経験的な方法では、FARとFRRの曲線が交わる点（Equal Error Rate、EER）をしきい値にすることが多いが、これは統計的な保証を持たない、単なる経験的な交点にすぎない
Conformal Predictionなら、FARとFRRの両方を、それぞれ統計的な保証つきで同時に満たすしきい値を求められる

2つのしきい値を別々に求める

negative側のキャリブレーションデータから、$\hat{q}_{\text{FAR}}$を求める（$p(x) > \hat{q}_{\text{FAR}}$ならpositive、というルールで$\text{FAR} \leq \alpha_{\text{FA}}$を保証するしきい値）
positive側のキャリブレーションデータから、$\hat{q}_{\text{FRR}}$を求める（$p(x) \leq \hat{q}_{\text{FRR}}$ならnegative、というルールで$\text{FRR} \leq \alpha_{\text{FR}}$を保証するしきい値）
どちらも、前述の「有限サンプル補正つき分位点」の手順をそのまま使うが、キャリブレーションに使うデータのクラスが逆になる

両立できる条件

以下が成り立てば、この2つの間のどの$t$を選んでも、両方の保証が同時に成り立つ。

$$ \hat{q}_{\text{FAR}} \leq \hat{q}_{\text{FRR}} $$

理由は、それぞれの保証が単調な集合の包含関係でできているため
$\text{FAR}(t)$は$t$を上げるほど単調に下がり、$\text{FRR}(t)$は$t$を上げるほど単調に上がる
$t \geq \hat{q}_{\text{FAR}}$なら、$\{p(x) > t\}$は$\{p(x) > \hat{q}_{\text{FAR}}\}$の部分集合になるので、$\text{FAR}(t) \leq \alpha_{\text{FA}}$がそのまま保たれる
同様に$t \leq \hat{q}_{\text{FRR}}$なら、$\text{FRR}(t) \leq \alpha_{\text{FR}}$がそのまま保たれる
つまり、区間$[\hat{q}_{\text{FAR}}, \hat{q}_{\text{FRR}}]$の中でどこに$t$を置いても、どちらの保証も壊れない。むしろ境界から離れるほど、両方に余裕（マージン）が乗る方向に働く
中間点$t = (\hat{q}_{\text{FAR}} + \hat{q}_{\text{FRR}})/2$を使うのが分かりやすいが、区間内であればどこでもよい

両立できない場合

$\hat{q}_{\text{FAR}} > \hat{q}_{\text{FRR}}$（区間が空）の場合は、$\alpha_{\text{FA}}$と$\alpha_{\text{FR}}$を同時に満たすしきい値が存在しないことを意味する
この場合、中間を取っても意味がない
目標のどちらか（あるいは両方）を緩めるか、モデル自体の性能を上げる必要がある、という診断に使える

保証されること・されないこと

marginal coverageの保証

以下は、Conformal Predictionが与える保証である。

$$ P\left(y_{\text{test}} \in C(x_{\text{test}})\right) \geq 1 - \alpha $$

$C(x_{\text{test}})$は、テスト入力に対する予測集合（しきい値の文脈では「positiveと判定される領域」）
キャリブレーションデータとテストデータが交換可能であれば、サンプル数に関わらずこの不等式が成り立つ
「marginal」は、「キャリブレーションデータの取り方（乱数）ごと平均すると」という意味
- 1回のキャリブレーションで固定された$\hat{q}$に対して、個々の入力$x$ごとに条件づけて成り立つ保証（conditional coverage）ではない
- キャリブレーションをやり直すたびに変わる$\hat{q}$も含めて、全体として平均するとこの不等式が成り立つ、という意味

なぜ成り立つのか（交換可能性と順位の対称性）

この保証は近似ではなく、交換可能性（exchangeability）だけから導ける、組み合わせ論的な事実
キャリブレーションの$n$個のスコア$s_1, \ldots, s_n$と、テストデータのスコア$s_{n+1}$を合わせた$n+1$個が交換可能（どの並び順も同じ確率で起こる）だとする
このとき、$s_{n+1}$が全体の中で何番目に大きいかは、対称性からどの順位も等確率になる
したがって、$s_{n+1}$が上位$k$番目以内に入る確率は、ちょうど$\frac{k}{n+1}$になる

以下のように$k$を選んでおくと、この確率が目標の$1-\alpha$以上になることが保証される。

$$ k = \lceil (n+1)(1-\alpha) \rceil \implies \frac{k}{n+1} \geq 1 - \alpha $$

この議論は、モデルの中身にも、スコアの分布の形にも一切依存していない
モデルの性能が悪くても、この保証自体は定理として成り立つ（ただし、モデルが悪いとしきい値が緩くなりすぎて、実用上は使い物にならなくなる、という形で影響が出る）
つまり、保証の強さは丸ごと「交換可能性」という前提に懸かっている。分布シフトなどでこの前提が崩れると、証明も成り立たなくなる

条件付きカバレッジは保証されない

marginal coverageは、データ全体で平均した保証であって、クラスやサブグループ単位では保証されない
例えば、あるサブクラスだけエラー率が目標を大きく超えていても、別のサブクラスでエラー率が低ければ、全体の平均としては目標を満たしてしまうことがある
対策として、クラスごとに別々にキャリブレーションを行うclass-conditional conformal predictionという拡張がある
- クラスごとにキャリブレーションデータを分けて、それぞれ別の$\hat{q}$を求める

分布シフトで保証が崩れる

交換可能性の前提が崩れると（キャリブレーション時と本番運用時でデータの分布が変わると）、保証は成り立たなくなる
これは、以前書いた分布シフトの問題そのもの
運用中にデータの性質が変わっていないか、定期的に確認する必要がある

実際に必要なサンプル数

キャリブレーションデータの件数$n$は、大きく2段階で考える。

最低限必要な件数（有限であるための下限）

$k = \lceil (n+1)(1-\alpha) \rceil$が$n$を超えると、$\hat{q}$が存在しなくなる（＝しきい値が無限大になり、全部positive扱いになってしまう）
この条件から、保証が成り立つための絶対的な下限が以下のように求まる

$$ n \geq \frac{1}{\alpha} - 1 $$

例えば$\alpha = 0.05$（目標エラー率5%）なら、最低でも$n \geq 19$必要
これはあくまで「保証が数学的に成立するための下限」であって、「実用に足る精度」とは別の話
境界を$\alpha$側から見ると、$\alpha \geq \frac{1}{n+1}$であれば成立し、$\alpha < \frac{1}{n+1}$（厳密に小さい）だと成立しない、という条件になる
- ちょうど$\alpha = \frac{1}{n+1}$の場合はギリギリ成立し、その場合$k=n$になるので、$\hat{q}$はキャリブレーションデータ中の最大値そのものになる（マージンがない、際どいケース）
- 例えば$n=9$なら$\frac{1}{n+1}=0.1$なので、$\alpha=0.1$は成立するが$\alpha=0.09$は不足する

実用上必要な件数（保証のブレを抑える）

marginal coverageの保証は、どんな$n$でも「平均すれば」成り立つが、1回のキャリブレーションで得られる$\hat{q}$の実際のカバレッジは、$n$が小さいとブレる
このブレの標準偏差は、キャリブレーションデータの取り方に関するBeta分布の性質から、おおよそ以下のように近似できる

$$ \text{std}(\text{実際のカバレッジ}) \approx \sqrt{\frac{\alpha(1-\alpha)}{n}} $$

具体的な数字を入れると、以下のようになる
- $\alpha=0.2$、$n=9$（前述の具体例と同じ条件）: std $\approx 13\%$。目標20%に対して、実際は大きくブレうる。手計算で仕組みを説明するには良いが、実用には足りない件数
- $\alpha=0.05$、$n=100$: std $\approx 2.2\%$
- $\alpha=0.05$、$n=1000$: std $\approx 0.7\%$
経験則として、$n$が数百〜1000以上あると、実運用で許容できる程度までブレが小さくなることが多い

実務上の注意点

前述の実装イメージではnegative_scoresだけを使ってキャリブレーションするので、「全サンプル数」ではなく「negativeクラスの件数」がこの$n$に当たる
class-conditional conformal predictionのように、クラスごとに較正を分ける場合は、クラスごとにこの$n$の条件を満たす必要がある
- 件数が少ないクラス・サブクラスがあると、そこだけ保証が緩くなったり、$\hat{q}$が求まらなくなったりするので注意が必要

実装イメージ

以下は、二値分類でのしきい値調整をConformal Predictionで行う場合の実装イメージである。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import numpy as np

# calib_scores: キャリブレーションデータに対する、モデルのpositive確率
# calib_labels: キャリブレーションデータの正解ラベル（0 or 1）
# negativeサンプルだけを使って、FA率を抑えるしきい値を求める
negative_scores = calib_scores[calib_labels == 0]

n = len(negative_scores)
alpha = 0.01  # 目標エラー率（この場合はFA率）1%

q_level = np.ceil((n + 1) * (1 - alpha)) / n
threshold = np.quantile(negative_scores, min(q_level, 1.0), method="inverted_cdf")

# 本番では、モデルのpositive確率がこのthresholdを超えたらpositiveと判定する

q_levelが1を超える場合（サンプル数が少なすぎる場合）は、保証を与えられないケースなので、サンプル数を増やす必要がある
method="inverted_cdf"を指定しているのは、これが前述の「小さい方から$k$番目の値」という定義と厳密に一致する分位点の取り方だから
- method="higher"など、他の補間方法を指定すると、$k$番目の値より大きい値になり、具体例で計算した$\hat{q}$とは異なる結果になってしまう

運用での使い方

キャリブレーションデータは、本番データの分布とずれないよう、定期的に更新して再計算する
目標エラー率$\alpha$を明示的なパラメータとして持てるため、「FA/hourをこの値以下に抑えたい」といった運用要件に、しきい値選定の手順を直接結びつけやすい
ただし、marginal coverageの保証はクラス・サブクラス単位では成り立たないため、サブクラスごとに運用上重要な誤り率がある場合は、class-conditionalな較正も検討する

まとめ

しきい値の経験的な決め方（パーセンタイル法）は、直感的だが将来のデータに対する統計的な保証がない
Conformal Predictionは、nonconformity scoreの分位点を有限サンプル補正つきで求めることで、分布によらない統計的保証（marginal coverage）を与える
保証されるのはデータ全体で平均したエラー率であり、クラス・サブグループ単位の保証や、分布シフトへの耐性は別途考える必要がある
経験的なパーセンタイル法とほぼ同じ手順で計算できるため、既存のしきい値調整の運用に組み込みやすい
FARとFRRをそれぞれConformal Predictionで較正し、2つのしきい値の間を使えば、EERのような経験的な交点ではなく、両方とも統計的に保証された区間を作れる