Entropy · 1 Oct 2026
Bridging Machine Learning and Algorithmic Information Theory, Part VII: Algorithmic Information Kernels and Kernel Discrepancies on Countable Spaces
Boumediene Hamzi, Marcus Hutterh-index 43, Houman Owhadih-index 14
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenAlex1
- OpenCitations0
- Crossref0
Citations per year
The current year is still counting.
- 2026 so far0
Abstract
Compression-based dissimilarities such as the normalized compression distance are widely used, but direct exponentiation need not produce a positive semidefinite kernel. We develop a systematic interface between prefix algorithmic information theory and three kernel discrepancy methods on finite or countable spaces: maximum mean discrepancy (MMD), the Hilbert–Schmidt independence criterion (HSIC), and a Markov-operator kernel Stein discrepancy (KSD). Explicit feature realizations guarantee positive semidefiniteness for distance-to-kernel embeddings and for an ideal Solomonoff feature-mixture kernel satisfying kSol,U(x,y)≍U2−KU(⟨x,y⟩). Zero-mass signed measures give the exact characteristicity criterion, and whether the ideal Solomonoff kernel meets that criterion turns out to depend on the universal machine: two universal prefix machines are exhibited, one whose kernel is not characteristic on a two-point set and one whose kernel separates all finite-total-variation signed measures on the countable string space. In the resulting RKHS geometry, the MMD compares compressibility profiles, the HSIC is product-kernel MMD from the joint law to the product of its marginals, and KSDTP,k(Q)=MMDk(QTP,Q) for a target-stationary Markov kernel TP. Expected algorithmic mutual information is connected to the HSIC only through explicit source-description, mutual-information, support, and kernel conditions. Ideal AIT objects, computable feature surrogates, and finite-sample errors are separated explicitly. Reproducible synthetic experiments examine the identities, landmark approximation, and selected testing alternatives at the computable and empirical layers. They provide no evidence about ideal AIT quantities or general superiority over baselines. An algebraic example also shows that a characteristic finite-support kernel can give a constant permutation statistic: identification alone does not guarantee test power.
What the data shows
- OpenAlex counts 1 citations, the most of the databases. The others count 0.
- Marcus Hutter has the highest h-index among the authors (43).
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (26)
What it cites, from open citation data, with Crossref's record of each.
Sign in to see 6 more references
A free account opens the rest of the citing papers and references on every paper’s page.