Related papers: Directed Metric Structures arising in Large Language Models

Directed Metric Structures arising in Large Language Models

URL: http://arxiv.org/abs/2405.12264v1
Date: Mon, 20 May 2024 17:16:27 GMT
Title: Directed Metric Structures arising in Large Language Models
Authors: Stéphane Gaubert, Yiannis Vlassopoulos,
Abstract summary: We find the mathematical structure defined by conditional probability distributions of text extensions. Changing the view point from probabilities to -log probabilities we observe that the subtext order is completely encoded in a metric structure.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Large Language Models are transformer neural networks which are trained to produce a probability distribution on the possible next words to given texts in a corpus, in such a way that the most likely word predicted is the actual word in the training text. In this paper we find what is the mathematical structure defined by such conditional probability distributions of text extensions. Changing the view point from probabilities to -log probabilities we observe that the subtext order is completely encoded in a metric structure defined on the space of texts $\mathcal{L}$, by -log probabilities. We then construct a metric polyhedron $P(\mathcal{L})$ and an isometric embedding (called Yoneda embedding) of $\mathcal{L}$ into $P(\mathcal{L})$ such that texts map to generators of certain special extremal rays. We explain that $P(\mathcal{L})$ is a $(\min,+)$ (tropical) linear span of these extremal ray generators. The generators also satisfy a system of $(\min+)$ linear equations. We then show that $P(\mathcal{L})$ is compatible with adding more text and from this we derive an approximation of a text vector as a Boltzmann weighted linear combination of the vectors for words in that text. We then prove a duality theorem showing that texts extensions and text restrictions give isometric polyhedra (even though they look a priory very different). Moreover we prove that $P(\mathcal{L})$ is the lattice closure of (a version of) the so called, Isbell completion of $\mathcal{L}$ which turns out to be the $(\max,+)$ span of the text extremal ray generators. All constructions have interpretations in category theory but we don't use category theory explicitly. The categorical interpretations are briefly explained in an appendix. In the final appendix we describe how the syntax to semantics problem could fit in a general well known mathematical duality.

Related papers

The Magnitude of Categories of Texts Enriched by Language Models [1.8416014644193064]
We use the next-token probabilities given by a language model to define a $[0,1]$-enrichment of a category of texts in natural language. We compute the M"obius function and the magnitude of an associated generalized space $mathcalM$ of texts.
arXiv Detail & Related papers (2025-01-11T23:28:50Z)
Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents [13.391318494060975]
We present the Federated Upper Confidence Bound Value Iteration algorithm ($textttFed-UCBVI$) We prove that the regret of $textttFed-UCBVI$ scales as $tildemathcalO(sqrtH3 |mathcalS| |mathcalA| T / M)$. We show that, unlike existing federated reinforcement learning approaches, $textttFed-UCBVI$'s communication complexity only marginally increases with the number of
arXiv Detail & Related papers (2024-10-30T11:05:50Z)
A Theory of Interpretable Approximations [61.90216959710842]
We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
arXiv Detail & Related papers (2024-06-15T06:43:45Z)
Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
arXiv Detail & Related papers (2024-06-03T17:56:58Z)
Provably learning a multi-head attention layer [55.2904547651831]
Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
arXiv Detail & Related papers (2024-02-06T15:39:09Z)
A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z)
Vocabulary for Universal Approximation: A Linguistic Perspective of Mapping Compositions [6.164223149261533]
We prove the existence of a finite emphvocabulary $V=phi_i: mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to math
arXiv Detail & Related papers (2023-05-20T14:50:34Z)
An Approximation Theory for Metric Space-Valued Functions With A View Towards Deep Learning [25.25903127886586]
We build universal functions approximators of continuous maps between arbitrary Polish metric spaces $mathcalX$ and $mathcalY$. In particular, we show that the required number of Dirac measures is determined by the structure of $mathcalX$ and $mathcalY$.
arXiv Detail & Related papers (2023-04-24T16:18:22Z)
Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z)
On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of $\mathbb{R}^N$ with Boundary [0.4125187280299246]
We consider the probability that a random matrix $A in mathbbRm times N$ will serve as a bi-Lipschitz function $A: mathcalM rightarrow mathbbRm$ with bi-Lipschitz constants close to one. We present a new class of highly structured distributions for embedding sufficiently low-dimensional submanifolds of $mathbbRN$.
arXiv Detail & Related papers (2021-10-08T15:27:52Z)
Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
We study efficient estimation and detection of a planted vector $v$ whose $ell_4$ norm differs from that of a Gaussian vector with the same $ell$ norm. We show that in the regime $n rho gg sqrtN$, any spectral method from a large class (and more generally, any low-degree of the input) fails to detect the planted vector.
arXiv Detail & Related papers (2021-05-31T16:10:49Z)

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