Target Encoding のスムージングについて

Target (Mean) Encoding の出典は、2001 年の ACM SIGKDD Explorations Newsletter, Volume 3, Issue 1 に掲載された以下の論文らしい。

https://dl.acm.org/doi/10.1145/507533.507538

この論文には Target Encoding のスムージングに関する詳しい記述があった。そこで、その内容を元に巷のフレームワークがどのようにスムージングを実装しているかを併せて調査してみた。自分用のメモも兼ねて、ここに書き残すことにする。

なお、Target Encoding 自体の説明については以下を参照のこと。

blog.amedama.jp

なぜスムージングするのか

そもそも、なぜスムージングが必要になるのか。それは、スムージングのない Target Encoding は、少数のサンプルしか含まれないカテゴリにおいて極端な値を取りやすいため。

たとえば、二値分類のタスクを題材にして考えてみよう。極端なケースとして、学習データの中にサンプルが 1 つしか含まれないカテゴリがあった場合の計算について考える。ただし、単純のため Target Leakage を軽減するための Out-of-fold (OOF) での計算は考えない。この場合、スムージングのないナイーブは Target Encoding の計算は論文の (2) 式に対応する。

$S_i = \frac{ n_iY }{ n_i }$

上記において $S_{i}$ が、あるカテゴリ $i$ の Target Statistics になる。 $n_i$ はカテゴリ $i$ に属するサンプル数を表す。 $n_iY$ はカテゴリ $i$ に属する $Y = 1$ のサンプル数を表している。

もし、1 つしかないサンプルの目的変数が 1 だとすると、Target Statistics は $S_i = \frac{1}{1} = 1$ になる。では、このカテゴリについて未知のテストデータにおいても Target Statistics が 1 と信じることは妥当だろうか。直感的には、サンプル数が不足していることから信頼できないと考えるはず。

このような値をモデルが信用して学習に利用してしまうと、過学習を引き起こす恐れ ¹ がある。

Empirical Bayesian (EB) を用いたスムージング

前述した問題を緩和するためにスムージングを導入する。やりたいこととしては、少数のサンプルしか含まれないカテゴリにおいても極端な値を取らないようにしたい。これには、学習データ全体で計算した目的変数の平均を計算結果に「ブレンド」する。論文で最初に示されている方法は以下で、これは (3) 式に対応する。なお、この式は Empirical Bayesian という手法に由来するらしい。

$S_i = \lambda (n_i) \frac{ n_iY }{ n_i } + (1 - \lambda (n_i) ) \frac{ n_Y }{ n_{TR} }$

上記は、第 1 項があるカテゴリ $i$ について計算した値で、第 2 項が学習データ全体について計算した値になる。第 2 項に登場する $n_{TR}$ は学習データに含まれるサンプル数で、 $n_Y$ が学習データの中で $Y = 1$ なサンプル数を表している。そして、 $\lambda (n_i)$ がスムージングの強度を決める (出力は 0 ~ 1)。もし $\lambda (n_i) = 0$ なら完全に学習データ全体の平均になり、 $\lambda (n_i) = 1$ なら完全にカテゴリ $i$ の平均になる。

$\lambda (n_i)$ の計算方法については、以下が例として挙げられている。これは論文において (4) 式に対応する。

$\lambda (n) = \frac{1}{1 + e^{\frac{n - k}{f}} }$

上記で $k$ と $f$ は特性を決めるハイパーパラメータとなる。つまり、対象のデータと扱うモデルごとに最適な値が存在する。

category_encoders の実装

この Empirical Bayesian に由来するスムージングは category_encoders の TargetEncoder が採用している。

ソースコードにおいて、以下が (4) 式に対応する。

github.com

そして、(4) 式で求めたスムージングの強度を、以下の (3) 式に対応する箇所で使っている。

github.com

m-probability estimate を用いたスムージング

論文では、もうひとつ簡略化したスムージングの手法が紹介されている。これは Additive Smoothing の一種で、m-probability estimate と呼ばれるやり方らしい。以下は論文の (7) 式に対応する

$p^*_c = \frac{ n_c + p_c m }{ n + m }$

上記で、 $p^*_c$ が、あるカテゴリ $c$ の Target Statistics になる。 $n$ は、あるカテゴリに属するサンプル数を表す。 $n_c$ は、あるカテゴリ $c$ に属する $Y = 1$ なサンプル数を表す。 $m$ は、スムージングの強度を決めるハイパーパラメータを表す (0 ~)。 $m = 0$ のときスムージングしないことになる。 $p_c$ は、あるカテゴリ $c$ の事前確率を表す。典型的には全カテゴリの平均的な Target Statistics を使えば良さそうだ。