The Power and Perils of MDL Export

@proceedings{citeulike:5695178, abstract = {We point out a potential weakness in the application of the celebrated Minimum Description Length (MDL) principle for model selection. Specifically, it is shown that (although the index of the model class which actually minimizes a two-part code has many desirable properties) a model which has a shorter two-part code-length than another is not necessarily better (unless of course it achieves the global minimum). This is illustrated by an application to infer a grammar (DFA) from positive examples. We also analyze computability issues, and robustness under recoding of the data. Generally, the classical approach is inadequate to express the goodness-of-fit of individual models for individual data sets. In practice however, this is precisely what we are interested in: both to express the goodness of a procedure and where and how it can fail. To achieve this practical goal, we paradoxically have to use the, supposedly impractical, vehicle of Kolmogorov complexity.}, author = {Adriaans, Pieter and Vitanyi, Paul}, booktitle = {Information Theory, 2007. ISIT 2007. IEEE International Symposium on}, citeulike-article-id = {5695178}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/ISIT.2007.4557549}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4557549}, doi = {10.1109/ISIT.2007.4557549}, journal = {Information Theory, 2007. ISIT 2007. IEEE International Symposium on}, keywords = {dfa, error\_bounds, formal\_languages, learning\_theory, mdl, statistics, sufficient\_statistics}, pages = {2216--2220}, posted-at = {2009-08-31 23:08:08}, priority = {2}, title = {The Power and Perils of MDL}, url = {http://dx.doi.org/10.1109/ISIT.2007.4557549}, year = {2007} }

TY - CONF ID - citeulike:5695178 L3 - citeulike-article-id:5695178 N2 - We point out a potential weakness in the application of the celebrated Minimum Description Length (MDL) principle for model selection. Specifically, it is shown that (although the index of the model class which actually minimizes a two-part code has many desirable properties) a model which has a shorter two-part code-length than another is not necessarily better (unless of course it achieves the global minimum). This is illustrated by an application to infer a grammar (DFA) from positive examples. We also analyze computability issues, and robustness under recoding of the data. Generally, the classical approach is inadequate to express the goodness-of-fit of individual models for individual data sets. In practice however, this is precisely what we are interested in: both to express the goodness of a procedure and where and how it can fail. To achieve this practical goal, we paradoxically have to use the, supposedly impractical, vehicle of Kolmogorov complexity. JF - Information Theory, 2007. ISIT 2007. IEEE International Symposium on EP - 2220 TI - The Power and Perils of MDL T2 - Information Theory, 2007. ISIT 2007. IEEE International Symposium on SP - 2216 KW - dfa KW - error_bounds KW - formal_languages KW - learning_theory KW - mdl KW - statistics KW - sufficient_statistics AU - Adriaans, Pieter AU - Vitanyi, Paul PY - 2007/// UR - http://dx.doi.org/10.1109/ISIT.2007.4557549 ER -