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

バックフィッティングアルゴリズム(backfitting algorithm)とは、統計学において一般化加法モデルをフィッティングするのに使用される単純な反復手順(iterative procedure)である。1985 年に一般化加法モデルとともに Leo Breiman と Jerome Friedman によって導入された。たいていの場合、バックフィッティングは線形方程式系(連立一次方程式、linear system of equations)を解くのに使用されるガウス＝ザイデル法と等価である。
アルゴリズム.
加法モデルは次の形のノンパラメトリックな回帰モデルのクラスである。
ここで、formula_2 は formula_3 次元予測子("p"-dimensional predictor) formula_4 中の変数であり、formula_5 は結果変数(outcome variable)である。formula_6 は固有誤差(inherent error)であり、平均がゼロであると仮定する。formula_7 は単一のformula_8の詳細不明な滑らかな関数(smooth functions)を表す。formula_7 の柔軟性が与えられたことにより、典型的にはユニークな解を持たない。どの formula_7 にも定数を加えることができ、formula_11 からこの値が引かれるので、formula_11 は不定である。formula_13 とし、すべての formula_14 に対して formula_15 という制約により修正するのが一般的である。
バックフィッティングアルゴリズムは、以下のようになる。
 Initialize formula_16,formula_17
 Do until formula_18 converge:
 For each predictor "j":
 (a) formula_19 (backfitting step)
 (b) formula_20 (mean centering of estimated function)
ここで、formula_21 はスムージング演算子(smoothing operator)である。典型的には3次スプラインスムーザー(cubic spline smoother)が選択されるが、他の適切なフィッティング演算子(fitting operator)を選んでも良い。たとえば、次のようなものがある。
理論上は、アルゴリズムのステップ(b)は、関数の推定値は和がゼロであるという制約があるので、不要である。しかし、数値的な問題により実践上はこれが問題となりうる。
動機.
以下の2乗誤差の期待値を最小化したいとする。
次で与えられる射影理論によりユニークな解が存在する。
これは、次の行列表現を与える。
ここで、formula_25 である。この文脈において、平滑化行列 formula_26 を考えることができ、それは formula_27 を推定し(approximate)、formula_28 の推定値(estimate) formula_29 を与える。
または省略系で : formula_31 とする。
大きい np に対する正確な解を計算するのは実行不可能である。そのため、バックフィッティングによる反復解法が使用される。初期値 formula_32 および formula_33 の更新をしていく。
省略形を見ることで、バックフィッティングアルゴリズムが平滑化演算子 "S" のガウス=ザイデル法に等しいということが簡単にわかる。
2 次元における明示的な導出.
2 次元の場合において、明示的にバックフィッティングアルゴリズムを定式化することができる。
formula_36 を、i 番目の更新ステップにおける formula_37 の推定値とすると、バックフィッティングステップは、以下となる。
誘導により、以下の 2 つを得る。
formula_11 をゼロと仮定し、formula_42 とすると、以下を得る。
これは formula_45 のときに収束する。
問題.
アルゴリズムをいつ停止させるかは任意であり、収束閾値に到達するのにどの程度かかるのかを事前に知ることは困難である。また、最終モデルは予測変数 formula_46 がフィットされる順序に依存する。
同様に、バックフィッティングによって得られる解はユニークではない。formula_47 を formula_48 であるようなベクトルとするとき、formula_49 が解ならば、任意の formula_50 に対して formula_51 も解である。固有空間への射影による修正を適用することで、アルゴリズムの改善が可能である。
アルゴリズムの修正.
ユニークな解を得やすくするための修正が可能である。formula_52 を、固有値が 1 である "S"i の固有ベクトルによって張られる空間とする。このとき、formula_48 を満たす どの "b" も、 formula_54 であるような formula_55 を持つ。今、formula_56 を、formula_57 上の直交射影行列にとるとき、次の修正バックフィッティングアルゴリズムを得る。
 Initialize formula_58,formula_59, formula_60
 Do until formula_18 converge:
 Regress formula_62 onto the space formula_63, setting formula_64
 For each predictor "j":
 Apply backfitting update to formula_65 using the smoothing operator formula_66, yielding new estimates for formula_18