Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On High-Quality Synthesis Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Algorithmic Statistics: Normal Objects and Universal Models

Author : Alexey Milovanov

Published in: Computer Science – Theory and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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 \(S_{ij}\) 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 \(S_{ij}\) are not strong for x. Our last result states that every best fit strong model for a normal object is again a normal object.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Sums of Read-Once Formulas: How Many Summands Suffice?
next chapter Subquadratic Algorithms for Succinct Stable Matching
Footnotes
1
by \(\log \) we denote \(\log _2\).
 
2
This theorem was proved in [10, Theorem VIII.4] with accuracy \(O(\max \{\log C(y)\mid y\in A\}+C(p))\) instead of \(O(\log n)\). Applying [10, Theorem VIII.4] to \(A'=\{y\in A\mid l(y)=n\}\) we obtain the theorem in the present form.
 
Literature
1.
2.
Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Probl. Inf. Trans. 1(1), 1–7 (1965)MathSciNetMATH
3.
Kolmogorov, A.N.: The complexity of algorithms, the objective definition of randomness. Usp. Matematicheskich Nauk 29(4(178)), 155 (1974). Summary of the talk presented April 16, at Moscow Mathematical SocietyMathSciNet
4.
Li, M., Vitányi, P.: An Introduction to Kolmogorov complexity and its applications, 3rd edn., xxiii+790 p. Springer, New York (2008). (1st edn. 1993; 2nd edn. 1997), ISBN 978-0-387-49820-1
5.
Shen, A.: Game arguments in computability theory and algorithmic information theory. In: Cooper, S.B., Dawar, A., Löwe, B. (eds.) CiE 2012. LNCS, vol. 7318, pp. 655–666. Springer, Heidelberg (2012)CrossRef
6.
Shen, A.: Around kolmogorov complexity: basic notions and results. In: Vovk, V., Papadoupoulos, H., Gammerman, A. (eds.) Measures of Complexity: Festschrift for Alexey Chervonenkis. Springer, Heidelberg (2015)
7.
Shen, A.: The concept of \((\alpha, \beta )\)-stochasticity in the Kolmogorov sense, and its properties. Sov. Math. Dokl. 271(1), 295–299 (1983)MATH
8.
9.
Vereshchagin, N.: Algorithmic minimal sufficient statistics: A new approach. Theory Comput. Syst. 56(2), 291–436 (2015)MathSciNetCrossRef
10.
Vereshchagin, N., Vitányi, P.: Kolmogorov’s structure functions with an application to the foundations of model selection. IEEE Trans. Inf. Theory 50(12), 3265–3290 (2004). Preliminary version: Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pp. 751–760 (2002)CrossRefMATH
11.
Vitányi, P., Vereshchagin, N.: On algorithmic rate-distortion function. In: Proceedings of 2006 IEEE International Symposium on Information Theory, Seattle, Washington, 9–14 July 2006
Metadata
Title
Algorithmic Statistics: Normal Objects and Universal Models
Author
Alexey Milovanov
Copyright Year
2016
Book
Computer Science – Theory and Applications

Print ISBN: 978-3-319-34170-5

Electronic ISBN: 978-3-319-34171-2

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-34171-2_20

Premium Partner

    Image Credits