Susanne Kaufmann

TCS Journal 2001 Journal Article

Predictive learning models for concept drift

• John Case
• Sanjay Jain
• Susanne Kaufmann
• Arun Sharma
• Frank Stephan

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, (nearly) optimal bounds on permanence for attaining learnability are established. 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 sequences defined by recurrence relations of bounded size. Some important, restricted cases of drifts are also studied, for example, 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.

TCS Journal 2001 Journal Article

Robust learning with infinite additional information

• Susanne Kaufmann
• Frank Stephan

The present work investigates Gold-style algorithmic learning from input–output examples where the learner has access to oracles as additional information. This access is required to be robust in the sense that a single learning algorithm has to succeed with every oracle which meets a given specification. The first main result considers oracles of the same Turing degree: Robust learning with any oracle from a given degree does not achieve more than learning without any additional information. The further work considers learning from function oracles which describe the whole class of functions to be learned in one of the following five ways: as a list of all functions in this class, a predictor for this class, a one-sided classifier accepting just the functions in this class, an identifier for the class or a martingale succeeding on this class. It is shown that for learning in the limit (Ex), lists are the most powerful additional information, the powers of predictors and classifiers are incomparable and identifiers and martingales are of no help at all. Similar results are obtained for the criteria of predicting the next value, finite, Popperian and finite Popperian learning. Lists are omniscient for the criterion of predicting the next value and also identifiers are helpful at this criterion. So it turns out that algorithms to predict the next value can much better exploit robustly oracles than algorithms which give explanations (Ex-learning). For Ex-learning none of these five types of help is omniscient, that is, some classes cannot be Ex-learned with any of these types of additional information. The class REC of all recursive functions is Ex-learnable with the help of a list, a predictor or a classifier.

MFCS Conference 1995 Conference Paper

On a Quantitative Notion of Uniformity

• Susanne Kaufmann
• Martin Kummer