백피팅 알고리즘

통계에서 백피팅 알고리즘은 일반화된 가법 모형을 적합시키는 데 사용되는 간단한 반복 절차다.1985년 레오 브레이만, 제롬 프리드먼이 일반화된 첨가제 모델과 함께 선보였다.대부분의 경우 백피팅 알고리즘은 방정식의 특정 선형 시스템을 해결하기 위한 가우스-세이델 방법 알고리즘과 동일하다.

알고리즘.

가법 모형은 다음과 같은 형태의 비모수 회귀 모형의 일종이다.

${\displaystyle Y_{i}=\알파 +\sum _{j=1}^{p}f_{j}(X_{ij})+\epsilon _{i}}}$

여기서 각 $X{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{X\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle p_{}}${\$displaystyle X_{1},X_{2},\ldots,X_{p}$는 $우리$의 p$${\$displaystyle$ X$}$ -차원$$ 예측 변수 $X{\displaystyle }$ ${\displaystyle X}$및 $Y{\displaystyle }$ ${\displaysty$ Y$}$이 우리의 결과 변수다$$.${\displaystyle ϵ}$ ${\displaystyle \epsilon }$은(는) 평균 0을 갖는 것으로 가정되는 우리의 고유 오류를 나타낸다$$.$f{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$는 단일 X ${\displaystyle j_{}}$ ${\$의 지정되지 않은 부드러운 기능을 나타낸다$$$.$ $f{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$의 유연성을 감안할 때$,$ 우리는 일반적으로 고유한 솔루션을 가지고 있지 않다: $\alpha {\displaystyle }${\$displaystylepha \ja}$는 어떤 상수도 추가될 수 있기 때문에 식별할 수 없다.${\displaystyle f_{}}$ ${\displaystyle j_{}}$ ${\$${$$j}}$을(를$)$α {\displaystyle $\alpha$ }에서 이 값을 뺀 후$,$ 이를 구속하여 수정하는 것이 일반적이다.

${\displaystyle \sum _{}^{}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= 1 ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle f_{}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \sum _{i=1}^{N}f_{j}(X_{ij})=0}$ 모든 j ${\displaysty j}$에 대해$$

떠나는

${\displaystyle \alpha =1/N\sum _{i=1}^{N}y_{i}}}$

필시

백피팅 알고리즘은 다음과 같다.

Initialize ${\displaystyle {\hat {\alpha }}=1/N\sum _{i=1}^{N}y_{i},{\hat {f_{j}}}\equiv 0}$,${\displaystyle \forall j}$ Do until ${\displaystyle {\hat {f_{j}}}}$ converge:For each predictor j:            (a) ${\displaystyle {\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) ${\displaystyle \stackrel{}{f_{}}}$${\displaystyle \stackrel{}{j_{}}}$ ${\displaystyle \stackrel{}{{}_{}}}$ ${\displaystyle ^}$ ${\displaystyle f\stackrel{}{{}_{}}}$ ${\displaystyle \stackrel{}{j_{}}}$ ${\displaystyle \stackrel{}{{}_{}}}$- ${\displaystyle 1}$ / ${\displaystyle \underset{}{\overset{=}{N}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ = ${\displaystyle \underset{}{\overset{}{}}\stackrel{}{{}_{}}}$ ${\displaystyle \stackrel{}{N_{}}}$ f j${\displaystyle \stackrel{}{{}_{}}}$ ( ${\displaystyle x_{}}$ i ${\displaystyle {}_{}}$) ${\displaystyle {\hat$ {$f_${j$}}\$좌측 $화살표 {\hat {f_{j}-1/N\sum _{i=1}^{n}{f_{j}}}}(x_{ij})})($추정 함수 중심)})

여기서 ${\displaystyle \text{Smooth}}$ ${\$은(는) 스무딩 연산자 입니다.이는 일반적으로 입방 스플라인 평활기로 선택되지만 다음과 같은 다른 적절한 장착 작업이 될 수 있다.

• 국소 다항식 회귀 분석
• 커널 평활 방법
• 2차 및 고차 교호작용을 위한 표면 평활기와 같은 보다 복잡한 연산자

이론적으로 함수 추정치는 합이 0으로 제한되므로 알고리즘의 단계(b)는 필요하지 않다.그러나 수치상의 문제로 인해 이것은 실제로 문제가 될 수 있다.^[1]

동기

예상되는 제곱 오차를 최소화하는 문제를 고려할 경우:

${\displaystyle \min E[Y-(\alpha +\sum _{j=1}^{p_{j}(X_{j})]]^{2}}$

다음과 같이 주어지는 투영 이론에 의한 독특한 해법이 존재한다.

${\displaystyle f_{i}(X_{i})=E[Y-(\Alpha +\sum _{j\neq i}^{p}f_{j}(X_{j}) X_{i}]}$

i = 1, 2, ..., p.

이를 통해 다음과 같은 행렬을 해석할 수 있다.

${\displaystyle {\pmatrix}I&P_{1}&\cdots &P_{1}\\P_{2}>I&\cdots &P_{2}\\\vdots &&\ddots &\\\vdots \\\p_{p}&\cdots &P_{p}&\cdots &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}P_{1}}Y\\P_{2}Y\\\vdots \\P_{p}Y\end{pmatrix}}}$

where ${\displaystyle P_{i}(\cdot )=E(\cdot X_{i})}$. In this context we can imagine a smoother matrix, ${\displaystyle S_{i}}$, which approximates our ${\displaystyle P_{i}}$ and gives an estimate, ${\displaystyle S_{i}Y}$, of ${\displaystyle$$E(Y X)}$

${\displaystyle {\pmatrix}I&S_{1}&\cdots &S_{1}\\S_{2}&I&\cdots &S_{2}\vdots >\vdots \\\\\S_{p}&\cdots &{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}}}$

또는 축약된 형태로

${\displaystyle {\hat{S}f=QY\,}$

이것의 정확한 용액은 큰 np에 대해 계산하는 것이 불가능하므로, 백피팅의 반복적 기법을 사용한다.초기 추측 f ${\displaystyle j_{}^{}}$( ${\displaystyle 0_{}^{}}$) ${\$을(를) 취하여$$ $각{\displaystyle {}_{}^f}$ j ( ${\displaystyle {)}_{}^{}}$ $){j$}^{$j}^{(\ell )}}}}$을(를) 차례로 업데이트하여 다른 모든 잔차에 대한 평활 핏이 되도록 한다.

${\displaystyle {\f_{j}}^{(\ell )}}\왼쪽 화살표 {\lbrace y_{i}-{\lbrace {\lbrace y_{ni}-{\alpha }-}-\com_{k}}{k}}}}\rbrace _{1}^{1}}}}}}}}}}}}}}}}}}}$

축약된 형태를 보면 선형 평활 연산자 S에 대한 가우스-세이델 방법과 동등한 백피팅 알고리즘을 쉽게 볼 수 있다.

2차원에 대한 명시적 파생

다음에,^[2] 우리는 2차원 케이스에 대한 백피팅 알고리즘을 명시적으로 공식화할 수 있다.다음이 있음:

${\displaystyle f_{1}=S_{1}(Y-f_{2}),f_{2}=S_{2}(Y-f_{1})}$

ih 업데이트 단계에서$$ $f{\displaystyle {\stackrel{}{}}_{}^{}}$ ${\displaystyle {\stackrel{}{^}}_{}^{}}$ ${\displaystyle 1_{\mathrm{}}^{}}$ (${\displaystyle i_{}^{}}$) ${\$을(를) $f{\displaystyle {}_{}}$ ${\$}의 추정치로$$ 나타낸다면, 백피팅 단계는 다음과 같다.

${\displaystyle {\f}_{1}^{{{1}^{{{}}=S_{1}[Y-{f}}_{2}^{{2}^{{f}}}=S_{2}}[Y-{f}}}}{f}}}}{1}^{{1}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}]}$

유도에 의해 우리는 얻는다.

${\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)}}$

그리고

${\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}{{1}{\hat{f}_{2}^{0}}}}}}}$

$f{\displaystyle {\stackrel{}{}}_{}^{}}$ ${\displaystyle {\stackrel{}{^}}_{}^{}}$ ${\displaystyle 2_{\mathrm{}}^{}}$( ${\displaystyle 0_{}^{}}$)${\displaystyle {}_{}^{}}$= ${\displaystyle 0}$ ${\displaystyle {\f}_{2}^{0}=0}$을(를) 설정하면

${\displaystyle {\hat {f}}_{1}^{(i)}=Y-S_{2}^{-1}{\hat {f}}_{2}^{(i)}=[I-\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})]Y}$

${\displaystyle {\f}_{2}^{{2}^{(i)}=[S_{2}\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }}}(I-S_{1})]Y}$

$여기$서 ${\displaystyle {f\mathrm{}}_{}}$${\displaystyle {\stackrel{}{}}_{}^{}}$ ${\displaystyle 1_{\mathrm{}}^{}}$ (${\displaystyle i_{}^{}}$ $){\$에서 f 2${\displaystyle {}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}Y}$- ${\displaystyle {}_{}}$ $){\displaystyle f_{2}=S_{2}(Y-f_{1})$를 직접 연결함으로써$$ 해결했다$.$

만약‖ S1S2‖<>우리는;1}. 이 경우, f, f^ 2(나는)→ f^ 1(∞), f^ 2(∞){\displaystyle{\hat{f}}_{1}^{(나는)},{\hat{f}}_{2}^{(나는)}{\xrightarrow{}}{\hat{f}}_{1}^{(\infty)},{\hat{f}}_{2}^{(\in 1(나는)^게 수렴 1{\displaystyle)S_{1}S_{2}\<>고 있다.fty)}$}$:

${\displaystyle {\f}_{1}^{{1}^{{2}^{-1}{\hat{f}_{2}^{2}^{{{2}}=Y-(I-S_{1}S_{2})^{-1}(I-S_{1})^{1}({1})^{1}(I-S_{1}})Y}$

${\displaystyle {\f}_{2}^{(\infit )}=S_{2}(I-S_{1}S_{2})^{-1}(I-S_{1})Y}$

We can check this is a solution to the problem, i.e. that ${\displaystyle {\hat {f}}_{1}^{(i)}}$ and ${\displaystyle {\hat {f}}_{2}^{(i)}}$ converge to ${\displaystyle f_{1}}$ and ${\displaystyle f_{2}}$ correspondingly, by plugging these expressions into the or이그날 방정식

문제들

알고리즘을 언제 중지할 것인지에 대한 선택은 임의적이며 특정 수렴 임계값에 도달하는 데 얼마나 시간이 걸릴지 선험적으로 알기는 어렵다.또한 최종 모형은 예측 변수 X ${\displaystyle i_{}}$ ${\$가 적합되는$$ 순서에 따라 달라진다.

또한, 뒷부분 피팅 절차에서 찾은 해결책은 독특하지 않다.If ${\displaystyle b}$ is a vector such that ${\displaystyle {\hat {S}}b=0}$ from above, then if ${\displaystyle {\hat {f}}}$ is a solution then so is ${\displaystyle {\hat {f}}+\alpha b}$ is also a solution for any ${\displaystyle \alpha \in \mathbb {R} }$. A modifiS의 Eigenspace에 대한 투영을 포함하는 백 피팅 알고리즘의 cation은 이 문제를 해결할 수 있다.

수정 알고리즘

우리는 독특한 솔루션을 제공하는 것이 더 쉽도록 백피팅 알고리즘을 수정할 수 있다.$V{\displaystyle {\mathcal{}}_{}}$ ${\displaystyle 1_{\mathrm{}}}$( ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle {\mathcal {V}_{1}(S_{i})$을 고유값 1에 해당하는 S의_i 모든 고유 벡터에 의해 확장되는 공간이 되도록$$ 한다.Then any b satisfying ${\displaystyle {\hat {S}}b=0}$ has ${\displaystyle b_{i}\in {\mathcal {V}}_{1}(S_{i})\forall i=1,\dots ,p}$ and ${\displaystyle \sum _{i=1}^{p}b_{i}=0.$$}$ Now if we take ${\displaystyle A}$ to be a matrix that projects orthogonally onto ${\displaystyle {\mathcal {V}}_{1}(S_{1})+\dots +{\mathcal {V}}_{1}(S_{p})}$, we get the following modified backfitting algorithm:

Initialize ${\displaystyle {\hat {\alpha }}=1/N\sum _{1}^{N}y_{i},{\hat {f_{j}}}\equiv 0}$,${\displaystyle \forall i,j}$, ${\displaystyle {\hat {f_{+}}}=\alpha +{\hat {f_{1}}}+\dots +{\hat {f_{p}}}}$ Do f ${\displaystyle \stackrel{}{j_{}}}$ ${\$ 수렴$$ 시까지:Regress ${\displaystyle y-{\hat {f_{+}}}}$ onto the space ${\displaystyle {\mathcal {V}}_{1}(S_{i})+\dots +{\mathcal {V}}_{1}(S_{p})}$, setting ${\displaystyle a=A(Y-{\hat {f_{+}}})}$ For each predictor j:            App스무딩 연산자$({\displaystyle I}$- ${\displaystyle A_{}}$ i${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$를 사용하여${\displaystyle }$(${\displaystyle Y}$- ${\displaystyle a)}$ ${\displaystyle(Y-a)}$에 대한 리백피팅 업데이트$S_{i}},$$f{\displaystyle \stackrel{}{{}_{}}}$ ${\displaystyle \stackrel{}{j_{}}}$ ${\$ {$f_{j}}}}$에 대한 새로운 추정치 제시

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2009년 12월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

참조

• 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; et al. (June 9, 2004). "Backfitting". Archived from the original on 2015-05-10. Retrieved 2015-08-19.

외부 링크

• GAM 백피팅용 R 패키지
• BRUTO 백피팅용 R 패키지