algorithm construct_subtree inputa node and subset of the training datas outputa (subdecision tree tv if termination criterion is met then / is leaf node train regional prediction function using the training data else /split the node find the best splitting rule sv for node create successors vt and vf of st {(xys sv (xtrue sf {(xys sv (xfalse tvt construct_subtree (vt st /left branch tvf construct_subtree (vf sf /right branch return tv the splitting rule sv divides the region rv into two disjoint partssay rvt and rvf the corresponding prediction functionsgt and gf satisfy gv (xgt ( { rvt gf ( { rvf } rv in order to implement the procedure described in algorithm we need to address the construction of the regional prediction functions gv at the leaves (line )the specification of the splitting rule (line )and the termination criterion (line these important aspects are detailed in the following sections and respectively regional prediction functions in generalthere is no restriction on how to choose the prediction function gw for leaf node in line of algorithm in principle we can train any model from the datae via linear regression howeverin practice very simple prediction functions are used belowwe detail popular choice for classificationas well as one for regression in the classification setting with class labels the regional prediction function gw for leaf node is usually chosen to be constant and equal to the most common class label of the training data in the associated region rw (ties can be broken randomlymore preciselylet nw be the number of feature vectors in region rw and let { =zpwz nw {( , ) xr be the proportion of feature vectors in rw that have class label the regional prediction function for node is chosen to be the constant gw (xargmax pwz ( { , - in the regression settinggw is usually chosen as the mean response in the regionthat isx gw (xyrw : ( nw {( , ) xr