Sampling : Gradient Boosting Tree

Question

I have a question regarding the algorithm of Gradient Boosting Tree. I understand Simple tree is built for only a randomly selected sub sample of the full data set (random without replacement). Each consecutive tree is built for the prediction residuals (from all previous trees) of an independently drawn random sample.If an observation is incorrectly classified, then the observation will receive more weight in the next iteration so that it gets properly classified.

My question - if trees are built on random without replacement sample (different observations in each tree). How thousands of trees are built if each tree is built on different observations altogether (random without replacement)? For example, i have a data set consisting of 20,000 records. If i take 0.5 as the fraction of the training set observations randomly selected to propose the next tree in the expansion, how would i be able to create more than 2 trees? My understanding - 50% of the data set is used in building the first tree and the remaining 50% in building the next tree as samples are drawn without replacement. I apologize if it sounds lame. I am very confused in the tree building process.

Answer 1

To clarify, here are my two cents:

• the general idea of Boosting is to add weak classifiers in sequence, such that each successive one focuses on capturing the regions of the training set that were missed by the preceding classifier
• what you say about the weights is only valid for Adaboost

• Adaboost is actually a particular case of Gradient Boosting where the loss function to minimize is the the exponential loss. The reweighing scheme in Adaboost is due to the exponential loss function, but more generally, each new weak classifier in the sequence is fitted directly on the gradient of the loss function. For instance, for least-squares Boosting (where the loss function is squared error), each new tree is built on the residuals of the current model (the sequence, or additive model, of all the trees built so far). I start at Equation 10.6 page 342 of the Elements of Statistical Learning:

  The loss function is: $L(y,f(x))=(y-f(x))^2$

  At iteration $m$, we want to come up with a new tree to add to the current model $f_{m-1}(x)$ (sum of all previous trees) in order to get the new model $f_{m}(x)$. We select the tree that minimizes $L$, or equivalently, the tree that best fits the residuals of the current model $y- f_{m-1}(x)$.

• This brings me to your particular issue. What you're interested in is Stochastic Gradient Boosting, when only a random subset of the data is selected without replacement to build each new tree. Let's consider least-squares Boosting for simplicity. If you have 20,000 observations, a bag fraction parameter of 0.5, it is true that you will build your first tree on 10,000 randomly selected observations. Then my understanding is that you use this first tree to make predictions for all observations (20,000), and get the residuals. Then you select 10,000 of these residuals at random, build a tree that best fits these residuals, add it to the model. Use the model to predict all observations, get the residuals. Repeat the process. Does that make sense?