?
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.
Semenov A., Shen A., Vereshchagin N., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606
The definition of descriptional complexity of finite objects suggested by Kolmogorov and other authors in the mid-1960s is now well known. In addition, Kolmogorov pointed out some approaches to a more fine-grained classification of finite objects, such as the resource-bounded complexity (1965), structure function (1974), and the notion of $(\alpha,\beta)$-stochasticity (1981). Later it turned out ...
Added: January 16, 2025
Мелкумова Л. Э., Шатских С. Я., Теория вероятностей и ее применения 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
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
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
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: 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
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
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: Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, ProceedingsVol. 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
Milovanov A., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 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 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
Zaev D., / 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
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