Multiclass classification utilising an estimated algorithmic probability prior

Abstract

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.

References in corpus (17)

• Scikit-learn: Machine Learning in Python
• Deep learning generalizes because the parameter-function map is biased towards simple functions
• Kernel Flows: from learning kernels from data into the abyss
• A Philosophical Treatise of Universal Induction
• Quantifying hidden order out of equilibrium
• Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
• Universal and accessible entropy estimation using a compression algorithm
• A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions
• Minimum Description Length Revisited
• Law without law: from observer states to physics via algorithmic information theory
• On the Brittleness of Bayesian Inference
• Lecture notes on descriptional complexity and randomness
• Thermodynamic costs of Turing Machines
• A Note on A Priori Forecasting and Simplicity Bias in Time Series
• A Dilemma for Solomonoff Prediction
• Robust and Efficient Bayesian Inference for Non-Probability Samples
• Computing the Information Content of Trained Neural Networks