the same predicted value of coursedifferent regions will usually have different predicted values constructing tree with training set {(xi yi )}}ni= amounts to minimizing the training loss ` ( loss(yi (xi ) = ( for some loss functionsee with of the form ( )we can write ` (gn xx loss(yi (xi ) {xi rw loss(yi (xi ) = = ww ww = {xi rw loss(yi gw (xi )){ (* ( ( where (*is the contribution by the regional prediction function gw to the overall training loss in the case where all {xi are differentfinding decision tree that gives zero squared-error or zero-one training loss is easysee exercise but such an "overfittedtree will have poor predictive behaviorexpressed in terms of the generalization risk instead we consider restricted class of decision trees and aim to minimize the training loss within that class it is common to use top-down greedy approachwhich can only achieve an approximate minimization of the training loss top-down construction of decision trees let {(xi yi )}ni= be the training set the key to constructing binary decision tree is to specify splitting rule for each node vwhich can be defined as logical function {falsetrueorequivalentlya binary function { for examplein the decision tree of figure the root node has splitting rule { }in correspondence with the logical condition { during the construction of the treeeach node is associated with specific region rv and therefore also the training subset {(xyt rv using splitting rule swe can divide any subset of the training set into two setsst :{(xys (xtrueand sf :{(xys (xfalse( starting from an empty tree and the initial data set ta generic decision tree construction takes the form of the recursive algorithm here we use the notation tv for subtree of starting from node the final tree is thus obtained via construct_subtree( )where is the root of the tree splitting rule