Sparse learning with CART

• URL: http://arxiv.org/abs/2006.04266v2
• Date: Wed, 18 Nov 2020 21:42:04 GMT
• Title: Sparse learning with CART
• Authors: Jason M. Klusowski
• Abstract summary: Decision trees with binary splits are popularly constructed using Classification and Regression Trees (CART) methodology. This paper aims to study the statistical properties of regression trees constructed with CART methodology.
• Score: 18.351254916713305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decision trees with binary splits are popularly constructed using Classification and Regression Trees (CART) methodology. For regression models, this approach recursively divides the data into two near-homogenous daughter nodes according to a split point that maximizes the reduction in sum of squares error (the impurity) along a particular variable. This paper aims to study the statistical properties of regression trees constructed with CART methodology. In doing so, we find that the training error is governed by the Pearson correlation between the optimal decision stump and response data in each node, which we bound by constructing a prior distribution on the split points and solving a nonlinear optimization problem. We leverage this connection between the training error and Pearson correlation to show that CART with cost-complexity pruning achieves an optimal complexity/goodness-of-fit tradeoff when the depth scales with the logarithm of the sample size. Data dependent quantities, which adapt to the dimensionality and latent structure of the regression model, are seen to govern the rates of convergence of the prediction error.

Related papers

• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  Policy evaluation via Monte Carlo simulation is at the core of many MC Reinforcement Learning (RL) algorithms. We propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths. We present an adaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO)
  arXiv  Detail & Related papers  (2024-10-17T11:47:56Z)
• Theoretical Insights into CycleGAN: Analyzing Approximation and Estimation Errors in Unpaired Data Generation [0.5735035463793009]
  We focus on analyzing the excess risk of the unpaired data generation model, called CycleGAN. Unlike classical GANs, CycleGAN not only transforms data between two unpaired distributions but also ensures the mappings are consistent. By considering the impact of both the model architecture and training procedure, the risk is decomposed into two terms: approximation error and estimation error.
  arXiv  Detail & Related papers  (2024-07-16T12:53:53Z)
• Statistical Advantages of Oblique Randomized Decision Trees and Forests [0.0]
  Generalization error and convergence rates are obtained for the flexible dimension reduction model class of ridge functions. A lower bound on the risk of axis-aligned Mondrian trees is obtained proving that these estimators are suboptimal for these linear dimension reduction models.
  arXiv  Detail & Related papers  (2024-07-02T17:35:22Z)
• 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)
• Piecewise linear regression and classification [0.20305676256390928]
  This paper proposes a method for solving multivariate regression and classification problems using piecewise linear predictors. A Python implementation of the algorithm described in this paper is available at http://cse.lab.imtlucca.it/bemporad/parc.
  arXiv  Detail & Related papers  (2021-03-10T17:07:57Z)
• Autoregressive Score Matching [113.4502004812927]
  We propose autoregressive conditional score models (AR-CSM) where we parameterize the joint distribution in terms of the derivatives of univariable log-conditionals (scores) For AR-CSM models, this divergence between data and model distributions can be computed and optimized efficiently, requiring no expensive sampling or adversarial training. We show with extensive experimental results that it can be applied to density estimation on synthetic data, image generation, image denoising, and training latent variable models with implicit encoders.
  arXiv  Detail & Related papers  (2020-10-24T07:01:24Z)
• Out-of-distribution Generalization via Partial Feature Decorrelation [72.96261704851683]
  We present a novel Partial Feature Decorrelation Learning (PFDL) algorithm, which jointly optimize a feature decomposition network and the target image classification model. The experiments on real-world datasets demonstrate that our method can improve the backbone model's accuracy on OOD image classification datasets.
  arXiv  Detail & Related papers  (2020-07-30T05:48:48Z)
• Model Fusion with Kullback--Leibler Divergence [58.20269014662046]
  We propose a method to fuse posterior distributions learned from heterogeneous datasets. Our algorithm relies on a mean field assumption for both the fused model and the individual dataset posteriors.
  arXiv  Detail & Related papers  (2020-07-13T03:27:45Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  We show that depending on the structure of the Hessian of the loss at the minimum, the SGD iterates will converge to a emphheavy-tailed stationary distribution. We translate our results into insights about the behavior of SGD in deep learning.
  arXiv  Detail & Related papers  (2020-06-08T16:43:56Z)
• Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
  We take one of the simplest inference methods, a truncated max-product Belief propagation, and add what is necessary to make it a proper component of a deep learning model. This BP-Layer can be used as the final or an intermediate block in convolutional neural networks (CNNs) The model is applicable to a range of dense prediction problems, is well-trainable and provides parameter-efficient and robust solutions in stereo, optical flow and semantic segmentation.
  arXiv  Detail & Related papers  (2020-03-13T13:11:35Z)
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation [77.7420231319632]
  We adapt contextual generation of categorical sequences to a policy gradient estimator, which evaluates a set of correlated Monte Carlo (MC) rollouts for variance control. We also demonstrate the use of correlated MC rollouts for binary-tree softmax models, which reduce the high generation cost in large vocabulary scenarios.
  arXiv  Detail & Related papers  (2019-12-31T03:01:55Z)

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.