Publication | Open Access
Stochastic Complexity and Modeling
947
Citations
0
References
1986
Year
EngineeringComputational ComplexityProbabilistic ComputationStochastic PhenomenonStochastic ComplexityData ScienceUncertainty QuantificationDescriptional ComplexityKolmogorov ComplexityAlgorithmic ComplexityStatisticsStochastic SystemProbability TheoryComputer ScienceAlgorithmic Information TheoryStochastic ModelingBinary DigitsStatistical InferenceProperty Testing
Stochastic complexity measures the minimal binary encoding length of data relative to a chosen probabilistic model class. Computing stochastic complexity yields a model that captures all extractable statistical information, enables optimal prediction with jointly optimized parameters, establishes a lower bound on code length and prediction error, and introduces new definitions of prior and useful information leading to a universal hypothesis‑testing statistic.
As a modification of the notion of algorithmic complexity, the stochastic complexity of a string of data, relative to a class of probabilistic models, is defined to be the fewest number of binary digits with which the data can be encoded by taking advantage of the selected models. The computation of the stochastic complexity produces a model, which may be taken to incorporate all the statistical information in the data that can be extracted with the chosen model class. This model, for example, allows for optimal prediction, and its parameters are optimized both in their values and their number. A fundamental theorem is proved which gives a lower bound for the code length and, therefore, for prediction errors as well. Finally, the notions of "prior information" and the "useful information" in the data are defined in a new way, and a related construct gives a universal test statistic for hypothesis testing.