Interpreting a matrix-valued word embedding with a mathematically proven characterization of all optima

[Joseph Van Name]

In this post, I shall first describe a new word embedding algorithm that I came up with called a matrix product optimized (MPO) word embedding, and I will prove a theorem that completely interprets this word embedding in the simplest case. While it is probably infeasible to mathematically characterize a word embedding with a mathematical proof when the corpus is something that one encounters in practice, this theorem should be a signal that such a word embedding (or a similar word embedding) should be interpretable and mathematical in other ways as well. This theorem also illustrates the way that MPO word embeddings should behave.

Unlike most word embedding algorithms, MPO word embeddings are matrix-valued so that they map tokens to matrices instead of simply mapping tokens to vectors. In our case, the matrices are not necessarily real matrices as they may be complex or even quaternionic matrices. MPO word embeddings also differ from other word embedding algorithms in that they are not constructed using neural networks though we still use gradient ascent.

Why MPO word embeddings?

Since tokens often have many meanings depending on context, it seems better to represent a token in a form where it is easy or easier to separate the individual meanings of a token. While vectors may be good for representing individual meanings of tokens, it is better to represent a polysemantic token as a matrix instead of a vector. If someone were to give me a task of interpreting a word embedding, I would be much happier if the word embedding were a matrix-valued word embedding that neatly organized each of the meanings of a polysemantic token into a matrix than if the word embedding were a vector-valued word embedding where each of the individual meanings of the token were awkwardly smushed together in a vector.

Spaces of matrices have additional structure that is lacking in vector spaces, and one can use this additional structure to analyze or interpret our word embedding. This additional structure also means that matrix-valued word embeddings should behave more mathematically than vector-valued word embeddings.

MPO word embeddings also satisfy some interesting properties. Let ${\chi }_A$ denote the fitness level of a random MPO word embeddings that we obtain from the set $A$ where $A$ consists of the corpus that we are training our word embedding on along with a couple of hyperparameters. Then the random variable ${\chi }_A$ will often have very low entropy or even zero entropy. Since ${\chi }_A$ often has zero/​low entropy, trained MPO word embeddings will not contain any/​much random information that was not already present in the training data. It will be easier to interpret machine learning models when the trained model only depends on the training data and hyperparameters and which does not depend on random choices such as the initialization. Quaternionic and complex MPO word embeddings will often become real word embeddings after a change of basis. This means that MPO word embeddings behave quite mathematically, and it seems like machine learning models that behave in ways that mathematicians like would be more interpretable and understandable than other machine learning models.

Quaternionic matrices:

In this section, we shall go over the basics of quaternionic matrices. I assume that the reader is already familiar with ideas in linear algebra up through the singular value decomposition. Much of the basic theory of quaternionic matrices is a straightforward generalization of the theory of complex matrices. I hope you are also familiar with the quaternions, but if you are not, then I will remind you the definition and basic facts about quaternions. We refer the reader to [1] for facts about quaternions. You may skip this section if you simply care about the real and complex cases.

If $A$ is a square real, complex, or quaternionic matrix, then the spectral radius of $A$ is

$\rho \left(A\right)={lim}_{n\to \infty }\parallel A^n{\parallel }^{1/n}$ where $\parallel \cdot \parallel$ is any matrix norm (since we are taking the limit, it does not matter which matrix norm we choose). If $A$ is a real or complex matrix, then

$\rho \left(A\right)=max\{|\lambda |:\lambda \text{is an eigenvalue of}A\}$. The same fact holds for quaternionic matrices, but we have to be careful about how we define the eigenvalues of quaternionic matrices due to non-commutativity.

The division ring $H$ of quaternions is the 4-dimensional associative but non-commutative algebra over the field of real numbers spanned by elements $1,i,j,k$ (so $H=\{a+bi+cj+dk:a,b,c,d\in R\}$) where quaternionic multiplication is the unique associative (but non-commutative) bilinear operation such that $i^2=j^2=k^2=ijk=-1$. We observe that if $\lambda \in R,\mu \in H$, then $\lambda \mu =\mu \lambda$. It is easy to show that $ij=k,jk=i,ki=j,ji=-k,kj=-i,ik=-j$.

Recall that the conjugate and the absolute value of a quaternion are defined by

$\overline{a+bi+cj+dk}=a-bi-cj-dk$ and $|a+bi+cj+dk|=\sqrt{a^2+b^2+c^2+d^2}$ whenever $a,b,c,d\in R$. If $u,v\in H$, then $\overline{u}\cdot \overline{v}=\overline{v\cdot u}$ and $|u|\cdot |v|=|u\cdot v|$. Observe that the field of complex numbers $C=\{a+bi:a,b\in R\}$ is a subring of $H$.

If $A=(a_{i,j}{)}_{i,j}$ is a quaternionic matrix, then define the adjoint of $A$ to be $A^{\ast }=(\overline{a_{j,i}}{)}_{i,j}$. While the adjoint of a quaternionic matrix is well-behaved, the transpose of a quaternionic matrix is not very well behaved since we typically have $A^T{B}^T\ne (BA{)}^T$ but $A^{\ast }{B}^{\ast }=(BA{)}^{\ast }$ for quaternionic matrices $A,B$.

We shall now associate $m\times n$-quaternionic matrices with $2m\times 2n$-complex matrices.

Suppose that $A_1,A_2$ are $m\times n$-complex matrices. Then the associated quaternionic complex matrix of the quaternionic matrix $A=A_1+A_2\cdot j$ is the complex matrix

${\chi }_A=\left[\begin{array}{cc}{A}_1& A_2\\ -\overline{A_2}& \overline{A_1}\end{array}\right]$. We observe that ${\chi }_{A+B}={\chi }_A+{\chi }_B$, and ${\chi }_{AB}={\chi }_A{\chi }_B$, and ${\chi }_{A^{\ast }}=({\chi }_A{)}^{\ast }$ whenever $A,B$ are quaternionic matrices and the operations are defined.

An eigenvalue of a quaternionic matrix $A$ is a quaternion $\lambda$ such that $Ax=x\cdot \lambda$ for some non-zero vector $x$.

Observation: If $\lambda$ is an eigenvalue of a quaternionic matrix $A$ corresponding to the eigenvector $x$ and $\mu$ is an eigenvalue of a quaternionic matrix $B$ corresponding to the same eigenvector $x$, then $ABx=Ax\mu =x\lambda \mu$, so $\lambda \mu$ is an eigenvector of the quaternionic matrix $AB$.

Observation: If $\lambda$ is an eigenvalue of a product of quaternionic matrices $AB$ and$ABx=x\lambda$, then $\left(BA\right)\left(Bx\right)=\left(Bx\right)\lambda$, so if $Bx\ne 0$, then $\lambda$ is also an eigenvalue of $BA$. In particular, $AB$ and $BA$ have the same non-zero eigenvalues.

Observation: If $A$ is a quaternionic matrix and $\lambda$ is an eigenvalue of $A$, then whenever $\mu$ is a non-zero quaternion, the value ${\mu }^{-1}\lambda \mu$ is also an eigenvalue of $A$.

Proof: If $\lambda$ is an eigenvalue of $A$, then there is some non-zero quaternionic vector $x$ with $Ax=x\lambda$. Therefore, set $y=x\mu$. Then $Ay=Ax\mu =x\lambda \mu =y\mu \lambda {\mu }^{-1}$, so ${\mu }^{-1}\lambda \mu$ is an eigenvalue of the quaternionic matrix $A$. $\square$

Let $G$ denote the group of all quaternions $\lambda$ with $|\lambda |=1$. Let $\text{SU}\left(n\right)$ denote the group of all $n\times n$-unitary matrices with determinant $1$. Let $\text{O}\left(n\right)$ denote the group of all—$n\times n$orthogonal matrices. Then the mapping $\lambda \mapsto {\chi }_{\lambda }$ is an isomorphism from $G$ to $\text{SU}\left(2\right)$. Let $V$ be the vector subspace of $H$ consisting of all elements of the form $ai+bj+ck$ where $a,b,c$ are real numbers. Then $V$ is an inner product space where inner product is the standard dot product operation on $V$ where $⟨ai+bj+ck,ri+sj+tk⟩=ar+bs+ct$ and where $⟨\lambda ,\mu ⟩=-\text{Re}\left(\lambda \mu \right)$ for quaternions $\lambda ,\mu \in V$). Then we can identify $\text{O}\left(3\right)$ with the linear transformations that preserve this inner product. We may now define a group homomorphism $\varphi :G\to \text{O}\left(3\right)$ by letting $\varphi \left(\lambda \right)\left(\mu \right)=\lambda \mu {\lambda }^{-1}$. Then the homomorphism $\varphi$ is a surjective homomorphism. In fact, $\text{O}\left(3\right)$ is a connected Lie group with ${\pi }_1\left(\text{O}\right(3\left)\right)\simeq Z_2$, and the group $G$ is simply connected; $G$ is the universal cover of the lie group $\text{O}\left(3\right)$. From these facts about quaternions, we may make a few observations:

Observation: If ${\lambda }_1,{\lambda }_2$ are quaternions, then there is some $\mu$ with ${\lambda }_2=\mu {\lambda }_1{\mu }^{-1}$ if and only if $\text{Re}\left({\lambda }_1\right)=\text{Re}\left({\lambda }_2\right)$ and $|{\lambda }_1|=|{\lambda }_2|$.

Observation: Suppose that $A$ is a square quaternionic matrix and ${\lambda }_1,{\lambda }_2$ are quaternions with $\text{Re}\left({\lambda }_1\right)=\text{Re}\left({\lambda }_2\right)$ and $|{\lambda }_1|=|{\lambda }_2|$. Then ${\lambda }_1$ is an eigenvalue of $A$ if and only if ${\lambda }_2$ is an eigenvalue of $A$.

Observation: Suppose that $x$ is a quaternionic vector, and $x_1,x_2$ are complex vectors with $x=x_1+x_2\cdot j$. Suppose furthermore that $\lambda$ is a complex number. Then $Ax=x\lambda$ if and only if ${\chi }_A\left[\begin{array}{c}{x}_1\\ -\overline{x_2}\end{array}\right]=\lambda \left[\begin{array}{c}{x}_1\\ -\overline{x_2}\end{array}\right]$. In particular, $\lambda$ is an eigenvalue of $A$ if and only if $\lambda$ is an eigenvalue of ${\chi }_A$.

Observation: Let $A$ be a square quaternionic matrix. Then the following quantities are equivalent:

1. $\rho \left({\chi }_A\right)$

2. ${lim}_{n\to \infty }\parallel A^n{\parallel }^{1/n}$

3. $max\{|\lambda |:\lambda \text{is an eigenvalue of}A\}$.

We shall therefore define the spectral radius of a square quaternionic matrix $A$ to be $\rho \left({\chi }_A\right)$ (or any of the quantities in the above observation).

If $A$ is a quaternionic matrix, then we say that $A$ is Hermitian, normal, or unitary respectively if ${\chi }_A$ is Hermitian, normal, or unitary. If $A$ is an $n\times n$-quaternionic matrix, then $A$ is Hermitian iff $A=A^{\ast }$, and $A$ is normal iff $A{A}^{\ast }=A^{\ast }A$, and $A$ is unitary iff$1_n=A{A}^{\ast }=A^{\ast }A$.

If $u,v$ are quaternionic column vectors, then define the quaternionic inner product $⟨u,v{⟩}_H$ of $u,v$ by $⟨u,v{⟩}_H=v^{\ast }u$. We observe that the quaternionic inner product is real bilinear and conjugate symmetric $⟨u+v,w{⟩}_H=⟨u,w{⟩}_H+⟨v,w{⟩}_H$,$⟨u,v{⟩}_H=\overline{⟨v,u{⟩}_H}$. The quaternionic inner product preserves right scalar multiplication $⟨u\lambda ,v{⟩}_H=⟨u,v{⟩}_H\lambda$. We define the real inner product of two quaternionic vectors by setting$⟨u,v{⟩}_R=\text{Re}\left(v^{\ast }u\right)=\frac{1}{2}(u^{\ast }v+v^{\ast }u)=\text{Re}(⟨u,v{⟩}_H)=\frac{1}{2}(⟨u,v{⟩}_H+⟨v,u{⟩}_H)$. We may recover the quaternionic inner product from the real-valued inner product since $⟨u,v{⟩}_H=⟨u,v{⟩}_R-⟨ui,v{⟩}_{R}i-⟨uj,v{⟩}_{R}j-⟨uk,v{⟩}_{R}k$ for quaternionic vectors $u,v$.

Observation: If $u,v$ are quaternionic vectors, then $\rho \left(u{v}^{\ast }\right)=|v^{\ast }u|=|⟨u,v{⟩}_H|$ and $\parallel u{v}^{\ast }{\parallel }_p=\parallel u\parallel \cdot \parallel v\parallel$ for $1\le p\le \infty$.

Observation: Suppose $u,v$ are quaternionic vectors. Then $|⟨u,v{⟩}_H|\le \parallel u\parallel \cdot \parallel v\parallel$.

Observation: Suppose $u,v$ are non-zero quaternionic vectors. If $|⟨u,v{⟩}_H|=\parallel u\parallel \cdot \parallel v\parallel$, then $v\gamma =u$ for some quaternion $\gamma$.

Counterexample: In general, if $\alpha$ is a non-zero quaternion, and $u$ is a quaternionic vector, then $\parallel (\alpha u{)}^{\ast }u\parallel \ne \parallel \alpha u\parallel \cdot \parallel u\parallel$.

Observation: Let $A$ be an $m\times n$ quaternionic matrix, and let $B$ be an $n\times m$-quaternionic matrix. Then the following are equivalent:

1. $A=B^{\ast }$

2. $⟨Au,v{⟩}_H=⟨u,Bv{⟩}_H$ for all quaternionic vectors $u,v$.

3. $⟨Au,v{⟩}_R=⟨u,Bv{⟩}_R$ for all quaternionic vectors $u,v$.

Proposition: Let $A$ be a quaternionic matrix. Then the following are equivalent:

1. $⟨Au,Av{⟩}_H=⟨u,v{⟩}_H$ for all quaternionic vectors $u,v$.

2. $⟨Au,Av{⟩}_R=⟨u,v{⟩}_R$ for all quaternionic vectors $u,v$.

3. $\parallel Au\parallel =\parallel u\parallel$ for all quaternionic vectors $u$.

4. $A^{\ast }A=I$

5. ${\chi }_A$ is an isometry.

If $A$ is a square quaternionic matrix, then the above statements are all equivalent to the following:

6.$A$ is unitary.

Theorem: (quaternionic singular value decomposition) If $A$ is a quaternionic matrix, then there exists quaternionic unitary matrices $U,V$ where $UAV$ is a diagonal matrix $D$ with non-negative real non-increasing diagonal entries.

In the above theorem, the diagonal entries in $D$ are called the singular values values of $A$ and they are denoted by ${\sigma }_1\left(A\right),\dots ,{\sigma }_n\left(A\right)$ where ${\sigma }_1\left(A\right)\ge \cdots \ge {\sigma }_n\left(A\right)$.

If $A$ is a real, complex, or quaternionic matrix, and $1\le p\le \infty$ then define the Schatten $p$-norm of $A$ to be $\parallel A{\parallel }_p=\parallel \left({\sigma }_1\right(A),\dots ,{\sigma }_n(A\left)\right){\parallel }_p$ where we define $\parallel (x_1,\dots ,x_n){\parallel }_p=(|x_1{|}^p+\cdots +|x_n{|}^p{)}^{1/p}$ for $1\le p<\infty$ and $\parallel (x_1,\dots ,x_n){\parallel }_{\infty }=max(|x_1|,\dots ,|x_n|)$.

Observation: If $A$ is a quaternionic matrix with singular values $\left({\sigma }_1\right(A),\dots ,{\sigma }_n(A\left)\right)$, then ${\chi }_A$ has singular values $\left({\sigma }_1\right(A),{\sigma }_1(A),{\sigma }_2(A),{\sigma }_2(A),\dots ,{\sigma }_n(A),{\sigma }_n(A\left)\right)$. In particular,$\parallel A{\parallel }_{\infty }=\parallel {\chi }_A{\parallel }_{\infty }$ and $\parallel {\chi }_A{\parallel }_p=2^{1/p}\cdot \parallel A{\parallel }_p$, so $\parallel A{\parallel }_p=2^{-1/p}\cdot \parallel {\chi }_A{\parallel }_p$ whenever $1\le p<\infty$.

Observation: If $A$ is a quaternionic matrix, then $\parallel A{\parallel }_{\infty }=max\frac{\parallel Av\parallel }{\parallel v\parallel }$.

If $A$ is an $n\times n$-quaternionic matrix, then define the quaternionic trace of $A$ as

$\text{HTr}\left(A\right)={\sum }_{r=1}^n{a}_{r,r}$. In general, $\text{HTr}\left(AB\right)\ne \text{HTr}\left(BA\right)$, so the notion of the quaternionic trace is deficient.

If $A$ is an $n\times n$-quaternionic matrix, then define the real trace of $A$ as$\text{RTr}\left(A\right)={\sum }_{r=1}^n\text{Re}\left(a_{r,r}\right).$ We observe that $\text{Tr}\left({\chi }_A\right)=2\text{RTr}\left(A\right)$ and$\text{RTr}\left(AB\right)=\text{RTr}\left(BA\right)$ whenever $A,B$ are quaternionic matrices.

Observe that we can recover $\text{HTr}$ from $\text{RTr}$ by using the formula $\text{HTr}\left(A\right)=\text{RTr}\left(A\right)-i\cdot \text{RTr}(i\cdot A)-j\cdot \text{RTr}(j\cdot A)-k\cdot \text{RTr}(k\cdot A)$.

If $A,B$ are $n\times n$-quaternionic matrices, then define the real-valued Frobenius inner product $⟨A,B{⟩}_R$ as $⟨A,B{⟩}_R=\text{RTr}\left(A{B}^{\ast }\right)$.

If $A=(a_{r,s}+b_{r,s}i+c_{r,s}j+d_{r,s}k{)}_{r,s}$ and $B=(w_{r,s}+x_{r,s}i+y_{r,s}j+z_{r,s}k{)}_{r,s}$ where every $a_{r,s},b_{r,s},c_{r,s},d_{r,s},w_{r,s},x_{r,s},y_{r,s},z_{r,s}$ is real, then

$⟨A,B{⟩}_R={\sum }_{r,s}{a}_{r,s}{w}_{r,s}+b_{r,s}{x}_{r,s}+c_{r,s}{y}_{r,s}+d_{r,s}{z}_{r,s}$. Define $\parallel A{\parallel }_R=\sqrt{⟨A,A{⟩}_R}$.

We observe that if $U,V$ are unitary, then $\parallel UAV{\parallel }_R^2=⟨UAV,UAV⟩=\text{RTr}\left(UAV\right(UAV{)}^{\ast })$

$=\text{RTr}\left(UAV{V}^{\ast }{A}^{\ast }{U}^{\ast }\right)=\text{RTr}\left(AV{V}^{\ast }{A}^{\ast }{U}^{\ast }U\right)=\text{RTr}\left(A{A}^{\ast }\right)=\parallel A{\parallel }_R^2$.

In particular, if $A=UDV$ where $U,V$ are unitary and $D$ is diagonal with diagonal entries ${\sigma }_1\left(A\right)\ge \cdots \ge {\sigma }_n\left(A\right)$, then $\parallel A{\parallel }_R^2=\parallel D{\parallel }_R^2={\sigma }_1(A{)}^2+\cdots +{\sigma }_n(A{)}^2=\parallel A{\parallel }_2^2$.

MPO word embeddings

Let $K$ denote either the field of real numbers, complex numbers, or the division ring of quaternions. Let $A$ be a finite set (in our case, $A$ will denote the set of all tokens). Let $Q_d(K;A)$ be the set of all functions $f:A\to M_d\left(K\right)$ such that ${\sum }_{a\in A}f\left(a\right)f(a{)}^{\ast }=1_d$. Observe that $Q_d(K;A)$ is compact. Define a function $L_{d,K}:A^{\ast }\times Q_d(K;A)\to [0,\infty )$ by letting $L_{d,K}(a_1\dots a_n,f)=\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}$. We say that $f$ is an MPO word pre-embedding for the string of tokens $a_1\dots a_n$ if the quantity $L_{d,K}(a_1\dots a_n,f)$ is locally maximized. To maximize $L_{d,K}(a_1\dots a_n,f)$, the function $f$ must simultaneously satisfy two properties. Since ${\sum }_{a\in A}f\left(a\right)f(a{)}^{\ast }=1_d$, the matrices $\left(f\right(a){)}_{a\in A}$ must be spread out throughout all the $d$ dimensions. But we also need for the matrices $f\left(a_r\right)$ to be compatible with $f\left(a_{r-1}\right)$ and $f\left(a_{r+1}\right)$ and more generally with $f\left(a_s\right)$ for $s$ near $r$.

We say that a collection of vectors $(v_1,\dots ,v_n)$ is a tight frame if$v_1{v}_1^{\ast }+\cdots +v_n{v}_n^{\ast }=\lambda \cdot 1_d$ for some necessarily positive constant $\lambda$. We say that a tight frame $(v_1,\dots ,v_n)$ is an equal norm tight frame if $\parallel v_1\parallel =\cdots =\parallel v_n\parallel$.

Theorem: Suppose that $d\le n$. Let $K$ denote either the field of real numbers or complex numbers. Let $S$ denote the unit sphere in $K^d$. Then the local minimizers of the frame potential $FP:S^n\to [0,\infty )$ defined by $FP(v_1,\dots ,v_n)={\sum }_{j=1}^n{\sum }_{k=1}^n|⟨v_j,v_k⟩{|}^2$ are global minimizers which are tight frames for $K^d$. In particular, there exists an equal norm tight frame $v_1,\dots ,v_n\in R^d$ whenever $d\le n$.

See [2, Thm 6.9] for a proof.

Theorem: Suppose that $K$ is the field of real numbers, complex numbers, or the division ring of quaternions. Let $|A|=n,A=\{a_1,\dots ,a_n\}$. Then $L_{d,K}(a_1\dots a_n,f)\le \sqrt{d/n}$ and $L_{d,K}(a_1\dots a_n,f)=\sqrt{d/n}$ if and only if there is an equal norm tight frame $(u_1,\dots ,u_n)$ with $\parallel u_1\parallel =\cdots =\parallel u_r\parallel =1$ and ${\alpha }_1,\dots ,{\alpha }_n\in K$ with $|{\alpha }_1|=\cdots =|{\alpha }_n|=\sqrt{d/n}$ where $f\left(a_r\right)=u_r(u_{r+1}{\alpha }_{r+1}{)}^{\ast }$ for all $r$ (where addition in the subscripts is taken modulo $r$).

Proof: In order to not repeat ourselves, our proof shall apply to all three cases: $K=R,K=C,K=H$, but for accessibility purposes, the proof shall be understandable to those are only familiar with real and/​or complex matrices.

Suppose that $(u_1,\dots ,u_n)$ is an equal norm tight frame with $\parallel u_1\parallel =\cdots =\parallel u_n\parallel =1$, ${\alpha }_1,\dots ,{\alpha }_n\in K$ are elements with $|{\alpha }_1|=\cdots =|{\alpha }_n|=\sqrt{d/n}$ and $v_r=u_{r+1}{\alpha }_{r+1}$ for all $r$. Since $\text{RTr}(1_d\cdot (n/d\left)\right)=n$ and $\text{RTr}(u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })=\parallel u_1{\parallel }^2+\cdots +\parallel u_n{\parallel }^2=n$, we have $u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast }=\left(n/d\right)\cdot 1_d$. Therefore,

$f\left(a_1\right)f(a_1{)}^{\ast }+\cdots +f(a_n\left)f\right(a_n{)}^{\ast }=u_1{v}_1^{\ast }(u_1{v}_1^{\ast }{)}^{\ast }+\cdots +u_n{v}_n^{\ast }(u_n{v}_n^{\ast }{)}^{\ast }$$=u_1{v}_1^{\ast }{v}_1{u}_1^{\ast }+\cdots +u_n{v}_n^{\ast }{v}_n{u}_n^{\ast }=u_1{u}_1^{\ast }\cdot \parallel v_1{\parallel }^2+\cdots +u_n{u}_n^{\ast }\parallel v_n{\parallel }^2$

$=\parallel v_1{\parallel }^2\cdot (u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })$$=\left(d/n\right)\cdot (u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })$$=\left(d/n\right)\cdot \left(n/d\right)\cdot 1_d=1_d.$

Therefore, $f\in Q_d(K;A)$.

Now, $\rho \left(f\right(a_1)\dots f(a_n\left)\right)=\rho (u_1{v}_1^{\ast }\dots u_n{v}_n^{\ast })=\rho (u_1{v}_1^{\ast }\dots u_n{v}_n^{\ast })=\rho (v_1^{\ast }{u}_2\dots v_{n-1}^{\ast }{u}_n{v}_n^{\ast }{u}_1)$

$=|v_1^{\ast }{u}_2|\dots |v_n^{\ast }{u}_1|=(\sqrt{d/n}{)}^n\cdot |u_2^{\ast }{u}_2|\dots |u_1^{\ast }{u}_1|=(\sqrt{d/n}{)}^n$. Therefore, we have

$L_{d,K}(a_1,\dots ,a_r,f)=\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}=\sqrt{d/n}$.

Suppose now that $f\in Q_d(K;A)$. By the arithmetic-geometric mean inequality, we have $\rho \left(f\right(a_1)\dots f(a_n){)}^{2/n}\le \parallel f(a_1)\dots f(a_n){\parallel }_{\infty }^{2/n}\le \parallel f(a_1){\parallel }_{\infty }^{2/n}\dots \parallel f(a_n){\parallel }_{\infty }^{2/n}$

$\le \parallel f\left(a_1\right){\parallel }_2^{2/n}\dots \parallel f\left(a_n\right){\parallel }_2^{2/n}\le \frac{\parallel f\left(a_1\right){\parallel }_2^2+\cdots +\parallel f\left(a_n\right){\parallel }_2^2}{n}$

$=\frac{\text{RTr}(f\left(a_1\right)f(a_1{)}^{\ast }+\cdots +f(a_n\left)f\right(a_n{)}^{\ast })}{n}=\frac{\text{RTr}\left(1_d\right)}{n}=d/n.$

Suppose now that $\rho \left(f\right(a_1)\dots f(a_n\left)\right)=d/n$. We observe that $\parallel f\left(a_r\right){\parallel }_{\infty }=\parallel f\left(a_r\right){\parallel }_2$ precisely when $\text{Rank}\left(f\right(a_r\left)\right)\le 1$. From the arithmetic-geometric mean inequality, we have $\parallel f\left(a_1\right){\parallel }_2^{1/n}\dots \parallel f\left(a_n\right){\parallel }_2^{1/n}=\frac{\parallel f\left(a_1\right){\parallel }_2+\cdots +\parallel f\left(a_n\right){\parallel }_2}{n}$ precisely when $\parallel f\left(a_1\right){\parallel }_2=\cdots =\parallel f\left(a_n\right){\parallel }_2$. Therefore, each $f\left(a_r\right)$ has rank at most $1$ and $\parallel f\left(a_r\right){\parallel }_2=\sqrt{d/n}$ for $1\le r\le n$, so we can set $f\left(a_r\right)=u_r{v}_r^{\ast }$ where $\parallel u_r\parallel =1$ and$\parallel v_r\parallel =\sqrt{d/n}$.

Observe that $\rho \left(f\right(a_1)\dots f(a_n\left)\right)=\rho (u_1{v}_1^{\ast }\dots u_n{v}_n^{\ast })$$=|v_n^{\ast }{u}_1{v}_1^{\ast }\dots u_{n-1}{v}_{n-1}^{\ast }{u}_n|=|v_n^{\ast }{u}_1|\dots |v_{n-1}^{\ast }{u}_n|$. Therefore,

$|v_n^{\ast }{u}_1|\dots |v_{n-1}^{\ast }{u}_n|=\parallel f\left(a_1\right){\parallel }_{\infty }\dots \parallel f\left(a_n\right){\parallel }_{\infty }$$=\parallel u_1\parallel \dots \parallel u_n\parallel \cdot \parallel v_1\parallel \dots \parallel v_n\parallel$, so

$|v_r^{\ast }{u}_{r+1}|=\parallel u_{r+1}\parallel \cdot \parallel v_r\parallel$ for all $r$.

Therefore, there are quaternions ${\alpha }_1,\dots ,{\alpha }_n$ with $|{\alpha }_1|=\cdots =|{\alpha }_n|=\sqrt{d/n}$ and where$v_r=u_{r+1}\cdot {\alpha }_r$ for all $r$.

We observe that $1_d=f\left(a_1\right)f(a_1{)}^{\ast }+\cdots +f(a_n\left)f\right(a_n{)}^{\ast }$$=u_1{v}_1^{\ast }(u_1{v}_1^{\ast }{)}^{\ast }+\cdots +u_n{v}_n^{\ast }(u_n{v}_n^{\ast }{)}^{\ast }=u_1{v}_1^{\ast }{v}_1{u}_1^{\ast }+\cdots +u_n{v}_n^{\ast }{v}_n{u}_n^{\ast }$

$=u_1{u}_1^{\ast }\parallel v_1{\parallel }^2+\cdots +u_n{u}_n^{\ast }\parallel v_n{\parallel }^2=(u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })\cdot \left(d/n\right)$.

Therefore, $(u_1,\dots ,u_n)$ is an equal norm tight frame. $\square$

Some thoughts:

It seems easier to prove theorems about MPO word pre-embeddings than it is to prove theorems about other machine learning models simply because MPO word pre-embeddings are more mathematical in nature. Of course, neural networks with ReLU activation are mathematical too, so we can prove theorems about them, but MPO word pre-embeddings are more like the objects that mathematicians like to investigate. And it seems easier to mathematically prove theorems that interpret MPO word pre-embeddings than it is to prove theorems that interpret other machine learning models. On the other hand, we are making a tradeoff here. MPO word pre-embeddings behave more mathematically, but word embeddings are simply the first layer in natural language processing.

Why use the spectral radius?

The matrix $f\left(a_1\right)\dots f\left(a_n\right)$ is in general approximately a rank-1 matrix. This means that$\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}\approx \parallel f(a_1)\dots f(a_n){\parallel }^{1/n}\approx |u^{\ast }f(a_1)\dots f(a_n)v|$ whenever $u,v$ are unit vectors. One may be tempted to define the fitness of the $f$ as $\parallel f\left(a_1\right)\dots f\left(a_n\right){\parallel }^{1/n}$ or $|u^{\ast }f\left(a_1\right)\dots f\left(a_n\right)v|$. But mathematical objects are better behaved when taking limits. Instead of considering the string $a_1\dots a_n$ as our corpus, we may consider the similar corpus $(a_1\dots a_n{)}^m$ as $m\to \infty$, and in this case, the fitness of $f$ would be$\parallel \left(f\right(a_1)\dots f(a_n){)}^m{\parallel }^{1/m}$ or $u^{\ast }\left(f\right(a_1)\dots f(a_n){)}^{m}v$ which will both converge to $\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}$ as $m\to \infty$. The use of the spectral radius simplifies and improves the behavior of the machine learning model for the same reason that integrals such as ${\int }_1^x\frac{dt}{t}$ behave better than sums ${\sum }_{k=1}^n\frac{1}{k}$.

Why complex numbers and quaternions?

While it takes more time to compute MPO word pre-embeddings for the complex numbers and for the quaternions, the complex and quaternionic MPO word pre-embeddings have some advantages over real MPO word pre-embeddings. It is currently unclear as to whether the advantages of complex and quaternionic MPO word pre-embeddings outweigh the cost of the increased computational complexity of training and using complex or quaternionic word pre-embeddings. Further research is needed on this topic.

Complex and quaternionic matrices provide new ways of testing MPO word pre-embeddings which are not available if we simply used real matrices. For example, if $f$ is a complex or quaternionic MPO word pre-embedding, then the existence of a unitary matrix $U$ where $U\cdot f\cdot U^{-1}$ is a real matrix should be considered evidence that the MPO word pre-embedding $f$ is a high quality machine learning model while the non-existence of $U$.

A complex or quaternionic MPO word pre-embedding $f\in Q_d(K;A)$ will typically have a higher fitness level than a corresponding real MPO word pre-embedding.

Sometimes, when one trains an MPO word pre-embedding twice to obtain two MPO word pre-embeddings $f,g$, the fitness levels are equal ($L_{d,K}(a_1\dots a_n,f)=L_{d,K}(a_1\dots a_n,g)$), and it is desirable to have equal fitness levels when training the word pre-embedding multiple times. But the probability of obtaining the equality $L_{d,K}(a_1\dots a_n,f)=L_{d,K}(a_1\dots a_n,g)$ will depend on the choice of $K$. In many cases, we would have

$P\left(L_{d,R}\right(a_1\dots a_n,f)=L_{d,R}(a_1\dots a_n,g\left)\right)<P\left(L_{d,K}\right(a_1\dots a_n,f)=L_{d,K}(a_1\dots a_n,g\left)\right)$

for $K\in \{C,H\}$. Of course, this probability depends on other factors besides the choice of division ring $K$ such as the initialization. For example, if the matrices of the form $f\left(a\right)$ are initialized to have random positive values, then the probability $P\left(L_{d,R}\right(a_1\dots a_n,f)=L_{d,R}(a_1\dots a_n,g\left)\right)$ would be much greater than if the matrices of the form $f\left(a\right)$ are initialized to have random real values; if each $f\left(a\right)$ initially has random positive values, then I would currently consider the real-valued MPO pre-embeddings to be about as good as the complex-valued MPO pre-embeddings but easier to compute.

The fitness function $L_{d,K}$ is not differentiable everywhere, and the gradient of $L_{d,K}$ has singularities. The singularities of $L_{d,K}$ have real codimension $[K:R]$. In the case when $K=R$ the singularities of the gradient of $L_{d,K}$ disconnect the domain $Q_d(K;A)$, and gradient ascent has difficulty crossing these singularities to reach a good local maximum.

Disadvantages of MPO word pre-embeddings:

1. Projectivity: If $M$ is a ring, then the center of $M$ is the collection $Z\left(M\right)$ of all elements $x\in M$ where $xy=yx$ for all $y\in M$. It is easy to show that $Z\left(M\right)$ is always a subring of $M$. We observe that $Z\left(R\right)=R,Z\left(C\right)=C,Z\left(H\right)=R$. If $f,g:A\to M_d\left(K\right)$, ${\lambda }_a\in Z\left(K\right)$$,|{\lambda }_a|=1$ for $a\in A$, and $f\left(a\right)={\lambda }_a\cdot g\left(a\right)$ for $a\in A$, then $f$ is an MPO word pre-embedding if and only if $g$ is an MPO word pre-embedding. This means that after one trains an MPO word pre-embedding $g$, one needs to find the constants ${\lambda }_a\in Z\left(K\right),|{\lambda }_a|=1$ where the function $f$ defined by $f\left(a\right)={\lambda }_a\cdot g\left(a\right)$ behaves optimally. I may talk about how we can find the constants${\lambda }_a$ in another post.

2. Locality: An MPO word pre-embedding is good at relating tokens to their immediate surroundings in the following sense. Suppose $f$ is an MPO word pre-embedding for the string $a_1\dots a_n$. Then the value of $f\left(a\right)$ will be determined mostly by all the other values $f\left(b\right)$ for $b\ne a$ together with the multiset of all strings $a_{i-2}{a}_{i-1}{a}_i{a}_{i+1}{a}_{i+2}$ such that $a=a_i$. In other words, $f\left(a\right)$ can see the immediate surroundings $a_{i-2}{a}_{i-1}{a}_i{a}_{i+1}{a}_{i+2}$ of $a=a_i$, but $f\left(a\right)$ will not be able to see much more than this.

3. Difficulty utilizing all dimensions without noise: Sometimes MPO word pre-embeddings behave poorly because it will be difficult to maximize the spectral radius while we still have ${\sum }_{a\in A}f\left(a\right)f(a{)}^{\ast }=1_d$. To ameliorate this problem, we can relax the requirement for ${\sum }_{a\in A}f\left(a\right)f(a{)}^{\ast }=1_d$ to the condition $\parallel {\sum }_{a\in A}f\left(a\right)f(a{)}^{\ast }{\parallel }_p=d^{1/p}$ for some $p>1$. But in this case, the MPO word pre-embedding will not use all of the dimensions in $K^d$ evenly.

Conclusion:

Spectral methods have already been quite valuable in machine learning for a good reason. I will continue to make more posts about using the spectral radius (and similar objects) to construct machine learning models.

Another possible advantages of quaternions: Added 9/​8/​2023

It seems like an increase in the value $d$ provides diminishing returns in the performance of MPO word embeddings since when $d$ is large, MPO word embeddings have difficulty utilizing all $d$ dimensions equally. MPO word embeddings therefore can only give us some information about a token. However, it seems like increasing the index $[K:R]$ increases the number of parameters of MPO word embeddings without the word embedding encountering substantially more difficulty in utilizing all $d$ dimensions significantly. Therefore, MPO word embeddings should perform better simply by increasing the index $[K:R]$. This means that complex MPO word embeddings should perform better than real MPO word embeddings, and quaternionic MPO word embeddings should perform better than complex MPO word embeddings. On the other hand, we still need to perform experiments to determine whether complex MPO word embeddings are that much better than real MPO word embeddings and quaternionic MPO word embeddings are even better than both real and complex MPO word embeddings.

References:

1. Quaternions and matrices of quaternions. Fuzhen Zhang. Linear Algebra and its Applications. Volume 251, 15 January 1997, Pages 21-57

2. An Introduction to Finite Tight Frames. Shayne F. D. Waldron. July 26, 2017

[the gears to ascension]

this does look like it might be interesting, but I think you might need to show—possibly visually—why this works. what does an embedding of a 5-word dataset look like on a chart? how does one interpret it on that chart? why do these expressions map to that chart, etc? that would allow introducing the math you’re using to anyone who doesn’t know it or is rusty, while reducing effort to follow it for those who don’t know it. If you’re only intending to communicate to those who already get the prereqs, which is a thing people do, then, well, post more posts like this and I’m sure someone who has the particular math background (quaternions?) will run into them eventually. it looks like the math is all here, just too dense for my current level of motivation, so maybe you just need the right eyes.

I personally can’t evaluate your idea within the time I would allot to reading this post because you use a lot of expressions I’m not immediately familiar with and I don’t see a way to shortcut through them in order to draw the conclusions about improved interpretability you’re implying. but it does seem conceivable that it could be pretty cool. I can imagine why having explicitly disambiguated word senses would be useful, if you could get your embedding to be sturdy about them.

[Joseph Van Name]

I appreciate your input. I plan on making more posts like this one with a similar level of technical depth. Since I included a proof with this post, this post contained a bit more mathematics than usual. With that being said, others have stated that I should be aware of the mathematical prerequisites for posts like this, so I will keep the mathematical prerequisites in mind.

Here are some more technical thoughts about this.

1. We would all agree that the problem of machine learning interpretability is a quite difficult problem; I believe that the solution to the interpretability problem requires us not only to use better interpretability tools, but the machine learning models themselves need to be more inherently interpretable. MPO word embeddings and similar constructions have a little bit (but not too much) of difficulty since one needs to get used to different notions. For example, if we use neural networks using ReLU activation (or something like that), then one has less difficulty upfront, but when it comes time to interpret such a network, the difficulty in interpretability will increase since neural networks with ReLU activation do not seem to have the right interpretability properties, so I hesitate to interpret neural networks. And even if we do decide to interpret neural networks, the interpretability tools that we use may have a more complicated design than the networks themselves.

2. There are some good reasons why complex numbers and quaternions have relatively little importance in machine learning. And these reasons do not apply to constructions like MPO word embeddings.

3. Since equal norm tight frames are local minimizers of the frame potential, it would help to have a good understanding of the frame potential. For simplicity, it is a good idea to only look at the real case. The frame potential is a potential for a force between a collection of particles on the sphere $S^{d-1}$ where particles are repelled from each other (and from each other’s antipodal point) and where the force tries to make all the particles orthogonal to each other. If $d=n$, then it is possible to make all of the particles orthogonal to each other, and in this case, when we minimize this potential, the equal norm tight frames will simply be orthonormal bases. In the case when $d<n$, we cannot make all of the particles orthogonal to each other, but we can try to get as close as possible. Observe that unlike the Newtonian and logarithmic potential, the frame potential does not have a singularity for when the two particles over lap. I will leave it to you to take the gradient (at least in the real case) of the frame potential to see exactly what this force does to the particles.

4. Training an MPO word embedding with the complex numbers of quaternions is actually easier in the sense that for real MPO word embeddings, one needs to use a proper initialization, but with complex and quaternionic MPO word embeddings, an improper initialization will only result in minor deficiencies in the MPO word embedding. This means that the quaternions and complex numbers are easier to work with for MPO word embeddings than the real numbers. In hindsight, the solution to the problem of real MPO word embeddings is obvious, but at the time, I thought that I must use complex or quaternionic matrices.

5. I like the idea of making animations, but even in the real case where things are easy to visualize, the equal norm tight frames are non-unique and they may involve many dimensions. The non-uniqueness will make it impossible to interpret the equal norm tight frames; for the same reason, it is hard to interpret what is happening with neural networks since if you retrain a neural network with a different initialization or learning rate, you will end up with a different trained network, but MPO word embeddings have much more uniqueness properties that make them easier to interpret. I have made plenty of machine learning training animations and have posted these animations on YouTube and TikTok, but it seems like in most cases, the animation still needs to be accompanied by technical details; with just an animation, the viewers can see that something is happening with the machine learning model, but they need both the animation and technical details to interpret what exactly is happening. I am afraid that most viewers just stick with the animations without going into so many technical details. I therefore try to make the animations more satisfying than informative most of the time.

[Joseph Van Name]

Is the Latex compiling here?

[Joseph Van Name]

I made the Latex compile by adding a space. Let me know if there are any problems.

[deleted]