こんにちは。この記事では、機械学習で使われるExtremely Randamized Treeについて調べてみてわかったことをまとめておこうと思います。
構造化データに対するモデリングではLightGBMを使うことが多かったのですが、Kaggleなどをみていると、現在においてもLightGBMよりもこちらが使われているケースも多くみられたので、そのモチベーションを探るために調べてみようと思った次第です。（実はLightGBMでもExtremely Randomized Treeが使えるみたいですので、その点も後述します。）
Contents
Extremely Randomized Treeとは？
こちらのブログに解説がありましたので、リンクを貼っておきます。
ポイントは、「決定木の枝の分岐点が、完全または部分的にランダムに決定される」「計算コストが低い」という事のようです。従来の決定木では、ジニ係数やエントロピーを基準に最適な分岐点を探る方法でしたが、それを完全にランダムに選択した方が精度が上がる、ということのようです。汎化性能が向上するのは分かりますが、完全にランダムに選択しても精度が上がる、というのは不思議ですね・・・！
Extremely Randomized Tree登場の背景
Extremely Randomized Treeは2006年の論文で発表されたようですね。XGBoostの登場が2014年、LightGBMの登場が2016年とかなので、それらよりは古いようです。
元の論文はこちら。
https://link.springer.com/content/pdf/10.1007/s10994-006-6226-1.pdf
流し読みですがわかったことは以下。（もしかすると英語の解釈間違ってるかもしれませんが、ご容赦を・・ご指摘いただけましたら幸いです。）
- 決定木をRandomizeするアイデア自体は1989年に発表されたが、当初は大抵のデータセットにおいて、従来の決定木と比較して大幅に精度が低かった
- しかし、従来のCARTやc4.5による決定木では、特定のデータセットに大きく影響を受けて分岐点の分散/バイアスが大きいことがしばしば精度に悪い影響を与えていた。
- その後もこの分岐点の分散/バイアスを低減させる方法の研究が進められた。分散を低減させる方法としてベイズ平均が、バイアスを低減させる方法としてスタッキングとブースティング（分散も同時に低減できる）が有名（いずれも1991年〜1992年の論文）。
- その後1994年(1996年?)にバイアスを抑えながら分散を低減させる方法として、バギングが提唱された。
- バギングはアンサンブル学習の一種で、Randomized Methodsと考えられた。
- その後も、バイアス/分散を低減させるためのさまざまなRandomize手法が提案されたが、Neural Networkやサポートベクターマシンなどの手法と比べて精度が出なかった。
- さらに、これらのRandomized Methodsでは成長する複数の木が必要となり計算コストを要するため、研究者たちは部分的にランダム化することで対処した。
- それでも大きなバイアスと分散が生まれる状況から、さらにランダム化する余地があると想定し、分岐点を完全にランダムに選択するExteremely Randomized Treeが提案された。
Extremely Randomized Treeの実装
Scikit-Learnで利用可能です。
[工事中]Extremely Randomized Tree vs Random Forest
これはネットを調べてみても結構議論されていました。以下あたりがわかりやすく解説していました。常にどちらが良い、というものではなく、状況に応じた使い分けができるとよさそうです。
Extremely Randomized Tree vs LightGBM/XGBoost
この比較は正確ではないかもしれません。LightGBMの中でもERTが使えるようです。ん、どういうこと・・？こちらの記事が参考になりました。
https://note.com/j26/n/n64d9c37167a6
LightGBMの公式ドキュメントをみても、確かにextra_treesオプションが選択可能です。計算コストの低下と、Overfitへの対処の観点で有効、とありますね。この点は上の論文の説明の通りっぽいです。
https://lightgbm.readthedocs.io/en/latest/Parameters.html#extra_trees
以上、ERTについて調べてわかったことのまとめでした。記事は徐々に深くしていきたいですが、まずはこのくらいに。
おしまい
コメントを残す