User talk:Kvh157

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 Freidman 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[edit]

Generalized additive models are a class of non-parametric regression models of the form:

where each is a variable in our p-dimensional predictor X, and Y is our outcome variable. represents our inherent error, which is assumed to have mean zero. The fi represent unspecified smooth functions of a single Xi. Given the flexibility in the fi, we typically do not have a unique solution: α is left unidentifiable. It is common to rectify this by constraining

leaving

necessarily.


The backfitting algorithm is then:

   Initialize ,
   Do until  converge:
       For each predictor j:
           
           

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

Motivation[edit]

If we consider the problem of minimizing the expected squared error:

There exists a unique solution by the theory of projections given by:

for all 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. We take initial guesses and update each 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[edit]

For the two dimensional case, we can formulate the backfitting algorithm explicitly. We have:

If we denote in the i-th updating step, the backfitting steps are

By induction we get

and

If we assume our constant is zero and we set then we get


This converges if .


Issues[edit]

The choice of when to stop the algorithm is arbitrary and it is hard to know a priori how long reaching a specific conversion threshold will take. Also, the final model depends on the order in which the predictor variables are fit.

As well, the solution found by the backfitting procedure is non-unique. If is a vector such that from above, then if is a solution then so is is also a solution for any . A modification of the backfitting algorithm involving projections onto the eigenspace of S can remedy this problem.

Modified Algorithm[edit]

We can modify the backfitting algorithm to make it easier to provide a unique solution. Let be the space spanned by all the eigenvectors of Si that correspond to eigenvalue 1. Then any b satisfying has and Now if we take to be a matrix that projects orthogonally onto , we get the following modified backfitting algorithm:

   Initialize ,, 
   Do until  converge:
       Regress  onto the space , setting 
       For each predictor j:
           Apply backfitting update to  using the smoothing operator , yielding new estimates for 


References[edit]

  • 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. 
  • 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". Retrieved 2009-11-15. 

External Links[edit]