XGBoostの論文を読み解く②(Introductionの把握)|論文と実装を元に掴む木構造ベースのアルゴリズムの変遷 #2

f:id:lib-arts:20190909191254p:plain

以前の記事で高校数学の内容を元に決定木(Decision Tree)やランダムフォレスト(Random Forest)についてまとめました。

微分・最小値問題の復習と増減表|高校数学の演習を通して理解する決定木・ランダムフォレスト #1 - lib-arts’s diary

ジニ係数と情報エントロピー|高校数学の演習を通して理解する決定木・ランダムフォレスト #3 - lib-arts’s diary

上記の記事はどちらかというと高校数学の理解に基づいた基本的な仕組みの解説がメインで、木構造ベース(Tree-based)のアルゴリズムの応用については詳しく触れていませんでしたので、木構造アルゴリズムの話題やその変遷について取り扱っていきます。
最初のテーマとしては近年よく聞くXGBoostについて取り扱います。

[1603.02754] XGBoost: A Scalable Tree Boosting System

#1ではAbstractの読解を通した概要の把握を行いました。
https://lib-arts.hatenablog.com/entry/tree_based_algo1
#2では引き続き同論文のIntroductionについて確認していければと思います。
以下目次になります。
1. Introductionの読解
2. まとめ


1. Introductionの読解
1節ではSection1のIntroductionについて確認していきます。

f:id:lib-arts:20190910105721p:plain

以下パラグラフ単位でリーディングを行なっていきます。

f:id:lib-arts:20190910105958p:plain

第一パラグラフでは、機械学習(Machine learning)やデータドリブン(data-driven)のアプローチが多くの分野で重要度を増しており、応用の具体例としてスパム判定、広告最適化、不正利用検知、物理学的な発見に繋がる事象の発見などが述べられています。また、次に応用にあたっての二つの重要な要素(factors)があるとしており、(1)複雑なデータの依存性を学習する効率的なモデルと、(2)大きなデータセットから学習するにあたってのスケーラブルな学習システムの二つであるとされています。ざっくりまとめるならば様々な応用に際して、精度と処理効率の双方が求められるとされています。

f:id:lib-arts:20190910111131p:plain

f:id:lib-arts:20190910111149p:plain

第二パラグラフでは、勾配ブースティング(gradient tree boosting)系のアプローチについて色々とまとまっています。[10]で示された、Greedy function approximation: a gradient boosting machine.をベースにLambdaMARTなどのモデルや、Netfilixのコンペティションにおいてデファクトチョイスとなったなどの話がまとまっています。

f:id:lib-arts:20190910112001p:plain

第三パラグラフでは、論文の主題であるXGBoostに話題が写っています。XGBoostはスケーラビリティの高い機械学習のシステムであるとされており、オープンソースで入手可能とされています。このXGBoostのインパクトについては、データマイニングコンペティションにおけるXGBoostの位置付けを元に話が進められています。コンペティションサイトのKaggleでは、2015年に行われた29のコンペティションのうち、17のソリューションにお知恵XGBoostが用いられたとされています。

f:id:lib-arts:20190910112841p:plain

第四パラグラフでは、XGBoostの汎用性について言及されています。XGBoostが幅広い分野の問題(wide range of problems)においてSotAとなったことについて触れられ、具体的な例としては、店舗の売上予測、顧客の行動予測、動作検知、広告クリック率の予測、コンピュータウィルスの検知、製品のカテゴリ化、病気のリスクの予測、オンラインコースを途中でやめる場合の予測などが挙げられています。feature engineeringの重要性が高い一方で、XGBoostがモデル選択されるコンセンサスがある事実はこの研究に重要性をもたらしているとされています。

f:id:lib-arts:20190910113829p:plain

f:id:lib-arts:20190910113845p:plain

第五パラグラフでは、XGBoostの成功の要因としてスケーラビリティ(scalability)に言及がされています。既存の他の分類器を用いた解法の10倍以上速いとされており、これは木の学習においてsparse dataを取り扱う新たなアルゴリズムのためであるとされています。また論文のメインのcontributuionsとして、下記の四点が挙げられています。

・高度にスケーラブル可能なend-to-endの木構造のブースティングシステムの設計(design)と構築(build)を行なった点。
・効率的な計算にあたって、理論的に証明されたweighted quantile sketchを提案している点。
・木の並行学習にあたって新しいsparsity-awareのアルゴリズムを導入している点。
・out-of-coreな木の学習にあたって、効率的なcache-aware block構造を提案している点。

f:id:lib-arts:20190910115024p:plain

第六パラグラフでは、先行研究との差分として、out-of-coreの計算、cache-aware、sparsity-aware、end-to-endの(学習)システムなどについて言及されています。またこれらの主要なcontributionに加えて、正則化された(regularized)な学習にあたっての目的関数における改善についても作成できたとあります。この辺は詳細を見た方がわかりやすいので、Introductionの読解においてはこれ以上立ち入らないものとします。

f:id:lib-arts:20190910115523p:plain

第七パラグラフでは、以降の章立てについて言及されています。Section2(TREE BOOSTING IN A NUTSHELL)では、tree boostingのレビューと正則化された目的関数(regularized objective)を行うとされています。Section3(SPLIT FINDING ALGORITHMS)では、分割の発見にあたっての方法(決定木の木を作成するにあたって変数を選ぶこと)について取り扱うとされています。Section4(SYSTEM DESIGN)ではシステムの設計と実験結果についてまとめたとあります。Section5(RELATED WORKS)では関連研究について、Section6(END TO END EVALUATIONS)ではend-to-endの評価、最後にSection7(CONCLUSION)では論文の結論について述べるとされています。

 

2. まとめ
#2ではIntroductionについてまとめました。Abstractの際と同様に数式などを用いた説明がないのでいまいち細かいところまではつかみきれていませんが、だいたい重要となるキーワードとマッピングについてはつかめたので現段階では十分とし、以降を進めていきたいと思います。
#3ではSection2のTREE BOOSTING IN A NUTSHELLについて取り扱っていきます。