Empirische Inferenz Conference Paper 2013

Falsification and future performance

We information-theoretically reformulate two measures of capacity from statistical learning theory: empirical VC-entropy and empirical Rademacher complexity. We show these capacity measures count the number of hypotheses about a dataset that a learning algorithm falsifies when it finds the classifier in its repertoire minimizing empirical risk. It then follows from that the future performance of predictors on unseen data is controlled in part by how many hypotheses the learner falsifies. As a corollary we show that empirical VC-entropy quantifies the message length of the true hypothesis in the optimal code of a particular probability distribution, the so-called actual repertoire.

Author(s): Balduzzi, D.
Book Title: Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence
Volume: 7070
Pages: 65--78
Year: 2013
Month: January
Day: 0
Series: Lecture Notes in Computer Science
Publisher: Springer
Bibtex Type: Conference Paper (inproceedings)
Address: Berlin, Germany
DOI: 10.1007/978-3-642-44958-1_5
Event Name: Solomonoff 85th Memorial Conference
Event Place: Melbourne, Australia
State: Published
Electronic Archiving: grant_archive
Links:

BibTex

@inproceedings{Balduzzi2011_3,
  title = {Falsification and future performance},
  booktitle = {Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence},
  abstract = {We information-theoretically reformulate two measures of
  capacity from statistical learning theory: empirical VC-entropy and empirical Rademacher complexity. We show these capacity measures count the number of hypotheses about a dataset that a learning algorithm falsifies when it finds the classifier in its repertoire minimizing empirical
  risk. It then follows from that the future performance of predictors on unseen data is controlled in part by how many hypotheses the learner falsifies. As a corollary we show that empirical VC-entropy quantifies the message length of the true hypothesis in the optimal code of a particular
  probability distribution, the so-called actual repertoire.},
  volume = {7070},
  pages = {65--78},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer},
  address = {Berlin, Germany},
  month = jan,
  year = {2013},
  slug = {balduzzi2011_3},
  author = {Balduzzi, D.},
  month_numeric = {1}
}