2001_greedy_function_approximation_a_gradient_boosting_machine

Greedy Function Approximation: A Gradient Boosting MachineAuthor(s): Jerome H. FriedmanReviewed work(s):Source: The Annals of Statistics, Vol. 29, No. 5 (Oct., 2001), pp. 1189-1232Published by: Institute of Mathematical StatisticsStable URL: http://www.jstor.org/stable/2699986 .

Accessed: 27/02/2012 02:34

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .http://www.jstor.org/page/info/about/policies/terms.jsp

JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range ofcontent in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new formsof scholarship. For more information about JSTOR, please contact support@jstor.org.

Institute of Mathematical Statistics is collaborating with JSTOR to digitize, preserve and extend access to TheAnnals of Statistics.

http://www.jstor.orgThe Annals of Statistics 2001, Vol. 29, No. 5, 1189-1232

1999 REITZ LECTURE

GREEDY FUNCTION APPROXIMATION: A GRADIENT BOOSTING MACHINE'

BY JEROME H. FRIEDMAN

Stanford University Function estimation/approximation is viewed from the perspective of numerical optimization in function space, rather than parameter space. A connection is made between stagewise additive expansions and steepest- descent minimization. A general gradient descent "boosting" paradigm is developed for additive expansions based on any fitting criterion. Specific algorithms are presented for least-squares, least absolute deviation, and Huber-M loss functions for regression, and multiclass logistic likelihood for classification. Special enhancements are derived for the particular case where the individual additive components are regression trees, and tools for interpreting such "TreeBoost" models are presented. Gradient boost- ing of regression trees produces competitive, highly robust, interpretable procedures for both regression and classification, especially appropriate for mining less than clean data. Connections between this approach and the boosting methods of Freund and Shapire and Friedman, Hastie and Tib- shirani are discussed.

1. Function estimation. In the function estimation or "predictive learn- ing" problem, one has a system consisting of a random "output" or "response" variable y and a set of random "input" or "explanatory" variables x = x1, ....

xn}. Using a "training" sample {yi,

Xi}N

of known (y, x)-values, the goal

is to

obtain an estimate or approximation F(x), of the function F*(x) mapping x to y, that minimizes the expected value of some specified loss function L(y, F(x)) over the joint distribution of all (y, x)-values,

(1) F* = argmin Ey

xL(y,

F(x))

=

argminEx[Ey(L(y, F(x)))

I x].

F F

Frequently employed loss functions L(y, F) include squared-error (y - F)2

and absolute error ly

-

Fl for y

E

R' (regression) and negative binomial log-

likelihood, log(1 +

e-2YF), when y

E {-1,

1} (classification).

A common procedure

is to restrict

F(x) to be a member of a parameterized

class of functions F(x; P), where P = {P1, P2, .. .} is a finite set of parameters whose joint values identify individual class members. In this article we focus

Received May 1999; revised April 2001. 1Supported in part by CSIRO Mathematical and Information Science, Australia; Department of Energy

Contract DE-AC03-76SF00515;

and NSF Grant DMS-97-64431.

AMS 2000 subject classifications. 62-02, 62-07, 62-08, 62G08, 62H30, 68T10. Key words and phrases. Function estimation, boosting, decision trees, robust nonparametric regression. 1189