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

バックフィッティングアルゴリズム(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}\|<1$ のときに収束する。

問題

アルゴリズムをいつ停止させるかは任意であり、収束閾値に到達するのにどの程度かかるのかを事前に知ることは困難である。また、最終モデルは予測変数 $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}}}$

参考文献

• Breiman, L. & Friedman, J. H. (1985). “Estimating optimal transformations for multiple regression and correlations (with discussion)”. Journal of the American Statistical Association 80 (391): 580–619. doi:10.2307/2288473. JSTOR 2288473. 
• Hastie, T. J. & Tibshirani, R. J. (1990). “Generalized Additive Models”. Monographs on Statistics and Applied Probability 43. 
• Härdle, Wolfgang (2004年6月9日). “Backfitting”. 2015年5月10日時点のオリジナルよりアーカイブ。2015年8月19日閲覧。

外部リンク

• R Package for GAM backfitting at Archive.is (archived 2012-12-11)
• R Package for BRUTO backfitting at the Wayback Machine (archived 2006-11-21)