Algorithmic statistics, prediction and machine learning

DOI10.4230/LIPICS.STACS.2016.54zbMATH Open1388.68143arXiv1509.05473MaRDI QIDQ4601906FDOQ4601906

Authors: Alexey Milovanov 

Publication date: 24 January 2018

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

Full work available at URL: https://arxiv.org/abs/1509.05473

Recommendations

• Algorithmic statistics and prediction for polynomial time-bounded algorithms
• Algorithmic statistics
• scientific article; zbMATH DE number 2080439
• Algorithmic statistics: forty years later
• Algorithmic statistics revisited

zbMATH Keywords

predictionlearningKolmogorov complexityalgorithmic information theoryminimal description length

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Inference from stochastic processes and prediction (62M20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (6)

• Algorithmic statistics revisited
• Algorithmic statistics: normal objects and universal models
• Machine learning versus statistical modeling
• Algorithmic statistics and prediction for polynomial time-bounded algorithms
• Algorithms with Predictions
• Algorithmic statistics: forty years later

This page was built for publication: Algorithmic statistics, prediction and machine learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601906)