Accession Number : ADA308441

Title :   Efficient Incremental Induction of Decision Lists. Can Incremental Learning Outperform Non-Incremental Learning?

Descriptive Note : Research rept.,

Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST

Personal Author(s) : Shen, Wei-Min

PDF Url : ADA308441

Report Date : JAN 1996

Pagination or Media Count : 19

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.

Descriptors :   *DECISION MAKING, *LEARNING, VELOCITY, ALGORITHMS, TRAINING, ACCURACY, EFFICIENCY, INDUCTION SYSTEMS.

Subject Categories : Psychology

Distribution Statement : APPROVED FOR PUBLIC RELEASE