Kaggleとかでよく使われている（らしい）DARTについて論文を読んでまとめた。
DART: Dropouts meet Multiple Additive Regression Trees (2015)
https://arxiv.org/abs/1505.01866
概要
通常のGBDT1では、イテレーションの回数が増えるほど、新しく追加される決定木が僅かなサンプルにしか寄与しなくなるover-specializationという問題が知られており、これが汎化性能を下げる要因となる。この問題に対し、これまではshrinkage（各木に微小な定数をかけるという正則化法）を行うことで対処がなされていた。DART（Dropouts meet Multiple Additive Regression Trees）は、このover-specializationの問題を、ニューラルネットにおける正則化法の一つであるドロップアウトを用いることで解消し、モデルの性能向上を実現している。
下の図はナイーブなGBDT、shrinkageを用いたGDBT、DARTそれぞれに対し、各イテレーション数において作成された木を可視化し、手法の振る舞いの比較を行ったもの。葉の大きさがそこに含まれるサンプル数、葉の色が予測値の大きさを表している（緑に行くほど正、黄色が0、赤に行くほど負）。大きい黄色の葉を持つような木が生成されることが、まさにover-specializationに対応している。ナイーブなGBDTでは100イテレーションほどでそのような木が生成されている一方で、DARTでは1000イテレーションでようやくそのような木が生じており、over-specializationが緩和されていることがわかる。
Rashmi and Gilad-Bachrach (2015) より引用
DARTのアルゴリズム
ニューラルネットにおけるドロップアウトはユニットを削除することにより行われるが、DARTにおけるドロップアウトは既に作成されている木を削除することにより行われる。すなわち、各イテレーションにおいて、既に作成されているそれぞれの木を独立に確率 で一時的に削除し、残った木のみを用いたモデルによる予測値の残差（より一般には損失関数の勾配）をターゲットとして新しい木を学習する。ただし、学習された新しい木をそのままモデルに追加すると、一時的に削除された木の効果とあわさって予測値が「オーバーシュート」するので、適切にスケーリングを行う（これはニューラルネットのドロップアウトにおいて、推論時にスケーリングを行うことと似ている）。
具体的には、次の手続きを定めたイテレーション数の上限まで繰り返す（細かい部分を少し省いているがだいたいこんな感じ、詳細は論文参照）。
$t$ステップ目における木の集合を$M = \lbrace T_i \rbrace_{i=1, \dots, t-1}$とする。
- 定めた確率$p_{drop}$にしたがい、ドロップアウトする木の集合$D \subset M$をランダムに選択する。
- 残った木$\hat{M} = M \setminus D$に基づくモデルの予測値の残差（より一般には損失の勾配）をターゲットとし、新しい木$T_t$を学習する。
- 新しい木をスケーリングして集合に追加する：$M \leftarrow M \cup \lbrace \frac{T_t}{|D|+1} \rbrace$
- ドロップアウトされた木もスケーリングする：$T \leftarrow \frac{|D|}{|D|+1} T \quad (T \in D)$
論文では、GBDT、ランダムフォレストがDARTの極端な場合と見なせることが述べられている。ドロップアウトを全く行わない場合が通常のGBDTに対応し、逆に全てドロップアウトする場合がランダムフォレストに対応する。
-
論文中ではMART（Multiple Additive Regression Trees）という言葉で説明されているが、GBDTとほぼ同義だと思うので、今回はこちらの言葉を使った（実際、カステラ本10章では同様のアルゴリズムが「勾配ブースティング木」という名前で解説されている）。 ↩