DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2017.17

Stochasticity in Algorithmic Statistics for Polynomial Time

Authors: Alexey Milovanov and Nikolay Vereshchagin

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract

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 m 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 m). 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 m is called an optimal explanation for x if m(x) is large. 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. Using the same techniques, 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). Finally, we study relationships between the introduced notions.

Cite as

Alexey Milovanov and Nikolay Vereshchagin. Stochasticity in Algorithmic Statistics for Polynomial Time. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{milovanov_et_al:LIPIcs.CCC.2017.17,
  author =	{Milovanov, Alexey and Vereshchagin, Nikolay},
  title =	{{Stochasticity in Algorithmic Statistics for Polynomial Time}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.17},
  URN =		{urn:nbn:de:0030-drops-75222},
  doi =		{10.4230/LIPIcs.CCC.2017.17},
  annote =	{Keywords: Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity}
}

Document

DOI: 10.4230/LIPIcs.STACS.2016.54

Algorithmic Statistics, Prediction and Machine Learning

Authors: Alexey Milovanov

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract

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 know what kind of data we may reasonably expect in similar situations (repeating the same experiment). We show that some kind of hierarchy can be constructed both in terms of algorithmic statistics and using the notion of a priori probability, and these two approaches turn out to be equivalent (Theorem 5). Second, a more realistic approach that goes back to machine learning theory, assumes that we have not a single data string x but some set of "positive examples" x_1,...,x_l that all belong to some unknown set A, a property that we want to learn. We want this set A to contain all positive examples and to be as small and simple as possible. We show how algorithmic statistic can be extended to cover this situation (Theorem 11).

Cite as

Alexey Milovanov. Algorithmic Statistics, Prediction and Machine Learning. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{milovanov:LIPIcs.STACS.2016.54,
  author =	{Milovanov, Alexey},
  title =	{{Algorithmic Statistics, Prediction and Machine Learning}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.54},
  URN =		{urn:nbn:de:0030-drops-57550},
  doi =		{10.4230/LIPIcs.STACS.2016.54},
  annote =	{Keywords: algorithmic information theory, minimal description length, prediction, kolmogorov complexity, learning}
}

Search Results

Documents authored by Milovanov, Alexey

Stochasticity in Algorithmic Statistics for Polynomial Time

Abstract

Cite as

Algorithmic Statistics, Prediction and Machine Learning

Abstract

Cite as

Thanks for your feedback!

Could not send message