Language Modeling with Reduced Densities

Statistical language models attempt to learn syntactic and semantic structure in language using the statistics of the language. Great progress has been made recently using neural network architectures RNSS (18); VSP⁺ (17); GGML (15); DCLT (19), although the problem of modeling the meaning of text—demonstrated, for instance, by a model’s ability to answer questions—is still unsolved. From a mathematical perspective, a number of questions remain unanswered: What mathematical structure captures the meaning of expressions in a natural language? How much of this structure can be sufficiently detected with corpora of text? Is there a way to naturally mine abstract concepts and their interrelations? How do logic and propositional entailment arise? Even so, today’s state of the art statistical language models are quite impressive for being built only from correlations in unstructured text data. This observation prompts a fundamental question that lies at the heart of this paper: What mathematical structure exists in unstructured text data? We propose that enriched category theory provides a natural home for the answer. In particular we show that sequences of symbols from a finite alphabet, such as those found in a corpus of text, form a category enriched over probabilities. Category theory thus gives a principled means of organizing “what goes with what” in a corpus of text along with the statistics of the resulting expressions—precisely the information used as input to today’s statistical language models. Equipped with this understanding, we then turn to another fundamental question: How can this information be stored and modeled in a way that preserves the categorical structure? In other words, what is a representation of this mathematical structure? We propose the answer lies in a functor from our enriched category of text to a particular enriched category of linear operators. Unwinding the details is the primary goal of this paper.

We have been led to these tools from a number of independent, yet complementary, viewpoints on mathematical structure in natural language. On meaning, we take inspiration from the Yoneda lemma in category theory, which informally states that a mathematical object is completely determined by the network of relationships that object has with other objects in its environment. In this way, two objects are isomorphic if and only if they share the same network of relationships. Putting this in the context of language, we view the meaning of a word as captured by the network of ways that word fits into other expressions in the language. In the words of linguist John Firth, “You shall know a word by the company it keeps” Fir (57). Distinguishing the meanings of words thus amounts to distinguishing the environments in which they occur in addition to, as we put forth in this paper, the statistics of these occurrences. Towards marrying these ideas, another viewpoint we take is that language exhibits both algebraic (or compositional) and statistical structure. Intuitively, language can be viewed as an algebra whose elements are expressions in the language and where the product of two expressions is their concatenation if the result is meaningful and is zero otherwise. Computing a representation of this algebra using statistical data in real-world text leads one directly to tensor networks PTV (17), which are factorizations of high-dimensional tensors often used for modeling states of complex quantum many body systems Orú (19); BC (17); Bia (19); Pen (71); Sch (11), a point revisited below.

What’s more, our algebraic viewpoint is not incompatible with our category theoretical one. For instance, the “network of ways a word fits into other expressions” may be identified with the two-sided ideal of that word. If the algebra were commutative, then we could think of language as a coordinate algebra on its spectrum whose points are the (prime) ideals of the algebra, and language would be considered as the coordinate algebra on the space of meanings (and so a translation would be a change of coordinates). A non-commutative version of this leads one to considering a category of modules, though this is a something to be studied in the future. Even so, algebraic structure alone is not sufficient to understand mathematical structure in language. Statistical features also play a vital role. Indeed, language exhibits long-distance correlations decaying with a power-law, and small-scale perturbations can propagate to all scales. For instance, changing a single word in an expression can change the entire meaning of the text: I’m going to the post office and I’m going postal have drastically different meanings. Such features are also characteristic of quantum critical systems LT (17), which are efficiently modeled by certain tensor networks. Inspiration also comes from a linguistic perspective, as Chomsky’s linguistic theory of generative grammars leads to tensor networks as soon as one tries to make them probabilistic GO (19); DeG (19).

The primary contributions of this work are theoretical, but let us emphasize a salient point about practical implementations. As alluded to above, the statistics in language observed in corpora of text resembles the same statistics observed in one-dimensional quantum critical systems, and the ground states of the latter are known to be well approximated by low rank tensor factorizations—see (LT, 17, and references therein) as well as KMH⁺ (20); GO (19); EV (11); PTV (17); PV (17). With this observation in mind, we therefore work under the premise that the linear operators in our framework can be approximated efficiently by tensor networks. Indeed, the ability of tensor network methods and algorithms to efficiently handle and store data in ultra large-dimensional spaces is well-understood—reviewing it here is beyond the scope of this paper, but see RL (19); Orú (19, 14); Ose (11) and references therein. Further note that such techniques have found a increasing success in machine learning in recent years, including anomaly detection, image classification, audio classification, language modeling, and more WRVL (20); SS (16); ST (19); MRT (21); RS (20); RL (19); MVRL (20); GPC (20); GJLP (18); CSS (16).

With this motivation in hand, the paper is organized as follows. Our model begins by viewing language as sequences from some finite vocabulary and by viewing the statistics of language as modeled by a probability distribution on this set. Section 2 recalls a particular passage from classical to quantum probability by modeling any probability distribution on a finite set of sequences as a particular rank 1 density operator. Section 2.2 focuses on the corresponding reduced density operators, which harness valuable statistical information about the original probability distribution. We review this information in the context of language. Section 3 builds on this framework to give the main construction, namely the assignment to any word or phrase $s$ a particular reduced density operator $\rho_{s}$. As seen in Corollary 3.1, this operator has the property that it decomposes as a weighted sum of reduced density operators—one associated to each meaningful expression in the language that contains $s$—where the weights are conditional probabilities of containment. As a result, $\rho_{s}$ captures something of the environment, or the “meaning,” of $s$ in a highly principled way. An immediate consequence is that the passage $s\mapsto\rho_{s}$ also preserves a certain hierarchical structure that is exhibited by expressions in language. In particular, Section 4 shows that both expressions in language and their associated operators form preordered sets. The former will be given by subsequence containment of consecutive symbols, for instance: red $\leq$ red rose. The latter will be given by the Loewner order, where we work with reduced densities $\hat{\rho}_{s}$ not normalized to unit trace. In addition to being a map of preorders, this assignment $s\mapsto\hat{\rho}_{s}$ also preserves statistics in a compatible way. Section 5 makes this statement precise using the language of category theory. We show that both the preorder of expressions $s$ and the preorder of their associated operators $\hat{\rho}_{s}$ can be equipped with the structure of categories enriched over the unit interval. The main result in Theorem 5.1 concludes that the passage $s\mapsto\hat{\rho}_{s}$ amounts to an enriched functor between these enriched categories.

Let $S$ be a finite set, and let $V=\mathbb{C}^{S}$ denote the free complex vector space generated by $S$. Concretely, the elements of $S$ define an orthonormal basis for $V$, and we will denote the basis vector associated to $s\in S$ using the same letter $s\in V$. If an ordering is chosen so that $S=\{s_{1},\ldots,s_{d}\}$, then by identifying each $s_{i}$ with the $i$th standard basis vector in $\mathbb{C}^{d}$ we have an isomorphism $V\cong\mathbb{C}^{d}$. This space has the usual inner product $\langle s_{i},s_{j}\rangle$, which is equal to $1$ if $i=j$ and is $0$ otherwise. Each vector $v\in V$ defines a linear functional $v^{*}\colon V\to\mathbb{C}$ defined by $v^{\prime}\mapsto\langle v,v^{\prime}\rangle$. We denote the vector space of such linear functionals on $V$ by $V^{*}:=\hom(V,\mathbb{C})$. Given a finite-dimensional space $W$, we may denote elements in the tensor product $V\otimes W$ with $vw$ in lieu of $v\otimes w.$ Note that each element $wv^{*}$ of the tensor product $W\otimes V^{*}$ corresponds to a linear map $V\to W$ defined by $v^{\prime}\mapsto w\langle v,v^{\prime}\rangle$. In particular, let $\operatorname{End}(V)$ denote the space of linear operators on $V$. Then for any unit vector $\psi\in V$, the vector $\psi\psi^{*}\in V\otimes V^{*}$ corresponds to an operator in $\operatorname{End}(V)$ that maps $\psi$ to itself and maps any vector orthogonal to $\psi$ to $0$. We will denote this orthogonal projection operator by $\text{Pr}_{\psi}$.

A density operator, or simply density, $\rho$ on a Hilbert space is a unit-trace, positive semidefinite operator. We will denote the latter property by $\rho\geq 0$. Density operators are also called quantum states and may be thought of as the quantum analogues of classical probability distributions. Indeed, every density $\rho$ on $V=\mathbb{C}^{S}$ defines a probability distribution $\pi_{\rho}\colon S\to\mathbb{R}$ on the set $S$ by the Born rule, where the probability of an element $s\in S$ is defined by $\pi_{\rho}(s):=\langle\rho s,s\rangle.$ These values are the diagonal entries of the matrix for $\rho$ in the basis provided by $S$. They are nonnegative since $\rho$ is positive semidefinite, and their sum is 1 since $\rho$ has unit trace. Going in the other direction, any probability distribution $\pi\colon S\to\mathbb{R}$ gives rise to a density on $V$ with the property that the Born distribution induced by it coincides with $\pi$. In fact there are multiple ways to define such a density. One could consider the maximal rank diagonal operator $\sum_{s}\pi(s)ss^{*}$, whose matrix representation contains the probabilities $\pi(s)$ along its diagonal and zeros elsewhere. In what follows, however, we focus on a rank 1 density operator—namely orthogonal projection onto a particular unit vector. Concretely, consider the following unit vector in $V$,

and let $\text{Pr}_{\psi}\colon V\to V$ denote the orthogonal projection operator onto $\psi$. This unit-trace operator is positive semidefinite and satisfies $\pi_{\text{Pr}_{\psi}}(s)=\langle\text{Pr}_{\psi}s,s\rangle=\sqrt{\pi(s)}^{2}=\pi(s)$ as claimed. The assignment $\pi\mapsto\text{Pr}_{\psi}$ provides for us a key passage from classical to quantum probability whose significance is seen when the probability distribution being modeled is a joint distribution. We elaborate below.

To assign reduced density operators to words and expressions from a language, we start with a joint probability distribution as in Section 2. There, we considered a product of two sets, thought of as prefixes and suffixes. In this discussion, we’ll consider a joint distribution on an $N$-fold product for $N\geq 2$. To this end, let $X$ be a finite ordered set consisting of the basic building blocks of a language. We’ll refer to elements of $X$ as words, though they may be characters, symbols, words, etc. Let $S=X^{N-1}\times X$ denote the set of all sequences of length $N\geq 2$. We write $S$ as a Cartesian product to obtain prefixes $(x_{i_{N-1}},\ldots,x_{i_{2}},x_{i_{1}})$ and suffixes $x_{a}$ so that each sequence $s\in S$ is a prefix-suffix pair $s=(x_{i_{N-1}}\cdots x_{i_{2}}x_{i_{1}},x_{a})$. As shown here, the concatenation $x_{i_{N-1}}\cdots x_{i_{2}}x_{i_{1}}$ will often be used in lieu of the tuple $(x_{i_{N-1}},\ldots,x_{i_{2}},x_{i_{1}})$. Further, the indices of a prefix are labeled starting from right to left: the right-most index is $i_{1}$ and the left-most index is $i_{N-1}$. Consistent with Section 2, words comprising prefixes are labeled with $i,j,\ldots$ while suffixes are labeled with $a,b,\ldots$. The set of suffixes $X$ may be replaced by $X^{k}$ for any $k\geq 1$, though we work with $k=1$ for simplicity. Any subsequence of consecutive words in a prefix is called a phrase, and a word is a phrase of length one. With this setup in mind, suppose $\pi\colon S\to\mathbb{R}$ is any probability distribution and consider the unit vector $\psi=\sum_{s\in S}\psi_{s}s$ with $\psi_{s}=\sqrt{\pi(s)}$ for each $s.$ Note that $\psi$ lies in the tensor product $\mathbb{C}^{S}\cong V^{\otimes N-1}\otimes V$ where $V=\mathbb{C}^{X}$, and so since each basis vector $s$ corresponds to a tensor product $s=x_{i_{N-1}}\cdots x_{i_{1}}x_{a}$ we may write

where the coefficients are the square root of probabilities $\psi_{i_{N-1}\cdots i_{1}a}=\sqrt{\pi(x_{i_{N-1}},\ldots,x_{i_{1}},x_{a})}$. Now consider the rank 1 density operator on $V^{\otimes N-1}\otimes V$ given by the orthogonal projection onto $\psi,$

Similarly as done in Equation (4), tracing out the prefix subsystem gives the reduced density ${\rho_{V}=\operatorname{tr}_{V^{\otimes N-1}}\text{Pr}_{\psi}\colon V\to\leavevmode\nobreak\ V}$, which has the following explicit description.

A slight modification of this expression gives rise to (unnormalized) reduced densities associated to phrases in $X^{N-1}$. Indeed, Equation (6) involves a sum over all prefixes, but suppose instead the sum is over all indices except those associated to a given phrase. For example, if $N=5$ and $x_{i_{2}}x_{i_{1}}$ is a fixed phrase of length 2, consider the following operator where the indices $i_{1}$ and $i_{2}$ are fixed.

This new operator may not have unit trace, though it is still positive semidefinite. We therefore view it as the unnormalized reduced density associated to the phrase $x_{i_{2}}x_{i_{1}}$. Informally, it is obtained by first composing the vector $x_{i_{2}}x_{i_{1}}$ with $\psi$ at the two sites directly adjacent to the suffix site, then forming the orthogonal projection onto this modified vector, and then tracing out the remaining prefix indices $i_{3}$ and $i_{4}$. The tensor network diagrams in Figure 1 illustrate this relationship between $\psi$ and $\rho_{V}$ and $\hat{\rho}_{x_{i_{2}}x_{i_{1}}}$. This construction is summarized in Definition 3.1 below and an example is given in Example 2. Afterwards, we will show that renormalizing $\hat{\rho}_{x_{i_{2}}x_{i_{1}}}$ to a unit-trace operator $\rho_{x_{i_{2}}x_{i_{1}}}$ will capture the conditional probability distribution on the set of suffixes of $x_{i_{2}}x_{i_{1}}$ in a principled way.

Further observe that Definition 3.1 and Lemma 3.1 only regard those phrases that occur adjacent to a suffix. One can also associate reduced densities to phrases that occur in any position in a sequence (for instance, see the discussion surrounding Figure 3) and find an analogous decomposition. We omit this more general discussion to streamline the presentation.

In the example below, we consider a toy corpus containing five phrases of length four. Each phrase will correspond to a sequence in a four-fold Cartesian product of different sets $A\times B\times C\times D$ rather than the same set $X\times X\times X\times X$, as one might use in practice. This minor adjustment will simply keep the example tidy (for instance, it allows us to consider a $2\times 2$ matrix rather than a sparse $8\times 8$ matrix) while still illustrating the theory.