LANGUAGE AS A MATRIX PRODUCT STATE

arXiv:1711.01416v1 [cs.CL] 4 Nov 2017

VASILY PESTUN1 , JOHN TERILLA2 , AND YIANNIS VLASSOPOULOS1
A BSTRACT. We propose a statistical model for natural language that begins by considering language as a monoid, then representing it in complex matrices with a compatible
translation invariant probability measure. We interpret the probability measure as arising
via the Born rule from a translation invariant matrix product state.

C ONTENTS
1. Introduction
1.1. Acknowledgements
2. The trace-density model for language
2.1. The structures in a corpus of text
2.2. Trace density representations
2.3. The trace-density model of a corpus of text
2.4. Graphical language for tensor networks
3. Density and identity constraints
3.1. The right density constraint
3.2. The left density constraint
4. Quantum physical interpretation of trace density models
5. Finding trace-density models
References

1
2
3
3
3
4
4
5
5
6
7
8
9

1. I NTRODUCTION
Statistical language modelling, whose aim is to capture the joint probability distribution of sequences of words, has applications to problems including information retrieval,
speech recognition, artificial intelligence, human-machine interfaces, translation, and natural language problems that involve incomplete information. Early successes of statistical
language models in industry include next-word prediction and vector embeddings of words
based on colocation with reasonable performance on word similiarity exams. Efforts to
build on early successes encounter difficulties arising from the high-dimensionality of the
data—the number of meaningful texts in a lanugage is exponentially smaller than the number of texts that a room full of randomly typing monkeys could produce [1]. One approach
to address “the curse of high-dimensionality” is to truncate sequences under consideration
to finite length phrases, or n-grams, and employ a hidden Markov model. Since hidden
Markov models essentially cutoff correlations between words beyond a fixed distance, the
1

I NSTITUT DES H AUTES É TUDES S CIENTIFIQUES (IH ÉS), B URES - SUR -Y VETTE , F RANCE
Q UEENS C OLLEGE AND CUNY G RADUATE C ENTER , T HE C ITY U NIVERSITY OF N EW Y ORK , N EW
Y ORK , NY
E-mail addresses: pestun@ihes.fr, jterilla@gc.cuny.edu, yvlassop@ihes.fr.
2

1

2

LANGUAGE AS A MATRIX PRODUCT STATE

success of this approach depends on the application. For example, 3-gram and 4-gram
models have been employed effectively for speech recognition and translation, applications in which very long distance correlations are of limited importance [2]. However,
n-gram models belie the essential critical behavior inherent in language [3]. Human languages, like many biological systems including families of proteins, genomes, neurons in
the brain, and the notes in a musical symphony, have significant long-range correlations
that decay with a power law [4–6]. In contrast, any Markov or hidden-Markov system,
such as an n-gram model, has long range correlations that decay exponentially.
Recently, long-short term memory (LSTM) recurrent neural networks have been employed to produce statistical language model applications that considerately outperform
those based on hidden Markov models. Notably, Google’s Neural Machine Translation
System [7] and the technology in Google Voice [8] have advanced the state of the art in
both translation and speech recognition. While much is unknown about how these deep
networks operate, new research indicates that it is hard to match long range and higher
order statistics of natural languages even with LSTM recurrent neural networks [9]. For
certain applications such as translating a few phrases, matching higher order statistics may
not be very important, but for other artificial intelligence applications, such as machine
determination of humorous or deceptive narratives, they are essential.
In order to develop a statistical language model capable of capturing the higher order statistics of language, we turn to quantum statistical physics, which contains models
such as solvable lattice models that exhibit correlation functions that decay with the power
law—the same kind of critical behavior as biological systems. Unlike classical statistical
physics, one spacial dimension suffices to exhibit criticality in quantum statistical physics
[10]. So, even a one dimensional quantum statistical language model could be a better alternative to LSTM recurrent neural networks, which may be likened to classical statistical
physics. Entanglement in a quantum many body system is the metaphorical vehicle for
statistical correlation in language, and serves as the proposed method to attack the highdimensionality of the data. The number of basis states in a quantum many body system
makes the state-space far too large to work with entirely but the number of physically relevant states occupy a subspace of exponentially smaller dimension, accessible by restricting
to low-energy.
In this paper, we introduce a simple translation-invariant quantum statistical language
model on a one-dimensional lattice which we call a trace-density model. While this tracedensity model isn’t critical, it is an experimental first step toward a critical quantum model
of language. The model involves matrix-product-states (MPS) which can approximate
power–law decays “over quite long distances” [11]. Two cubic constraintes are introduced.
These constraints are physically motivated and mathematically related to the moment map
of the action of the unitary group U(d) on complex d × n matrices. Training algorithms
based on maximizing entropy and minimizing energy, similar to what’s described in [12,
13] can be developed and density matrix renormalization [11] can be used. The model
is introduced first using representation theoretic language and then interpretted using the
physical language of MPS. A related language model based on an isometric tensor network
is considered in [14].
1.1. Acknowledgements. The authors would like to thank Maxim Kontsevich and Miles
Stoudenmire for helpful and stimulating discussions. The research of V.P. on this project
has received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation program (QUASIFT grant agreement 677368);

LANGUAGE AS A MATRIX PRODUCT STATE

3

J.T. was supported in part by a grant from the US Army, Research, Development and Engineering Command, Mathematical Sciences Division, 711567-MA-II; and Y.V. received
funding from Simons Foundation Award 385577.
2. T HE

TRACE - DENSITY MODEL FOR LANGUAGE

A mathematical model called a trace-density model for a corpus of text will be described
in three steps. First, the input structures related to a corpus of text will be explained and
some notation will be fixed. Second, the concept of a trace-density representation for a
corpus will be defined. Third, the property that a representation must possess in order to
be considered a trace-density model will be given.
2.1. The structures in a corpus of text. A corpus of text
C = wi1 wi2 · · · wiM

is a finite sequence of words from a vocabulary {w1 , . . . , wn } =: W(C). We refer to the
elements of the vocabulary as words, and denote typical words with the letter w, but the
vocabulary can be comprised of any symbols (letters, bits, ...) representing the atomic
elements from which the corpus is constructed as a sequence. Let X(C) denote the set of
all phrases contained in the corpus C, a phrase being a finite subsequence consisting of
adjacent elements. The set X(C) of phrases has more structure than merely a set. It is
graded—each phrase has a well defined length given by the number of words comprising
that phrase and the set of phrases is the disjoint union of sets phrases with same word
length:
X(C) =

M
G

k=1

Xk (C) where Xk (C) := {phrases in the corpus C consisting of k words.}

Also, X(C) has a (partially defined) product X(C) × X(C) → X(C) defined by concatanation of phrases. By adding a formal zero phrase to each graded component of X(C), the
product can be extended to all of X(C) by defining the product of two phrases to be zero if
the concatanation is not a phrase contained in the corpus. The product is compatible with
the grading
Xk (C) × Xl (C) → Xk+l (C).
Viewed with the structure, the set of phrases X(C) is a graded monoid, a quotient, in fact,
of the free monoid generated by the vocabulary W(C) = X1 (C).
Moreover, for each phrase length k, there is a probability distribution, call it q̂k , on the
set Xk (C). Explicitly, q̂k (x) is the number of times the phrase x = wi1 · · · wik appears in
the corpus C, divided by |Xk (C)|, the total number of phrases of length k. If the corpus is
sufficiently large, this probability distribution is considered an approximation to a nonexistent, idealized probability distribution on all phrases in the language, of which the corpus
is an observed sample. The goal is to model the collection of these idealized probability
distributions.
2.2. Trace density representations. A density on a Hilbert space is a positive semidefinite operator (in the scope of this paper we do not assume that density is normalized
by unit trace). Here, we fix a finite dimension d and work entirely with Cd with its standard inner product so that operators are identified with matrices. A d × d density P defines
a nonnegative real valued function on the set Matd×d (C) of d × d complex matrices by
M 7→ tr(MPM ∗ ). Here, the superscript ∗ denotes complex conjugate transpose and tr denotes trace. The (i, i) element of MPM ∗ is the nonegative real number hv, Pvi where v ∈ Cd

4

LANGUAGE AS A MATRIX PRODUCT STATE

is the i-th row of the matrix A, and tr(MPM ∗ ) is the sum of these numbers as v ranges over
the columns of A.
A d-dimensional trace density representation of a corpus C consists of the following
data:
(1) A pair of densities PL , PR on Cd such that tr PL PR = 1
(2) a function D : W(C) → Matd×d (C) called the dictionary.

The dictionary D assigns a d × d complex matrix Mi to each word wi in the vocabulary
and extends to a function X(C) → Md×d (C) on all phrases by mapping a phrase to the
product of matrices assigned to the words that comprise the phrase. That is, the phrase
x = wi1 · · · wik ∈ Xk (C) is mapped to the matrix M = Mi1 · · · Mik . The trace density of the
trace density representation is the nonegative, real valued function q : X(C) → R defined
as the composition:
q

X(C)

Md×d (C)

R

wi1 . . . wik

Mi1 · · · Mik


∗ 
tr PL Mi1 · · · Mik PR Mi1 · · · Mik

Notice that tr(PL MPR M ∗ ) ≥ 0 because for any two positive semi-definite operators P, Q
it holds that tr(PQ) ≥ 0 1, and MPR M ∗ is positive semi-definite operator.
2.3. The trace-density model of a corpus of text. A trace density representation for a
corpus of text C will be considered a trace density model for that corpus if the trace density
of a phrase approximates the probability of the phrase x appearing; that is, if q(x) ≈ q̂k (x)
for all phrases x ∈ Xk (C). The nature of the approximation and its dependence on k is left
vague.
A trace density model for a corpus C captures the joint probability distribution of sequences of words efficiently since all of the information is contained in the dicitonary D
that translates individual words to d × d matrices. The model requires no additional memory to store the matrices assigned to phrases, sentences, paragraphs, etc... Only a relatively
efficient computation is required: a matrix product that is polynomial in the dimension of
the representation and linear in the number of words.
Note also that a trace density model is translation invariant. The probability q(x) of the
phrase x appearing is independent of its position in the corpus.
2.4. Graphical language for tensor networks. Fix a corpus C with vocabulary W(C) =
{w1 , . . . , wn } and let W denote the complex n-dimensional vector space generated by the
vocabulary. Let V = Cd . The dictionary {wi 7→ Mi } of a d-dimensional trace-density
representation can be assembled into a single map M : W → Hom(V,V ) by extending the
assignment wi 7→ Mi linearly. The single map M is described by nd 2 complex numbers
{Miab } and defines a tensor of order (n, d, d). A particular number Miab and the entire
tensor M can be denoted graphically using a tensor network diagram as
1Indeed, for positive semi-definite operators P,Q let A and B be Hermtian operators such that P = A2 , Q = B2 ,
then tr PQ = tr AABB = tr BAAB = tr(AB)∗ AB

LANGUAGE AS A MATRIX PRODUCT STATE

5

i
a

b

These tensor network diagrams are oriented and rotating a labeled diagram upside down
indicates complex conjugation. Connected edges denote contraction of indices. In this
pictorial language, the following diagram represents the product of matrices Mi1 Mi2 · · · Mik
i1

ik

i2

···

∗ 
and the number q(wi1 · · · wik ) = tr PL Mi1 · · · Mik PR Mi1 · · · Mik
is depicted
···

i1

ik

i2
···

where the circular nodes depict the densities PL , PR . The presence of the particular indices i1 , . . . , ik indicates that they are not summed over. The condition that tr(PL PR ) = 1 is
pictured as
= 1.

3. D ENSITY AND

IDENTITY CONSTRAINTS

We now describe a pair of technically important constraints on a trace-density representation called the left density constraint and the right density constraint. These constraints
guarantee that a trace-density has the abstract properties required of the joint-probability
distributions on phrases in a language. These constraints also fit into a physical interpretation of our model which we describe in Section 4.
3.1. The right density constraint. Let C be a corpus of text with vocabulary W(C) =
{w1 , . . . , wn } of n words. Consider a d-dimensional trace-density representation of C with
density P and dictionary D that maps wi 7→ Mi . The trace-density representation satisfies
the right density constraint provided
n

(1)

∑ Mi PRMi∗ = PR

i=1

In tensor network notation, the density constraint is

=

6

LANGUAGE AS A MATRIX PRODUCT STATE

The trace-density q(x) of a phrase x is a nonnegative real number, but with no further a
priori restrictions. The density constraint (1), however, implies that the trace-density q of
a representation gives rise to probability distributions on the set of length k phrases Xk (C).
Proposition 1. If q is the trace density of a representation satisfying the density constraint
(1) then for every k = 1, 2, . . .
∑ q(x) = 1.
x∈Xk (C)

Proof. Applying trace to the density constraint says the sum of trace densities over all
vocabulary words is one:
!

∑

x∈X 1 (C)

n

n

n

i=1

i=1

i=1

q(x) = ∑ q(wi ) = ∑ tr(PL Mi PR Mi∗ ) = tr PL ∑ Mi PR Mi∗

= tr(PL PR ) = 1.

Here is the corresponding picture

=

=1

which, applied repeatedly, proves the theorem:
···
=

=1

···

3.2. The left density constraint. Let C be a corpus of text with vocabulary W(C) =
{w1 , . . . , wn } of n words. Consider a d-dimensional trace-density representation of C with
density P and dictionary D : wi 7→ Mi . The trace-density representation satisfies the left
density constraint provided
n

(2)

∑ Mi∗ PL Mi = PL .

i=1

The tensor network picture of the left density constraint is

=

Now, the right density constraint (1) together with the left density constraint (2) imply that the probability distributions defined by the trace-density fit together the way joint
probabilities for sequences of words do; the probability distributions for phrases of different length are related as marginal probability distributions.

LANGUAGE AS A MATRIX PRODUCT STATE

7

Proposition 2. If q is the trace density of a representation satisfying the density and identity constraints (1) and (2) and x is any phrase, then for every k, l = 1, 2, . . .
q(x′ xx′′ )

∑

q(x) =

x′ ∈Xk (C),x′′ ∈Xl (C)

Proof. For a fixed phrase x = wi1 · · · wis , the argument begins with the picture
···

···

···
is

i1
···

···

···

and repeatedly use the left density constraint to reduce the left and the right density constraint to reduce the right yielding
···
i1

ik

i2
···


Note that the left and right density constraints are cubic in the entries of the matrices PL , PR , M1 , . . . , Mn . Yet, these two constraints imply the infinitely many higher order
constraints stated in Proposition 1 and Proposition 2, which are required for the joint distributions determined by the trace-density to fit together the way they must for statistical
language model.
4. Q UANTUM

PHYSICAL INTERPRETATION OF TRACE DENSITY MODELS

This section relates a quantum physical interpretation of a trace density model for language. Imagine a word as a quantum system consisting of a single particle having n possible states—each word in the vocabulary being a possible state. Let W be the n-dimensional
complex vector space generated by the vocabulary W(C). The space W becomes a Hilbert
space with inner product defined by declaring that the vocabulary {w1 , . . . , wn } defines an
orthonormal, independent spanning set of basis vectors.
The Hilbert space for a quantum many body system consisting of k interacting particles
is W ⊗k with an orthonormal basis consisting of the nk vectors wi1 ,i2 ,...,ik := wi1 ⊗ wi2 ⊗ · · · ⊗
wik . A state of such a many body system is a unit trace density Q : W ⊗k → W ⊗k and the
probability that such a system is observed in the state wi1 ,...,ik is tr(QO) where O is the
projection on wi1 ,...,ik . A density Q : W ⊗k → W ⊗k induces a density on W ⊗ j → W ⊗ j for
j < k by partial trace.
The hypothesis is that language is well described statistically by a pure state density Q
in a tensor product of a very large number of copies of W , which means that there exists
ψ ∈ W ⊗k such that Q is projection operator on ψ .
A pure state ψ in a tensor product of copies of W is sometimes well approximated by
a matrix product state (MPS). This means that there are auxillary spaces V1 , . . . ,Vk and
vectors φ1 ∈ W ⊗ V1∗ , φ2 ∈ V1 ⊗ W ⊗ V2∗ , φ3 ∈ V2 ⊗ W ⊗ V3∗ , ..., φk−1 ∈ Vk−1 ⊗ W ⊗ Vk∗ ,

8

LANGUAGE AS A MATRIX PRODUCT STATE

φk ∈ Vk ⊗ W with ψ obtained from φ1 ⊗ φ2 ⊗ · · · ⊗ φk by contracting all adjacent Vi∗ ⊗ Vi
pairs in the expression
φ1 ⊗ φ2 ⊗ · · · ⊗ φk ∈ (W ⊗ V1∗ ) ⊗ (V1 ⊗ W ⊗ V2∗ ) ⊗ · · · ⊗ (Vk ⊗ W )

Note the decomposition of ψ as an MPS is not unique. Even for fixed auxillary spaces,
V1 , . . . ,Vk , there is a large gauge group acting the MPS decomposition. For example, automorphisms of each Vi act nontrivially on the MPS decomposition, while fixing the state ψ
obtained after contraction.
A trace-density model for language attempts to approximate the pure state ψ by a translation invariant MPS. Putting aside for the moment what happens at the far left and far right
boundaries, a translation invariant MPS involves a single auxillary space V of dimension d
(called the bond dimension) and a single tensor M ∈ V ⊗ W ⊗ V ∗ so that ψ is obtain from
M ⊗ · · · ⊗ M by contracting V ∗ ⊗ V in adjacent pairs. The space V ⊗ W ⊗ V ∗ is isomorphic to hom(W, hom(V,V )), precisely the data of a dictionary. Training of translationally
invariant MPS model is discussed in [15, 16].
Now, let us consider the boundary conditions. Assume ψ is a state in an essentially
infinite number of copies of W . Then, for any finite k, by partial trace, ψ induces a state
on W ⊗k . Tracing out the far left and far right yields a density as pictured below
···
···
···
···
···

···

···

···

···

···

Replacing the left and right boundaries by left and right densities, one obtains
···

···
Remark. Note that if PL is identity I so that
n

∑ Mi∗ Mi = I

(3)

i=1

then we can also interpret the collection (Mi )i=1,...,n as a collection of n measurement operators Mi : V → V on the Hilbert space V with unit trace density PR : V → V , see [17] page
102.
5. F INDING

TRACE - DENSITY MODELS

Trace-density representations satisfying both the right density and the left density constraints are plentiful. The simple trace-density representation consisting of
1
1
PL = I, PR = I, and M1 = M2 = · · · = Mn = √ I
n
n
shows that representations satisfying both the left density and the right density constraints
exist. To describe the moduli space of constrained representations, note that the left density
constraint has the form of the isometry constraint on M if the tensor M is considered as a

LANGUAGE AS A MATRIX PRODUCT STATE

9

map M : V → W ∨ ⊗ V with the standard Hermitian metric on W and Hermitian metric on
V defined by PL . So, for a fixed PL the space of isometric tensors M (i.e. those that satisfy
the left density constraint) form homogeneous space
(4)

U(nd)
U(nd − d)

Moreover, there is automorphism group U(d) on V preserving the Hermitian form. Modulo
action of the automorphism group the moduli space of tensors M that satisfy the left density
constraint is Grassmanian of d-dimensional complex planes in nd-dimensional complex
space W ∨ ⊗ V ≃ Cnd

U(nd)
U(nd − d)U(d)
Given a tensor M satisfying the left identity constraint, an appropriate positive density PR
that fits with the right density constraint can be found, as the following theorem proves.
(5)

Grd (Cnd ) =

Theorem 1. Let M be a tensor M of order (n, d, d) satisfying the left density constraint (2)
with PL . Then there exists a right density PR so that M together with PR satisfies the right
density constraint.
Proof. Let M be any tensor of order (n, d, d) and consider the operator M̂ : Matd×d →
Matd×d defined by
n

M̂(A) = ∑ Mi AMi∗ .
i=1

∗
(1) For any A, M̂(A) = M̂ (A∗ ) and so M̂ preserves self-adjoint matrices.
(2) For any v ∈ Cd , hM̂(A)v, vi = ∑ni=1 hMi∗ AMi v, vi = ∑ni=1 hAMv, Mvi and so M̂ preserves positive semi-definite matrices.
(3) We have tr(PL M̂(A)) = tr (PL ∑ni=1 Mi AMi∗ ) = tr (∑ni=1 Mi∗ PL Mi A) = tr(PL A) so if M
satisfies the left density constraint (2), the operator M̂ preserves the hyperlane in the space
of d × d matrices A defined by the linear equation tr(PL A) = 1.
Combining (1), (2) and (3) we obtain that M̂ is a map of the set APL of positive semidefinite self-adjoint matrices that satisfy constraint tr(PL A) = 1 to itself. Moreover, M̂ :
APL → APL is continuous because it is a linear operator.
Since the set APL is convex (a hyperplane section of a convex set of positive semidefinite operators), it is homeomorphic to a closed ball, then Brauer’s fixed point theorem

implies that there exists a density PR ∈ APL such that M̂(PR ) = PR .
The left density and right density constraints make it possible to numerically find a
trace-density model by a maximum log-likelihood algorithm [18]. The idea is to find
a trace-density representation that maximizes the (logarithm of the) trace-density for a
training corpus. Intuitively, the constraints make certain that the total trace density over
all possible phrases of a fixed length will equal one, and so maximizing the trace-densities
of the phrases in the corpus will automatically make the exponential number of nonsense
phrases have nearly zero trace-density.
R EFERENCES
[1] J. T. Goodman, “A bit of progress in language modeling,” Computer Speech and
Language 15 (2001), no. 4 403 – 434. 1
[2] A. D. Brown and G. E. Hinton, “Products of hidden markov models.,” in AISTATS,
Citeseer, 2001. 2

10

LANGUAGE AS A MATRIX PRODUCT STATE

[3] G. Zipf, Human behavior and the principle of least effort: an introduction to human
ecology. Addison-Wesley Press, 1949. 2
[4] R. Barbieri and M. Shimono, “Criticality in large-scale brain fmri dynamics
unveiled by a novel point process analysis,” Networking of Psychophysics,
Psychology and Neurophysiology (2012) 61. 2
[5] T. Mora and W. Bialek, “Are biological systems poised at criticality?,” Journal of
Statistical Physics 144 (2011), no. 2 268–302. 2
[6] Ł. Dȩbowski, “Is Natural Language Strongly Nonergodic? A Stronger Theorem
about Facts and Words,” ArXiv e-prints (June, 2017) 1706.04432. 2
[7] Y. W. et al., “Google’s neural machine translation system: Bridging the gap between
human and machine translation,” CoRR abs/1609.08144 (2016). 2
[8] H. Sak, A. W. Senior, and F. Beaufays, “Long short-term memory based recurrent
neural network architectures for large vocabulary speech recognition,” CoRR
abs/1402.1128 (2014). 2
[9] H. W. Lin and M. Tegmark, “Critical Behavior from Deep Dynamics: A Hidden
Dimension in Natural Language,” ArXiv e-prints (June, 2016) 1606.06737. 2
[10] V. Korepin, “Universality of entropy scaling in one dimensional gapless models,”
Phys. Rev. Lett. 92 (2004), no. 9. 2
[11] E. Miles Stoudenmire and D. J. Schwab, “Supervised Learning with
Quantum-Inspired Tensor Networks,” ArXiv e-prints (May, 2016) 1605.05775. 2
[12] R. Bailly, “Quadratic weighted automata:spectral algorithm and likelihood
maximization,” in Proceedings of the Asian Conference on Machine Learning (C.-N.
Hsu and W. S. Lee, eds.), vol. 20 of Proceedings of Machine Learning Research,
(South Garden Hotels and Resorts, Taoyuan, Taiwain), pp. 147–163, PMLR, 14–15
Nov, 2011. 2
[13] Z.-Y. Han, J. Wang, H. Fan, L. Wang, and P. Zhang, “Unsupervised Generative
Modeling Using Matrix Product States,” ArXiv e-prints (Sept., 2017) 1709.01662.
2
[14] V. Pestun and Y. Vlassopoulos, “Tensor network language model,” ArXiv e-prints
(Oct., 2017) 1710.10248. 2
[15] I. P. McCulloch, “Infinite size density matrix renormalization group, revisited,”
ArXiv e-prints (Apr., 2008) 0804.2509. 8
[16] G. M. Crosswhite, A. C. Doherty, and G. Vidal, “Applying matrix product operators
to model systems with long-range interactions,” Physics Review B 78 (July, 2008)
035116, 0804.2504. 8
[17] M. A. Nielsen and I. Chuang, Quantum computation and quantum information.
AAPT, 2002. 8
[18] R. Rosenfeld, “A maximum entropy approach to adaptive statistical language
modelling,” Computer Speech and Language 10 (1996), no. 3 187 – 228. 9

