Yet Another Representation of Binary Decision Trees: A Mathematical Demonstration
This provides a theoretical framework for representing decision trees numerically, which is incremental to existing tree-based methods.
The authors mathematically reformulated binary decision trees as computational graphs using bitvector matrices to implement tree traversal through arithmetic operations, unifying diverse decision tree concepts.
A decision tree looks like a simple directed acyclic computational graph, where only the leaf nodes specify the output values and the non-terminals specify their tests or split conditions. 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, 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, where the core is to convert the logical `AND' operation to arithmetic operations. And we apply this numerical representation to extend and unify diverse decision trees in concept.