Decision trees

Decision trees [32] implement functions which are piecewise constant on rectangular areas parallel to the coordinate axes $z_l$. Such an approach can be written in tree structure with nodes only performing comparisons of the form $x<a$ or $x>a$ which allows a very effective hardware implementation. Such a piecewise constant approach can be written in the form

$$\phi(z) = \sum_l c_{l} \prod_k \Theta(z_{\nu(l,k)}-a_{lk})$$ (407)

with step function $\Theta$ and $z_{\nu(l,k)}$ indicating the component of $z$ which is compared with the reference value $a_{lk}$. While there are effective constructive methods to build trees the use of gradient-based minimization or maximization methods would require, for example, to replace the step function by a sigmoid. In particular, decision trees correspond to neural networks at zero temperature, where sigmoids become step functions, and which are restricted to weight vectors in coordinate directions (see Section 4.9).

An overview over different variants of decision trees together with a comparison with rule-based systems, neural networks (see Section 4.9) techniques from applied statistics like linear discriminants, projection pursuit (see Section 4.8) and local methods like for example $k$-nearest neighbors methods ($k$NN), Radial Basis Functions (RBF), or learning vector quantization (LVQ) is given in [158].