Norbert Klasner, Hans Ulrich Simon:

From Noise-Free to Noise-Tolerant and from On-line to Batch Learning

A simple method is presented which, loosely speaking, virtually removes noise or misfit from data, and thereby converts a ``noise-free'' algorithm A, which on-line learns linear functions from data without noise or misfit, into a ``noise-tolerant'' algorithm A^{nt} which learns linear functions from data containing noise or misfit. Given some technical conditions, this conversion preserves optimality. For instance, the optimal noise-free algorithm B of Bernstein from [Ber92] is converted into an optimal noise-tolerant algorithm B^{nt}. The conversion also works properly for all function classes which are closed under addition and contain linear functions as a subclass.

In the second part of the paper, we show that Bernstein's on-line learning algorithm B can be converted into a batch learning algorithm ^B which consumes an (almost) minimal number of random training examples. This is true for a whole class of ``pac-style'' batch learning models (including learning with an $(\epsilon, \gamma)$-good model and learning with an $\epsilon$-bounded expected r-loss). The upper bound on the sample size is shown by applying a method of Littlestone from [Lit89] which converts an on-line learning algorithm A into a batch learning algorithm  and relates the sample size of  to the total loss of A. For this purpose, Littlestone's method is extended from 0,1-valued functions to real-valued functions. The lower bound on the sample size is shown by generalizing and applying a method of Simon from [Sim93b].

Last update: 11/17/98. Norbert Klasner, klasner@lmi.ruhr-uni-bochum.de.

Return to list of my publications.