### ?

## Predictions and Algorithmic Statistics for Infinite Sequences

Ch. 17. P. 283-295.

We combine Solomonoff’s approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best “explanation” for the observed data (in the sense of algorithmic statistics) for prediction. In this way we keep the expected sum of squares of prediction errors bounded (as it was for the Solomonoff’s predictor) and, moreover, guarantee that the sum of squares of prediction errors is bounded along any Martin-Löf random sequence.

Publication based on the results of:

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

Algorithmic statistics considers the following problem: given a binary string
x
(e.g., some
experimental data), find a “good” explanation of this data. It uses algorithmic information
theory to define formally what is a good explanation. In this paper we extend this framework in
two directions.
First, the explanations are not only interesting in themselves but also used for prediction: we
want to ...

Added: June 27, 2016

Bienvenu L., Desfontaines D., Shen A., Logical Methods in Computer Science 2016 Vol. 12 No. 2

The halting problem is undecidable --- but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the ...

Added: February 7, 2017

Vereshchagin N., Milovanov A., , in : 32nd Computational Complexity Conference. : Вадерн : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18.

A fundamental notion in Algorithmic Statisticsis 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 ...

Added: October 12, 2017

Bienvenu L., Muchnik A., Shen A. et al., Limit complexities revisited [once more] / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.

The main goal of this article is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result of Vereshchagin saying that lim supnC(x|n) equals C0′(x). Then we use the same argument to prove similar results for prefix complexity, a priori probability on binary ...

Added: December 14, 2013

Antunes L., Bauwens B. F., Souto A. et al., 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 ...

Added: May 4, 2016

V'yugin V., М. : МЦНМО, 2013

Книга предназначена для первоначлаьного знакомства с математическими основами современной теории машинного обучения (Machine Learning) и теории игр на предсказания. В первой части излагаются основы статистической теории машинного обучения, рассматриваются задачи классификации и регрессии с опорными векторами, теория обобщения и алгоритмы построения разделяющих гиперплоскостей. Во второй и третьей частях рассматриваются задачи адаптивного прогнозирования в нестохастических теоретико-игровой ...

Added: July 9, 2014

Bauwens B. F., Shen A., Journal of Symbolic Logic 2013 Vol. 79 No. 2 P. 620-632

Added: October 2, 2015

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

Shen A., Uspensky V. A., Vereshchagin N., American Mathematical Society, 2017

Added: October 12, 2017

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

Bauwens B. F., Archive for Mathematical Logic 2015 Vol. 54 No. 5 P. 615-629

Joseph Miller [16] and independently Andre Nies, Frank Stephan and Sebastiaan Terwijn [18] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C: they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller [17] showed that prefix complexity K ...

Added: October 2, 2015

Ella Y Tyuryumina, Neznanov A., , in : Proceedings of the 2017 International Conference on Digital Health. : NY : Association for Computing Machinery (ACM), 2017. P. 60-66.

This paper is devoted to mathematical modelling of the progression and stages of breast cancer. The Consolidated mathematical growth Model of primary tumor (PT) and secondary distant metastases (MTS) in patients with lymph nodes MTS (Stage III) (CoM-III) is proposed as a new research tool. The CoM-III rests on an exponential tumor growth model and ...

Added: July 20, 2017

Bogolepova S. V., , in : Rivers of Language, Rivers of Learning. Proceedings of the 18th NATE-Russia Annual Conference. Yaroslavl, May 24-26, 2012. : Yaroslavl : Yaroslavl State University, 2012. P. 44-46.

The article deals with different ways of using technology to develop learners' skill of prediction, as one of the metalinguistic skills the recent National Educational Standard puts emphasis on. The use of short videos, Power Point and Wordle word clouds for the purpose is described. ...

Added: October 23, 2013

Rubtsov A. A., , in : Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. : Cham : Springer, 2018. P. 553-565.

We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), ...

Added: September 12, 2018

Kiselyova N. N., Dudarev V., Ryazanov V. V. et al., Inorganic Materials: Applied Research 2021 Vol. 12 No. 2 P. 328-336

New chalcospinels of the most common compositions were predicted: AIBIIICIVX4 (X = S or Se)
and AIIBIIICIIIS4 (A, B, and C are various chemical elements). They are promising for the search for new
materials for magneto-optical memory elements, sensors, and anodes in sodium-ion batteries. The parameter
“a” values of their crystal lattice are estimated. When predicting, only the ...

Added: April 2, 2021

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

Думлер А. А., Черепанов Ф. М., Терапия 2018 № 1(19) С. 109-118

This article is devoted to the methodological issues of the application of artificial intelligence techniques in preventive medicine. We showed a specific example of the neural network application allows not only to diagnose cardiovascular diseases, but also on a quantitative basis to predict their emergence and development in future periods of life. This allows you ...

Added: January 9, 2019

Nadezhdina E. Y., Rebrova O., Ivaschenko O. V. et al., Pituitary 2019 Vol. 22 No. 6 P. 574-580

Background Some laboratory and clinical features are associated with a probability of recurrence after transnasal adenomectomy for Cushing disease (CD). However, there is no consensus on a set of predictors. Rules for prediction of recurrence were not proposed earlier.
Aim To develop prediction model of recurrence/remission after successful neurosurgical treatment for CD.
Methods Retrospective single-site comparative study included 349 ...

Added: October 23, 2019

Bauwens B. F., Blinnikov I., , in : Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings. Vol. 12159.: Springer, 2020. P. 130-141.

It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all 𝜀<1/2, there exist no semicomputable functions that differ from N by at most 𝜀. Moreover, for any computable function f such that |lim𝑡𝑓(𝑥,𝑦,𝑡)−N(𝑥,𝑦)|≤𝜀 and for all n, there exist strings x, y of length n such that ...

Added: February 5, 2021

Bauwens B. F., , in : 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1-46:14.

Added: March 20, 2020

Vereshchagin N., Theoretical Computer Science 2020 Vol. 809 P. 531-537

The purpose of this paper is to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Science 171 (2001), pp. 47--58]. Namely, we consider the following two complexities of an infinite computable 0-1-sequence $\alpha$: $C^{0'}(\alpha )$, defined as ...

Added: January 17, 2020

Vereshchagin N., Bauwens B. F., Makhlin A. et al., Computational Complexity 2018 Vol. 27 No. 1 P. 31-61

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...

Added: April 22, 2017

Bauwens B., Makhlin A., Vereshchagin N. et al., Short lists with short programs in short time / . 2013. No. TR13-007.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...

Added: December 14, 2013