




























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ács, J. Tromp, P.M.B. Vitányi 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 $α$ there is a hypothesis $S_{ij}$ with $j\le i\le l(x)$ of complexity at most $α$ that has almost the best fit among all hypotheses of complexity at most $α$. 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 $α$ 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。