この項目「
バックフィッティングアルゴリズム 」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：
en:Backfitting_algorithm 04:12, 26 April 2017）
修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。
ノートページ や
履歴 も参照してください。
（2017年5月 ）
バックフィッティングアルゴリズム (backfitting algorithm)とは、統計学 において一般化加法モデル をフィッティングするのに使用される単純な反復手順(iterative procedure)である。1985 年に一般化加法モデルとともに Leo Breiman と Jerome Friedman によって導入された。たいていの場合、バックフィッティングは線形方程式系(連立一次方程式、linear system of equations)を解くのに使用されるガウス＝ザイデル法 と等価である。
加法モデル は次の形のノンパラメトリック な回帰モデルのクラスである。
Y
i
=
α
+
∑
j
=
1
p
f
j
(
X
i
j
)
+
ϵ
i
{\displaystyle Y_{i}=\alpha +\sum _{j=1}^{p}f_{j}(X_{ij})+\epsilon _{i}}
ここで、
X
1
,
X
2
,
…
,
X
p
{\displaystyle X_{1},X_{2},\ldots ,X_{p}}
p
{\displaystyle p}
p -dimensional predictor)
X
{\displaystyle X}
Y
{\displaystyle Y}
ϵ
{\displaystyle \epsilon }
f
j
{\displaystyle f_{j}}
X
j
{\displaystyle X_{j}}
滑らかな関数 (smooth functions)を表す。
f
j
{\displaystyle f_{j}}
f
j
{\displaystyle f_{j}}
α
{\displaystyle \alpha }
α
{\displaystyle \alpha }
α
=
1
/
N
∑
i
=
1
N
y
i
{\displaystyle \alpha =1/N\sum _{i=1}^{N}y_{i}}
j
{\displaystyle j}
∑
i
=
1
N
f
j
(
X
i
j
)
=
0
{\displaystyle \sum _{i=1}^{N}f_{j}(X_{ij})=0}
Initialize
α
^
=
1
/
N
∑
i
=
1
N
y
i
,
f
j
^
≡
0
{\displaystyle {\hat {\alpha }}=1/N\sum _{i=1}^{N}y_{i},{\hat {f_{j}}}\equiv 0}
∀
j
{\displaystyle \forall j}
Do until
f
j
^
{\displaystyle {\hat {f_{j}}}}
For each predictor j :
(a)
f
j
^
←
Smooth
[
{
y
i
−
α
^
−
∑
k
≠
j
f
k
^
(
x
i
k
)
}
1
N
]
{\displaystyle {\hat {f_{j}}}\leftarrow {\text{Smooth}}[\lbrace y_{i}-{\hat {\alpha }}-\sum _{k\neq j}{\hat {f_{k}}}(x_{ik})\rbrace _{1}^{N}]}
(b)
f
j
^
←
f
j
^
−
1
/
N
∑
i
=
1
N
f
j
^
(
x
i
j
)
{\displaystyle {\hat {f_{j}}}\leftarrow {\hat {f_{j}}}-1/N\sum _{i=1}^{N}{\hat {f_{j}}}(x_{ij})}
ここで、
Smooth
{\displaystyle {\text{Smooth}}}
理論上は、アルゴリズムのステップ(b)は、関数の推定値は和がゼロであるという制約があるので、不要である。しかし、数値的な問題により実践上はこれが問題となりうる[ 1]
以下の2乗誤差の期待値を最小化したいとする。
min
E
[
Y
−
(
α
+
∑
j
=
1
p
f
j
(
X
j
)
)
]
2
{\displaystyle \min E[Y-(\alpha +\sum _{j=1}^{p}f_{j}(X_{j}))]^{2}}
次で与えられる射影理論によりユニークな解が存在する。
f
i
(
X
i
)
=
E
[
Y
−
(
α
+
∑
j
≠
i
p
f
j
(
X
j
)
)
|
X
i
]
{\displaystyle f_{i}(X_{i})=E[Y-(\alpha +\sum _{j\neq i}^{p}f_{j}(X_{j}))|X_{i}]}
i = 1, 2, ..., p .これは、次の行列表現を与える。
(
I
P
1
⋯
P
1
P
2
I
⋯
P
2
⋮
⋱
⋮
P
p
⋯
P
p
I
)
(
f
1
(
X
1
)
f
2
(
X
2
)
⋮
f
p
(
X
p
)
)
=
(
P
1
Y
P
2
Y
⋮
P
p
Y
)
{\displaystyle {\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
(
⋅
)
=
E
(
⋅
|
X
i
)
{\displaystyle P_{i}(\cdot )=E(\cdot |X_{i})}
S
i
{\displaystyle S_{i}}
P
i
{\displaystyle P_{i}}
E
(
Y
|
X
)
{\displaystyle E(Y|X)}
S
i
Y
{\displaystyle S_{i}Y}
(
I
S
1
⋯
S
1
S
2
I
⋯
S
2
⋮
⋱
⋮
S
p
⋯
S
p
I
)
(
f
1
f
2
⋮
f
p
)
=
(
S
1
Y
S
2
Y
⋮
S
p
Y
)
{\displaystyle {\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}}}
または省略系で :
S
^
f
=
Q
Y
{\displaystyle {\hat {S}}f=QY\ }
大きい np に対する正確な解を計算するのは実行不可能である。そのため、バックフィッティングによる反復解法が使用される。初期値
f
i
(
0
)
{\displaystyle f_{i}^{(0)}}
f
i
(
j
)
{\displaystyle f_{i}^{(j)}}
f
i
^
(
j
)
←
Smooth
[
{
y
i
−
α
^
−
∑
k
≠
j
f
k
^
(
x
i
k
)
}
1
N
]
{\displaystyle {\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 次元の場合において、明示的にバックフィッティングアルゴリズムを定式化することができる。
f
1
=
S
1
(
Y
−
f
2
)
,
f
2
=
S
2
(
Y
−
f
1
)
{\displaystyle f_{1}=S_{1}(Y-f_{2}),f_{2}=S_{2}(Y-f_{1})}
f
^
1
(
i
)
{\displaystyle {\hat {f}}_{1}^{(i)}}
i 番目の更新ステップにおける
f
1
{\displaystyle f_{1}}
f
^
1
(
i
)
=
S
1
[
Y
−
f
^
2
(
i
−
1
)
]
,
f
^
2
(
i
)
=
S
2
[
Y
−
f
^
1
(
i
−
1
)
]
{\displaystyle {\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 つを得る。
f
^
1
(
i
)
=
Y
−
∑
α
=
0
i
−
1
(
S
1
S
2
)
α
(
I
−
S
1
)
Y
−
(
S
1
S
2
)
i
−
1
S
1
f
^
2
(
0
)
{\displaystyle {\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)}}
f
^
2
(
i
)
=
S
2
∑
α
=
0
i
−
1
(
S
1
S
2
)
α
(
I
−
S
1
)
Y
+
S
2
(
S
1
S
2
)
i
−
1
S
1
f
^
2
(
0
)
{\displaystyle {\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)}}
α
{\displaystyle \alpha }
f
^
2
(
0
)
=
0
{\displaystyle {\hat {f}}_{2}^{(0)}=0}
f
^
1
(
i
)
=
[
I
−
∑
α
=
0
i
−
1
(
S
1
S
2
)
α
(
I
−
S
1
)
]
Y
{\displaystyle {\hat {f}}_{1}^{(i)}=[I-\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})]Y}
f
^
2
(
i
)
=
[
S
2
∑
α
=
0
i
−
1
(
S
1
S
2
)
α
(
I
−
S
1
)
]
Y
{\displaystyle {\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
{\displaystyle \|S_{1}S_{2}\|<1}
アルゴリズムをいつ停止させるかは任意であり、収束閾値に到達するのにどの程度かかるのかを事前に知ることは困難である。また、最終モデルは予測変数
X
i
{\displaystyle X_{i}}
同様に、バックフィッティングによって得られる解はユニークではない。
b
{\displaystyle b}
S
^
b
=
0
{\displaystyle {\hat {S}}b=0}
f
^
{\displaystyle {\hat {f}}}
α
∈
R
{\displaystyle \alpha \in \mathbb {R} }
f
^
+
α
b
{\displaystyle {\hat {f}}+\alpha b}
ユニークな解を得やすくするための修正が可能である。
V
1
(
S
i
)
{\displaystyle {\mathcal {V}}_{1}(S_{i})}
S i の固有ベクトルによって張られる空間とする。このとき、
S
^
b
=
0
{\displaystyle {\hat {S}}b=0}
b も、
∑
i
=
1
p
b
i
=
0
{\displaystyle \sum _{i=1}^{p}b_{i}=0}
b
i
∈
V
1
(
S
i
)
∀
i
=
1
,
…
,
p
{\displaystyle b_{i}\in {\mathcal {V}}_{1}(S_{i})\forall i=1,\dots ,p}
A
{\displaystyle A}
V
1
(
S
1
)
+
⋯
+
V
1
(
S
p
)
{\displaystyle {\mathcal {V}}_{1}(S_{1})+\dots +{\mathcal {V}}_{1}(S_{p})}
Initialize
α
^
=
1
/
N
∑
1
N
y
i
,
f
j
^
≡
0
{\displaystyle {\hat {\alpha }}=1/N\sum _{1}^{N}y_{i},{\hat {f_{j}}}\equiv 0}
∀
i
,
j
{\displaystyle \forall i,j}
f
+
^
=
α
+
f
1
^
+
⋯
+
f
p
^
{\displaystyle {\hat {f_{+}}}=\alpha +{\hat {f_{1}}}+\dots +{\hat {f_{p}}}}
Do until
f
j
^
{\displaystyle {\hat {f_{j}}}}
y
−
f
+
^
{\displaystyle y-{\hat {f_{+}}}}
V
1
(
S
i
)
+
⋯
+
V
1
(
S
p
)
{\displaystyle {\mathcal {V}}_{1}(S_{i})+\dots +{\mathcal {V}}_{1}(S_{p})}
a
=
A
(
Y
−
f
+
^
)
{\displaystyle a=A(Y-{\hat {f_{+}}})}
For each predictor j :
Apply backfitting update to
(
Y
−
a
)
{\displaystyle (Y-a)}
(
I
−
A
i
)
S
i
{\displaystyle (I-A_{i})S_{i}}
f
j
^
{\displaystyle {\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日 閲覧。 
![{\displaystyle {\hat {f_{j}}}\leftarrow {\text{Smooth}}[\lbrace y_{i}-{\hat {\alpha }}-\sum _{k\neq j}{\hat {f_{k}}}(x_{ik})\rbrace _{1}^{N}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8b2f22cdb64e32f98170ed0233cff0b74aee851)
![{\displaystyle \min E[Y-(\alpha +\sum _{j=1}^{p}f_{j}(X_{j}))]^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ffa852510ad3b906ac93cd4aed5537c10cda774)
![{\displaystyle f_{i}(X_{i})=E[Y-(\alpha +\sum _{j\neq i}^{p}f_{j}(X_{j}))|X_{i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ace4767dde5a70c9832a94246ab63df57b81721e)
![{\displaystyle {\hat {f_{i}}}^{(j)}\leftarrow {\text{Smooth}}[\lbrace y_{i}-{\hat {\alpha }}-\sum _{k\neq j}{\hat {f_{k}}}(x_{ik})\rbrace _{1}^{N}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2647e5da6b47675af051aaffafcad0c13b94dc37)
![{\displaystyle {\hat {f}}_{1}^{(i)}=S_{1}[Y-{\hat {f}}_{2}^{(i-1)}],{\hat {f}}_{2}^{(i)}=S_{2}[Y-{\hat {f}}_{1}^{(i-1)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f570d54983162127f5bc67dd2d3b7020a5cb5408)
![{\displaystyle {\hat {f}}_{1}^{(i)}=[I-\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})]Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfe8573e34b13924dbb8fdbc1d24815d73fbd118)
![{\displaystyle {\hat {f}}_{2}^{(i)}=[S_{2}\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})]Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9e8dcbc9b2f6abbf3f3cf7209a676744c875722)
