Does snooping help?

V. V. V'yugin

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

One of the most efficient way of improving the performance of learning algorithms is "snooping", i.e. using some information about the data to be predicted for choosing the parameters of the learning algorithm or the learning algorithm itself. Allowing different degrees of snooping α makes it possible to attain a better performance LossP(x) of a prediction strategy P on the given data set x. We study the "snooping curves" Lx(α)=infK(P)≤αLossP(x), where K(P) is the Kolmogorov complexity of the prediction strategy P. We prove that every non-increasing function can be approximated with arbitrary precision by some snooping function Lx. Our framework is that of on-line prediction; for simplicity we assume that sequences x are binary.

Original languageEnglish
Pages (from-to)407-415
Number of pages9
JournalTheoretical Computer Science
Volume276
Issue number1-2
DOIs
Publication statusPublished - 6 Apr 2002
Externally publishedYes

Keywords

  • Computer learning
  • Computer prediction
  • Kolmogorov complexity
  • Snooping

Fingerprint

Dive into the research topics of 'Does snooping help?'. Together they form a unique fingerprint.

Cite this