Skip to main content
Cross Validated

Return to Question

replaced http://stats.stackexchange.com/ with https://stats.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

While trying to make sense of MDL and stochastic complexity, I found this previous question: Measures of model complexityMeasures of model complexity, in which Yaroslav Bulatov defines model complexity as "how hard it is to learn from limited data."

It is not clear to me how Minimal Description Length (MDL) measures this. What I am looking for is some sort of probability inequality (analagous to the VC upper bound) which relates the "code length" of a model with its worst case behavior on fitting data generated by itself. If such a concrete result cannot be found in the literature, even an empirical example would be enlightening.

While trying to make sense of MDL and stochastic complexity, I found this previous question: Measures of model complexity, in which Yaroslav Bulatov defines model complexity as "how hard it is to learn from limited data."

It is not clear to me how Minimal Description Length (MDL) measures this. What I am looking for is some sort of probability inequality (analagous to the VC upper bound) which relates the "code length" of a model with its worst case behavior on fitting data generated by itself. If such a concrete result cannot be found in the literature, even an empirical example would be enlightening.

While trying to make sense of MDL and stochastic complexity, I found this previous question: Measures of model complexity, in which Yaroslav Bulatov defines model complexity as "how hard it is to learn from limited data."

It is not clear to me how Minimal Description Length (MDL) measures this. What I am looking for is some sort of probability inequality (analagous to the VC upper bound) which relates the "code length" of a model with its worst case behavior on fitting data generated by itself. If such a concrete result cannot be found in the literature, even an empirical example would be enlightening.

added mdl tag
Link
edit approved Mar 16, 2011 at 20:23
bayerj
edit approved Mar 16, 2011 at 20:23
bayerj
  • 14k
  • 3
  • 40
  • 61
Source Link
charles.y.zheng
charles.y.zheng
  • 8k
  • 2
  • 32
  • 35

Relationship between MDL and "difficulty of learning from data"

While trying to make sense of MDL and stochastic complexity, I found this previous question: Measures of model complexity, in which Yaroslav Bulatov defines model complexity as "how hard it is to learn from limited data."

It is not clear to me how Minimal Description Length (MDL) measures this. What I am looking for is some sort of probability inequality (analagous to the VC upper bound) which relates the "code length" of a model with its worst case behavior on fitting data generated by itself. If such a concrete result cannot be found in the literature, even an empirical example would be enlightening.