KeRF: Random ForestはKernel - データサイエンス関連+αのメモ

Scornet, E. (2016). Random forests and kernel methods. IEEE Transactions on Information Theory, 62(3), 1485-1500.

ランダムフォレストの定義をわずかに変更することで、ランダムフォレストをカーネル法として書き換えられることを示す。
この手法を、Random Forest に基づく Kernel という意味で KeRF と呼ぶ。KeRF は通常のランダムフォレストより解釈しやすく、理論解析も容易である。

有限forestについて、点 $x$ と標本点 $X_i$ が同じセルに入った木の割合を、接続関数

K_{M,n}(x,z) = \frac{1}{M} \sum_{j=1}^{M} \mathbf{1}_{{z\in A_n(x,\Theta_j)}}

(1)

として定義する。KeRF 推定量は

\widetilde m_{M,n}(x) = \frac{\sum_{i=1}^{n}Y_iK_{M,n}(x,X_i)} {\sum_{\ell=1}^{n}K_{M,n}(x,X_\ell)}

(2)

というカーネル回帰の形で表される。

前提知識¶

カーネル回帰¶

\widehat{m}(x) = \frac{ \sum_{i=1}^{n} Y_iK(x,X_i) }{ \sum_{i=1}^{n} K(x,X_i) }

(3)

ここで

$\widehat{m}(x)$ ：点 $x$ における回帰関数の推定値
$K(x,X_i)$ ： $x$ と訓練点 $X_i$ の近さを表すカーネル
$Y_i$ ：訓練点 $X_i$ に対応する応答値

Random Forest¶

Tree¶

第 $j$ 番目の木の予測は、そのセル内の応答変数の平均として次のように表すことができる。

m_n(x,\Theta_j) = \frac{ \sum_{i=1}^{n} Y_i \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} }{ N_n(x,\Theta_j) }

(4)

ここで

$x$ ：予測対象の点
$A_n(x,\Theta_j)$ ：第 $j$ 番目の木で $x$ が属する終端セル
$\Theta_j$ ：第 $j$ 番目の木を構築するランダム性（ブートストラップ標本、分割変数、分割位置など）
$Y_i$ ：第 $i$ 番目の訓練標本の応答値
$\mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}}$ ： $X_i$ が $x$ と同じ葉に入れば1、それ以外は0
$N_n(x,\Theta_j)$ ：その葉に含まれる訓練標本数

Random Forest¶

$M$ 本の木からなるRandom Forestは次のように書くことができる

\begin{aligned} m_{M,n}(x) &= \frac{1}{M} \sum_{j=1}^{M} m_n(x,\Theta_j) \\ &= \frac{1}{M} \sum_{j=1}^{M} \frac{ \sum_{i=1}^{n} Y_i \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} }{ N_n(x,\Theta_j) } \\ &= \sum_{i=1}^{n} Y_iW_{i,M,n}(x) \end{aligned}

(5)

ここで $W_{i,M,n}(x)$ は同じ葉に入る頻度と葉の大きさの両方を反映した重み

W_{i,M,n}(x) = \frac{1}{M} \sum_{j=1}^{M} \frac{ \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} }{ N_n(x,\Theta_j) }

(6)

KeRF¶

接続関数¶

接続関数 $K_{M,n}(x,z)$ は $x$ と $z$ が同じ葉に入った木の割合

K_{M,n}(x,z) = \frac{1}{M} \sum_{j=1}^{M} \mathbf{1}_{\{z\in A_n(x,\Theta_j)\}}

(7)

ここで

$K_{M,n}(x,z)$ ：有限forestにおける接続関数
$x,z$ ：比較する2点

通常のRandom Forestの重み $W_{i,M,n}(x)$ から葉内のサンプル数 $N_n(x,\Theta_j)$ による正規化をなくしたのが接続関数

W_{i,M,n}(x) = \frac{1}{M} \sum_{j=1}^{M} \frac{ \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} }{ N_n(x,\Theta_j) } = \frac{1}{M} \sum_{j=1}^{M} \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} \cdot \frac{1}{N_n(x,\Theta_j)} = K_{M,n}(x,z) \cdot \frac{1}{N_n(x,\Theta_j)}

(8)

KeRF¶

\widetilde{m}_{M,n}(x) = \frac{ \sum_{i=1}^{n} Y_iK_{M,n}(x,X_i) }{ \sum_{\ell=1}^{n} K_{M,n}(x,X_\ell) }

(9)

ここで

$\widetilde{m}_{M,n}(x)$ ：有限forestに基づくKeRFの予測
$K_{M,n}(x,X_i)$ ： $x$ と $X_i$ が同じ葉に入った割合
$Y_i$ ：訓練点 $X_i$ の応答値

接続関数を展開すると

\widetilde{m}_{M,n}(x) = \frac{ \sum_{j=1}^{M} \sum_{i=1}^{n} Y_i \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} }{ \sum_{j=1}^{M} N_n(x,\Theta_j) }

(10)

ここで

分子：森林全体で $x$ と同じ葉に入った応答値の合計
分母：森林全体で $x$ と同じ葉に入った訓練標本数の合計

Random ForestとKeRFの違い¶

Random Forestは

\frac{1}{M} \sum_{j=1}^{M} \frac{ \sum_i Y_i \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} }{ N_n(x,\Theta_j) }

(11)

KeRFは

\frac{ \sum_j \sum_i Y_i \mathbf{1}_{\{X_i\in A_n(x,\Theta_j)\}} }{ \sum_j N_n(x,\Theta_j) }

(12)

ここで

Random Forest：各木の葉内で正規化してから平均する
KeRF：森林全体の接続回数を集計してから一度だけ正規化する
両者の本質的な違い：正規化のタイミング

KeRFは、Random Forestの接続関数をカーネルとして用いたカーネル回帰である。

Random Forestとの関係¶

特定の条件下では、ランダムフォレストとKeRFは一致、あるいは漸近的に等価になる

Breimanのフォレスト: 各葉に含まれる観測値がちょうど1つの場合（分類問題のデフォルト設定など）、ランダムフォレストとKeRFの推定値は完全に一致する