A Novel Splitting Criterion Inspired by Geometric Mean Metric Learning for Decision Tree

• URL: http://arxiv.org/abs/2204.11011v1
• Date: Sat, 23 Apr 2022 07:33:57 GMT
• Title: A Novel Splitting Criterion Inspired by Geometric Mean Metric Learning for Decision Tree
• Authors: Dan Li, Songcan Chen
• Abstract summary: Decision tree (DT) attracts persistent research attention due to its impressive empirical performance and interpretability in numerous applications. In this paper, we newly design a splitting criterion to speed up the growth. The criterion is induced from Geometric Mean Metric Learning (GMML) and then optimized under its diagonalized metric matrix constraint.
• Score: 27.253204680627952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decision tree (DT) attracts persistent research attention due to its impressive empirical performance and interpretability in numerous applications. However, the growth of traditional yet widely-used univariate decision trees (UDTs) is quite time-consuming as they need to traverse all the features to find the splitting value with the maximal reduction of the impurity at each internal node. In this paper, we newly design a splitting criterion to speed up the growth. The criterion is induced from Geometric Mean Metric Learning (GMML) and then optimized under its diagonalized metric matrix constraint, consequently, a closed-form rank of feature discriminant abilities can at once be obtained and the top 1 feature at each node used to grow an intent DT (called as dGMML-DT, where d is an abbreviation for diagonalization). We evaluated the performance of the proposed methods and their corresponding ensembles on benchmark datasets. The experiment shows that dGMML-DT achieves comparable or better classification results more efficiently than the UDTs with 10x average speedup. Furthermore, dGMML-DT can straightforwardly be extended to its multivariable counterpart (dGMML-MDT) without needing laborious operations.

Related papers

• Enhance Learning Efficiency of Oblique Decision Tree via Feature Concatenation [16.81813720905545]
  We propose an enhanced ODT method with Feature Concatenation (textttFC-ODT) textttFC-ODT enables in-model feature transformation to transmit the projections along the decision paths. Experiments show that textttFC-ODT can outperform the other state-of-the-art decision trees with a limited tree depth.
  arXiv  Detail & Related papers  (2025-02-01T15:49:18Z)
• RGMDT: Return-Gap-Minimizing Decision Tree Extraction in Non-Euclidean Metric Space [28.273737052758907]
  We introduce an upper bound on the return gap between the oracle expert policy and an optimal decision tree policy. This enables us to recast the DT extraction problem into a novel non-euclidean clustering problem over the local observation and action values space of each agent. We also propose the Return-Gap-Minimization Decision Tree (RGMDT) algorithm, which is a surprisingly simple design and is integrated with reinforcement learning.
  arXiv  Detail & Related papers  (2024-10-21T21:19:49Z)
• Towards Scalable Semantic Representation for Recommendation [65.06144407288127]
  Mixture-of-Codes is proposed to construct semantic IDs based on large language models (LLMs) Our method achieves superior discriminability and dimension robustness scalability, leading to the best scale-up performance in recommendations.
  arXiv  Detail & Related papers  (2024-10-12T15:10:56Z)
• Zeroth-Order Fine-Tuning of LLMs in Random Subspaces [66.27334633749734]
  As language models grow in size, memory demands for backpropagation increase. Zeroth-order (ZOZO) optimization methods offer a memory-efficient alternative. We show that SubZero enhances fine-tuning and achieves faster results compared to standard ZOZO approaches.
  arXiv  Detail & Related papers  (2024-10-11T17:01:43Z)
• Graph-Structured Speculative Decoding [52.94367724136063]
  Speculative decoding has emerged as a promising technique to accelerate the inference of Large Language Models. We introduce an innovative approach utilizing a directed acyclic graph (DAG) to manage the drafted hypotheses. We observe a remarkable speedup of 1.73$times$ to 1.96$times$, significantly surpassing standard speculative decoding.
  arXiv  Detail & Related papers  (2024-07-23T06:21:24Z)
• Estimating the Hessian Matrix of Ranking Objectives for Stochastic Learning to Rank with Gradient Boosted Trees [63.18324983384337]
  We introduce the first learning to rank method for Gradient Boosted Decision Trees (GBDTs) Our main contribution is a novel estimator for the second-order derivatives, i.e., the Hessian matrix. We incorporate our estimator into the existing PL-Rank framework, which was originally designed for first-order derivatives only.
  arXiv  Detail & Related papers  (2024-04-18T13:53:32Z)
• Coevolutionary Algorithm for Building Robust Decision Trees under Minimax Regret [12.72963164625931]
  This paper proposes a novel coevolutionary algorithm (CoEvoRDT) designed to create robust algorithms-decision trees (DTs) Motivated by the limitations of traditional DT algorithms, we leverage adaptive coevolution to allow DTs to evolve and learn from interactions with perturbed input data. CoEvoRDT is tested on 20 popular datasets and shows superior performance compared to 4 state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-12-14T16:12:22Z)
• GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent [10.27211960475599]
  Decision Trees (DTs) are commonly used for many machine learning tasks. In this paper, we propose a novel approach to learn DTs using a greedy algorithm. We propose backpropagation with a straight-through operator on a dense DT representation, to jointly optimize all tree parameters.
  arXiv  Detail & Related papers  (2023-05-05T13:24:35Z)
• Enhancing Robustness of Gradient-Boosted Decision Trees through One-Hot Encoding and Regularization [10.942447664917061]
  We apply one-hot encoding to convert a GBDT model into a linear framework, through encoding of each tree leaf to one dummy variable. This allows for the use of linear regression techniques, plus a novel risk decomposition for assessing the robustness of a GBDT model. It is demonstrated through numerical experiments that the proposed regularization approach can enhance the robustness of the one-hot-encoded GBDT models.
  arXiv  Detail & Related papers  (2023-04-26T18:04:16Z)
• Greedy based Value Representation for Optimal Coordination in Multi-agent Reinforcement Learning [64.05646120624287]
  We derive the expression of the joint Q value function of LVD and MVD. To ensure optimal consistency, the optimal node is required to be the unique STN. Our method outperforms state-of-the-art baselines in experiments on various benchmarks.
  arXiv  Detail & Related papers  (2022-11-22T08:14:50Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  Although model-agnostic metalearning (MAML) is a very successful algorithm meta-learning practice, it can have high computational complexity. Our paper shows that such complexity can significantly affect the overall convergence performance of ANIL.
  arXiv  Detail & Related papers  (2020-06-16T19:57:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.