A simple, fast, and effective rule learner
Published 1 January 1999
William W. Cohen, Yoram Singer
Citations330
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We describe SLIPPER, a new rule learner that generates rulesets by repeatedly boosting a simple, greedy, rule-builder. Like the rulesets built by other rule learners, the ensemble of rules created by SLIPPER is compact and comprehensible. This is made possible by imposing appropriate constraints on the rule-builder, and by use of a recently-proposed generalization of Adaboost called confidence-rated boosting. In spite of its relative simplicity, SLIPPER is highly scalable, and an effective learner. Experimentally, SLIPPER scales no worse than O(n log n), where n is the number of examples, and on a set of 32 benchmark problems, SLIPPER achieves lower error rates than RIPPER 20 times, and lower error rates than C4.5rules 22 times. Introduction Boosting (Schapire 1990
Keywords
Computer Science
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
Experiments with a new boosting algorithm
7,585 Citations1996Yoav Freund, Robert E. Schapire
Elsevier eBooksFast Effective Rule Induction
3,767 Citations1995William W. Cohen
This paper evaluates the recently-proposed rule learning algorithm IREP on a large and diverse collection of benchmark problems, and proposes a number of modifications resulting in an algorithm RIPPERk that is very competitive with C4.5 and C 4.5rules with respect to error rates, but much more efficient on large samples.
Machine LearningThe Strength of Weak Learnability
3,293 Citations1990Robert E. Schapire
In this paper, a method is described for converting a weak learning algorithm into one that achieves arbitrarily high accuracy, and it is shown that these two notions of learnability are equivalent.
Improved boosting algorithms using confidence-rated predictions
2,568 Citations1998Robert E. Schapire, Yoram Singer
Machine LearningThe CN2 Induction Algorithm
2,015 Citations1989Peter Clark, Tim Niblett
A description and empirical evaluation of a new induction system, CN2, designed for the efficient induction of simple, comprehensible production rules in domains where problems of poor description language and/or noise may be present.
Information and ComputationBoosting a Weak Learning Algorithm by Majority
1,686 Citations1995Yoav Freund
An algorithm for improving the accuracy of algorithms for learning binary concepts by combining a large number of hypotheses, each of which is generated by training the given learning algorithm on a different set of examples, is presented.
Machine LearningLearning Logical Definitions from Relations
1,425 Citations1990J. R. Quinlan
FOIL is a system that learns Horn clauses from data expressed as relations, but extends them to a first-order formalism, which has been applied successfully to several tasks taken from the machine learning literature.
Research Commons (The University of Waikato)Generating Accurate Rule Sets Without Global Optimization
1,284 Citations1998Eibe Frank, Ian H. Witten
This paper presents an algorithm for inferring rules by repeatedly generating partial decision trees, thus combining the two major paradigms for rule generation—creating rules from decision trees and the separate-and-conquer rule-learning technique.
Journal of the ACMCryptographic limitations on learning Boolean formulae and finite automata
744 Citations1994Michael Kearns, Leslie G. Valiant
It is proved that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata or constant-depth threshold circuits would have dramatic consequences for cryptography and number theory and is applied to obtain strong intractability results for approximating a generalization of graph coloring.
QUT ePrints (Queensland University of Technology)Boosting the margin: A new explanation for the effectiveness of voting methods
578 Citations1997Robert E. Schapire, Yoav Freund +2 more
Pruning Adaptive Boosting
512 Citations1997Dragos D. Margineantu, Thomas G. Dietterich
Machine LearningBoolean Feature Discovery in Empirical Learning
398 Citations1990Giulia Pagallo, David Haussler
Two new methods that adaptively introduce relevant features while learning a decision tree from examples are presented, showing empirically that these methods outperform a standard decision tree algorithm for learning small random DNF functions when the examples are drawn at random from the uniform distribution.
Elsevier eBooksIncremental Reduced Error Pruning
363 Citations1994Johannes Fürnkranz, Gerhard Widmer
Experiments show that in many noisy domains this method is much more efficient than alternative algorithms, along with a slight gain in accuracy, however, the experiments show that the use of the algorithm cannot be recommended for domains which require a very specific concept description.
Machine LearningUnifying Instance-Based and Rule-Based Induction
218 Citations1996Pedro Domingos
In an extensive empirical study, RISE consistently achieves higher accuracies than state-of-the-art representatives of both its parent approaches, as well as a decision tree learner (C4.5).
eScholarship (California Digital Library)HYDRA: A Noise-tolerant Relational Concept Learning Algorithm.
55 Citations1993Kamal Ali, Michael J. Pazzani
This paper presents a method using likelihood ratios attached to clauses to classify test examples, and demonstrates that attaching weights and allowing concept descriptions to compete to classify examples reduces an algorithm's susceptibility to noise.
A Redundant Covering Algorithm Applied to Text Classification
5 Citations1998David Hsu, Oren Etzioni +1 more
A basic covering algorithm is presented, DAIRY, that learns unordered rule sets, and two extensions are presented that encourage the rule learner to milk the training data to varying degrees, by recycling covered training data, and by searching for completely redundant but highly accurate rules.