LOWER BOUNDS ON GENERALIZATION ERRORS FOR DRIFTING RULES

The problem of generalization by single-layer perceptrons is studied i n the case of time-dependent rules. Lower bounds for the generalizatio n errors within the 'single presentation of examples' case are obtaine d for randomly drifting rules. These bounds suggest a learning algorit hm which uses knowledge of the error itself. Since this error is not r eadily available it has to be estimated through a mechanism of self-ev aluation. The capacity of incorporating recency information into the e rror estimate is highly desirable. The mechanism proposed has the adva ntage, beyond good performance, of being self-adaptive, in the sense t hat it adjusts to changes in the unknown drift rate of the rule. The p erformance of the rule is also studied for sudden changes in an attemp t to mimic the so-called Wisconsin test.