Stochastic Complexity in Learning

摘要

This is an expository paper on the latest results in the theory of stochastic complexity and the associated MDL principle with special interest in modeling problems arising in machine learning. As an illustration we discuss the problem of designing MDL decision trees, which are meant to improve the earlier designs in two ways: First, by use of the sharper formula for the stochastic complexity at the nodes the earlier found tendency of getting too small trees appears to be overcome. Second, a dynamic programming-based pruning algorithm is described for finding the optimal trees, which generalizes an algorithm described in R. Nohre (Ph.D. thesis Linkoping University, 1994).