XGBoostの論文を読み解く①(Abstractの確認と概要の把握)｜論文と実装を元に掴む木構造ベースのアルゴリズムの変遷 #1
以前の記事で高校数学の内容を元に決定木(Decision Tree)やランダムフォレスト(Random Forest)についてまとめました。
微分・最小値問題の復習と増減表｜高校数学の演習を通して理解する決定木・ランダムフォレスト #1 - lib-arts’s diary
ジニ係数と情報エントロピー｜高校数学の演習を通して理解する決定木・ランダムフォレスト #3 - lib-arts’s diary
上記の記事はどちらかというと高校数学の理解に基づいた基本的な仕組みの解説がメインで、木構造ベース(Tree-based)のアルゴリズムについては詳しく触れていませんでした。
木構造ベースのアルゴリズムでXGBoostなどをここ何年かよく聞きますが、そういった新しい話題などについても触れられればということで、新しいシリーズをスタートさせ、木構造アルゴリズムの話題やその変遷について取り扱っていければと思います。
進め方としては、XGBoostについてがやはりよく聞くので、まずはXGBoostの論文について確認した後、実装や他のトピックなどについて確認していければと思います。
[1603.02754] XGBoost: A Scalable Tree Boosting System
#1ではAbstractの読解を通した概要の把握を行えればと思います。
以下目次になります。
1. Abstractの読解
2. まとめ
1. Abstractの読解
1節ではAbstractの読解を行なっていきます。一文ずつ和訳と簡単な補足解説を行なっていければと思います。
Tree boosting is a highly effective and widely used machine learning method.
和訳：『木(決定木)のブースティングは非常に効率的で広範に用いられている機械学習の手法である。』
第1文は決定木のブースティングについて言及されています。機械学習の文脈で木と言ったら決定木を指すことが多いので和訳でもそちらを反映させています。また、ブースティングについては以下のWikipediaの記述がわかりやすいので引用しておきます。
上記によるとブースティング(Boosting)は教師あり学習におけるメタアルゴリズムの一種で、「一連の弱い学習器をまとめて強い学習器を生成する」というのが概要になります（画像の学習器は誤記のようだったので訂正しています）。ランダムフォレスト(Random Forest)などがこの具体的な例であり、詳しい考察は以前の記事の#2で行っています。
二項定理と多数決｜高校数学の演習を通して理解する決定木・ランダムフォレスト #2 - lib-arts’s diary
In this paper, we describe a scalable end-to-end tree boosting system called XGBoost, which is used widely by data scientists to achieve state-of-the-art results on many machine learning challenges.
和訳：『この論文においては、我々はXGBoostと名付けた拡張性のあるend-to-endの決定木のブースティングを紹介している。このXGBoostは多くの機械学習のコンペティションにおいてデータサイエンティストがSotAの結果を出すにあたって広く用いられている。』
カンマ区切りの関係代名詞の後が長かったため、セオリー通り二文に分けた和訳を行っています。決定木ベースのブースティングの手法を開発し、XGBoostと読んだとあります。また、多くのコンペティションにおいて用いられていることについても言及がなされています。
We propose a novel sparsity-aware algorithm for sparse data and weighted quantile sketch for approximate tree learning.
和訳：『我々は疎なデータのための新しいsparsity-awareなアルゴリズムと木の学習の近似のための重み付けquantile sketchについて提案する。』
sparsity-aware algorithmやweighted quantile sketchがいまいち意味が取れなかっったのですが、こちらについては論文の肝となりそうなので、詳細の読解とともに掴むと良さそうです。
More importantly, we provide insights on cache access patterns, data compression and sharding to build a scalable tree boosting system.
和訳：『さらに重要なこととして、我々は拡張可能なブースティングシステムを構築するにあたってキャッシュアクセスのパターン、データ圧縮、シャーディングの洞察も提供している。』
こちらに関しては規模的に拡張可能(scalable)にするために、処理に関して効率化を行っていることについて言及されています。詳細の記述は論文内にあると思うので、詳しく知るにはそちらを見るのが良さそうです。
By combining these insights, XGBoost scales beyond billions of examples using far fewer resources than existing systems.
和訳：『ここまでに挙げた洞察を合わせることで、XGBoostの処理は既存のシステムよりもずっと少ない計算リソースを用いて何十億ものサンプル以上にスケールさせることができる。』
scaleが直訳だと少々わかりづらくなったので、若干意訳を行いました。Abstractで述べた様々な工夫を元に、計算リソースの効率化を行い、処理のスケールが可能になることについて述べられています。
2. まとめ
#1ではXGBoostの論文のAbstractを元に簡単な概要の把握を行いました。とりあえず、木構造がベースになっていること、多くのコンペティションにおいて用いられていること、処理の効率が高くスケーラビリティに優れることというのが読み取れた形になったかと思います。
#2ではIntroduction以下について確認していければと思います。
