I have a data set of approximately 400,000 records (for those of you who know, the data set is the one provided by yahoo for their yahoo learning to rank challenge). From this data set I learn a regression tree.
The algorithm leaning the regression tree accepts as parameter the number of levels (height) that the learned tree should have. After learning a tree, I measure its accuracy using Mean Squared Error (MSE). The test data set is the one provided by yahoo (and it has about 165,000 test records).
To determine the ideal level, I run the algorithm with different parameter (height of the resulting tree) values (2 to 40). In the end I plot the MSE vs. the level. My expectation would be to get a convex graph with a bowl-like shape: for small heights the tree underfits the training data, so the MSE would be high, as the height increases the MSE decreases until it reaches a minimum and in the end the MSE starts increasing again because of the overfitting (too many levels mean the resulted tree will overfit the training data).
Unfortunately, I don't get this. What I get is an L-like graph with the vertical bar decreasing slowly (not like in the L letter). The decreasing part is as expected, it reaches a minimum (as expected) but it doesn't start going up afterwards (like there is no overfitting, no matter how many levels the tree has).
Do you have any explanations for this?