Stochastic Complexity in Learning
Journal of Computer and System SciencesPublished 1 August 1997
J. Rissanen
Citations42
SJR quartileQ1
SJR score1.03
SNIP1.08
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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.
Abstract
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).
Keywords
Computer Science
Texts in computer scienceAn Introduction to Kolmogorov Complexity and Its Applications
3,734 Citations2019Ming Li, Paul Vitányi
International Journal of Computer MathematicsThree approaches to the quantitative definition of information<sup>*</sup>
2,013 Citations1968A. N. Kolmogorov
Information and ControlA formal theory of inductive inference. Part II
1,786 Citations1964Ray J. Solomonoff
Four ostensibly different theoretical models of induction are presented, in which the problem dealt with is the extrapolation of a very long sequence of symbols—presumably containing all of the information to be used in the induction.
Information and ControlA formal theory of inductive inference. Part I
1,149 Citations1964Ray J. Solomonoff
Journal of the ACMOn the Length of Programs for Computing Finite Binary Sequences
917 Citations1969Gregory J. Chaitin
An attempt is made to carry out a program for defining the concept of a random or patternless, finite binary sequence, and for subsequently defining arandom or patterned, infinite binary sequence to be a sequence whose initial segments are all random orpatternless finite binary sequences.
Journal of the ACMOn the Length of Programs for Computing Finite Binary Sequences
912 Citations1966Gregory J. Chaitin
An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed to study the use of Turing machines for calculating finite binary sequences.
IEEE Transactions on Information TheoryUniversal coding, information, prediction, and estimation
903 Citations1984J. Rissanen
A connection between universal codes and the problems of prediction and statistical estimation is established, and a known lower bound for the mean length of universal codes is sharpened and generalized, and optimum universal codes constructed.
IEEE Transactions on Information TheoryFisher information and stochastic complexity
841 Citations1996J. Rissanen
A sharper code length is obtained as the stochastic complexity and the associated universal process are derived for a class of parametric processes by taking into account the Fisher information and removing an inherent redundancy in earlier two-part codes.
Information and ComputationInferring decision trees using the minimum description lenght principle
665 Citations1989J. R. Quinlan, Ronald L. Rivest
The use of Rissanen's minimum description length principle for the construction of decision trees is explored and empirical results comparing this approach to other methods are given.
An Introduction to Kolmogorov Complexity and Its Applications
638 Citations1993Ming Li, Paul Vitányi
IEEE Transactions on Information TheoryUniversal noiseless coding
372 Citations1973L. Davisson
This paper considers noiseless coding for sources with unknown parameters, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter.
IEEE Transactions on Information TheoryA universal finite memory source
228 Citations1995M.J. Weinberger, J. Rissanen +1 more
It is shown that this universal source incorporates any minimal data-generating tree machine in an asymptotically optimal manner in the following sense: the negative logarithm of the probability it assigns to any long typical sequence, generated by any tree machine, approaches that assigned by the tree machine at the best possible rate.
Conference on Learning TheoryA learning criterion for stochastic rules
85 Citations1990Kenji Yamanishi
Chaotic time series modeling with optimum neural network architecture
4 Citations2005Mikko Lehtokangas, Jukka Saarinen +2 more
The neural network is found to yield better predictions than an optimum ARMA model and comparatively the performance of neural networks and conventional methods in predicting chaotic time series is discussed.