Probability Models and The Kolmogorov Structure Function
For every computable probability distribution P it can be proved that . For example, if P is the uniform distribution on the set S of strings of length n, then each has probability . In the general case of computable probability mass functions we incur a logarithmic additive error term. Kolmogorov's structure function becomes
where x is a binary string of length n with where P is a contemplated model (computable probability of n-length strings) for x, is the Kolmogorov complexity of P and is an integer value bounding the complexity of the contemplated P's. Clearly, this function is nonincreasing and reaches for where c is the required number of bits to change x into and is the Kolmogorov complexity of x. Then . For every complexity level the function is the Kolmogorov complexity version of the maximum likelihood (ML).
Read more about this topic: Kolmogorov Structure Function
Famous quotes containing the words probability, models, structure and/or function:
“Crushed to earth and rising again is an author’s gymnastic. Once he fails to struggle to his feet and grab his pen, he will contemplate a fact he should never permit himself to face: that in all probability books have been written, are being written, will be written, better than anything he has done, is doing, or will do.”
—Fannie Hurst (1889–1968)
“The greatest and truest models for all orators ... is Demosthenes. One who has not studied deeply and constantly all the great speeches of the great Athenian, is not prepared to speak in public. Only as the constant companion of Demosthenes, Burke, Fox, Canning and Webster, can we hope to become orators.”
—Woodrow Wilson (1856–1924)
“There is no such thing as a language, not if a language is anything like what many philosophers and linguists have supposed. There is therefore no such thing to be learned, mastered, or born with. We must give up the idea of a clearly defined shared structure which language-users acquire and then apply to cases.”
—Donald Davidson (b. 1917)
“We are thus able to distinguish thinking as the function which is to a large extent linguistic.”
—Benjamin Lee Whorf (1897–1934)