Efficient Incremental Induction of Decision Lists. Can Incremental Learning Outperform Non-Incremental Learning?
Abstract
Although incremental learning has many advantages in theory, it is not in practice as widely used as non-incremental learning for real-world applications. One major reason for this situation is the lack of incremental algorithms that can perform as fast as non-incremental algorithms in general. In this paper, we present an effective yet very efficient incremental algorithm CDM for learning decision lists whose complexity is O(dn(2)), where d is the number of attributes and n the number of training instances. On the experiments we have conducted, CDLA's performance is as fast and accurate as the best non-incremental learning algorithms for batch tasks, and is much faster than the best-known incremental and non-incremental learning algorithms for serial tasks. We also show that efficient incremental algorithms can provide new research opportunities for learners to actively select training instances for better accuracy and higher speed, and that incremental learning may eventually outperform non-incremental learning in many aspects.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1996
- Accession Number
- ADA308441
Entities
People
- Wei-min Shen
Organizations
- University of Southern California