A Gradient Boosting Machine

GBDT = Gradient Boosting + Decision Tree
another names:

Ensemble learning

Bootstrap AGGregatING
train weak learner parallelly
low variance

train weak learner iteratively
low bias

optimization goal:

P^{*} = \underset{P}{a r g m i n} Φ (P)

= \underset{P}{a r g m i n} E_{y, x} ψ (y, F (x; P))

solution for the parameters in the form:

P^{*} = \sum_{m = 0}^{M} p_{m}

where $p_{0}$ is an initial guess and ${P_{m}}_{1}^{m}$ are successive increments (“steps” or “boosts”)

define the increments ${p_{m}}_{1}^{M}$ as follows

current gradient $g_{m}$ is computed $g m = {g_{j m}} = [\frac{\partial Φ (P)}{\partial P_{j}}]_{P = P_{m - 1}}$
where $P_{m - 1} = \sum_{i = 0}^{m - 1} P_{i}$
linear search learning rate $ρ_{m} = \underset{ρ}{a r g m i n} Φ (P_{m - 1} - ρ g_{m})$
the step is taken to be $P_{m} = - ρ_{m} g_{m}$

we consider $F (x)$ evaluated at each point x to be a “parameter” and seek to minimize

F^{*} (x) = \underset{F (x)}{a r g m i n} E_{y, x} ψ (y, F (x))

we take solution to be

F^{*} (x) = \sum_{m = 0}^{M} f_{m} (x)

where $f_{0} (x)$ is an initial guess, and ${f_{m} (x)}_{1}^{M}$ are incremental functions

current gradient:

g_{m} (x) = E_{y} [\frac{\partial ψ (y, F (x))}{\partial F (x)} | x]_{F (x) = F_{m - 1} (x)}

and

F_{m - 1} (x) = \sum_{i = 0}^{m - 1} f_{i} (x)

the multiplier $ρ_{m}$ is given by the linear search

ρ_{m} = \underset{ρ}{a r g m i n} E_{y, x} ψ (y, F_{m - 1} (x) - ρ g_{m} (x))

and the steepest-descent:

f_{m} (x) = - ρ_{m} g_{m} (x)

above approach breaks down when the joint distribution of (y, x) is represented by a finite data sample

(β_{m}, a_{m}) = \underset{β, a}{a r g m i n} \sum_{i = 1}^{N} ψ (y_{i}, F_{m - 1} (x_{i}) + β h (x_{i}; a))

and then

F_{m} (x) = F_{m - 1} + β_{m} h (x; a_{m})

train gradient model by:

a_{m} = \underset{a, β}{a r g m i n} \sum_{i = 1}^{N} [- g_{m} (x_{i}) - β h (x_{i}; a)]^{2}

get learning rate $β$ by linear search