section 14.4 in pattern recognition and machine learning (free) says

Now consider how to determine the structure of the decision tree. Even for a fixed number of nodes in the tree, the problem of determining the optimal structure (including choice of input variable for each split as well as the corresponding thresholds) to minimize the sum-of-squares error is usually computationally infeasible due to the combinatorially large number of possible solutions. Instead, a greedy optimization is generally done by starting with a single root node, corresponding to the whole input space, and then growing the tree by adding nodes one at a time. At each step there will be some number of candidate regions in input space that can be split, corresponding to the addition of a pair of leaf nodes to the existing tree. For each of these, there is a choice of which of the D input variables to split, as well as the value of the threshold. The joint optimization of the choice of region to split, and the choice of input variable and threshold, can be done efficiently by exhaustive search noting that, for a given choice of split variable and threshold, the optimal choice of predictive variable is given by the local average of the data, as noted earlier. This is repeated for all possible choices of variable to be split, and the one that gives the smallest residual sum-of-squares error is retained.

"adding nodes one" sounds a little bit ambiguous. Does that mean "adding only one node" or "adding a bunch of nodes" associated with some "one", if the latter, what exactly the "one" is?

  • 2
    $\begingroup$ The phrase is "adding nodes one at a time." $\endgroup$ – TheIncredibleZ1 Dec 15 '19 at 8:06

The discussion, in essence, is about adding nodes sequentially instead of coming up with the complete tree, and it especially focuses on continuous features where you need to pick one of the features together with an associated threshold value. When you select a feature and threshold to split a node, you actually add a pair of nodes underneath it, as it's also been noted by Bishop. One of them is for the points larger than the threshold, and the other is for the points smaller than (and equal to) the threshold.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.