タイトルの通りなんですが、Kaggleでとても人気のある手法のXGBoostがどういった仕組みで動いているのかを知るために次の論文を読みました。
XGBoost: A Scalable Tree Boosting System
詳しいことは、日本語で読める分かりやすい解説記事（こことか）があるのでそちらを参照していただきたいです。この記事は個人的な備忘録です。
要するにXGBoostとは決定木をすでに作った木の情報をもとにしながら何個も作ってそれらの結果を足し合わせることで、性能を向上させるBoostingの手法を効率的に実装したものと言えます。
基本的なポイントは単純ですが、決定木を作っていくうえですべての木の中から最も良いものを調べて選択するのは計算量的に難しいため、ある種の近似を用いて精度的に問題の少ない気を作っていき高速に実行可能なアルゴリズムとなっています。また、オーバーフィッティングを防ぐために、サブサンプリングや縮退化などの仕組みも導入されており、汎化性能が良くなるようになっていることもKaggleのコンテストで人気の理由の一つだと思います。
また、論文では並列化や分散処理をした場合の速度性能の評価が行われており、高い並列性能が出ています。提供されているライブラリではキャッシュが当たりやすくなるようになどの最適化が施されているので、自分で実装せずにライブラリを使いましょう。pipで簡単に入れられるようです。
