# Multiclass classification utilising an estimated algorithmic probability prior

arXiv: https://arxiv.org/abs/2212.07426 · HTML: https://mlsanity.com/paper/2212.07426/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 76 references that are in the map.
- First posted on arXiv 14 Dec 2022.

## Builds on (most cited first, 11 of 11)

- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Kernel Flows: from learning kernels from data into the abyss](https://mlsanity.com/paper/1808.04475/) (2018)
- [Minimum Description Length Revisited](https://mlsanity.com/paper/1908.08484/) (2019)
- [Revisiting minimum description length complexity in overparameterized models](https://mlsanity.com/paper/2006.10189/) (2020)
- [Formal Definitions of Unbounded Evolution and Innovation Reveal Universal Mechanisms for Open-Ended Evolution in Dynamical Systems](https://mlsanity.com/paper/1607.01750/) (2016)
- [Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks](https://mlsanity.com/paper/1306.0322/) (2013)
- [A Dilemma for Solomonoff Prediction](https://mlsanity.com/paper/2206.06473/) (2022)
- [Computing the Information Content of Trained Neural Networks](https://mlsanity.com/paper/2103.01045/) (2021)
- [Inference from Non-Random Samples Using Bayesian Machine Learning](https://mlsanity.com/paper/2104.05192/) (2021)
- [SGD Through the Lens of Kolmogorov Complexity](https://mlsanity.com/paper/2111.05478/) (2021)
- [Robust and Efficient Bayesian Inference for Non-Probability Samples](https://mlsanity.com/paper/2203.14355/) (2022)

## Built on by (most cited first, 1 of 1)

- [Simplicity bias, algorithmic probability, and the random logistic map](https://mlsanity.com/paper/2401.00593/) (2023)

## Abstract (arXiv)

Methods of pattern recognition and machine learning are applied extensively in science, technology, and society. Hence, any advances in related theory may translate into large-scale impact. Here we explore how algorithmic information theory, especially algorithmic probability, may aid in a machine learning task. We study a multiclass supervised classification problem, namely learning the RNA molecule sequence-to-shape map, where the different possible shapes are taken to be the classes. The primary motivation for this work is a proof of concept example, where a concrete, well-motivated machine learning task can be aided by approximations to algorithmic probability. Our approach is based on directly estimating the class (i.e., shape) probabilities from shape complexities, and using the estimated probabilities as a prior in a Gaussian process learning problem. Naturally, with a large amount of training data, the prior has no significant influence on classification accuracy, but in the very small training data regime, we show that using the prior can substantially improve classification accuracy. To our knowledge, this work is one of the first to demonstrate how algorithmic probability can aid in a concrete, real-world, machine learning problem.