No subject

predictable are those carrying most information [haussler-91].

Suppose that the learning machine was trained on a sequence of examples x1,
x2, ... xn and is presented pattern xn+1. If pattern xn+1 is easily predicted
(i.e. its error is small) the benefit from learning that pattern is going to be
small: the hypothesis space is not going to shrink much. Conversely, if
xn+1 is hard to predict, learning it will result in a large shrinking
of hypothesis space.

Minimax algorithms which minimize the maximum error instead of the average
error rely on this principal. The solution of minimax algorithms depend only
on a number of informative patterns that are those patterns having maximum
error (and that other people would call outlyers) [boser-92].

What happens when the data is not perfectly clean? Then, outlyers can be either
very informative, if they correspond to atypical patterns, or very
non-informative, if they correspond to garbage patterns. With algorithms that
detect the outlyers (e.g. minimax algorithms) one can clean the data either
automatically or by hand by removing a subset of the outlyers. The VC-theory
predicts the point of optimal cleaning [matic-92].

Isabelle Guyon

---------------------------------

@inproceedings{haussler-91,
author =  "Haussler, D. and Kearns, M. and Shapire, R.",
title  =  "Bounds on the Sample Complexity of Bayesian Learning Using
Information Theory and the {VC} Dimension",
booktitle = "Computational Learning Theory workshop",
organization = "ACM",
year  = "1991",
}

@inproceedings{boser-92,
author =  "Boser, B. and Guyon, I. and Vapnik, V.",
title  =  "An Training Algorithm for Optimal Margin Classifiers",
year  = "1992",
booktitle = "Fifth Annual Workshop on Computational Learning Theory",
address =       "Pittsburgh",
publisher = "ACM",
month = "July",
pages = "144-152"
}

@inproceedings{matic-92,
author  =       "Mati\'{c}, N. and Guyon, I. and Bottou, L. and Denker, J. and
                Vapnik, V.",
title   =       "Computer Aided Cleaning of Large Databases for Character Recognition",
organization = "IAPR/IEEE",
address = 	"Amsterdam",
month = 	"August",
year = 		1992,
booktitle =     "11th International Conference on Pattern Recognition",
volume  =       "II",
pages   =       "330-333",
}