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

post by Joseph Van Name (joseph-van-name) · 2023-09-04T16:19:24.401Z · LW · GW · 4 comments

Contents

  Why MPO word embeddings?
  Quaternionic matrices:
  MPO word embeddings
  Some thoughts:
  Why use the spectral radius?
  Why complex numbers and quaternions?
  Disadvantages of MPO word pre-embeddings:
  Conclusion:
  Another possible advantages of quaternions: Added 9/8/2023
None
5 comments

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

 

4 comments

Comments sorted by top scores.