Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Predictive Learning Models for Concept Drift
| |
|
Predictive Learning Models for Concept Drift
John Case5 , Sanjay Jain6 , Susanne Kaufmann7 , Arun Sharma8 and Frank Stephan9 
| (5) |
Department of Computer and Information Sciences, University of Delaware, 101A Smith Hall, Newark, DE 19716-2586, USA |
| (6) |
Department of Information Systems and Computer Science, National University of Singapore, Singapore, 119260, Republic of Singapore |
| (7) |
Institut für Logik, KomplexitÄt und Deduktionssysteme, UniversitÄt Karlsruhe, 76128 Karlsruhe, Germany, EU |
| (8) |
School of Computer Science and Engineering, University of New South Wales, Sydney, NSW, 2052, Australia |
| (9) |
Mathematisches Institut, UniversitÄt Heidelberg, Im Neuenheimer Feld 294, 69120 Heidelberg, Germany, EU |
Abstract
Concept drift means that the concept about which data is obtained may shift from time to time, each time after some minimum permanence.
Except for this minimum permanence, the concept shifts may not have to satisfy any further requirements and may occur infinitely
often. Within this work is studied to what extent it is still possible to predict or learn values for a data sequence produced
by drifting concepts. Various ways to measure the quality of such predictions, including martingale betting strategies and
density and frequency of correctness, are introduced and compared with one another. For each of these measures of prediction
quality, for some interesting concrete classes, usefully established are (nearly) optimal bounds on permanence for attaining
learnability. The concrete classes, from which the drifting concepts are selected, include regular languages accepted by finite
automata of bounded size, polynomials of bounded degree, and exponentially growing sequences defined by recurrence relations
of bounded size. Some important, restricted cases of drifts are also studied, e.g., the case where the intervals of permanence
are computable. In the case where the concepts shift only among finitely many possibilities from certain infinite, arguably
practical classes, the learning algorithms can be considerably improved.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|