Algorithmic Statistics: Normal Objects and Universal Models

A. Milovanov

doi:10.1007/978-3-319-34171-2_20

Публикации

?

Algorithmic Statistics: Normal Objects and Universal Models

P. 280–293.

Милованов А. С.

In algorithmic statistics quality of a statistical hypothesis (a model) P for a data x is measured by two parameters: Kolmogorov complexity of the hypothesis and the probability P(x). A class of models SijSij that are the best at this point of view, were discovered. However these models are too abstract. To restrict the class of hypotheses for a data, Vereshchaginintroduced a notion of a strong model for it. An object is called normal if it can be explained by using strong models not worse than without this restriction. 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 models SijSij are not strong for x. Our last result states that every best fit strong model for a normal object is again a normal object.

Язык: английский

DOI

Текст на другом сайте

Ключевые слова: algorithmic statistics minimum description length denoising Algorithmic sufficient statistics stochastic objects

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Теоретическая информатика (2016)

В книге

Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings

Vol. 9691: Lecture Notes in Computer Science. , Switzerland: Springer, 2016.

Kolmogorov’s Last Discovery? (Kolmogorov and Algorithmic Statistics)

Семенов А. Л., Шень А., Верещагин Н. К., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606

Добавлено: 16 января 2025 г.

Real-time Streaming Wave-U-Net with Temporal Convolutions for Multichannel Speech Enhancement

Соколов А. С., / Series Computer Science "arxiv.org". 2021.

Добавлено: 26 сентября 2021 г.

Algorithmic Statistics: Forty Years Later.

Shen A., Верещагин Н. К., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.

Добавлено: 26 октября 2018 г.

On Algorithmic Statistics for Space-bounded Algorithms

Милованов А. С., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833–848

Добавлено: 17 октября 2018 г.

Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms

Милованов А. С., , in: Sailing Routes in the World of Computation.: Springer, 2018. P. 287–296.

Добавлено: 4 сентября 2018 г.

Fast Approximate Energy Minimization with Label Costs

Delong A., Осокин А. А., Isack H. и др., International Journal of Computer Vision 2012 Vol. 96 No. 1 P. 1–27

Добавлено: 18 октября 2017 г.

On Algorithmic Statistics for Space-Bounded Algorithms

Милованов А. С., , in: Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017)Vol. 10304.: Luxemburg: Springer, 2017. P. 232–244.

Добавлено: 15 октября 2017 г.

Algorithmic Statistics: Forty Years Later.

Верещагин Н. К., Shen A., Lecture Notes in Computer Science 2017 Vol. 10010 P. 669–737

Добавлено: 13 февраля 2017 г.

Algorithmic Minimal Sufficient Statistics: a New Approach

Верещагин Н. К., Theory of Computing Systems 2016 Vol. 58 No. 3 P. 463–481

Добавлено: 7 февраля 2017 г.

Algorithmic Statistics, Prediction and Machine Learning

Милованов А. С., , in: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54 P. 1–13.

Добавлено: 27 июня 2016 г.

Some Properties of Antistochastic Strings

Милованов А. С., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 339–349.

Добавлено: 27 июня 2016 г.

Some Properties of Antistochastic Strings

Милованов А. С., Theory of Computing Systems 2017 Vol. 61 No. 2 P. 521–535

Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms ...

Добавлено: 27 июня 2016 г.

A combinatorial formula for affine Hall–Littlewood functions via a weighted Brion theorem

Фейгин Б. Л., Махлин И. Ю., Selecta Mathematica, New Series 2016 Vol. 22 No. 3 P. 1703–1747

We present a new combinatorial formula for Hall–Littlewood functions associated with the affine root system of type (Formula presented.), i.e., corresponding to the affine Lie algebra (Formula presented.). Our formula has the form of a sum over the elements of a basis constructed by Feigin, Jimbo, Loktev, Miwa and Mukhin in the corresponding irreducible representation. ...

Добавлено: 4 мая 2016 г.

Sophistication vs Logical Depth

Antunes L., Баувенс Б. Ф., Souto A. и др., Theory of Computing Systems 2017 Vol. 60 No. 2 P. 280–298

Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program ...

Добавлено: 4 мая 2016 г.

Algorithmic Statistics Revisited

Верещагин Н. К., Shen A., , in: Measures of Complexity. Festschrift for Alexey Chervonenkis.: Springer, 2015. P. 235–252.

Добавлено: 3 марта 2016 г.