Sampling : Gradient Boosting Tree 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.
 A: 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?

