The Information Theory of Similarity

• URL: http://arxiv.org/abs/2512.00378v1
• Date: Sat, 29 Nov 2025 08:12:45 GMT
• Title: The Information Theory of Similarity
• Authors: Nikit Phadke,
• Abstract summary: We establish a precise mathematical equivalence between witness-based similarity systems (REWA) and Shannon's information theory.<n>This unification reveals that fifty years of similarity search research implicitly developed information theory for relational data.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish a precise mathematical equivalence between witness-based similarity systems (REWA) and Shannon's information theory. We prove that witness overlap is mutual information, that REWA bit complexity bounds arise from channel capacity limitations, and that ranking-preserving encodings obey rate-distortion constraints. This unification reveals that fifty years of similarity search research -- from Bloom filters to locality-sensitive hashing to neural retrieval -- implicitly developed information theory for relational data. We derive fundamental lower bounds showing that REWA's $O(Δ^{-2} \log N)$ complexity is optimal: no encoding scheme can preserve similarity rankings with fewer bits. The framework establishes that semantic similarity has physical units (bits of mutual information), search is communication (query transmission over a noisy channel), and retrieval systems face fundamental capacity limits analogous to Shannon's channel coding theorem.

Related papers

• REWA: A General Theory of Witness-Based Similarity [0.0]
  We present a universal framework for similarity-preserving encodings that subsumes all discrete, continuous, algebraic, and learned similarity methods.<n>This unification reveals that Bloom filters, Locality Sensitive Hashing (LSH), Count-Min sketches, Random Fourier Features, and Transformer attention kernels are instances of the same underlying mechanism.
  arXiv  Detail & Related papers  (2025-11-25T07:04:44Z)
• The qubit information logic theory for understanding multi-qubit entanglement and designing exotic entangled states [3.716663957642983]
  We develop a "qubit information logic" (QIL) theory that uses the "qubit information equation" (QIE) and logic to describe the correlation behaviors of multi-qubit entanglement. The QIL directly describes the correlation of each possible pair of qubits and how the correlation changes when other qubits are measured.
  arXiv  Detail & Related papers  (2024-02-24T03:21:05Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis [0.7106986689736827]
  We show the difference in encoding techniques can be visualized by investigating the topology of the data embedded in complex Hilbert space. Our results suggest the encoding method needs to be considered carefully within different quantum machine learning models.
  arXiv  Detail & Related papers  (2022-09-21T18:46:08Z)
• Neuro-Symbolic Artificial Intelligence (AI) for Intent based Semantic Communication [85.06664206117088]
  6G networks must consider semantics and effectiveness (at end-user) of the data transmission. NeSy AI is proposed as a pillar for learning causal structure behind the observed data. GFlowNet is leveraged for the first time in a wireless system to learn the probabilistic structure which generates the data.
  arXiv  Detail & Related papers  (2022-05-22T07:11:57Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Information Field Theory as Artificial Intelligence [0.0]
  Information field theory (IFT) is a mathematical framework for signal reconstruction and non-parametric inverse problems. In this paper, the inference in IFT is reformulated in terms of GNN training and the cross-fertilization of numerical variational inference methods used in IFT and machine learning are discussed.
  arXiv  Detail & Related papers  (2021-12-19T12:29:01Z)
• Shannon theory for quantum systems and beyond: information compression for fermions [68.8204255655161]
  We show that entanglement fidelity in the fermionic case is capable of evaluating the preservation of correlations. We introduce a fermionic version of the source coding theorem showing that, as in the quantum case, the von Neumann entropy is the minimal rate for which a fermionic compression scheme exists.
  arXiv  Detail & Related papers  (2021-06-09T10:19:18Z)
• Neural Distributed Source Coding [59.630059301226474]
  We present a framework for lossy DSC that is agnostic to the correlation structure and can scale to high dimensions. We evaluate our method on multiple datasets and show that our method can handle complex correlations and state-of-the-art PSNR.
  arXiv  Detail & Related papers  (2021-06-05T04:50:43Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• Building and Interpreting Deep Similarity Models [0.0]
  We propose to make similarities interpretable by augmenting them with an explanation in terms of input features. We develop BiLRP, a scalable and theoretically founded method to systematically decompose similarity scores on pairs of input features.
  arXiv  Detail & Related papers  (2020-03-11T17:46:55Z)
• A Theory of Usable Information Under Computational Constraints [103.5901638681034]
  We propose a new framework for reasoning about information in complex systems. Our foundation is based on a variational extension of Shannon's information theory. We show that by incorporating computational constraints, $mathcalV$-information can be reliably estimated from data.
  arXiv  Detail & Related papers  (2020-02-25T06:09:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.