One of the central concerns of learning is to understand and to
\nprevent overfitting. Various notion of “function complexity” often
\narise: VC dimension, Rademacher complexity, comparison classes of
\nexperts, and program length are just a few.<\/p>\n
The term “complexity” to me seems somehow misleading; the terms never
\ncapture something that meets my intuitive notion of complexity. The
\nBayesian notion clearly captures what’s going on. Functions aren’t
\n“complex”– they’re just “surprising”: we assign to them low
\nprobability. Most (all?) complexity notions I know boil down
\nto some (generally loose) bound on the prior probability of the function.<\/p>\n
In a sense, “complexity” fundementally arises because probability
\ndistributions must sum to one. You can’t believe in all possibilities
\nat the same time, or at least not equally. Rather you have to
\ncarefully spread the probability mass over the options you’d like to
\nconsider. Large complexity classes means that beliefs are spread
\nthinly. In it’s simplest form, this phenomenom give the log (1\\n) for
\nn hypotheses in classic PAC bounds. <\/p>\n
In fact, one way to think about good learning algorithms is that they
\nare those which take full advantage of their probability mass.
\nIn the language of Minimum Description Length, they correspond to
\n“non-defective distributions”. <\/p>\n
So this raises a question: are there notions of complexity (preferably finite,
\ncomputable ones) that differ fundementally from the notions of “prior”
\nor “surprisingness”? Game-theoretic setups would seem to be promising,
\nalthough much of the work I’m familiar with ties it closely to the notion
\nof prior as well.<\/p>\n","protected":false},"excerpt":{"rendered":"
One of the central concerns of learning is to understand and to prevent overfitting. Various notion of “function complexity” often arise: VC dimension, Rademacher complexity, comparison classes of experts, and program length are just a few. The term “complexity” to me seems somehow misleading; the terms never capture something that meets my intuitive notion of … <\/p>\n