OpenResearchAlpha

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

1
Citations
OpenAlex's count; others 0
0
Citations in 2026
so far
43
Leading author's h-index
Marcus Hutter, in QAI's scholar index
26
References
works it cites, from open citation data

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.

Citing paper shares an authorAuthor without a profileSize shows citations, or h-index for authors

Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.

Start with

Authors (3)

Each author's standing in QAI's scholar index: the works their ORCID iD is attached to, and for anyone whose ORCID record names a lab OpenResearch follows, their arXiv preprints matched by name and a shared co-author. Names are as printed on the paper.

ProfileMost-cited paper

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.

0 shown
No citing papers for this filter.

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.