バイアス-バリアンス分解：バギングとランダムフォレスト

　データセット$${D\{(x_1,y_1),\dots (x_n,y_n)\}}$$が、ある分布に従う$${P(\bf{X,Y})}$$から、IIDに従い与えられているとする。ここで、$${\bf x}$$と$${y}$$は一対一対応である必要なはい。
　特徴量$${\bf x}$$を与えた時に、得られる$${y}$$の期待値は、
$${\bar y({\bf x})=E_{y|{\bf x}}[Y]=\int_y Pr(y|{\bf x})dy}$$
と与えられる。
　機械学習アルゴリズム$${\mathcal A}$$が、データセット$${D}$$を与えれた時に推定する結果を$${h_D}$$とし、
$${h_D=\mathcal A(D)}$$
と表現し、$${h_D}$$の期待値$${\bar h_D}$$は、$${P^n}$$空間から$${D}$$が抽出される確率$${P(D)}$$を用い、
$${\bar h_D = E_D[h_D]=\int_D h_DP(D)dD}$$
と与えられる。
　この$${h_D}$$の推定誤差の期待値は
$${E_{({\bf x},y)}[(h_D - y)^2] = \int_{\bf x} \int_y (h_D({\bf x})- y)^2Pr({\bf x},y)d{\bf x}dy}$$
$${=\int_D\int_{\bf x}\int_y (h_D({\bf x})-y)^2P({\bf x},y)P(D)d{\bf x}dydD}$$
で与えられ、以下でVariance-Bias-Noizeに分解する。
$${E_{x,y,D}[(h_D({\bf x})-y)^2]=E_{x,y,D}[\bigl( (h_D({\bf x})-\bar{h}({\bf x}) )+(\bar{h}({\bf x}) -y)\bigl)^2]}$$
$${=E_{{\bf x},D}[(h_D({\bf x})-\bar{h}({\bf x}))^2] + 2E_{{\bf x},y,D}[(h_D({\bf x})-\bar{h}({\bf x}) )(\bar{h}({\bf x}) -y)] + E_{{\bf x},y}[(\bar{h}({\bf x}) -y)^2]}$$
ここで、最初の項の$${E_{{\bf x},D}[(h_D({\bf x})-\bar{h}({\bf x}))^2]}$$は、$${h_D({\bf x})}$$の分散（Variance）である。
真ん中の項は、
$${E_{{\bf x},y,D}[(h_D({\bf x})-\bar{h}({\bf x}))(\bar{h}({\bf x}) -y)] }$$
$${=E_{{\bf x},y}[E_D[(h_D({\bf x})-\bar{h}({\bf x}))](\bar{h}({\bf x}) -y) ]=E_{{\bf x},y}[(\bar{h}(({\bf x})-\bar{h}(({\bf x}))(\bar{h}({\bf x}) -y) ]=0}$$
となり、消える。
最後の項は、
$${E_{{\bf x},y}[(\bar{h}({\bf x}) -y)^2]=E_{{\bf x},y}[\bigl((\bar{h}({\bf x}) -\bar{y}({\bf x})) + (\bar{y}({\bf x})-y)\bigl)^2]}$$
$${=E_{{\bf x},y}[(\bar{h}({\bf x}) -\bar{y}({\bf x}))^2 -2(\bar{h}({\bf x}) -\bar{y})(\bar{y}({\bf x})-y)+(\bar{y}({\bf x})-y)^2]}$$
$${=E_{{\bf x},y}[(\bar{h}({\bf x}) -\bar{y}({\bf x}))^2]-0+E_{{\bf x},y}[(\bar{y}({\bf x})-y)^2]}$$
で、第一項の$${E_{{\bf x},y}[(\bar{h}({\bf x}) -\bar{y}({\bf x}))^2]}$$はバイアスの二乗で、第三項の$${E_{{\bf x},y}[(\bar{y}({\bf x})-y)^2]}$$は$${y}$$のノイズである。
よって、
$${E_{x,y,D}[(h_D({\bf x})-y)^2]=E_{{\bf x},D}[(h_D({\bf x})-\bar{h}({\bf x}))^2]+E_{{\bf x},y}[(\bar{h}({\bf x}) -\bar{y}({\bf x}))^2]+E_{{\bf x},y}[(\bar{y}({\bf x})-y)^2]}$$
と、バリアンス、バイアス、ノイズに分解できる。
　トレイニングデータ量を増やすと、バリアンスは解消できるが、バイアスは、学習アルゴリズムがデータセットのある特有のパターンに引っかかっているため、データ量が増えるとその引っ掛かりの強さも増し解消しない。
　ノイズは、IIDに従う雑音であれば、データ量を増やすことでノイズの平均値に落ち着くが、測定方法に基づく雑音の場合は除くのは難しい。

ランダムフォレスト

　決定木に使われるバギングは、トレーニングデータから重複を許してサンプリングすることで、バリアンスを軽減する。
　なぜなら、あるデータセット$${D:\{x_1,\dot,x_N\}}$$から$${x_i}$$が選ばれない確率は$${\displaystyle{1-\frac{1}{N}}}$$であり、重複を許してN個をサンプリングするから、$${x_i}$$がサンプルリングされない確率は、$${\displaystyle{(1-\frac{1}{N})^N}}$$となる。
よって、$${N-1=t}$$と置き、
$${\displaystyle{\lim_{N\rightarrow\infty}(1-\frac{1}{N})^N=\lim_{t\rightarrow\infty}(\frac{t}{t+1})^{t+1}=\lim_{t\rightarrow\infty}(1+\frac{1}{t})^{-(t+1)}}}$$
ここで、$${\displaystyle{\lim_{t\rightarrow\infty}(1+\frac{1}{t})^t=e}}$$から、
$${\displaystyle{\lim_{t\rightarrow\infty}(1+\frac{1}{t})^{-(t+1)}=e^{-1}\lim_{t\rightarrow\infty}(1+\frac{1}{t})^{-1}=e^{-1}}}$$
$${\frac{1}{e}=0.368}$$から、全体の63％が決定木に渡されている。
　残りの、34％で推定されるのが、アウトオブバッグスコアであり、このエラーがアウトオブバッグエラーと呼ばれる。決定木に渡されていないデータであることから、テストデータでのスコア予測にも使われる。
　ランダムフォレストは、バギングを使い、分割時に修正を与えた決定木であり、以下の手順で行われる。

1. 訓練データセット$${D}$$から重複を許して、決定技の数の$${m}$$ のデータセット$${D_1,\dots D_m}$$を抽出する。

2. 各木$${j}$$は$${D_j}$$で訓練され、分割時にそれぞれがランダムで特徴量を重複なしで$${d}$$選び、これを元に分割を決める。この操作が決定木が似たような木になることを防ぎ、バイアスからくるエラーを減らしている。

3. 各結果$${h_j({\bf x})}$$の単純平均で最終結果を決める$${\displaystyle{h({\bf x})=\frac{1}{m}\sum_{j=1}^mh_j({\bf x})}}$$

ランダムフォレストのパラメータは以下のものがあるが、計算機負荷を増やさないことと、バリアンスとバイアスのバランスを取る必要がある。

• n_estimators:決定木の数で、木を増やせば、互いに相関している木がなくなるためバイアスが減少するが、計算機負荷が増大する。

• max_depth:決定木の分割の回数を制限する。分割回数を増やすことは、訓練データを細かく見ていくことになるが、バリアンスが高くなる。このパラメータを増加させ、限界まで分割したとしても、結局あるパターンは解析できずバイアスが高くなる。よって、max_depthは低く設定し早期終了させるか、デフォルトのNoneのままにしておく。

• min_sample_leaf:決定木の分割をリーフの数で制限する。この数まで減らしたらそれ以上の分割はない。

• max_features:分割時に評価する特徴量の数。一般に特徴量の数$${d}$$の$${\sqrt{d}}$$とするのが望ましいとされている。