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, an algorithm used for solving a certain linear system of equations. Additive models are a class of non-parametric regression models of the form: where each is a variable in our -dimensional predictor , and is our outcome variable. represents our inherent error, which is assumed to have mean zero. The represent unspecified smooth functions of a single . Given the flexibility in the , we typically do not have a unique solution: is left unidentifiable as one can add any constants to any of the and subtract this value from . It is common to rectify this by constraining for all leaving necessarily. The backfitting algorithm is then: Initialize , Do until converge: For each predictor j: (a) (backfitting step) (b) (mean centering of estimated function) where is our smoothing operator. This is typically chosen to be a cubic spline smoother but can be any other appropriate fitting operation, such as: local polynomial regression kernel smoothing methods more complex operators, such as surface smoothers for second and higher-order interactions 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. 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 . In this context we can imagine a smoother matrix, , which approximates our and gives an estimate, , of or in abbreviated form An exact solution of this is infeasible to calculate for large np, so the iterative technique of backfitting is used.