Journal of Artificial Intelligence Research 8 (1998), pp. 129-164. Submitted 11/97; published 5/98
© 1998 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.
Postscript and PDF versions of this document are available from here.

Integrative Windowing

Johannes Fürnkranz
Carnegie Mellon University
School of Computer Science
Pittsburgh, PA 15213
E-mail: juffi@cs.cmu.edu

Abstract:

In this paper we re-investigate windowing for rule learning algorithms. We show that, contrary to previous results for decision tree learning, windowing can in fact achieve significant run-time gains in noise-free domains and explain the different behavior of rule learning algorithms by the fact that they learn each rule independently. The main contribution of this paper is integrative windowing, a new type of algorithm that further exploits this property by integrating good rules into the final theory right after they have been discovered. Thus it avoids re-learning these rules in subsequent iterations of the windowing process. Experimental evidence in a variety of noise-free domains shows that integrative windowing can in fact achieve substantial run-time gains. Furthermore, we discuss the problem of noise in windowing and present an algorithm that is able to achieve run-time gains in a set of experiments in a simple domain with artificial noise.

 

• Introduction
• A Brief History of Windowing
• A Closer Look at Windowing
  • A Motivating Example
  • Windowing versus Random Sub-sampling
  • Rule Learning versus Decision Tree Learning
  • Domain Redundancy
• Integrative Windowing
  • The Algorithm
  • Implementation
  • Experimental Setup
  • Domains
  • Results
  • A Note on Parameter Settings
• Windowing and Noise
  • Noise is a Problem
  • Towards Noise-Tolerant Windowing
    • Consistency-Check
    • Completeness-Check
    • Resampling
  • The Algorithm
  • Experimental Evaluation
• Related Work
  • Sub-Sampling Techniques
  • Active Learning
  • Complexity Reduction
• Future Work
• Conclusion
• Acknowledgements
• References

• About this document ...