Safe RuleFit: Learning Optimal Sparse Rule Model by Meta Safe Screening

• URL: http://arxiv.org/abs/1810.01683v2
• Date: Wed, 12 Mar 2025 05:59:48 GMT
• Title: Safe RuleFit: Learning Optimal Sparse Rule Model by Meta Safe Screening
• Authors: Hiroki Kato, Hiroyuki Hanada, Ichiro Takeuchi,
• Abstract summary: We consider the problem of learning a sparse rule model, a prediction model in the form of a sparse linear combination of rules.<n>Since the number of all possible such rules is extremely large, it has been computationally intractable to select the optimal set of active rules.<n>We propose Safe RuleFit (SRF), which is a non-trivial extension of well-known safe screening techniques.
• Score: 19.524479577246336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning a sparse rule model, a prediction model in the form of a sparse linear combination of rules, where a rule is an indicator function defined over a hyper-rectangle in the input space. Since the number of all possible such rules is extremely large, it has been computationally intractable to select the optimal set of active rules. In this paper, to solve this difficulty for learning the optimal sparse rule model, we propose Safe RuleFit (SRF). Our basic idea is to develop meta safe screening (mSS), which is a non-trivial extension of well-known safe screening (SS) techniques. While SS is used for screening out one feature, mSS can be used for screening out multiple features by exploiting the inclusion-relations of hyper-rectangles in the input space. SRF provides a general framework for fitting sparse rule models for regression and classification, and it can be extended to handle more general sparse regularizations such as group regularization. We demonstrate the advantages of SRF through intensive numerical experiments.

Related papers

• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Dynamic selection of p-norm in linear adaptive filtering via online kernel-based reinforcement learning [8.319127681936815]
  This study addresses the problem of selecting dynamically, at each time instance, the optimal'' p-norm to combat outliers in linear adaptive filtering. Online and data-driven framework is designed via kernel-based reinforcement learning (KBRL)
  arXiv  Detail & Related papers  (2022-10-20T14:49:39Z)
• Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
  We propose a new distributed dynamic safe screening (DDSS) method for sparsity regularized models and apply it on shared-memory and distributed-memory architecture respectively. We prove that the proposed method achieves the linear convergence rate with lower overall complexity and can eliminate almost all the inactive features in a finite number of iterations almost surely.
  arXiv  Detail & Related papers  (2022-04-23T02:45:55Z)
• Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
  We propose a non-additive and deterministic smoothing method, Deterministic Smoothing with Splitting Noise (DSSN) In contrast to uniform additive smoothing, the SSN certification does not require the random noise components used to be independent. This is the first work to provide deterministic "randomized smoothing" for a norm-based adversarial threat model.
  arXiv  Detail & Related papers  (2021-03-17T21:49:53Z)
• Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares [21.42115891216612]
  We propose a flexible framework for safe screening based on the Fenchel-Rockafellar duality. We show that our screening rule can eliminate more features and increase the speed of the solver.
  arXiv  Detail & Related papers  (2021-02-08T10:25:40Z)
• Better Short than Greedy: Interpretable Models through Optimal Rule Boosting [10.938624307941197]
  Rule ensembles are designed to provide a useful trade-off between predictive accuracy and model interpretability. We present a novel approach aiming to fit rule ensembles of maximal predictive power for a given ensemble size.
  arXiv  Detail & Related papers  (2021-01-21T01:03:48Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning. Proximal gradient methods are used as standard approaches to solve OWL regression. We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
  arXiv  Detail & Related papers  (2020-06-29T23:35:53Z)
• The Strong Screening Rule for SLOPE [5.156484100374058]
  We develop a screening rule for SLOPE by examining its subdifferential and show that this rule is a generalization of the strong rule for the lasso. Our numerical experiments show that the rule performs well in practice, leading to improvements by orders of magnitude for data in the $p gg n$ domain.
  arXiv  Detail & Related papers  (2020-05-07T20:14:20Z)
• Safe Screening Rules for $\ell_0$-Regression [3.04585143845864]
  The screening rules can be computed from a convex relaxation solution in linear time. Experiments on real and synthetic data indicate that, on average, 76% of the variables can be fixed to their optimal values.
  arXiv  Detail & Related papers  (2020-04-19T06:07:09Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)

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.