Incremental Learning from Positive Data

AbstractThe present paper deals with a systematic study of incremental learning algorithms. The general scenario is as follows. Letcbe any concept; then every infinite sequence of elements exhaustingcis calledpositive presentationofc. An algorithmic learner successively takes as input one element of a positive presentation as well as its previously made hypothesis at a time and outputs a new hypothesis about the target concept. The sequence of hypotheses has to converge to a hypothesis correctly describing the concept to be learned. This basic scenario is referred to asiterative learning. Iterative inference can be refined by allowing the learner to store ana prioribounded number of carefully chosen examples resulting inbounded example memory inference. Additionally,feed-backidentification is introduced. Now, the learner is enabled to ask whether or not a particular element did already appear in the data provided so far. Our results are threefold: First, the learning capabilities of the various models of incremental learning are related to previously studied learning models. It is proved that incremental learning can be always simulated by inference devices that are both set-driven and conservative. Second, feed-back learning is shown to be more powerful than iterative inference, and its learning power is incomparable to that of bounded example memory inference which itself extends that of iterative learning, too. In particular, the learning power of bounded example memory inference always increases if the number of examples the learner is allowed to store is incremented. Third, a sufficient condition for iterative inference allowingnon-enumerativelearning is provided. The results obtained provide strong evidence that there is no unique way to design superior incremental learning algorithms. Instead, incremental learning is the art of knowing what to overlook