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.
My Menu
Saved Items

Predictive Learning Models for Concept Drift

John CaseContact Information, Sanjay JainContact Information, Susanne KaufmannContact Information, Arun SharmaContact Information and Frank StephanContact Information

(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.

Contact Information John Case
Email: case@cis.udel.edu

Contact Information Sanjay Jain
Email: sanjay@iscs.nus.edu.sg

Contact Information Susanne Kaufmann
Email: kaufmann@ira.uka.de

Contact Information Arun Sharma
Email: arun@cse.unsw.edu.au

Contact Information Frank Stephan
Email: fstephan@math.uni-heidelberg.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb18
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)