---
title: "Efficient Pruning Methods for Separate-and-Conquer Rule Learning Systems"
authors:
  - "William W. Cohen"
doi: ""
url: "https://ijcai.org/proceedings/1993/136"
pdf: "https://ijcai.org/proceedings/1993/0136.pdf"
venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence"
year: 1993
pages: "988-993"
track: "Machine Learning"
keywords:
---

# Efficient Pruning Methods for Separate-and-Conquer Rule Learning Systems

William W. Cohen

*Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 988-993.

## Abstract

Recent years have seen increased interest in systems that learn sets of rules. The goal of this paper is to study the degree to which "separate and conquer" rule learning induction methods scale up to large, real-world learning problems. In particular, we study the asymptotic complexity of rule induction on large training sets in the presence of noise. We present formal arguments and experimental data supporting the claim that existing methods do not scale up well on noisy data . We then present a solution in the form of new pruning techniques that dramatically improve the runtime of rule induction methods with no loss in accuracy: formal analysis shows an improvement in asymptotic time complexity, and experiments show an order-of-magnitude speedup on a set of benchmark problems while obtaining slightly more accurate hypotheses.