Friedman の MSE

scikit-learn において、回帰木 (Regression Tree) の criterion （Impurity の規準）に指定できるものの中に、friedman_mse というものがある。

cf. sklearn.tree.DecisionTreeRegressor

MSE は Mean Squared Error （二乗平均誤差）のことと思われ、ここでは分散 (Variance) のことを指すようである。Friedman はアメリカの統計学者。

ではこの friedman_mse は通常の MSE すなわち分散とは何が異なるのだろうか。以下の PDF 資料の 14 ページ目、式 (35) に言及がある。

http://www-personal.umich.edu/~jizhu/jizhu/wuke/Friedman-AoS01.pdf

i^2(R_l, R_r) = \frac{w_l w_r}{w_l + w_r} (\bar{y}_l - \bar{y}_r)^2

結論から言うと、情報ゲイン (Information Gain) と同じように使える指標である。決定木学習の一過程における、データセットのある分割（左の子ノードに割り振られるデータセットが $R_l$ で、右の子ノードに割り振られるデータセットが $R_r$）に対する情報ゲインを $IG(R_l, R_r)$ とし、同じ分割に対する “Friedman の情報ゲイン” を $i^2(R_l, R_r)$ とし、分割前のデータセットに含まれるサンプル数を $n$ とすると、ざっくり言って以下の関係がある。

n \cdot IG(R_l, R_r) = i^2(R_l, R_r)

要するに、真面目に分散を計算せずとも、左右それぞれのデータセットにおけるラベルの平均値 $\bar{y}_l$ と $\bar{y}_r$ を求めれば、Friedman の計算式を用いて簡便に情報ゲインが計算できるということのようだ。

ご存知の通り、分散を定義通りに

V = \frac{1}{n} \sum_i \left( x_i - \bar{x} \right) ^2

で真面目に計算しようとすると、まず平均値 $\bar{x}$ を求め、改めて各値と $\bar{x}$ の差の二乗和を計算しなければならない。

また、分散の展開公式

V = \frac{1}{n} \sum_i x_i^2 - \bar{x}^2

を用いるとしても、値の二乗和を計算しなければならない。浮動小数点の計算誤差も気になるかもしれない。

その点 Friedman の計算式ならば、計算量も誤差も減る（ような気がする）。

細かい話

情報ゲインの定義と Friedman の計算式の関係の確認のために行った式変形をログとして残しておく。上述した PDF 資料ではかなり抽象化した記述になっているが、以下では初等数学程度の式変形のみで確認を行う。

記号の定義
- $y_i$: 分割前のラベル，$y_j$: 左のラベル，$y_k$: 右のラベル
- $\bar{y}$: 分割前のラベルの平均，$\bar{y} _l$: 左のラベルの平均，$\bar{y} _r$: 右のラベルの平均
- $V$: 分割前のラベルの分散，$V_l$: 左のラベルの分散，$V_r$: 右のラベルの分散
- 重み：ここでは重み $w_l, w_r$ として、データセットに含まれるサンプル数を用いる
  - $n$: 分割前のサンプル数，$n_l$: 左のサンプル数，$n_r$: 右のサンプル数

さて、分散を Impurity として用いる場合は、情報ゲイン $IG$ は

IG = V - \left( \frac{n_l}{n} V_l + \frac{n_r}{n} V_r \right)

である。これに $n$ を掛けた $n \cdot IG$ を展開していく。分散公式を用いれば、

\begin{align}
n \cdot IG &= nV - n_l V_l - n_r V_r\\
&= n \frac{1}{n} \sum_i y_i^2 - n \bar{y}^2 - n_l \frac{1}{n_l} \sum_j y_j^2 + n_l \bar{y}_l^2 - n_r \frac{1}{n_r} \sum_k y_k^2 + n_r \bar{y}_r^2 \\
&= \sum_i y_i^2 - \sum_j y_j^2 - \sum_k y_k^2 + n_l \bar{y}_l^2 + n_r \bar{y}_r^2 - n \bar{y}^2
\end{align}

となるが、二乗和に関して

\sum_i y_i^2 = \sum_j y_j^2 + \sum_k y_k^2

であるため、

n \cdot IG = n_l \bar{y}_l^2 + n_r \bar{y}_r^2 - n \bar{y}^2

となる。次に $\bar{y}$ について左右に分解すると、

\begin{align}
\bar{y}^2 &= \left( \frac{ \sum_i y_i }{n} \right)^2 \\
&= \left( \frac{ \sum_j y_j + \sum_k y_k }{n} \right)^2 \\
&= \left( \frac{ n_l \frac{1}{n_l} \sum_j y_j + n_r \frac{1}{n_r} \sum_k y_k }{n} \right)^2 \\
&= \left( \frac{ n_l \bar{y}_l + n_r \bar{y}_r }{n} \right)^2 \\
&= \frac{1}{n^2} \left( n_l^2 \bar{y}_l^2 + 2 n_l n_r \bar{y}_l \bar{y}_r + n_r^2 \bar{y}_r^2 \right)
\end{align}

であるから、

\begin{align}
n \cdot IG &= n_l \bar{y}_l^2 + n_r \bar{y}_r^2 - \frac{1}{n} \left( n_l^2 \bar{y}_l^2 + 2 n_l n_r \bar{y}_l \bar{y}_r + n_r^2 \bar{y}_r^2 \right) \\
&= \frac{1}{n} \left( n n_l \bar{y}_l^2 + n n_r \bar{y}_r^2 - n_l^2 \bar{y}_l^2 - 2 n_l n_r \bar{y}_l \bar{y}_r - n_r^2 \bar{y}_r^2 \right) \\
&= \frac{1}{n} \left( \left( n n_l - n_l^2 \right) \bar{y}_l^2 - 2 n_l n_r \bar{y}_l \bar{y}_r + \left( n n_r - n_r^2 \right) \bar{y}_r^2 \right)
\end{align}

となる。ここで $n = n_l + n_r$ が成り立つことから、

\begin{align}
n n_l - n_l^2 &= (n_l + n_r) n_l - n_l^2 \\
&= n_l^2 + n_l n_r - n_l^2 \\
&= n_l n_r, \\
n n_r - n_r^2 &= n_l n_r
\end{align}

であり、

\begin{align}
n \cdot IG &= \frac{1}{n_l + n_r} \left( n_l n_r \bar{y}_l^2 - 2 n_l n_r \bar{y}_l \bar{y}_r + n_l n_r \bar{y}_r^2\right) \\
&= \frac{n_l n_r}{n_l + n_r} \left( \bar{y}_l^2 - 2 \bar{y}_l \bar{y}_r + \bar{y}_r^2 \right) \\
&= \frac{n_l n_r}{n_l + n_r} \left( \bar{y}_l - \bar{y}_r \right)^2
\end{align}

となり、Friedman の計算式と一致する。

ちなみに、あるひとつの節点（決定木のノード）において最良のデータセット分割を探索する（情報ゲインの最大値を探索する）過程の間は $n$ は定数となるため、

IG \propto n_l n_r \left( \bar{y}_l - \bar{y}_r \right)^2

として $n$ を含めずに計算してよい。最後に $n^2$ で割っておくと元の $IG$ の値となる。