バックフィッティングアルゴリズム

**バックフィッティングアルゴリズム**(backfitting algorithm)とは、統計学において一般化加法モデルをフィッティングするのに使用される単純な反復手順(iterative procedure)である。1985 年に一般化加法モデルとともに Leo Breiman と Jerome Friedman によって導入された。たいていの場合、バックフィッティングは線形方程式系(連立一次方程式、linear system of equations)を解くのに使用されるガウス＝ザイデル法と等価である。

## アルゴリズム
加法モデルは次の形のノンパラメトリックな回帰モデルのクラスである。

:  Y_i  = \alpha + \sum_{j=1}^p f_j(X_{ij}) + \epsilon_i 

ここで、X_1, X_2, \ldots, X_p  は p 次元予測子(*p*-dimensional predictor) X 中の変数であり、Y は結果変数(outcome variable)である。\epsilon は固有誤差(inherent error)であり、平均がゼロであると仮定する。f_j は単一のX_jの詳細不明な滑らかな関数(smooth functions)を表す。f_j の柔軟性が与えられたことにより、典型的にはユニークな解を持たない。どの f_j にも定数を加えることができ、\alpha からこの値が引かれるので、\alpha は不定である。\alpha = 1/N \sum_{i = 1}^N y_i とし、すべての j に対して \sum_{i = 1}^N f_j(X_{ij}) = 0 という制約により修正するのが一般的である。
バックフィッティングアルゴリズムは、以下のようになる。

    **Initialize** \hat{\alpha} = 1/N \sum_{i = 1}^N y_i, \hat{f_j} \equiv 0, \forall j
    **Do** until \hat{f_j} converge:
        **For** each predictor *j*:
            **(a)**  \hat{f_j} \leftarrow \text{Smooth}[\lbrace y_i - \hat{\alpha} - \sum_{k \neq j} \hat{f_k}(x_{ik}) \rbrace_1^N ] (backfitting step)
            **(b)**  \hat{f_j} \leftarrow \hat{f_j} - 1/N \sum_{i=1}^N \hat{f_j}(x_{ij}) (mean centering of estimated function)

ここで、\text{Smooth} はスムージング演算子(smoothing operator)である。典型的には3次スプラインスムーザー(cubic spline smoother)が選択されるが、他の適切なフィッティング演算子(fitting operator)を選んでも良い。たとえば、次のようなものがある。
* 局所多項式回帰
* カーネル平滑化
* より複雑な演算子、たとえば二次あるいはより高次の表面平滑化(surface smoothers)
理論上は、アルゴリズムのステップ(b)は、関数の推定値は和がゼロであるという制約があるので、不要である。しかし、数値的な問題により実践上はこれが問題となりうる。

## 動機
以下の2乗誤差の期待値を最小化したいとする。

: \min E[Y - (\alpha + \sum_{j=1}^p f_j(X_j))]^2

次で与えられる射影理論によりユニークな解が存在する。

: f_i(X_i) = E[Y - (\alpha + \sum_{j \neq i}^p f_j(X_j)) | X_i] for **i** = 1, 2, ..., **p**.

これは、次の行列表現を与える。

: 

\begin{pmatrix}
I & P_1 & \cdots  & P_1 \\
P_2 & I &  \cdots  & P_2 \\
\vdots &  &  \ddots & \vdots \\
P_p & \cdots  & P_p & I 
\end{pmatrix}

\begin{pmatrix}
f_1(X_1)\\
f_2(X_2)\\
\vdots \\
f_p(X_p)
\end{pmatrix}
=
\begin{pmatrix}
P_1 Y\\
P_2 Y\\
\vdots \\
P_p Y
\end{pmatrix}


ここで、P_i(\cdot) = E(\cdot|X_i) である。この文脈において、平滑化行列 S_i を考えることができ、それは P_i を推定し(approximate)、E(Y|X) の推定値(estimate) S_i Y を与える。

: 
\begin{pmatrix}
I & S_1 & \cdots  & S_1 \\
S_2 & I &  \cdots  & S_2 \\
\vdots &  &  \ddots & \vdots \\
S_p & \cdots  & S_p & I 
\end{pmatrix}

\begin{pmatrix}
f_1\\
f_2\\
\vdots \\
f_p
\end{pmatrix}
=
\begin{pmatrix}
S_1 Y\\
S_2 Y\\
\vdots \\
S_p Y
\end{pmatrix}



または省略系で :  \hat{S}f = QY \  とする。

大きい np に対する正確な解を計算するのは実行不可能である。そのため、バックフィッティングによる反復解法が使用される。初期値 f_i^{(0)} および f_i^{(j)} の更新をしていく。

:  \hat{f_i}^{(j)} \leftarrow \text{Smooth}[\lbrace y_i - \hat{\alpha} - \sum_{k \neq j} \hat{f_k}(x_{ik}) \rbrace_1^N ]

省略形を見ることで、バックフィッティングアルゴリズムが平滑化演算子 *S* のガウス=ザイデル法に等しいということが簡単にわかる。

## 2 次元における明示的な導出
2 次元の場合において、明示的にバックフィッティングアルゴリズムを定式化することができる。

:  f_1 = S_1(Y-f_2), f_2 = S_2(Y-f_1) 

 \hat{f}_1^{(i)}  を、**i** 番目の更新ステップにおける f_1 の推定値とすると、バックフィッティングステップは、以下となる。

:  \hat{f}_1^{(i)} = S_1[Y - \hat{f}_2^{(i-1)}], \hat{f}_2^{(i)} = S_2[Y - \hat{f}_1^{(i-1)}] 

誘導により、以下の 2 つを得る。

:  \hat{f}_1^{(i)} = Y - \sum_{\alpha = 0}^{i-1}(S_1 S_2)^\alpha(I-S_1)Y - (S_1 S_2)^{i -1} S_1\hat{f}_2^{(0)} 

:  \hat{f}_2^{(i)} = S_2 \sum_{\alpha = 0}^{i-1}(S_1 S_2)^\alpha(I-S_1)Y + S_2(S_1 S_2)^{i -1} S_1\hat{f}_2^{(0)} 

\alpha をゼロと仮定し、 \hat{f}_2^{(0)}= 0 とすると、以下を得る。

:  \hat{f}_1^{(i)} = [I - \sum_{\alpha = 0}^{i-1}(S_1 S_2)^\alpha(I-S_1)]Y 

:  \hat{f}_2^{(i)} = [S_2 \sum_{\alpha = 0}^{i-1}(S_1 S_2)^\alpha(I-S_1)]Y 

これは  \|S_1 S_2\|  のときに収束する。

## 問題
アルゴリズムをいつ停止させるかは任意であり、収束閾値に到達するのにどの程度かかるのかを事前に知ることは困難である。また、最終モデルは予測変数 X_i がフィットされる順序に依存する。

同様に、バックフィッティングによって得られる解はユニークではない。b を \hat{S}b = 0 であるようなベクトルとするとき、\hat{f} が解ならば、任意の  \alpha \in \mathbb{R} に対して \hat{f} + \alpha b も解である。固有空間への射影による修正を適用することで、アルゴリズムの改善が可能である。

## アルゴリズムの修正
ユニークな解を得やすくするための修正が可能である。 \mathcal{V}_1(S_i)  を、固有値が 1 である *S*i の固有ベクトルによって張られる空間とする。このとき、\hat{S}b = 0 を満たす どの *b* も、  \sum_{i=1}^p b_i = 0 であるような  b_i \in \mathcal{V}_1(S_i) \forall i=1,\dots,p を持つ。今、 A  を、 \mathcal{V}_1(S_1) + \dots + \mathcal{V}_1(S_p)  上の直交射影行列にとるとき、次の修正バックフィッティングアルゴリズムを得る。

    **Initialize** \hat{\alpha} = 1/N \sum_1^N y_i, \hat{f_j} \equiv 0, \forall i, j, \hat{f_+} = \alpha + \hat{f_1} + \dots + \hat{f_p} 
    **Do** until \hat{f_j} converge:
        Regress  y - \hat{f_+}  onto the space  \mathcal{V}_1(S_i) + \dots + \mathcal{V}_1(S_p) , setting  a = A(Y- \hat{f_+})
        **For** each predictor *j*:
            Apply backfitting update to (Y - a) using the smoothing operator (I - A_i)S_i, yielding new estimates for \hat{f_j}

## 脚注

## 参考文献
* 
* 
* 

## 外部リンク
*
*