### ?

## Algorithmic Statistics Revisited

P. 235-252.

Vereshchagin N., Shen A.

A survey of main results in algorithmic statistics

### In book

Vovk V., Gammerman A., Papadopoulos H. Springer, 2015

Vereshchagin N., , in : 9th Conference on Computability in Europe. : Berlin : Springer, 2013. P. 424-433.

The notion of a strong sufficient statistic was introduced in [N.~Vereshchagin, Algorithmic Minimal Sufficient Statistic Revisited. \emph{Proc. 5th Conference on Computability in Europe}, CiE 2009, LNCS 5635, pp. 478-487]. In this paper, we give a survey of nice properties of strong sufficient statistics and show that there are strings for which complexity of every strong ...

Added: December 14, 2013

Milovanov A., , in : Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017). Vol. 10304.: Luxemburg : Springer, 2017. P. 232-244.

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable.
In this paper we develop algorithmic ...

Added: October 15, 2017

Milovanov A., , in : Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015. Vol. 9139.: Springer, 2015. P. 339-349.

Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string x is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of x. Further we will ...

Added: June 27, 2016

Milovanov A., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833-848

Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we ...

Added: October 17, 2018

Shen A., Vereshchagin N., , in : Computability and Complexity. : Berlin : Springer, 2017. P. 669-737.

Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...

Added: October 26, 2018

Vereshchagin N., Shen A., Lecture Notes in Computer Science 2017 Vol. 10010 P. 669-737

Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...

Added: February 13, 2017

Milovanov A., 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 ...

Added: June 27, 2016

Vereshchagin N., Theory of Computing Systems 2016 Vol. 58 No. 3 P. 463-481

We introduce the notion of a strong sufficient statistic for a given data string. We show that strong sufficient statistics have better properties than just sufficient statistics. We prove that there are “strange” data strings, whose minimal strong sufficient statistic have much larger complexity than the minimal sufficient statistic. ...

Added: February 7, 2017

Milovanov A., , in : Sailing Routes in the World of Computation. : Springer, 2018. P. 287-296.

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice as is because Kolmogorov complexity is not computable.
In recent years resource-bounded ...

Added: September 4, 2018

Milovanov A., , in : 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. 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 ...

Added: June 27, 2016

Мелкумова Л. Э., Шатских С. Я., Теория вероятностей и ее применения 2018 Т. 63 № 4 С. 808-816

De Finetti’s theorem states that the elements of an infinite exchangeable sequence of random variables are conditionally independent and identically distributed relative to some random variable (or a sigma-algebra generated by that random variable). In this work, we construct this random variable using the maximum likelihood method. ...

Added: June 8, 2021

Zaev D., Decomposition of the Kantorovich problem and Wasserstein distances on simplexes / Cornell University. Series math "arxiv.org". 2015.

We consider L^p-Wasserstein distances on a subset of probability measures. If the subset of interest appears to be a simplex, these distances are determined by their values on extreme points of the simplex. We show that this fact is a corollary of the following decomposition result: an optimal transport plan can be represented as a mixture ...

Added: May 25, 2015