  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.
