let be the initial (deeptree and let tk be the tree obtained after the -th pruning operationfor as soon as the sequence of trees tk is availk ableone can choose the best tree of {tk } = according to the smallest generalization risk specificallywe can split the data into training and validation sets in this casealgorithm is executed using the training set and the generalization risks of {tk } = are estimated via the validation set while algorithm and the corresponding best tree selection process look appealingthere is still an important question to considernamelyhow to choose the node and the corresponding branch tv in line of the algorithm in order to overcome this problembreiman proposed method called cost complexity pruningwhich we discuss next cost-complexity pruning let be tree obtained via pruning of tree denote the set of leaf (terminalnodes of by the number of leaves |wis measure for the complexity of the treerecall that |wis the number of regions {rw in the partition of corresponding to each tree is prediction function gas in ( in cost-complexity pruning the objective is to find prediction function (orequivalentlytree tthat minimizes the training loss ` (gwhile taking into account the complexity of the tree the idea is to regularize the training losssimilar to what was done in by adding penalty term for the complexity of the tree this leads to the following definition cost-complexity pruning definition cost-complexity measure let {(xi yi )}ni= be data set and be real number for given tree tthe cost-complexity measure ct (gtis defined asn ct (gt: {xi rw loss(yi (xi ) |wn ww = ( ` (gg | |where ` (gis the training loss ( small values of result in small penalty for the tree complexity | |and thus large trees (that fit the entire training data wellwill minimize the measure ct (gtin particularfor will be the minimizer of ct (gton the other handlarge values of will prefer smaller trees ormore preciselytrees with fewer leaves for sufficiently large gthe solution will collapse to single (rootnode it can be shown thatfor every value of gthere exists smallest minimizing subtree with respect to the cost-complexity measure in practicea suitable is selected via observing the performance of the learner on the validation set or by cross-validation these advantages and the corresponding limitations are detailed next cost-complexity measure