Algorithmic statistics: normal objects and universal models

DOI10.1007/978-3-319-34171-2_20MaRDI QIDQ5740192zbMATH OpenOpenAlexFDO

Authors Alexey Milovanov

Publication date 25 July 2016

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.04510

zbMATH Keywords

algorithmic statisticsdenoisingminimum description lengthstochastic stringssufficient statistictotal conditional complexity

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Kolmogorov suggested to measure quality of a statistical hypothesis $P$ for a data $x$ by two parameters: Kolmogorov complexity $C(P)$ of the hypothesis and the probability $P(x)$ of $x$ with respect to $P$. P. G'acs, J. Tromp, P.M.B. Vit'anyi discovered a small class of models that are universal in the following sense. Each hypothesis $S_{ij}$ from that class is identified by two integer parameters $i,j$ and for every data $x$ and for each complexity level $alpha$ there is a hypothesis $S_{ij}$ with $jleilel(x)$ of complexity at most $alpha$ that has almost the best fit among all hypotheses of complexity at most $alpha$. The hypothesis $S_{ij}$ is identified by $i$ and the leading $i-j$ bits of the binary representation of the number of strings of complexity at most $i$. On the other hand, the initial data $x$ might be completely irrelevant to the the number of strings of complexity at most $i$. Thus $S_{ij}$ seems to have some information irrelevant to the data, which undermines Kolmogorov's approach: the best hypotheses should not have irrelevant information. To restrict the class of hypotheses for a data $x$ to those that have only relevant information, Vereshchagin introduced a notion of a strong model for $x$: those are models for $x$ whose total conditional complexity conditional to $x$ is negligible. An object $x$ is called normal if for each complexity level $alpha$ at least one its best fitting model of that complexity is strong. In this paper we show that there are "many types" of normal strings. Our second result states that there is a normal object $x$ such that all its best fitting models $S_{ij}$ are not strong for $x$. Our last result states that every best fit strong model for a normal object is again a normal object.

Recommendations

• Algorithmic statistics: forty years later
• Algorithmic statistics
• scientific article; zbMATH DE number 2080439
• Algorithmic statistics revisited
• Algorithmic statistics, prediction and machine learning

Cites work

• Algorithmic statistics
• An introduction to Kolmogorov complexity and its applications
• Game arguments in computability theory and algorithmic information theory
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3860059 (Why is no real title available?)
• Kolmogorov's Structure Functions and Model Selection
• On the Turing completeness of the semantic web

Cited in

(5)

• Algorithmic statistics revisited
• Algorithmic statistics: forty years later
• Kolmogorov's Structure Functions and Model Selection
• Correction to "Algorithmic statistics"
• On algorithmic strong sufficient statistics

This page was built for publication: Algorithmic statistics: normal objects and universal models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5740192)