Backfitting algorithm

In statistics, the backfitting algorithm is a simple iterative procedure used to fit a generalized additive model. It was introduced in 1985 by Leo Breiman and Jerome Friedman along with generalized additive models. In most cases, the backfitting algorithm is equivalent to the Gauss–Seidel method algorithm for solving a certain linear system of equations.
Algorithm.
Additive models are a class of non-parametric regression models of the form:
where each formula_2 is a variable in our formula_3-dimensional predictor formula_4, and formula_5 is our outcome variable. formula_6 represents our inherent error, which is assumed to have mean zero. The formula_7 represent unspecified smooth functions of a single formula_8. Given the flexibility in the formula_7, we typically do not have a unique solution: formula_10 is left unidentifiable as one can add any constants to any of the formula_7 and subtract this value from formula_10. It is common to rectify this by constraining
leaving
necessarily.
The backfitting algorithm is then:
 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)
where formula_21 is our smoothing operator. This is typically chosen to be a cubic spline smoother but can be any other appropriate fitting operation, such as:
In theory, step (b) in the algorithm is not needed as the function estimates are constrained to sum to zero. However, due to numerical issues this might become a problem in practice.
Motivation.
If we consider the problem of minimizing the expected squared error:
There exists a unique solution by the theory of projections given by:
for "i" = 1, 2, ..., "p".
This gives the matrix interpretation:
where formula_25. In this context we can imagine a smoother matrix, formula_26, which approximates our formula_27 and gives an estimate, formula_28, of formula_29
or in abbreviated form
An exact solution of this is infeasible to calculate for large np, so the iterative technique of backfitting is used. We take initial guesses formula_32 and update each formula_33 in turn to be the smoothed fit for the residuals of all the others:
Looking at the abbreviated form it is easy to see the backfitting algorithm as equivalent to the Gauss–Seidel method for linear smoothing operators "S".
Explicit derivation for two dimensions.
Following, we can formulate the backfitting algorithm explicitly for the two dimensional case. We have:
If we denote formula_36 as the estimate of formula_37 in the "i"th updating step, the backfitting steps are
By induction we get
and
If we set formula_41 then we get
Where we have solved for formula_36 by directly plugging out from formula_45.
We have convergence if formula_46. In this case, letting formula_47:
We can check this is a solution to the problem, i.e. that formula_36 and formula_51 converge to formula_52 and formula_53 correspondingly, by plugging these expressions into the original equations.
Issues.
The choice of when to stop the algorithm is arbitrary and it is hard to know a priori how long reaching a specific convergence threshold will take. Also, the final model depends on the order in which the predictor variables formula_54 are fit.
As well, the solution found by the backfitting procedure is non-unique. If formula_55 is a vector such that formula_56 from above, then if formula_57 is a solution then so is formula_58 is also a solution for any formula_59. A modification of the backfitting algorithm involving projections onto the eigenspace of "S" can remedy this problem.
Modified algorithm.
We can modify the backfitting algorithm to make it easier to provide a unique solution. Let formula_60 be the space spanned by all the eigenvectors of "S"i that correspond to eigenvalue 1. Then any "b" satisfying formula_56 has formula_62 and formula_63 Now if we take formula_64 to be a matrix that projects orthogonally onto formula_65, we get the following modified backfitting algorithm:
 Initialize formula_66,formula_67, formula_68
 Do until formula_18 converge:
 Regress formula_70 onto the space formula_71, setting formula_72
 For each predictor "j":
 Apply backfitting update to formula_73 using the smoothing operator formula_74, yielding new estimates for formula_18