Bridging Algorithmic Information Theory and Machine Learning: A New Approach to Kernel Learning
This work provides a foundational link between AIT and ML, potentially impacting theoretical frameworks in kernel methods, though it is incremental in applying existing AIT concepts to a specific ML problem.
The paper tackles the problem of learning kernels in kernel ridge regression by bridging algorithmic information theory (AIT) and machine learning, showing that Sparse Kernel Flows naturally align with the Minimal Description Length principle and offer a more robust theoretical basis than cross-validation.
Machine Learning (ML) and Algorithmic Information Theory (AIT) look at Complexity from different points of view. We explore the interface between AIT and Kernel Methods (that are prevalent in ML) by adopting an AIT perspective on the problem of learning kernels from data, in kernel ridge regression, through the method of Sparse Kernel Flows. In particular, by looking at the differences and commonalities between Minimal Description Length (MDL) and Regularization in Machine Learning (RML), we prove that the method of Sparse Kernel Flows is the natural approach to adopt to learn kernels from data. This approach aligns naturally with the MDL principle, offering a more robust theoretical basis than the existing reliance on cross-validation. The study reveals that deriving Sparse Kernel Flows does not require a statistical approach; instead, one can directly engage with code-lengths and complexities, concepts central to AIT. Thereby, this approach opens the door to reformulating algorithms in machine learning using tools from AIT, with the aim of providing them a more solid theoretical foundation.