4
$\begingroup$

I have problem in intuitive understanding of following arguement:

"The trees generated via bagging are identically distributed, thus the expectation of the average of a set of trees is the same as the Expectation of a single tree"

1) What does really distribution of tree mean? 2) Why, when there are generated via bagging are ID?

$\endgroup$
2
$\begingroup$

Bagging technique uses bootstraps (random samples of the same length with replacement) to train each tree from the assembly. Thus, the samples used to build each individual tree comes from the same population as the original sample. This is why the input and target variables are called ID (identically distributed = same distribution).

More than that, because the samples are drawn randomly, the samples are also independent (knowing elements of a sample does not give hints on the elements of another sample). This is usually denoted as IID (independent and identically distributed).

The expectation of the mean is preserved because input and target variables are IID (samples are independent and are drawn from the same population). [see Law of Large numbers]

Because trees are basically a piece-wise constant approximation, what those trees can learn are constant averages on various regions. The trees only define input space regions (the leaf nodes), but on those regions approximates with an average.

Those constants are averages of some sort (mean, median) depending on the loss function. So what you can say about averages from the input and target variables, you can say about trees themselves (that they preserve the expectation of the average).

The bagging is used to reduce variance by averaging the models, while they preserve as much as possible the expectation of those variables.

I hope I was clear somehow, I will retry later when I will have the chance, to improve this, eventually.

$\endgroup$
1
$\begingroup$

I think rapaio is conflating a couple key concepts and in doing so misinterpreted the OP's question. Yes, the bootstrap samples utilized within a bagging algorithm are IID. However, the bagging estimator is ID, NOT IID.

The bagging algorithm will generate B trees and the corresponding prediction estimates, $\{\hat{f}^b(X)\}_{b=1}^B$. Since the tree estimator estimated each tree using draws from the same distribution, the identical distribution assumption will hold. However, the independence assumption will not hold!!! For example, imagine that there is one very strong predictor within the data. In each tree this strong predictor will likely be the first split. Therefore, the prediction of most trees will be similar. Said another way, the predictions will be correlated (i.e. not independent).

Think about it, the bagging algorithm is taking a sequence of IID random variables (i.e. the bootstrap samples) and turning them into a sequence of ID random variables (by generating tree estimates)

The bagging algorithm is still helpful. The bagging estimator is unbiased; bias is unaffected the lack of independence. Therefore the average of $\hat{f}^b(X)$ will be the same as the expected value of any tree, i.e. $E(f^b(X)) = \frac{1}{B} \sum_{i=1}^B \hat{f}^b(X)$. The variance of the bagging estimator will, however, be affected by non-independence i.e. remember $Var(X+Y) = Var(X) + Var(Y) + 2Cov(X,Y)$. It turns out that bagging estimator will have a smaller variance then a tree estimator (see pg 518 Elements of Statistical Learning). However, we can further reduce estimator variance by attempting to decorrelate the trees. This is where the notion of Random Forest comes from. Again see pg 518 Elements of Statistical Learning or pg 319 Introduction to Statistical Learning for more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.