今更だけどExtremely Randomized Treeについて調べてみた

こんにちは。この記事では、機械学習で使われるExtremely Randamized Treeについて調べてみてわかったことをまとめておこうと思います。

構造化データに対するモデリングではLightGBMを使うことが多かったのですが、Kaggleなどをみていると、現在においてもLightGBMよりもこちらが使われているケースも多くみられたので、そのモチベーションを探るために調べてみようと思った次第です。(実はLightGBMでもExtremely Randomized Treeが使えるみたいですので、その点も後述します。)

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について調べてわかったことのまとめでした。記事は徐々に深くしていきたいですが、まずはこのくらいに。

おしまい

この記事を気に入っていただけたらシェアをお願いします!

コメントを残す

メールアドレスが公開されることはありません。

ABOUT US
Yuu113
初めまして。ゆうたろうと申します。 兵庫県出身、東京でシステムエンジニアをしております。現在は主にデータ分析、機械学習を活用してビジネスモデリングに取り組んでいます。 日々学んだことや経験したことを整理していきたいと思い、ブログを始めました。旅行、カメラ、IT技術、江戸文化が大好きですので、これらについても記事にしていきたいと思っています。