0. 執筆の背景
以前、Xにてどなたかが
「LightGBMをはじめとするGBDT、ぶっちゃけ理論的なところはほぼ理解してない...」
みたいな旨のポストがあって「俺も俺もぉ！！」みたいなコメントが結構あったなぁとふと思い出したので、GBDT(というかより一般的な勾配ブースティング)について改めて書いてみようと思いました^ω^
一般的な勾配ブースティングの解説記事の場合
- 一般的な学習モデル(NNやロジスティック回帰など)のパラメータ最適化の文脈で勾配降下法を説明
- ブースティングの反復学習の中で$t$ラウンド目のモデルでは、$t-1$ラウンドまでの学習結果による負の勾配を予測すればいいんじゃね？というノリの紹介
- 具体的なアルゴリズム
みたいな流れかと思うのですが、勉強不足かつ生まれつきの情報処理能力も高くない若かりし頃の私は
「あれ?勾配降下法ってモデル内の係数とか、そーいうパラメータを最適化する方法だよな？各モデルの予測値を負の勾配にする？？そうすれば、アンサンブルのモデル全体で勾配降下法やってることと同じ？？？ワケワカラーン🤪🤪🤪」
てな感じで、分かったような分かんないような状態、つまり全く分かってない状態になってしまったんですよね。
というわけで、過去の自分や自分と同じような誰かに向けて、改めて基本的な勾配ブースティングについて記してみようと思いました。とはいえ、既存のネット記事と同じ構成では面白くないので、一般的な記事とはちょっと違った視点で勾配ブースティングについて書いていこうと思います。
[記事の目的】
勾配ブースティングのことについて、具体的には、ブースティングで次の弱学習器の予測値を負の勾配(のスカラー倍)にすることの妥当性についてちょっと違った視点で考えてみる
【想定読者】
- 基本的な数学(キーワードはテイラー展開、偏微分、２次形式)は知ってる
- 勾配ブースティングについてチョット知ってるが、ピンときてない人
1. 記号
訓練データは$n$件あり、$t-1$ラウンド時点でのサンプル$i$の現時点での予測値を$z_i^{(t-1)}$とします。$t$ ラウンドでの弱学習器での予測値を$\Delta_i$ とすると
z_i^{(t)} = z_i^{(t-1)} + \Delta_i \tag{1.1}
となります。これらの$z_i^{(t-1)}$や$\Delta_i$を添え字の番号順に並べた$n$次元ベクトルを$\mathbf{z}^{(t-1)}, \mathbf{\Delta} $ とします。
また、サンプル$i$のラベルを$y_i$とした時にその損失を$l(z_i^{(t)}, y_i)$とします。この$l$は回帰なら２乗誤差、分類なら交差エントロピーなどがあるあるですね。全体の損失$\mathcal{L}$は$i=1$から$n$までの$l(z_i^{(t)}, y_i)$の総和とするのが一般的ですが、今、結局のところ関心があるのは「予測値をどんな値にすれば良いのか？」ということなので、
\mathcal{L}\Big(\mathbf{z}^{(t-1)} + \mathbf{\Delta} \Big) = \displaystyle \sum_{i=1}^n{l(z_i^{(t-1)} + \Delta_i, y_i)} \tag{1.2}
のように$\mathcal{L}$を$n$変数関数として扱います。
2. 準備〜Lの偏微分の構造〜
2-1. 勾配
$\mathcal{L}(\mathbf{z})$ の$z_i$での偏微分は次のようになります
\begin{align}
\frac{\partial \mathcal{L}(\mathbf{z})}{\partial z_i} &= \frac{\partial}{\partial z_i}\Big(\displaystyle \sum_{k=1}^n{l(z_k, y_k)} \Big)\\
&= \frac{\partial}{\partial z_i}l(z_i, y_i) \tag{2.1}
\end{align}
点$\mathbf{z}$において、$\mathcal{L}$の勾配とは
\mathbf{g}(\mathbf{z}) =\Big[\frac{\partial \mathcal{L}(\mathbf{z})}{\partial z_1}, \frac{\partial \mathcal{L}(\mathbf{z})}{\partial z_2},\cdots, \frac{\partial \mathcal{L}(\mathbf{z})}{\partial z_n} \Big]^T \tag{2.2}
で定義されるベクトル$\mathbf{g}(\mathbf{z}) \in \mathbb{R}^n$です。
2-2. ヘッセ行列
さらに$\mathcal{L}$の$z_i, z_j$での2階偏微分は(2.1)式より
\frac{\partial^2 \mathcal{L}(\mathbf{z})}{\partial z_i \partial z_j}
=
\begin{cases}
0, & i \ne j,\\[6pt]
\dfrac{\partial^2 \mathcal{L}(\mathbf{z})}{\partial z_i^2}, & i = j, \tag{2.3}
\end{cases}
となります。
点$\mathbf{z}$において、$i$行$j$列の要素が$z_i, z_j$での2階偏微分となる$n$次正方行列を$\mathcal{L}$のヘッセ行列といい$H(\mathbf{z})$で表すことにします。今回、(2.3)式より、任意の点$\mathbf{z}$のヘッセ行列は対角行列になります。
2-3 具体的な1階・2階の偏微分の値
損失として、回帰と分類(今回は議論を単純にするため2値分類)でよく使われる２乗誤差と交差エントロピーを用いて具体的な(2.1)と(2.3)式を計算してみましょう。
回帰で２乗誤差($l(z_i, y_i) = \frac{1}{2}(z_i - y_i)^2$)の場合、
\begin{align}
\frac{\partial}{\partial z_i}l(z_i, y_i) &= (z_i - y_i)\\
\frac{\partial^2}{\partial z_i^2}l(z_i, y_i) &= 1 \tag{2.4}
\end{align}
2値分類で交差エントロピー($l(z_i, y_i) = -y_i\log\sigma(z_i) - (1 - y_i)\log(1-\sigma(z_i))$、$\sigma$はシグモイド関数)の場合、
\begin{align}
\frac{\partial}{\partial z_i}l(z_i, y_i) &= \sigma(z_i) - y_i\\
\frac{\partial^2}{\partial z_i^2}l(z_i, y_i) &= \sigma(z_i)(1-\sigma(z_i)) \tag{2.5}
\end{align}
$0 < \sigma(z_i) < 1$ であるので、$\frac{\partial^2}{\partial z_i^2}l(z_i, y_i)$は必ず正になることがわかります。つまり、$\mathcal{L}$のヘッセ行列は対角行列で、しかも対角成分が全て正の値になることがわかります。ヘッセ行列$H(\mathbf{z})$をn個の正の実数$h_i$を用いて
H(\mathbf{z}) = \text{diag}\{h_1,h_2, \cdots ,h_n \}
とすると、その２次形式は
\mathbf{x}^TH(\mathbf{z})\mathbf{x} = \sum_{i=1}^n{h_i x_i^2} \tag{2.6}
となり、$\mathbf{x}$がゼロベクトルの時を除くと必ず正の値になります。このような、ゼロベクトルを除いた$\mathbf{x}$に対して２次形式が常に正の値になるような対称行列のことを正定値行列と呼びます。
以下、記事の本筋には関わらない余談ですが、関数$f$のヘッセ行列が正定値行列の場合、その関数は狭義凸関数と呼ばれる関数になります。この狭義凸関数は最適化問題を考える際に素敵な性質を持ち、機械学習の理論を学ぶ上ではとても重要なので、初めて知ったという人はぜひご自身で色々調べてみてください。
3. Lの一次近似とΔの決め方
$\mathcal{L}$について計算処理をしていきます。$\mathbf{z}^{(t-1)}$の周りで1次までのテイラー展開をしていきます。
\begin{align}
\mathcal{L}\Big(\mathbf{z}^{(t-1)} + \mathbf{\Delta} \Big) &\simeq \mathcal{L}\Big(\mathbf{z}^{(t-1)}\Big) + \mathbf{\Delta^T g(\mathbf{z}^{(t-1)})} \tag{3.1}
\end{align}
さて $t-1$ラウンドの学習は既に終了しているとし、$\mathbf{z}^{(t-1)}$は既知の定数とします。なので、今関心があるのは
$\mathbf{\Delta}$がどんなベクトルなら良いのか？
言い換えると、
各サンプルでの次の弱学習器ではどんな予測値$\Delta_i$だと良いのか？？
ということです。なので、(3.1)式を最小にするような$\mathbf{\Delta}$を考えます。(3.1)式右辺で、$\mathbf{\Delta}$が関与するのは第2項だけです。第2項は内積の形をしているので、$\mathbf{\Delta}$の長さを固定すると、(3.1)式右辺を最小にする$\mathbf{\Delta}$の方向は$-\mathbf{g}(\mathbf{z}^{(t-1)})$だということが分かります。(割愛しますが、コーシー・シュワルツの不等式を用いると示せます）
適当な正の実数$C$を用いて
\mathbf{\Delta}^{\star} = -C \mathbf{g}(\mathbf{z}^{(t-1)})
としましょう。
これだけでも勾配ブースティングの実態がかなり見えてきましたね。何度も繰り返しますが$\mathbf{\Delta}$は今のラウンドで既存の予測値$\mathbf{z}^{(t-1)}$に追加しようとしている部分なので、巷によくある勾配ブースティングの記事で言うところの
「tラウンド目ではモデルにt-1ラウンド目までの予測値$\mathbf{z}^{(t-1)}$を用いた負の勾配を予測させる。その出力のスカラー倍を加えたものを新たな予測$\mathbf{z}^{(t)}$にする」
に対応します。
4. Δ^*によって、本当にLは低下するのか？
前節で、$\mathbf{\Delta}^{\star}$をとることによって、$\mathbf{z}^{(t-1)}$地点をベースにした時の最小値となるので、ラウンドをどんどん繰り返すと$\mathcal{L}$も小さくなっていきそうだなぁ、と言うお気持ちが分かったと思います。
ただ、よくよく考えると(3.1)の右辺って$\mathcal{L}$をテイラー展開、しかもすごい雑に１次の項までで打ち切りしたものなんですね。
なので当然、「$\mathbf{\Delta}^{\star}$によって、本当に$\mathcal{L}$は低下するのか？」と言う疑問がついてきます。この4節ではそのことについて深掘りして見ていき、この記事を閉じたいと思います。
テイラーの定理より、
\mathcal{L}(\mathbf{z}^{(t-1)} + \Delta^{\star}) = \mathcal{L}(\mathbf{z}^{(t-1)}) + \mathbf{g}(\mathbf{z}^{(t-1)})^T\Delta^{\star} + \frac{1}{2}(\Delta^{\star})^T H(\mathbf{a})\Delta^{\star} \tag{4.1}
を満たすある$\mathbf{a} \in \mathbb{R}^n$が存在します。
ここで(2.6)式を用いて、$(\Delta^{\star})^T H(\mathbf{a})\Delta^{\star}$の上界を評価します。
\begin{align}
(\Delta^{\star})^T H(\mathbf{a})\Delta^{\star} &= \sum_{i=1}^n{h_i (\Delta_i^{\star})^2}\\
&\le h_{max}\sum_{i=1}^n{(\Delta_i^{\star})^2} \\
&= h_{max}|| \mathbf{\Delta}^{\star}||^2 \tag{4.2}
\end{align}
ここで$h_{max}$は$h_i$の最大値,$||\cdot||$はユークリッドノルムです。$h_{max}$は$\mathbf{a}$に依存するため未知ですが、損失を２乗誤差かクロスエントロピーとした場合、(2.4),(2.5)式より $0 < h_{max} \le 1$ となります。
(4.1),(4.2)式より
\begin{align}
\mathcal{L}(\mathbf{z}^{(t-1)} + \Delta^{\star}) &\le \mathcal{L}(\mathbf{z}^{(t-1)}) + \mathbf{g}(\mathbf{z}^{(t-1)})^T\Delta^{\star} + \frac{h_{max}}{2}|| \mathbf{\Delta}^{\star}||^2 \\
&= \mathcal{L}(\mathbf{z}^{(t-1)}) - C\mathbf{g}(\mathbf{z}^{(t-1)})^T\mathbf{g}(\mathbf{z}^{(t-1)})+ \frac{h_{max}}{2}||C\mathbf{g}(\mathbf{z}^{(t-1)})||^2\\
&= \mathcal{L}(\mathbf{z}^{(t-1)}) - C||\mathbf{g}(\mathbf{z}^{(t-1)})||^2+ \frac{C^2h_{max}}{2}||\mathbf{g}(\mathbf{z}^{(t-1)})||^2\\
&= \mathcal{L}(\mathbf{z}^{(t-1)}) - C||\mathbf{g}(\mathbf{z}^{(t-1)})||^2\Big[ 1 - \frac{Ch_{max}}{2}\Big] \tag{4.3}
\end{align}
今$C>0$であるので、$1 - \frac{Ch_{max}}{2} > 0 $の時
\mathcal{L}(\mathbf{z}^{(t-1)} + \Delta^{\star}) \le \mathcal{L}(\mathbf{z}^{(t-1)})
となります。この時の$C$の条件としては
0 < C < \frac{2}{h_{max}}
この条件を満たすのような$C$を毎回とって$\mathbf{\Delta}^{\star}$を定めることより、$\mathcal{L}$は少しずつ小さい値になっていきます。
実は、もっと難しい数学を駆使すれば大域的な最小化解に収束するかどうかも論じることができるのですがそれはまた今度の機会で。