Lab member paper accepted at ICMLA 2022

• Post by: Bahareh Arghavani
• February 16, 2023
• Comments off

Congratulations on the acceptance of your paper titled “Stochastic Induction of Decision Trees with Application to Learning Haar Tree ” This is a significant achievement that reflects your hard work, dedication, and expertise in the field of machine learning and artificial intelligence.

The paper is available on OpenReview.

Your research has great potential to make a real impact on the development of more robust and reliable AI systems, which is an essential task in today’s rapidly evolving technological landscape. Your approach to using the Theory of Mind framework to mitigate adversarial communication at test time is innovative and promising, and we look forward to seeing the results of further research and development in this area.

Abstract :

Decision trees are a convenient and established approach for any supervised learning task. Decision trees are used in a broad range of applications from medical imaging to computer vision. Decision trees are trained by greedily splitting the leaf nodes into a split and two leaf nodes until a certain stopping criterion is reached. The procedure of splitting a node consists of finding the best feature and threshold that minimizes a criterion. The criterion minimization problem is solved through an exhaustive search algorithm. However, this exhaustive search algorithm is very expensive, especially, if the number of samples and features are high. In this paper, we propose a novel stochastic approach for the criterion minimization. Asymptotically, the proposed algorithm is faster than conventional exhaustive search by several orders of magnitude. It is further shown that the proposed approach minimizes an upper bound for the criterion. Experimentally, the algorithm is compared with several other related state-of-the-art decision tree learning methods, including the baseline non-stochastic approach. The proposed algorithm outperforms every other decision tree learning (including online and fast) approaches and performs as well as the baseline algorithm in terms of accuracy and computational cost, despite being non-deterministic. For empirical evaluation, we apply the proposed algorithm to learn a Haar tree over MNIST dataset that consists of over 200,000 features and 60,000 samples. This tree achieved a test accuracy of 94% over MNIST which is 4% higher than any other known axis-aligned tree. This result is comparable to the performance of oblique trees, while providing a significant speed-up at both inference and training times.

One-sentence Summary: We propose a novel fast decision tree induction algorithm, outperforming the state-of-the-art by several orders of magnitude.

Author(s):

Alizadeh, Azar and Tavallali, Pooya and Behzadan, Vahid and Singhal, Mukesh