An information criterion for automatic gradient tree boosting

• URL: http://arxiv.org/abs/2008.05926v1
• Date: Thu, 13 Aug 2020 14:24:27 GMT
• Title: An information criterion for automatic gradient tree boosting
• Abstract summary: An information theoretic approach to learning the complexity of classification and regression trees and the number of trees in gradient tree boosting is proposed. The optimism (test loss minus training loss) of the greedy leaf splitting procedure is shown to be the maximum of a Cox-Ingersoll-Ross process. Relative to xgboost, speedups on numerical experiments ranges from around 10 to about 1400, at similar predictive-power measured in terms of test-loss.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An information theoretic approach to learning the complexity of classification and regression trees and the number of trees in gradient tree boosting is proposed. The optimism (test loss minus training loss) of the greedy leaf splitting procedure is shown to be the maximum of a Cox-Ingersoll-Ross process, from which a generalization-error based information criterion is formed. The proposed procedure allows fast local model selection without cross validation based hyper parameter tuning, and hence efficient and automatic comparison among the large number of models performed during each boosting iteration. Relative to xgboost, speedups on numerical experiments ranges from around 10 to about 1400, at similar predictive-power measured in terms of test-loss.

Related papers

• LoBoost: Fast Model-Native Local Conformal Prediction for Gradient-Boosted Trees [3.4988194836573894]
  LoBoost is a model-native local conformal method that reuses the fitted ensemble's leaf structure to define multiscale calibration groups.<n>Experiments show competitive interval quality, improved test MSE on most datasets, and large calibration speedups.
  arXiv  Detail & Related papers  (2026-02-25T21:44:19Z)
• Sparse Additive Model Pruning for Order-Based Causal Structure Learning [4.55744151522751]
  Causal structure learning aims to estimate causal relationships between variables as a form of a causal directed acyclic graph (DAG) from observational data.<n>One of the major frameworks is the order-based approach that first estimates a topological order of the underlying DAG and then prunes spurious edges from the fully-connected DAG induced by the estimated topological order.<n>We introduce a new pruning method based on sparse additive models, which enables direct pruning of redundant edges without relying on hypothesis testing.
  arXiv  Detail & Related papers  (2026-02-17T02:06:42Z)
• Rethinking LLM Evaluation: Can We Evaluate LLMs with 200x Less Data? [82.09573568241724]
  EssenceBench is a coarse-to-fine framework utilizing an iterative Genetic Algorithm (GA)<n>Our approach yields superior compression results with lower reconstruction error and markedly higher efficiency.<n>On the HellaSwag benchmark (10K samples), our method preserves the ranking of all models shifting within 5% using 25x fewer samples, and achieves 95% ranking preservation shifting within 5% using only 200x fewer samples.
  arXiv  Detail & Related papers  (2025-10-12T05:38:10Z)
• Tree Boosting Methods for Balanced andImbalanced Classification and their Robustness Over Time in Risk Assessment [0.10925516251778125]
  Tree-based methods such as XGBoost, stand out in several benchmarks due to detection performance and speed. The developed method increases its recognition performance as more data is given for training. It is still significantly superior to the baseline of precision-recall determined by the ratio of positives divided by positives and negatives.
  arXiv  Detail & Related papers  (2025-04-25T07:35:38Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach. Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Soft regression trees: a model variant and a decomposition training algorithm [0.24578723416255752]
  We propose a new variant of soft multivariate regression trees (SRTs) where, for every input vector, the prediction is defined as a linear regression associated to a single leaf node. SRTs exhibit the conditional computational property, i.e., each prediction depends on a small number of nodes. Experiments on 15 wellknown datasets indicate that our SRTs and decomposition algorithm yield higher accuracy and robustness compared with traditional soft regression trees.
  arXiv  Detail & Related papers  (2025-01-10T13:06:36Z)
• Can a Single Tree Outperform an Entire Forest? [5.448070998907116]
  The prevailing mindset is that a single decision tree underperforms classic random forests in testing accuracy. This study challenges such a mindset by significantly improving the testing accuracy of an oblique regression tree. Our approach reformulates tree training as a differentiable unconstrained optimization task.
  arXiv  Detail & Related papers  (2024-11-26T00:18:18Z)
• Binary Classification: Is Boosting stronger than Bagging? [5.877778007271621]
  We introduce Enhanced Random Forests, an extension of vanilla Random Forests with extra functionalities and adaptive sample and model weighting. We develop an iterative algorithm for adapting the training sample weights, by favoring the hardest examples, and an approach for finding personalized tree weighting schemes for each new sample. Our method significantly improves upon regular Random Forests across 15 different binary classification datasets and considerably outperforms other tree methods, including XGBoost.
  arXiv  Detail & Related papers  (2024-10-24T23:22:33Z)
• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  We propose a Deep Tree-based Retriever (DTR) for efficient recommendation. DTR frames the training task as a softmax-based multi-class classification over tree nodes at the same level. To mitigate the suboptimality induced by the labeling of non-leaf nodes, we propose a rectification method for the loss function.
  arXiv  Detail & Related papers  (2024-08-21T05:09:53Z)
• An Adaptive Tensor-Train Decomposition Approach for Efficient Deep Neural Network Compression [4.869958813908807]
  We introduce a novel, automatic, and budget-aware rank selection method for efficient model compression.<n> Layer-Wise Imprinting Quantitation (LWIQ) quantifies each layer's significance within a neural network by integrating a proxy classifier.<n> Experimental results on the CIFAR-10 dataset show that our LWIQ improved by 63.2% in rank search efficiency.
  arXiv  Detail & Related papers  (2024-08-02T18:47:11Z)
• A Robust Hypothesis Test for Tree Ensemble Pruning [2.4923006485141284]
  We develop and present a novel theoretically justified hypothesis test of split quality for gradient boosted tree ensembles. We show that using this method instead of the common penalty terms leads to a significant reduction in out of sample loss. We also present several innovative extensions to the method, opening the door for a wide variety of novel tree pruning algorithms.
  arXiv  Detail & Related papers  (2023-01-24T16:31:49Z)
• A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks [65.34977803841007]
  Predictive coding networks are neuroscience-inspired models with roots in both Bayesian statistics and neuroscience. We show how by simply changing the temporal scheduling of the update rule for the synaptic weights leads to an algorithm that is much more efficient and stable than the original one.
  arXiv  Detail & Related papers  (2022-11-16T00:11:04Z)
• Optimal randomized classification trees [0.0]
  Classification and Regression Trees (CARTs) are off-the-shelf techniques in modern Statistics and Machine Learning. CARTs are built by means of a greedy procedure, sequentially deciding the splitting predictor variable(s) and the associated threshold. This greedy approach trains trees very fast, but, by its nature, their classification accuracy may not be competitive against other state-of-the-art procedures.
  arXiv  Detail & Related papers  (2021-10-19T11:41:12Z)
• A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds [9.546094657606178]
  We study the generalization performance of decision trees with respect to different generative regression models. This allows us to elicit their inductive bias, that is, the assumptions the algorithms make (or do not make) to generalize to new data. We prove a sharp squared error generalization lower bound for a large class of decision tree algorithms fitted to sparse additive models.
  arXiv  Detail & Related papers  (2021-10-18T21:22:40Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)
• Solving Long-tailed Recognition with Deep Realistic Taxonomic Classifier [68.38233199030908]
  Long-tail recognition tackles the natural non-uniformly distributed data in realworld scenarios. While moderns perform well on populated classes, its performance degrades significantly on tail classes. Deep-RTC is proposed as a new solution to the long-tail problem, combining realism with hierarchical predictions.
  arXiv  Detail & Related papers  (2020-07-20T05:57:42Z)
• Variable Skipping for Autoregressive Range Density Estimation [84.60428050170687]
  We show a technique, variable skipping, for accelerating range density estimation over deep autoregressive models. We show that variable skipping provides 10-100$times$ efficiency improvements when targeting challenging high-quantile error metrics.
  arXiv  Detail & Related papers  (2020-07-10T19:01:40Z)
• Fast, Accurate, and Simple Models for Tabular Data via Augmented Distillation [97.42894942391575]
  We propose FAST-DAD to distill arbitrarily complex ensemble predictors into individual models like boosted trees, random forests, and deep networks. Our individual distilled models are over 10x faster and more accurate than ensemble predictors produced by AutoML tools like H2O/AutoSklearn.
  arXiv  Detail & Related papers  (2020-06-25T09:57:47Z)

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.