Scalable Rule Lists Learning with Sampling

• URL: http://arxiv.org/abs/2406.12803v1
• Date: Tue, 18 Jun 2024 17:15:00 GMT
• Title: Scalable Rule Lists Learning with Sampling
• Authors: Leonardo Pellegrina, Fabio Vandin,
• Abstract summary: We present a novel approach to learn nearly optimal rule lists from large datasets. Our algorithm uses sampling to efficiently obtain an approximation of the optimal rule list. Our algorithm identifies nearly optimal rule lists with a speed-up up to two orders of magnitude over state-of-the-art exact approaches.
• Score: 9.681286056736292
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning interpretable models has become a major focus of machine learning research, given the increasing prominence of machine learning in socially important decision-making. Among interpretable models, rule lists are among the best-known and easily interpretable ones. However, finding optimal rule lists is computationally challenging, and current approaches are impractical for large datasets. We present a novel and scalable approach to learn nearly optimal rule lists from large datasets. Our algorithm uses sampling to efficiently obtain an approximation of the optimal rule list with rigorous guarantees on the quality of the approximation. In particular, our algorithm guarantees to find a rule list with accuracy very close to the optimal rule list when a rule list with high accuracy exists. Our algorithm builds on the VC-dimension of rule lists, for which we prove novel upper and lower bounds. Our experimental evaluation on large datasets shows that our algorithm identifies nearly optimal rule lists with a speed-up up to two orders of magnitude over state-of-the-art exact approaches. Moreover, our algorithm is as fast as, and sometimes faster than, recent heuristic approaches, while reporting higher quality rule lists. In addition, the rules reported by our algorithm are more similar to the rules in the optimal rule list than the rules from heuristic approaches.

Related papers

• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Efficient learning of large sets of locally optimal classification rules [0.0]
  Conventional rule learning algorithms aim at finding a set of simple rules, where each rule covers as many examples as possible. In this paper, we argue that the rules found in this way may not be the optimal explanations for each of the examples they cover. We propose an efficient algorithm that aims at finding the best rule covering each training example in a greedy optimization consisting of one specialization and one generalization loop.
  arXiv  Detail & Related papers  (2023-01-24T11:40:28Z)
• Bayes Point Rule Set Learning [5.065947993017157]
  Interpretability is having an increasingly important role in the design of machine learning algorithms. Disjunctive Normal Forms are arguably the most interpretable way to express a set of rules. We propose an effective bottom-up extension of the popular FIND-S algorithm to learn DNF-type rulesets.
  arXiv  Detail & Related papers  (2022-04-11T16:50:41Z)
• US-Rule: Discovering Utility-driven Sequential Rules [52.68017415747925]
  We propose a faster algorithm, called US-Rule, to efficiently mine high-utility sequential rules. Four tighter upper bounds (LEEU, REEU, LERSU, RERSU) and their corresponding pruning strategies are proposed. US-Rule can achieve better performance in terms of execution time, memory consumption and scalability.
  arXiv  Detail & Related papers  (2021-11-29T23:38:28Z)
• Interpretable and Fair Boolean Rule Sets via Column Generation [18.08486863429421]
  An integer program is formulated to optimally trade classification accuracy for rule simplicity. We consider the fairness setting and extend the formulation to include explicit constraints on two different measures of classification parity. Compared to other fair and interpretable classifiers, our method is able to find rule sets that meet stricter notions of fairness with a modest trade-off in accuracy.
  arXiv  Detail & Related papers  (2021-11-16T13:40:28Z)
• LPRules: Rule Induction in Knowledge Graphs Using Linear Programming [4.94950858749529]
  Rule-based methods learn first-order logic rules that capture existing facts in an input graph and then use these rules for reasoning about missing facts. A major drawback of such methods is the lack of scalability to large datasets. We present a simple linear programming (LP) model to choose rules from a list of candidate rules and assign weights to them.
  arXiv  Detail & Related papers  (2021-10-15T17:58:16Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• 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)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  We devise a simple algorithm whose sampling complexity matches known instance-specific lower bounds. Unlike existing best-arm identification strategies, our algorithm uses a stopping rule that does not depend on the number of arms.
  arXiv  Detail & Related papers  (2020-06-29T14:25:51Z)

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.