Lower bounds on generalization errors for drifting rules

The problem of generalization by single-layer perceptrons is studied in the case of time-dependent rules. Lower bounds for the generalization errors within the 'single presentation of examples' case are obtained for randomly drifting rules. These bounds suggest a learning algorithm which uses knowledge of the error itself. Since this error is not readily available it has to be estimated through a mechanism of self-evaluation. The capacity of incorporating recency information into the error estimate is highly desirable. The mechanism proposed has the advantage, beyond good performance, of being self-adaptive, in the sense that it adjusts to changes in the unknown drift rate of the rule. The performance of the rule is also studied for sudden changes in an attempt to mimic the so-called Wisconsin test.