Coda

メモ CatBoost: unbaiased boosting with categorical features

August 10, 2019

概要

表題はNeurIPS 2018で発表されたCatBoostという勾配ブースティングの手法を論文にちなむ。 Target Statisticsというカテゴリカル特徴量の前処理と勾配ブースティングの学習時に生じる一種のleakageが起きることを示し、leakageをさけて前処理と学習をする手法を示した。 CatBoostは二進木の決定木を弱識別器に用いる。

Target Statisticsは、濃度が大きい特徴量の値から目的変数の推定値への関数を求め、推定値を学習に使うことで濃度の大きさに対処する手法をさす。 データセットを\(\mathcal{D}=\{({\bf x}_k, y_k)\}_{k=1\dots n}\)、\({\bf x_k}\)は\(m\)次元のベクトル\((x_k^1, \dots ,x_k^m)\)、 対応する正解を\(y_k\in\mathbb{R}\)とするとTarget Statistics \(\hat{x}_k^i\)は\(\hat{x}_k^i\approx\mathbb{E}(y \mid x^i=x^i_k)\)となる。 推定時には\(y\)は与えられないため、\(\hat{x}^i_k\)を計算するときに\(y_k\)を含めるとleakageが生じる。 そこで、\(\sigma\)を訓練データの無作為な順列の順序の関数、\(\mathcal{D}_k=\{{\bf x}_j:\sigma(j)<\sigma(k)\}\)、\(a>0\)をパラメタ、\(p\)を教師データにおける\(y\)の平均値とすると

$$ \newcommand{\1}{\mbox{1}\hspace{-0.25em}\mbox{l}} \hat{x}^i_k = \frac{\sum_{{\bf x}_j\in\mathcal{D}_k}\1_{\{x_j^i=x_k^i\}}y_j+ap}{\sum_{{\bf x}_j\in\mathcal{D}_k}\1_{\{x^i_j=x^i_k\}}+a} $$ とすることで、leakageを避けて濃度の高いカテゴリカル特徴量の濃度を下げることができる。

学習においても、leakageを避けるために訓練データに順序を与える。例えば、損失関数を\(\frac{1}{2}[y_i-f(x_i)]^2\)とすると、勾配\(-\partial L(y_i,f(x_i))/\partial f(x_i)\)は\(y_i - f(x_i)\)となる。このとき、\(m\)ステップで勾配を計算するときに使われる弱識別器\(f_{m-1}\)の学習に\((x_i, y_i)\)が訓練データに含まれているとleakageが生じる。そこで、Algorithm 1 では、訓練データに順列を設定し、leakageが生じないようにしている。なお、\(I\)は決定木の数をさす。 ALgorithm 1 は訓練データの数以上のモデルを学習する必要があるのでスケールしない。論文中ではこれを近似するアルゴリズムも提案されており、実験や評価ではそちらが使われている。

感想

訓点データ数が少ないほどleakageの影響が大きいことが解析的にも実験においても示されてるので、訓練データ数が少なく、濃度が大きいカテゴリカル特徴量がある問題で使ってみたいと思う。


論文はこちらからダウンロードできます。