Algorithmic Statistics

2020. Auflage 2012
ISBN: 978-0-387-00542-3
Verlag: Springer

Buch, Englisch, 400 Seiten, Format (B × H): 155 mm x 235 mm

Reihe: Monographs in Computer Science

Whereas Kolmogorov complexity is the accepted absolute measure of

information content of an individual finite object, a similarly

absolute notion is needed for the relation between an individual data

sample and an individual model summarizing the information in the data

---for example, a finite set (or probability distribution) where the

data sample typically came from. The statistical theory based on such

relations between individual objects can be called algorithmic

statistics, in contrast to classical statistical theory that deals

with relations between probabilistic ensembles. 'Algorithmic Statistics' develops the algorithmic theory of

statistics, sufficient statistics, and minimal sufficient statistics.

This theory is based on two-part codes consisting of the code for the

statistic (the model summarizing the regularity, the meaningful

information, in the data) and the model-to-data code. In contrast to

the situation in probabilistic statistical theory, the algorithmic

relation of (minimal) sufficiency is an absolute relation between the

individual model and the individual data sample. The book

distinguishes implicit and explicit descriptions of the models and

gives characterizations of algorithmic (Kolmogorov) minimal sufficient

statistic for all data samples for both description modes--in the

explicit mode under some constraints. It also strengthens and

elaborates upon earlier results on the ``Kolmogorov structure

function'' and ``absolutely non-stochastic objects''--those rare

objects for which the simplest models that summarize their relevant

information (minimal sufficient statistics) are at least as complex as

the objects themselves.

Zielgruppe

Research

Autoren/Hrsg.

Vitanyi, Paul

Vitányi, Paul M.B.

Fachgebiete

• Mathematik | Informatik EDV | Informatik Business Application Mathematische & Statistische Software
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Zeichen- und Zahlendarstellungen
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
• Mathematik | Informatik EDV | Informatik Informatik

Inhaltsverzeichnis

* Introduction * Kolmogorov complexity issues * Finite set models * Nonstochastic objects * Probabilistic models * Algorithmic versus probabilistic methods * Select applications * Conclusions