XGBoostを理解する: 決定株編

XGBoostを理解するためには，決定木（decision tree）を理解しなければならない．決定木を理解するためには，決定株（decision stump）を理解しなければならない．というわけで決定株について勉強してみた．と言ってもそんなに難しい話ではない．でも少しだけ奥が深い．

入力を$\bm{x} \in \mathbb{R}^d$，出力を$y \in \mathcal{Y}$とし，学習データ$\left\{(\bm{x}_i, y_i)\right\}_{i=1}^n$が与えられるとする．決定株では，$\mathcal{I} = \{1, \ldots, n\}$を$I_L, I_R$に分割する．そして，ある関数$w: 2^{\mathcal{I}} \rightarrow \mathcal{Y}$を用いて$I_L, I_R$に$w_L = w(I_L), w_R = w(I_R)$を割り当てる．この分割は，$\hat{i} \in \mathcal{I}, \hat{j} \in \{1, \ldots, d\}$を選ぶことにより決定する．なので，ここからは，$I_L(i, j), I_R(i, j)$と表記する．$(i, j)$に対する損失$L(i, j)$を以下のように定義し，これを最小化するように$\hat{i}, \hat{j}$を選ぶ．

$\begin{aligned} (\hat{i}, \hat{j}) &= \text{argmin}_{(i, j)} \ L(i, j) \\ L(i, j) &= \tilde{L}(I_L(i, j)) + \tilde{L}(I_R(i, j)) \\ \tilde{L}(I) &= \sum_{i \in I} \ell(y_i, w(I))\\ I_L(i, j) &= \left\{i' \vert i' \in \mathcal{I}, x_{i', j} < x_{i, j}\right\} \\ I_R(i, j) &= \left\{i' \vert i' \in \mathcal{I}, x_{i', j} \geq x_{i, j}\right\} \end{aligned}$

ただし，$\ell$は適当な損失関数である．
流れとしては，$(i, j)$に対して，分割$I_L(i, j), I_R(i, j)$が決まり，その損失$\tilde{L}(I_L(i, j)), \tilde{L}(I_L(i, j))$が求まり，その合計である．$L(i, j)$が求まるという 感じだ．

$w$に関しては，分類問題の場合，$\mathcal{Y} = \{-1, 1\}$として，例えば以下のようなものが考えられるだろう．

$\begin{aligned} w(I) = sgn \left(\sum_{i \in I} y_i\right) \end{aligned}$

回帰の場合は，以下のものが考えられるだろう．

$\begin{aligned} w(I) = \frac{1}{|I|} \sum_{i \in I} y_i \end{aligned}$

損失関数は，分類の場合，0-1損失，回帰の場合は二乗誤差を使えば良いのではないか．この辺は自由である．

今回は，決定株について書いた．調べてもなかなか丁寧に説明している文献がなかったので，自分で書いてみたが，なんか複雑になった．正直自分以外わかりにくいと思う．．．．次は決定木について書こうと思う．

Written with StackEdit.