Algorithmic Luckiness. Herbrich, R. & Williamson, R. C In Advances in Neural Information Processing Systems 14, pages 391--397, Vancouver, 2001.
Algorithmic Luckiness [pdf]Paper  abstract   bibtex   
In contrast to standard statistical learning theory which studies uniform bounds on the expected error we present a framework that exploits the specific learning algorithm used. Motivated by the luckiness framework [Taylor et al., 1998] we are also able to exploit the serendipity of the training sample. The main difference to previous approaches lies in the complexity measure; rather than covering all hypotheses in a given hypothesis space it is only necessary to cover the functions which could have been learned using the fixed learning algorithm. We show how the resulting framework relates to the VC, luckiness and compression frameworks. Finally, we present an application of this framework to the maximum margin algorithm for linear classifiers which results in a bound that exploits both the margin and the distribution of the data in feature space.
@inproceedings{DBLP:conf/nips/HerbrichW01,
abstract = {In contrast to standard statistical learning theory which studies uniform bounds on the expected error we present a framework that exploits the specific learning algorithm used. Motivated by the luckiness framework [Taylor et al., 1998] we are also able to exploit the serendipity of the training sample. The main difference to previous approaches lies in the complexity measure; rather than covering all hypotheses in a given hypothesis space it is only necessary to cover the functions which could have been learned using the fixed learning algorithm. We show how the resulting framework relates to the VC, luckiness and compression frameworks. Finally, we present an application of this framework to the maximum margin algorithm for linear classifiers which results in a bound that exploits both the margin and the distribution of the data in feature space.},
address = {Vancouver},
author = {Herbrich, Ralf and Williamson, Robert C},
booktitle = {Advances in Neural Information Processing Systems 14},
file = {:Users/rherb/Code/herbrich.me/papers/nips01\_algoluck.pdf:pdf},
pages = {391--397},
title = {{Algorithmic Luckiness}},
url = {http://www.herbrich.me/papers/nips01\_algoluck.pdf},
year = {2001}
}
Downloads: 0