Algorithmic statistics: forty years later
From MaRDI portal
Abstract: 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 is no good model? If yes, how often these bad ("non-stochastic") data appear "in real life"? Another, more technical motivation comes from algorithmic information theory. In this theory a notion of complexity of a finite object (=amount of information in this object) is introduced; it assigns to every object some number, called its algorithmic complexity (or Kolmogorov complexity). Algorithmic statistic provides a more fine-grained classification: for each finite object some curve is defined that characterizes its behavior. It turns out that several different definitions give (approximately) the same curve. In this survey we try to provide an exposition of the main results in the field (including full proofs for the most important ones), as well as some historical comments. We assume that the reader is familiar with the main notions of algorithmic information (Kolmogorov complexity) theory.
Recommendations
Cites work
- A formal theory of inductive inference. Part I
- A formal theory of inductive inference. Part II
- Algorithmic Complexity and Stochastic Properties of Finite Binary Sequences
- Algorithmic minimal sufficient statistic revisited
- Algorithmic minimal sufficient statistics: a new approach
- Algorithmic statistics
- Algorithmic statistics revisited
- Algorithmic statistics, prediction and machine learning
- Algorithmic statistics: normal objects and universal models
- Algorithmic tests and randomness with respect to a class of measures
- An almost machine-independent theory of program-length complexity, sophistication, and induction
- An Information Measure for Classification
- An introduction to Kolmogorov complexity and its applications
- Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising
- Around Kolmogorov complexity: basic notions and results
- Computational depth: Concept and applications
- Depth as randomness deficiency
- Discussion on Kolmogorov Complexity and Statistical Analysis
- Does snooping help?
- scientific article; zbMATH DE number 3860059 (Why is no real title available?)
- scientific article; zbMATH DE number 4072382 (Why is no real title available?)
- Kolmogorov Complexity and Algorithmic Randomness
- Kolmogorov's Structure Functions and Model Selection
- Mathematical metaphysics of randomness
- Meaningful Information
- Modeling by shortest data description
- On the Defect of Randomness of a Finite Object with Respect to Measures with Given Complexity Bounds
- On the relation between descriptional complexity and algorithmic probability
- Randomness conservation inequalities; information and independence in mathematical theories
- Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
- Sophistication as randomness deficiency
- Sophistication revisited
- Sophistication vs logical depth
- Stability of properties of Kolmogorov complexity under relativization
- What percentage of programs halt?
Cited in
(24)- Algorithmic statistics and prediction for polynomial time-bounded algorithms
- Dimension 1 sequences are close to randoms
- Special issue on 40 years of statistical selection theory, Part I
- Predictions and algorithmic statistics for infinite sequences
- An extended coding theorem with application to quantum complexities
- Winograd's algorithm statistically revisited: it pays to weigh than to count!
- Real patterns and indispensability
- Algorithmic statistics revisited
- scientific article; zbMATH DE number 194187 (Why is no real title available?)
- scientific article; zbMATH DE number 194221 (Why is no real title available?)
- scientific article; zbMATH DE number 2080439 (Why is no real title available?)
- Algorithmic statistics
- Algorithmic statistics, prediction and machine learning
- Correction to "Algorithmic statistics"
- Randomness Tests: Theory and Practice
- Inequalities for space-bounded Kolmogorov complexity
- Algorithmic statistics: normal objects and universal models
- Andrei Kolmogorov and Leonid Levin on Randomness
- The Kolmogorov birthday paradox
- Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)
- Prediction and MDL for infinite sequences
- Kolmogorov complexity in the USSR (1975--1982): isolation and its end
- Chair of Mathematical Logic and Theory of Algorithms
- Vladimir V'yugin: short biography and some research contributions
This page was built for publication: Algorithmic statistics: forty years later
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970987)
