|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Stochasticity in algorithmic statistics for polynomial timeстатья
- Авторы: Milovanov Alexey, Vereshchagin Nikolay
- Сборник: Electronic Colloquium on Computational Complexity
- Серия: TR17
- Том: 43
- Год издания: 2017
- Место издания: Weizmann Institute of Science Rehovot
- Первая страница: 1
- Последняя страница: 21
- Аннотация: A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical hypothesis for Algorithmic Statistics with polynomial time bounds, which are called acceptability, plausibility and optimality. Roughly speaking, a probability distribution is called an acceptable explanation for x, if x possesses all properties decidable by short programs in a short time and shared by almost all objects (with respect to ). Plausibility is a similar notion, however this time we require x to possess all properties T decidable even by long programs in a short time and shared by almost all objects. To compensate the increase in program length, we strengthen the notion of `almost all'---the longer the program recognizing the property is, the more objects must share the property. Finally, a probability distribution is called an optimal explanation for x if (x) is large (close to 2−Kpoly(x)). Almost all our results hold under some plausible complexity theoretic assumptions. Our main result states that for acceptability and plausibility there are infinitely many non-stochastic objects, i.e. objects that do not have simple plausible (acceptable) explanations. We explain why we need assumptions---our main result implies that P = PSPACE. In the proof of that result, we use the notion of an elusive set, which is interesting in its own right. Using elusive sets, we show that the distinguishing complexity of a string x can be super-logarithmically less than the conditional complexity of x with condition r for almost all r (for polynomial time bounded programs). Such a gap was known before, however only in the case when both complexities are conditional, or both complexities are unconditional. It follows from the definition that plausibility implies acceptability and optimality. We show that there are objects that have simple acceptable but implausible and non-optimal explanations. We prove that for strings whose distinguishing complexity is close to Kolmogorov complexity (with polynomial time bounds) plausibility is equivalent to optimality for all simple distributions, which fact can be considered as a justification of the Maximal Likelihood Estimator. URL: https://eccc.weizmann.ac.il/report/2017/043/
- Добавил в систему: Верещагин Николай Константинович