Jinxiong Zhang

Jinxiong Zhang

This paper introduces a series of methods for traversing binary decision trees using arithmetic operations. We present a suite of binary tree traversal algorithms that leverage novel representation matrices to flatten the full binary tree structure and embed the aggregated internal node Boolean tests into a single binary vector. Our approach, grounded in maximum inner product search, offers new insights into decision tree.

Jinxiong Zhang

The decision tree recursively partitions the input space into regions and derives axis-aligned decision boundaries from data. Despite its simplicity and interpretability, decision trees lack parameterized representation, which makes it prone to overfitting and difficult to find the optimal structure. We propose Decision Machines, which embed Boolean tests into a binary vector space and represent the tree structure as a matrices, enabling an interleaved traversal of decision trees through matrix computation. Furthermore, we explore the congruence of decision trees and attention mechanisms, opening new avenues for optimizing decision trees and potentially enhancing their predictive power.

Jinxiong Zhang

Based on decision trees, many fields have arguably made tremendous progress in recent years. In simple words, decision trees use the strategy of "divide-and-conquer" to divide the complex problem on the dependency between input features and labels into smaller ones. While decision trees have a long history, recent advances have greatly improved their performance in computational advertising, recommender system, information retrieval, etc. We introduce common tree-based models (e.g., Bayesian CART, Bayesian regression splines) and training techniques (e.g., mixed integer programming, alternating optimization, gradient descent). Along the way, we highlight probabilistic characteristics of tree-based models and explain their practical and theoretical benefits. Except machine learning and data mining, we try to show theoretical advances on tree-based models from other fields such as statistics and operation research. We list the reproducible resource at the end of each method.

Jinxiong Zhang

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.