TOLERATING CONCEPT AND SAMPLING SHIFT IN LAZY LEARNING USING PREDICTION ERROR CONTEXT SWITCHING

In their unmodified form, lazy-learning algorithms may have difficulty learning and tracking time-varying input/output function maps such as those that occur in concept shift. Extensions of these algorithms, su ch as Time-Windowed forgetting (TWF), can permit learning of time-vary ing mappings by deleting older exemplars, but have decreased classific ation accuracy when the input-space sampling distribution of the learn ing set is time-varying. Additionally, TWF suffers from lower asymptot ic classification accuracy than equivalent non-forgetting algorithms w hen the input sampling distributions are stationary. Other shift-sensi tive algorithms, such as Locally-Weighted forgetting (LWF), avoid the negative effects of time-varying sampling distributions, but still hav e lower asymptotic classification in non-varying cases. We introduce P rediction Error Context Switching (PEGS), which allows lazy-learning a lgorithms to have good classification accuracy in conditions having a time-varying function mapping and input sampling distributions, while still maintaining their asymptotic classification accuracy in static t asks. PECS works by selecting and re-activating previously stored inst ances based on their most recent consistency record. The classificatio n accuracy and active learning set sizes for the above algorithms are compared in a set of learning tasks that illustrate the differing time varying conditions described above. The results show that the PEGS al gorithm has the best overall classification accuracy over these differ ing time-varying conditions, while still having asymptotic classificat ion accuracy competitive with unmodified lazy-learners intended for st atic environments.