XGBoostは、だいたいこんな感じらしい

XGBoostの原論文を完全に理解する
https://ml-for-experts.connpass.com/event/144710/
を聞いて、だいたいこんな感じ？というのをメモ

---

【論文概観】

・提案する手法
1.欠損データ、重み付き分位点の算出の高速化→ 3章で説明
2.勾配情報のプリフェッチ、ブロック圧縮、断片化→ 4章で説明

・２章
　ロス関数→テイラー展開による近似
　特徴量をランダムサンプリング:Column Subsampling

・３章
　分割点探索
　重み付き分位点の算出→高速化

・４章
　ＣＳＣによる行列データ圧縮
　勾配情報のプリフェッチ
　ブロック圧縮、断片化


【詳細】
●２章
決定木（ＣＡＲＴ）
・ＣＡＲＴ→２分される
・ノード：根ノード　葉ノード　末端　
　　　分割すべき変数
　　　分割する場所
　　　木の形（深さやリーフの数）
　　　各リーフの値

ロス関数、正則化項
・一般のツリーブースティング
　外れた部分（残差）をまた別の木で近似して…という形で
　additive mannerで訓練する．
　　↓
・XGBoost
→２次の項までのテイラー展開する
　　Ω（ft）が最小値となるＷを求める
　→ｇとｈの情報を持っていれば、ｗが計算できる

木の成長（学習方法）
・グリーティ・アルゴリズム

過学習を防ぐ
・シュリンケージ：イテレーションが増えるごとにηをかける
　→勾配法で学習率を小さくしている手法と同じアイデア
・コラム　サブサンプリング：特徴量をサンプリングする

●３章
・分割候補点をどう決めるか
　単純にグリーディーでやると大変
　→各特徴量をパーセンタイル点で区切り、
　　各パーセンタイル点を分割候補店として探索する
　　→パーセンタイル点で区切る方法:
　　　treeごと（＝全体で１回）global
　　　splitごと（分岐したごとにやり直し） local

・重み付き分位点の採用
　→単純にパーセンタイル点で区切るのではなく、二次偏微分の値で
　　重み付けする
　　※ロス関数をiについてまとめると。hiの重みが付いているので
　　　　　↓
　重み付き分位点の高速化(Weighted Quantile Sketch)
　　分割候補点を求める方法
　　　ソートする→パーセンタイルを求める
　　　　→ソートに時間がかかる
　　ソートの工夫
　　　マージオペレーション
　　　→集合をマージしても誤差はそれほど変わらない
　　 プルーン(prune)オペレーション
ランクｄとサマリーＱを指定すると、近いものを返す
　Ｑｕｅｒｙ　Ｆｕｎｃｔｉｏｎを定義
　　　→データをb+1個まで減らしたとき、approxination errorはε+1/b
　　　　で抑えられる

・欠損データの取り扱い
　あらかじめ、木のどちらに行くか決めておく
　　右に行く、左に行くと決めて、よいほうをとる


●４章（を５分で）
・読めばわかる
・ＣＳＣ：ソートの計算コストの削減
　行列を３つのベクトルで表現する
　　　非０要素の位置と値をベクトル化