# Determining optimal height for regression tree

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?

• What regression tree algorithm are you using? Have you tried to see what happens if you learn from a subset of the training data? You might also want to try you own cross-validation on the training data. – Jonathan Jan 26 '13 at 1:42
• I use a CART-like algorithm (no tree pruning) in which a variance-based splitting criterion is used. The algorithm uses a stopping criteria involving the current height of the tree. Yes I tried for various subsets of the original training data set, namely: first 5% of the records, first 10%, ... first 90%. For 5%, 10%, 20% the graph has the expected shape. From 30% on the graph doesn't have an obvious bowl-like shape. At 80% it starts looking like a L as described in the question. – Razvan Jan 27 '13 at 10:02
• Did you try with a different range (e.g. >40)? Also, how many variables or features are there in the data? – soufanom Jan 27 '13 at 14:20
• For the subsets 90% and 100% I tried also for very large heights such as 40,60 even 90. There is no significant accuracy negative impact due to over-fitting, i.e. the MSE increases but not notably (the right end of the graph doesn't go as high as I expected). Anyway, the trees of the ensemble don't even go beyond a specific height (approx. 50 levels) because all the leaves at that level contain perfectly pure data and there is no need for splitting. 700 features but it's sparse dataset – Razvan Jan 28 '13 at 14:22