An enriched category theory of language: from syntax to semantics

Language is a compositional structure: expressions can be combined to make longer expressions. This is not a new idea. Theoretical linguists have studied grammatical structures for a long time — think, for example, of the richly developed field of formal grammars [Wik21]. Focusing on the compositionality, one may consider language as some kind of algebraic structure, perhaps simply as the free monoid on some set of atomic symbols quotiented by the ideal of all expressions that are not grammatically correct; or, perhaps, as something more operadic, resembling the tree-like structures of parsed texts, labelled with classes that can be assembled by some set of tree-grafting rules. In either case, the algebraist might identify the meaning of a word, such as “red” with the principal ideal of all expressions that contain “red.” The concept of red, then, is the ideal containing red ruby, bright red ruby, red hot chili peppers, red rover, blood red, red blooded, the workers’ and peasants’ red army, red meat, red firetruck,… If one knows every expression that contains a word, then, as the thinking goes, one understands the meaning of that word. One is then led to a geometric picture by an algebro-geometric analogy: construct a space whose points are ideals and view the algebraic structure as a sort of coordinate algebra on the space. From this perspective, language is a coordinate algebra on a space of meanings. This geometric picture points in appealing directions. If one can say the same kinds of things in different languages, then those languages should be regarded as having comparable ideal structures (or possibly equivalent categories of modules), translating between different languages involves a change of coordinates on the space of meanings, and so on. Going further, one has a way to model semantics via sheaves on this space of meanings, as Lawvere in his classic 1969 paper [Law69] about syntax-semantic duality.

We think this algebro-geometric picture is inspirational, but incomplete. Here, we furnish it with an important refinement. The compositional structure of language is only part of the structure that exists in language. What is missing is the distribution of meaningful texts. What has been, and what will be, said and written is crucially important. When one encounters the word “firetruck” it’s relevant that “red firetruck” has been observed more often than “green firetruck.” The fact that “red firetruck” is observed more often than “red idea” contributes to the meaning of red. Encountering an unlikely expression like “red idea” involves a shift in expectation that demands attention and contributes to the meaning of the broader context containing it. Again, the idea that distributional structure is important in language is not new. The so called distributional hypothesis [Har54] in linguistic states that linguistic items with similar distributions have similar meanings. In machine learning, word frequency counts have been employed to automatically extract knowledge from a text corpus in Latent Semantic Analysis and vector models of meaning [TP10].

So, the ideals mentioned above are just a first approximation for the space of meanings. In this paper, we formalize a marriage of the compositional structure of language with the distributional structure as a category enriched over the unit interval, which we denote by $\mathcal{L}$ and call the language syntax category. Then, once we have defined this language syntax category, we pass to the category of enriched copresheaves on $\mathcal{L}$, the objects of which are unit interval valued functions on $\mathcal{L}$ satisfying a certain monotonicity condition. The category $\widehat{\mathcal{L}}$ of enriched copresheaves, which is itself a category enriched over the unit interval, is the semantic category. Meanings reside in this semantic category, which also admits ways for meanings to be manipulated and combined to form higher semantic concepts.

Before we discuss why we are using category theory, let us comment briefly on two other efforts to study natural language using categorical methods. The DisCoCat program of [CSC10] seeks to combine compositional and distributional structures in a single categorical framework, though a choice of grammar is needed as input. In our work, syntactical structures are inherent within the enriched category theory and no grammatical input is required. This is motivated by the observation that LLMs can continue texts in a grammatically correct way without the additional input of a grammatical structure, suggesting that all important grammatical information is already contained in the enriched category. In short, the DisCoCat program aims to attribute meaning to parts of texts and grammatical rules for combining them to build meaning of larger texts. This is like the reverse of our work, which asserts that the meaning of small texts is derived from the distribution of larger texts that contain them. In [AS14], Abramsky and Sadrzadeh consider a sheaf theoretic framework for studying language. That work makes some interesting use of the gluing condition for sheaves. Here, we work with copresheaves, without any kind of gluing conditions, but the most important difference is that Abramsky and Sadrzadeh are not using the distributional structure that we are focused on here.

The algebraic perspective of viewing ideals as a proxy for meaning is consistent with a category theoretical perspective, and the latter provides a better setting in which to merge the compositional and distributional structures of language. But even before adding distributional structures, moving from an algebraic to a categorical perspective provides certain conceptual advantages that we highlight first.

Consider the category whose objects are elements of the free monoid on some finite set of atomic symbols, where there is a morphism $x\to y$ whenever $x$ is a substring of $y$, that is, when the expression $y$ is a continuation of $x$. If the finite set is taken to be a set of English words, for example, then there are morphisms red $\to$ red firetruck and red $\to$ bright red ruby and so on. Each string is a substring of itself, providing the identity morphisms, and composite morphisms are provided by transitivity: if $x$ is a substring of $y$ and $y$ is a substring of $z$, then $x$ is a substring of $z.$ This category is simple to visualize: it is thin, which is to say there is at most one morphism between any two objects, and so one might have in mind a picture like that in Figure 1. A consequence of the Yoneda lemma implies that a fixed object in this category is determined up to unique isomorphism by the totality of its relationships to all other objects in the category. One thus thinks of identifying an expression $x$ with the functor $h^{x}:=\hom(x,-)$ whose value on an expression $y$ is the one-point set $\ast$ if $x$ is contained in $y$ and is the empty set otherwise. The functor $h^{x}$ is an example of a copresheaf, the name given to a functor from a given category to the category of sets, and is in fact a representable copresheaf, represented by the object $x$. So in this way the preimage of $\ast$ is precisely the principal ideal generated by $x.$ Representable copresheaves, therefore, are comparable to principal ideals and both can be thought of as a first approximation for the meaning of an expression.

An immediate advantage to the shift in perspective is that the functor category of copresheaves $\widehat{\mathsf{C}}:=\mathsf{Set}^{\mathsf{C}}$ on any small category $\mathsf{C}$ is better behaved than $\mathsf{C}$ itself. It has all limits and colimits and is Cartesian closed. In fact, the category of copresheaves is a topos, which is known to be the appropriate setting for intuitionistic logic [MM12]. The full theory of toposes is not incorporated in this work, but intuition abounds when one takes inspiration from the field. Importantly, one has concrete operations for building new copreasheaves from representable ones, suggestive of the “meanings are composable instructions” perspective of internalist semantics [Pie18].

A preorder is a set together with a reflexive, transitive relation. Any preorder becomes a category whose objects are the elements of the set, with a single morphism from $a$ to $b$ if and only if $a$ is related to $b$. Reflexivity provides identity morphisms and transitivity provides composition of morphisms, which is defined in the only way it can be. Limits and colimits of finite diagrams always exists and are easy to compute: the limit is the minimum of the elements in the diagram and the colimit of a diagram is the maximum.

A monoid is a set together with an associative binary operation and a unit for that operation. A commutative monoid is a monoid whose operation is commutative. A preorder with a compatible commutative monoidal structure naturally becomes a kind of category over which one can enrich. Formally,

The unit interval $[0,1]:=\{x\in\mathbb{R}:0\leq x\leq 1\}$ is a commutative monoidal preorder with multiplication being the monoidal product, having $1$ as the unit, and with the usual $\leq$ relation being the preorder. The data of a $[0,1]$-category consists of a set of objects $\mathcal{C}$ and a $[0,1]$-valued function $(x,y)\mapsto\mathcal{C}(x,y)$ defined for every $x,y\in\mathcal{C}$ satisfying $\mathcal{C}(x,x)=1$ for every $x\in\mathcal{C}$ and $\mathcal{C}(y,z)\mathcal{C}(x,y)\leq\mathcal{C}(x,z)$ for all $x,y,z\in\mathcal{C}$.

The relevance is that a closed commutative monoidal preorder $\mathcal{V}$ becomes a category enriched over itself by replacing the hom set $\mathcal{V}(x,y)$, which is either the empty set or the one-point set, by the internal hom $[x,y]$, which is an object of $\mathcal{V}$. To see that the assignment $(x,y)\mapsto[x,y]$ does in fact make $\mathcal{V}$ a category enriched over itself, one needs to check that $1\leq[x,x]$ and $[y,z]\otimes[x,y]\leq[x,z]$. The first inequality follows from the fact that $1\otimes x\leq x$ and Equation (5). One can check that $[y,z]\otimes[x,y]\leq[x,z]$ in two steps. First, $[y,z]\leq[y,z]$ and Equation (5) gives $[y,z]\otimes y\leq z$ and similarly, $[x,y]\otimes x\leq y$. Putting these two inequalities together yields $[y,z]\otimes[x,y]\otimes x\leq z$ which implies $[y,z]\otimes[x,y]\leq[x,z]$. Much can be said about commutative monoidal preorders and enrichment, for instance, see [FS19, Chapter 2], though for now our primary focus will be on the unit interval.

While everything constructed using the internal hom in $[0,1]$ ultimately involves statements about multiplication and less than or equal to, trying to argue using only multiplication and order can get messy, as statements often break down into multiple cases owing to the minimum in truncated division. Using the fact that for all $a,b,c\in[0,1]$ we have

often makes arguments simpler. In what follows, we refer to the equivalence in (7) as the closure property of $[0,1]$. We occasionally will write $\min\{b/a,1\}$ when $a$ might be zero. The reader should interpret $b/0\geq 1$ for any $0\leq b\leq 1.$

Also, keep in mind that we use juxtaposition $ab$ for ordinary multiplication of numbers. For our purposes, this is shorthand for the monoidal product $a\otimes b.$ We also have the categorical product in $[0,1]$, which is given by the minimum. So, for two numbers $a,b\in[0,1]$ the expression $a\times b$ means $\min\{a,b\}.$ The coproduct is given by the maximum and is denoted by $a\sqcup b$. So, when we are working in the unit interval $[0,1]$, remember Equation (6) for the internal hom and

As a final remark, any thin category $\mathsf{C}$ can become a category enriched over $[0,1]$ by setting $\mathsf{C}(x,y)=1$ if there is a morphism between objects $x\to y$ and $\mathsf{C}(x,y)=0$ otherwise. In fact, $2:=\{0,1\}$, the set that contains zero and one only, is itself a commutative monoidal preorder that is closed, a sub-commutative monoidal preorder of the unit interval, and can serve as a base category over which to enrich.

Following [BV20], we now define a category $\mathcal{L}$ enriched over $[0,1]$.

So, for example, one might have

That $\mathcal{L}$ is indeed a category enriched over $[0,1]$ follows from the fact that $\pi(x|x)=1$ and

for all texts $x,y,z$ and so satisfies the required inequalities (3) and (4) with equalities. The reader might think of these probabilities $\pi(y|x)$ as being most well defined when $y$ is a short extension of $x$. While one may be skeptical about assigning a probability distribution on the set of all possible texts, it’s reasonable to say there is a nonzero probability that cat food will follow I am going to the store to buy a can of and, practically speaking, that probability can be estimated. Indeed, existing LLMs [RNSS18, RWC⁺18, B⁺20] successfully learn these conditional probabilities $\pi(y|x)$ using standard machine learning tools trained on large corpora of texts, which may be viewed as providing a wealth of samples drawn from these conditional probability distributions. Figure 2 gives the right toy picture: the objects are expressions in language, and the labels on the arrows describe the probability of extension.

As in the unenriched setting of Section 1.2, the category $\mathcal{L}$ is inherently syntactical—it encodes “what goes with what” together with the statistics of those expressions. But what about semantics? Following the same line of reasoning that led to the consideration of copresheaves in the unenriched case, we now wish to pass from $\mathcal{L}$ to the enriched version of copresheaves on $\mathcal{L}$ where we propose that meaning lies, and where concepts can again be combined through the enriched version of limits, colimits, and internal homs. This discussion first requires a few mathematical preliminaries, beginning with what an enriched functor is, what an enriched copresheaf is, and what the enriched version of natural transformations between functors are.

Before going on to the next section, we briefly comment on the work in [BV20]. In that paper, a $[0,1]$-enriched functor is defined between the syntax category $\mathcal{L}$ and another $[0,1]$-enriched category, embedding $\mathcal{L}$ as subcategory of a $[0,1]$-enriched category $\mathcal{D}$ consisting of “density” operators. In this paper we construct a category $\widehat{\mathcal{L}}$ of $[0,1]$-copresheaves on $\mathcal{L}$, and the enriched version of the Yoneda embedding defines an embedding ${\mathcal{L}}\to\widehat{\mathcal{L}}$. The reader may think of the $[0,1]$-enriched Yoneda embedding as factoring through the functor $\mathcal{L}\to\mathcal{D}$ defined in [BV20], as in the picture below:

While technical details are needed to construct the third arrow , one may think of the category $\mathcal{D}$ is a kind of intermediary. The logical and semantic possibilities within $\mathcal{D}$ are more limited than in the semantic $\widehat{\mathcal{L}}$. However, the category $\mathcal{D}$, as is argued in [BV20], can be approximated by a computer model, while providing more room for semantic exploration than in the syntactic category $\mathcal{L}$.

Lemma 2 says that enriched copresheaves form an enriched category. Lemma 3 says that each object defines a representable copresheaf. In this subsection, we see that the assignment $x\mapsto h^{x}$ defines an enriched functor that embeds (the opposite of) a $[0,1]$-category within its category of copresheaves. It is a corollary of an enriched Yoneda lemma.

Therefore, we have the expected interpretation of Corollary 1 as an enriched version of the (co)Yoneda embedding.

The op in $\mathcal{C}^{\text{op}}$ stands for “opposite” and is there because the assignment $x\mapsto h^{x}$ reverses morphisms, as in the statement of Corollary 1 above.

Often, when a mathematical object $Y$ has nice structure, the set of functions $\{X\to Y\}$ from a fixed $X$ has nice struture also, even if $X$ does not. Real valued functions on any set form a vector space, etc…. The unit interval has rich structure from the perspective of category theory. It is commutative monoidal closed and complete and cocomplete. For any $[0,1]$-enriched category $\mathcal{C}$, the category $\widehat{\mathcal{C}}=[0,1]^{\mathcal{C}}$ of copresheaves on $\mathcal{C}$, as a category of functors into the unit interval, inherits rich structure, as well. In particular, it has enriched versions of products, coproducts, and an internal hom. Corollary 2, from this perspective, says that any $[0,1]$-category embeds into the $[0,1]$-category $\widehat{\mathcal{C}}$, which is often much nicer.

We now look at the copresheaves on the enriched syntax category $\mathcal{L}$ which will provide a place for the combination of concepts in language in a way that’s parallel to the ideas explored in Section 1.2.

For each object $x$ in $\mathcal{L}$, the representable copresheaf $h^{x}:=\mathcal{L}(x,-)$ is given by the conditional probability of extending $x$,

where we use “$x\leq c$” as shorthand for “$x$ is contained as a subtext of $c$.”

The representable enriched copresheaf $h^{x}$ is our proposal for the meaning of the expression $x$. Its support consists of all expressions containing $x$, which coincides with the principal ideal associated to $x$, and $h^{x}$ further accounts for the statistics associated with those expressions, which is precisely the distributional structure missing from Section 1.2. In other words, the meaning of a text is the varying potential of all contexts in which it is used, making our definition of $h^{x}$ as the meaning of the text $x$ consistent with at least several philosophical traditions, including a use theory of meaning [Hor04] and dynamic semantics [NBvEV16]. The embedding in Corollary 2 assigns to a text $x$ its meaning $h^{x}$.

From a mathematical point of view, the assignment $x\mapsto h^{x}$ faithfully embeds the syntax category $\mathcal{L}$ into the category of copresheaves on $\mathcal{L}$. The category $\widehat{\mathcal{L}}$ is complete and cocomplete and so contains all (the enriched versions of) limits and colimits. The meanings of texts that live in $\widehat{\mathcal{L}}$ can be manipulated and combined to form higher concepts in $\widehat{\mathcal{L}}$, none of which is possible within the confines of $\mathcal{L}$. These operations on copresheaves are the subject of the next section.

The reversal of arrows in the $[0,1]$-enriched Yoneda Lemma has a nice interpretation here also. Suppose the text $y$ extends the text $x$ and $\mathcal{L}(x,y)=a\neq 0.$ We have the following picture:

On the left, the text $y$ is an extension of the text $x$ in the syntax category $\mathcal{L}$. Passing to the semantic category $\widehat{\mathcal{L}}$ on the right, $h^{x}$ is the meaning of the text $x$, which represents the varying potential contexts in which $x$ might appear, and $h^{y}$ represents the varying potential contexts in which the text $y$ appears. The contexts that $x$ can appear extend the contexts that in which $y$ can appear. Continuing an expression restricts the potential contexts in which the expression can be used.

The appropriate notion of limits and colimits in enriched category theory are called weighted limits and colimits. We focus on building intuition around limits as the discussion for colimits is analogous. Now, to understand weighted limits, it will first help to recall the defining isomorphism for ordinary limits, also called “conical limits.” To that end, let $\mathsf{J}$ be an indexing category and let $\mathsf{C}$ be any category. Recall that the limit of a diagram $F\colon\mathsf{J}\to\mathsf{C}$, if it exists, is an object $\lim F$ in $\mathsf{C}$ together with the following isomorphism of functors $\mathsf{C}\to\mathsf{Set}$,

which is natural in the first variable. Here, $\ast$ is used to denote the constant functor at the one-point set:

So for each object $Z$ in $\mathsf{C}$ there is a bijection $\mathsf{C}(Z,\lim F)\cong\mathsf{Set}^{\mathsf{J}}(\ast,\mathsf{C}(Z,F))$ and so “morphisms into the limit are the same as a cone over the diagram, whose legs commute with morphisms in the diagram,” and one has in mind the following picture.

Taking a closer look at the right-hand side of the isomorphism in (13), notice that for each object $Z$ in $\mathsf{C},$ a natural transformation from $\ast$ to $\mathsf{C}(Z,F)$ consists of a function $\ast=\ast(i)\to\mathsf{C}(Z,Fi)$ for each object $i$ in $\mathsf{J}$. This simply picks out a morphism $Z\to Fi$ in $\mathsf{C}$, and these morphisms comprise the legs of the limit cone over $\lim F$. Naturality ensures that these legs are compatible with the morphisms in the diagram.

With this background in mind, we now introduce weighted limits. The essential difference between the two constructions is that the constant functor in (14) is replaced with a so-called $\mathcal{V}$-functor of weights $W\colon\mathcal{J}\to\mathcal{V}$, where $\mathcal{V}$ is the base category over which enrichment takes place and where $\mathcal{J}$ is an indexing $\mathcal{V}$-category. Here is the formal definition.

So in other words, for each object $Z$ in $\mathcal{E}$ there is an isomorphism $\mathcal{E}(Z,\text{lim}_{W}F)\cong\mathcal{V}^{\mathcal{J}}(W,\mathcal{E}(Z,F))$ of objects in $\mathcal{V}$. The idea behind a weighted colimit is analogous. Given a $\mathcal{V}$-functor $F\colon\mathcal{J}\to\mathcal{E}$ and a $\mathcal{V}$-functor of weights $W\colon\mathcal{J}^{\text{op}}\to\mathcal{V}$, the weighted colimit of $F$ is an object $\operatorname{colim}_{W}F$ of $\mathcal{E}$ together with an isomorphism

Details may be found in [Rie14, Chapter 7].

Let’s unwind the isomorphism in (15) in the simple case when $\mathcal{V}=[0,1]$, when $\mathcal{E}=\widehat{\mathcal{L}}:=[0,1]^{\mathcal{L}}$, and when the indexing category $\mathcal{J}$ is a discrete category with two objects, call them $1$ and $2$, enriched over $[0,1]$ by setting $\mathcal{J}(i,j)=\delta_{ij}$ for $i,j\in\{1,2\}.$ To begin, fix a functor of weights $W\colon\mathcal{J}\to[0,1]$. This is nothing more than a choice of two numbers $w_{1}:=W(1)$ and $w_{2}:=W(2)$. Further, for a fixed pair of copresheaves $f,g:\mathcal{L}\to[0,1]$, define $F\colon\mathcal{J}\to\widehat{\mathcal{L}}$ to be the $[0,1]$-functor with $f:=F(1)$ and $g:=F(2)$.

Keeping in mind that products in intuitionist logic serve as a kind of conjunction, let’s look closer at the weighted product $(w_{1},f)\times(w_{2},g)$ in the case $f$ and $g$ are representable. Fix a pair of expressions $x$ and $y$ in $\mathcal{L}$ and a pair of nonzero weights $w_{1},w_{2}\in[0,1]$. The weighted product $(w_{1},h^{x})\times(w_{2},h^{y})\colon\mathcal{L}\to[0,1]$ assigns to an expression $c$:

Remembering Equation (12), the value of this minimum depends on whether the expressions $x$ and $y$ are jointly contained within $c$, and whether $\pi(c|x)\leq w_{1}$ and $\pi(c|y)\leq w_{2}$.

The support of this copresheaf thus coincides with the support of logical “and” in Boolean logic. As the weights decrease, the values of the quotients in Equation (19) increase and thus contribute less to the value of $w_{1}h^{x}(c)\times w_{2}h^{y}(c)$, which is a minimum. The copresheaf $(w_{1},h^{x})\times(w_{2},h^{y})$ captures something like a weighted conjunction.