この記事は, MicroAd Advent Calendar 2020の10日目の記事です.
はじめに
Click Through Rate (CTR)の予測などを2値分類問題(クリックされた:1,クリックされなかった:0)として定式化し, 機械学習を用いて確率を予測する場合, 分類精度やAUCだけでなくモデルの出力が実際の確率に近いかも重要である.
(well-calibratedであるならば, 実際の確率が10%であれば予測モデルは10%付近の値を出力する)
Neural Networkなどで高い分類精度を実現したとしても, 出力が自信過剰な場合があり必ずしもwell-calibratedとは言えない.
ノンパラメトリックな確率補正の手法として, Isotonic Regressionを用いた確率補正が以下で提案されている.
Predicting Good Probabilities With Supervised Learning
Transforming Classifier Scores into Accurate Multiclass Probability Estimates
scikit-learnで以下のモジュールが実装されている.
sklearn.isotonic.IsotonicRegression-
sklearn.calibration.CalibratedClassifierCV
(CalibratedClassifierCVは内部でIsotonicRegressionを呼んでいる)
利用するのは簡単であるが, 何をやっているか説明している記事はあまりないのでまとめておく
Isotonic Regression
学習データセットを$\lbrace(y_i, f_i)\rbrace_{i=1,\ldots,N}$としたとき, 単調増加な関数$m(\cdot)$を学習する.
y_i = m(f_i) + \epsilon_i
probability calibrationにIsotonic Regressionを用いる場合は, $y_i$は正解ラベル($y_i \in (0,1)$), $f_i$は分類器の出力値である. ただし, バイアスが生じるため分類器の学習データとは別にcalibration用のデータセットを使わなければいけない.
isotonic regressionでは平均二乗誤差を最小化するIsotonic(単調増加)な等張関数を求める
\hat{m} = argmin_{z}\sum (y_i - z(f_i))^2
この解を求めるアルゴリズムの一つに以下のpair-adjacent violators(PAV) algorithm (Ayer et al., 1955)がある.
PAVアルゴリズムでやっていることは以下である.
- calibration用のデータセット$\lbrace(y_i, f_i)\rbrace_{i=1,\ldots,N}$を $f_i$の順にソート
- $m(f_i) = y_i$で初期化
- 正解ラベルの大小関係に間違いがあれば平均値で置換
- 推論の際にデータセット中にない値は近傍の値を出力
分類器が事例を正しくランク付けすると仮定すると、分類器の出力から予測確率への写像は非減少的であるため, 単調増加の制約があるisotonic regressionでこの写像を学習している.
分類器が事例を正しくランク付けできていない部分ではより多くの事例を平均化し，分類器が正しくランク付けしている部分ではより少ない事例を平均化する． つまり, probability calibrationにおいてPAVアルゴリズムは分類器がどれだけ事例を正しくランク付けできてるかによって， 境界の位置とビンのサイズが選択されるビニングアルゴリズムとして見ることができる.
おまけ
Isotonic Regressionが確率補正に応用される以前に, Learning and Making Decisions When Costs and Probabilities are Both Unknownでビニングによる確率補正が提案されている. (以下, ビニング法)
ビニング法では以下の手順で確率補正を行っている.
- 分類器の出力値でソート
- ソートされた集合を$b$個の同じ大きさの部分集合(ビン)に分割
- ビンの範囲の値をビン内に含まれる正例の割合に置換
この方法ではビンの数(大きさ)は任意であり, 交差検証によってビンの数を選択しなければならない． データセットが小さい場合や, 非常にアンバランスな場合, 交差検証では最適なビン数を求めることが困難な場合がある. また, 境界の位置は任意に選ばれるため明らかに異なる確率推定値を持つはずの事例のラベルを平均化するような境界では、ビニング法は正確な確率推定値を得ることができない. そこでisotonic regressionの確率補正への応用が提案された.