Information, learning and falsification
  There are (at least) three approaches to quantifying information. The first,
algorithmic information or Kolmogorov complexity, takes events as strings and,
given a universal Turing machine, quantifies the information content of a
string as the length of the shortest program producing it. The second, Shannon
information, takes events as belonging to ensembles and quantifies the
information resulting from observing the given event in terms of the number of
alternate events that have been ruled out. The third, statistical learning
theory, has introduced measures of capacity that control (in part) the expected
risk of classifiers. These capacities quantify the expectations regarding
future data that learning algorithms embed into classifiers.
  This note describes a new method of quantifying information, effective
information, that links algorithmic information to Shannon information, and
also links both to capacities arising in statistical learning theory. After
introducing the measure, we show that it provides a non-universal analog of
Kolmogorov complexity. We then apply it to derive basic capacities in
statistical learning theory: empirical VC-entropy and empirical Rademacher
complexity. A nice byproduct of our approach is an interpretation of the
explanatory power of a learning algorithm in terms of the number of hypotheses
it falsifies, counted in two different ways for the two capacities. We also
discuss how effective information relates to information gain, Shannon and
mutual information.
