Yet Another Representation of Binary Decision Trees: A Mathematical Demonstration

Decision tree looks like a simple computational graph without cycles, where only the leaf nodes specify the output values and the non-terminals specify their tests or computation. From the numerical perspective, we express decision trees in the language of computational graph. We explicitly parameterize the test phase, traversal phase and prediction phase of decision trees based on the bitvectors of non-terminal nodes. As shown later, the decision tree is a shallow binary network in some sense. Especially, we introduce the bitvector matrix to implement the tree traversal in numerical approach, which is equivalent to convert the logical `AND' operation to numerical optimization. And we apply this numerical representation to extend and unify diverse decision trees in concept.