以下の論文を読みます。
前回の話をまとめると、「勾配ブースティング」とは複数のモデル（弱学習器）を直列に組み合わせて一つの判定モデル（強学習器）とする「ブースティング」といわれるアンサンブル学習手法の一つです。勾配ブースティングの考え方としては「現時点の強学習器に足し合わせると損失が最小になる弱学習器」を探して重ねていくわけですが、厳密に探すのは難しいので近似的に「『現時点の強学習器の予測の正解との誤差』を正解ラベルとして学習した弱学習器」を最適な重みで重ねていきます。
「勾配ブースティング」の個々の弱学習器として具体的に採用されるのは典型的には「決定木」であるそうです。決定木とはよくある性格診断テストのように Yes/No で答えられる質問をして、その回答によってまた別の質問をして、最終判断まで導くモデルです。弱学習器として決定木を採用する場合、最終的にたどりつく診断結果のマスごとに、強学習器に足し合わせるときの重みを変えることができるんでしたよね。
それでこの論文は CatBoost という勾配ブースティングのツールがすごいっていう話なんですよね。やはり弱学習器は決定木ということなんでしょうか。
論文を "tree" で検索すると2ページの中ほどに "CatBoost is an implementation of gradient boosting, which uses binary decision trees as base predictors" とあるから決定木、それも二分木を弱学習器として採用しているということで間違いないね。gradient boosting（勾配ブースティング）とだけいったとき gradient boosting decision tree（勾配ブースティング決定木）を意味していることが多いんだと思う。
なるほど。二分木というのは枝分かれが必ず2つということでしょうか。確かに Yes/No で分岐していく木をイメージしていましたが、必ず2つの枝に分かれると決めなくてもいい気もしますが。
初期の決定木の実装には、「カテゴリカル値をとる特徴について、とりうるカテゴリカル値だけ分岐させる」という方針のものもあったみたいだけどね。
でも、多分木で実現できる決定木って別に二分木でも実現できるからね。分岐が深くはなるけど。それに、分岐数を任意にしてしまったら、そのノードで分岐に用いる特徴を選択する基準をどうするって話になる。特徴ごとに分岐数が違ったら、分岐が多ければ分岐後の誤差が小さいのは当然だから特徴間のフェアな比較ができない。そもそも分岐数に上限を設けなきゃ連続値特徴は全てのデータをばらばらに分岐することになっちゃうね。カテゴリカル値をとる特徴であっても、カテゴリカル値だけ必ず分岐させてしまうのは過学習になりそうだな。このカテゴリカル値とこのカテゴリカル値は実は目的上分けて取り扱う必要がないってありそうだし。なるべくシンプルなモデルから攻めて最低限の精度を達成するようにしたい気がするよね。まあそういわれれば。それで、この論文で紹介する CatBoost はアルゴリズムに以下の2つの特長を取り入れたとありますね。
- ordered boosting, a permutation-driven alternative to the classic algorithm
- innovative algorithm for processing categorical features
私も勾配ブースティング業界の知識はないからそこは続きを読みながらの宿題なんだけど、イメージで言うと…まずベースの決定木というのがこれと確定されたアルゴリズムじゃないよね。「特徴と境界の選択」「分岐の終了」「予測値の割り当て」をそれぞれどう達成するかは自明じゃない。勾配ブースティング決定木の実装をみてみると、特徴と境界の選択を全探索しているわけでもなかったりする。全探索すると計算が遅くなりすぎるからどう全探索せずにモデルの性能を保つかってのも勾配ブースティング決定木パッケージの領分なのかも。その2点目のようにカテゴリ特徴をどう扱うかってのも流儀がありそう。加えて、勾配ブースティングでは1ラウンド、2ラウンド、…と決定木を学習していくわけだから、1ラウンド目はこの流儀で学習して、2ラウンド目はそれを補うようにこの流儀で学習して、…っていう自由度もありそうかな。
そのレベルの話だとどんなデータセットを学習するのかにもよりそうですね…勾配ブースティング業界に詳しくないのでイントロから読んでいきましょう。勾配ブースティングはここ何年も、データが異質な特徴が混在するものであったり、ノイジーであったり、複雑な依存構造があったりするときには primary な手法であり続けていると。勾配ブースティングの理論は以下の文献に示されているのですか？ タイトルとアブストラクトを読む限り「distribution-free な2値モデルには限界がある」という話にみえますが…。
まあそれは置いておいて、既存のあらゆる勾配ブースティングの実装の問題点というのは「数ラウンド学習した強学習器は全ての学習データに依存している」ということらしいですが、このことが問題なんですか？？ これによってリーケージが生じるということですが、この箇所だけだとわからないですね…。あと、カテゴリカル値をとる特徴の取り扱いも、目的変数の統計量に代替する手法がよく使われるが、これもリーケージを引き起こすと…目的変数の統計量にエンコーディングするやり方ではリーケージになりそうというのはわかりますが、これはもう特徴量エンジニアリングの話ですよね？ 既存の勾配ブースティングのパッケージってそんな機能まで内蔵してるんですか？引き合いに出されている既存のパッケージは以下だよね。
- XGBoost（ https://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf ）
- LightGBM（ LightGBM: A Highly Efficient Gradient Boosting Decision Tree ）
それだとなんかあるパッケージは捌けるデータ量を競い、あるパッケージは学習速度を競い、あるパッケージはカテゴリカル値をとる特徴の取り扱いを競っていることになってしまいませんか…。2節に移ると、冒頭にデータ は i.i.d. に
にしたがうとするとありますね。現実のデータって独立なものなんでしょうか…まあいいです、いまの目的は損失
を最小にする関数
を探すことですね。ここで
ということですから、訓練データセット上での損失でもテストデータセット上での損失でもなく、未知のあるデータに対する期待損失ですね。それは目指すところはそうでしょう。勾配ブースティングでは前回みたとおり
といった形でこれを求めていくわけです。
です。無論、真の分布
を知り得ないので真にこの最適化を実行することはできないですよね。よく用いられる手法としては、
と「時点
での予測値
における損失の傾きのマイナス1倍」との誤差の2乗の期待値が最小になるような
を選ぶということですが（傾きが負なら予測値を増やすべきですし、傾きが正なら予測値を減らすべきですし、そのような理想的な修正がなるべく全ての
で達成されてほしいですね）、これも真の分布を知らなければ真に誤差の2乗の期待値を知ることはできないと思います。私たちは未知の
における正解
（の期待値）を知らないので、未知の
でも理想的な修正が達成されているかをわからないと思うのですが…。
3節はカテゴリカル値をとる特徴の話のようですね。二分木でカテゴリカル値をとる特徴を扱う常套手段として one-hot encoding がありますが、取りうるカテゴリカル値が多いと特徴が増殖しすぎてしまうのはそれはそうですね。それでよくとられる方法として、多すぎるカテゴリカル値を目的変数に応じてグルーピングするとか、カテゴリカル値を目的変数に応じた数値変数にしてしまうとか（TS: target statistics）があるということです。
以下の本の5章でやった話だね。
まあ何にせよカテゴリカル値をとる特徴をより粗いカテゴリカル値とか数値とかの新しい特徴に変換した上で、新しい特徴の上でありうるあらゆる分岐点の中から、対数損失（各データについて、正例であれば負例っぽさの対数、負例であれば正例っぽさの対数をとったものの和でしょうか）なりジニ係数なりMSEなりを最小にする分岐点を選ぶというわけです。…改めて、膨大なカテゴリカル値をとる特徴を変換するというのは、「分岐点の候補を捨てる」ということなんですね。粗いカテゴリにまとめるなら、一緒にまとめられたカテゴリはもう分岐されることはありませんし、何らかの数値特徴に変換するにしても、変換の仕方如何で分岐は大いにコントロールされてしまうでしょう。それで、単なる特徴の変換とはまた違った方法として、LightGBM ではカテゴリカル値をとる特徴を勾配ブースティングの各ラウンドで "gradient statistics" に変換するとありますね？ この方法は有用な情報を引き出せる一方で、計算時間とメモリを消費するので、少数カテゴリをひとまとめにするなどの対策をしなければならず、情報の損失を免れないとか。
LightGBM のペーパーにそんなことかいてあったかな…と思ったけど LightGBM のドキュメントの方に載ってるのか。LightGBM のカテゴリカル値をとる特徴の取り扱いは ont-hot じゃなかったんだね。以下の記述をみるに、どうも各ラウンド毎に、その時点での各カテゴリカル値のデータに残っている勾配の合計値を計算して、その合計値でカテゴリをソートして（合計値を数値特徴のように扱って）分岐点候補を絞っているみたいだ。参考文献が付されているみたいだけど、このアイデア自体は LightGBM 独自のものでなく伝統的なものってことなのかな。
というか「とりうるカテゴリカル値が膨大なときは単純に整数として扱うか、低次元に埋め込むのがよいことが多い」ってかいてあるね…。そんな殺生な…できたら苦労しませんよ…。まあしかし、gradient statistics は計算が大変なのでやはり target statistics を利用したいわけです。つまり、カテゴリカル値をとる特徴 についてカテゴリカル値
を数値
に変換してしまいたいのですが、基本路線としては
というようにその特徴が与えられた下での目的変数の期待値にするということです…うーん、ユーザが検索結果のリンクをクリックするか予測するのに、ユーザIDを特徴とするととりうる値が膨大すぎるのでそのユーザのクリック率の期待値で代えるということですよね。なんだか荒っぽくないですか？ いくら普段からクリック率が高めのユーザでも、興味がないリンクはクリックしないと思うんですが。
私にいわれても…別に、ユーザIDをクリック率に代えるという操作はそのユーザIDに対する予測値をただちに上げるわけじゃないし。クリック率が高いユーザは検索語が含まれるサイトを軒並みクリックするようだが、クリック率が低いユーザは必ずしもそうでない傾向がみられる、みたいな「境界」を発見できればいいんだよ。発見できるかは知らないけど…。
はあ。とにかくそれで、TS を扱うやり方でも Greedy TS、Holdout TS、Leave-one-out TS、Ordered TS と4種類が紹介されていますね。最後の Ordered TS が CatBoost が採用している流儀ということです。
- Greedy TS： 期待値を単純に訓練データ上の平均としてしまうやり方ですが、単純すぎるので事前信念値（いま適当につくった語）
を
件分混ぜ込むといった感じのようですね。少数カテゴリに弱いようです。そしてこれは当然のようにリーケージを起こします。
- Holdout TS： 期待値の計算を訓練データでやるのは乱暴なので、訓練データを期待値用と訓練用に分割するということですが、データを有効につかえないのが欠点とありますね。
- Leave-one-out TS： 期待値の計算に「自分を除いた」データをつかうということのようですね。
- Ordered TS： 訓練データをランダムに並べて「自分より過去の」データをつかうようです。ラウンド毎にランダムに並び替えるようですね。この箇所だけ読むと Leave-one-out TS に対する優位性がよくわからないのですが、後の方を読んでみると、Leave-one-out TS はむしろ多数カテゴリに弱いようですが…？
