Is some degree of overfitting always going to occur in tree based models? So, I am somewhat new to machine learning, and I am trying my hand at a bunch of different Kaggle datasets.  In a lot of the datasets that I ended up a tree-based model on, I noticed one that all of them had. After graphing the learning curve, I noticed that they all had a level of variance.  While the variance wasn't very high, and the bias was low, I was wondering if this variance is possible to get rid of, or is it just part of tree-based models, and is there always going to be some level of overfitting?
 A: The problem with tree models, and the reason they tend to have high variance, is that they are not truly minimizing a loss function (i.e. miss-classification, MSE).  Rather they are a heuristic that gives a "good" approximation of an algorithm that minimizes a loss function.  
Think about what a tree does, at the first node it generates leafs that seek to minimize the loss function at that node, i.e. the split is the best split for that node. Then it moves on again generating a leaf that minimize the loss function at the next node, but now is conditional on the result from the previous leaf.  This step-wise approach is a good idea, but it does not ensure that the resulting tree will generate predictions that minimize the loss function, i.e. the entire tree might not be optimal.
For example, it is possible that the loss function, evaulated at the tree level, would be smaller if the first split did not minimize the loss function at that node.  In general, however, we can't solve a problem that looks at all possible splits (it's NP-hard).  This is why we follow the step-wise heuristic approach.
Now this step-wise heuristic will likely do a good job on average and therefore it's bias should be low.  However, sometimes we will estimate trees in which the sequence of splits are not optimal at the tree-level.  Therefore predictions will sometimes stray far from the "true" tree, i.e. have a large variance.
This is why Random Forests are sooo coool.  They attempt to solve this problem.  This is accomplished by taking some variables out of consideration at a split.  Therefore it is more likely that some of the trees within the forest are closer to the "true" tree.  More technically, by removing some of the variables from consideration, you de-correlate some of the trees (i.e. all tree will not have the same splits) and in doing so reduce the variance of predictions. 
However, Random Forest can only do so much to reduce variance.  This is because the decision tree frame work itself generates predictions with high variance.  As a result, yes you're right.  Trees generally have a higher variance.
A: Practically no method has 0 variance if it learns from data (unless it just spits out the same estimate which is not based on data).  The same estimators are slightly different from data set to data set, even if that data is generated by the exact same phenomenon.  
If you perform the learning procedure right, there should not be any over fitting.  
