Some ML-Related Math I Now Understand Better

post by Fabien Roger (Fabien) · 2023-03-09T16:35:44.797Z · LW · GW · 4 comments

Contents

  SVD Is Decomposing a Matrix Into a Sum of Simple Read and Write Operations
  There Is Exponentially Much Room for Almost Orthogonal Vectors in High Dimensional Space
  Layer Normalization Is a Projection
  Appendix: Solutions to the Simple Questions Using the Geometric Interpretation of SVD
None
4 comments

Here are some simple Math facts rarely taught in ML & Math lectures:

• SVD is decomposing a matrix into a sum of simple read-and-write operations
• There is exponentially much room for close vectors in high dimensional space
• Layer Normalization is a projection

SVD Is Decomposing a Matrix Into a Sum of Simple Read and Write Operations

Thanks to zfurman, on EleutherAI, which told me about the core idea.

Let's say I want to understand what a weight matrix does. A large table of numbers isn't really helpful, I want something better.

Here is a linear transformation which is much easier to understand than a table of numbers: $f\left(x\right)=\lambda ⟨v,x⟩u$ (where $u$ and $v$ are unit vectors, $\lambda$ is a non-negative scalar, and $⟨v,x⟩$ is the dot product between $v$ and $x$). $f$ is reading in the $v$ direction, and writing in the $u$ direction with a magnitude scaled by $\lambda$. I can understand this much more clearly and do nice interpretability with it. Therefore, if I know things about my embedding space (for example, using the logit lens), I can tell what $f$ is doing.

Sadly, not all linear transformations can be expressed in this way: it's just a rank-1 transformation, so there is no hope of capturing something as complex as a usual linear transformation.

But what if I allow myself to sum many simple transformations? Then I could just look at each operation independently. More precisely, here is a wishlist to understand the big matrix $M$ of the transformation $g$ :

• $g\left(x\right)={\sum }_{i=1}^r{\lambda }_i⟨v_i,x⟩u_i$ where $u$ and $v$ are unit vectors, and $\lambda$ is a positive scalar - it's a sum of simple transformations;
• $⟨v_i,v_j⟩=0$ for all $i\ne j$ - no double read, always read in orthogonal directions;
• $⟨u_i,u_j⟩=0$ for all $i\ne j$ - no double write, always write in orthogonal directions;
• $r=\text{rank}\left(g\right)$ - the number $r$ of simple transformation summed should be as small as possible, because that would mean less individual transformation to inspect (and I can't hope for fewer than $\text{rank}\left(g\right)$ operations, since the rank of the sum of $r$ rank-1 linear transformations is at most $r$).

In terms of matrices, this is $M=U\text{diag}\left(\lambda \right)V^{\text{T}}$ where $U$ and $V$ are semi-unitary matrices (orthogonal matrices when they are square matrices). This is exactly SVD.

Understanding matrices & SVD this way helped me find a geometric intuition behind some basic properties of matrices. The questions below can also be quickly answered by "doing the math", but I think it's interesting to have a geometric understanding of why these are true. 

• What is a geometric interpretation of a symmetric matrix? Why is the inverse of an invertible symmetric matrix always symmetric?
• What is the geometric interpretation of transposing a linear transformation ?
• Why are ${\lambda }_i^2$ the eigenvalues of $M{M}^{\text{T}}$ and why are its eigenvectors $u_i$? Why are ${\lambda }_i^2$ the eigenvalues of $M^{\text{T}}M$ and why are its eigenvectors $v_i$?

Feel free to share yours in the comments!

There Is Exponentially Much Room for Almost Orthogonal Vectors in High Dimensional Space

According to this paper, the number of almost orthogonal vectors you can put in $n$ dimensional space is at least $\exp \left(n\log \right(\frac{1}{\sin \theta })+o(n\left)\right)$ where all pairs of vectors have an angle of at least $\theta$ between them (and $o\left(n\right)\underset{n\to +\infty }{\overset{}{\to }}0$).^[1]

Ignoring the $o\left(n\right)$, and using $n=1600$ (the number of dimensions of the embedding space of GPT-2 XL) it means you can fit at least 3000 vectors with pairwise cosine similarities smaller than 0.1 and ${10}^{14}$ vectors with cosine similarities smaller than 0.2. Using $n=12288$ (the number of dimensions of the embedding space of GPT-3), you can fit at least ${10}^6$ vectors with pairwise cosine similarities smaller than 0.05 and ${10}^{26}{10}^{26}$ vectors with cosine similarities smaller than 0.1.

This means you can get a lot of vectors in your embedding space if you allow for relatively small cosine similarities. But this does not hold for tiny cosine similarities (e.g. 0.01 for $n=12288$, which gives a lower bound of 2 using the formula above). I'm not aware of a lower bound better than $n$ for tiny angles. Therefore, for a neural network to use this space to fit independent concepts, it needs to be resilient to many small-but-not-that-small conflicts.

Layer Normalization Is a Projection

Thanks to Lawrence Chan for telling me about this.

Layer Normalization is a normalization layer often found in LLMs. People usually write it as $y=\frac{x-E\left[x\right]}{\sqrt{Var\left[x\right]}}$ (followed by a scaling and a bias term^[2]), which is confusing because we are taking the expected value and the variance of a vector, which is not a common geometric operation.

But it can easily be expressed in terms of two successive projection: $x-E\left[x\right]$ is simply $p_{\overrightarrow{1}}\left(x\right)$, the projection on the hyperplane orthogonal to the vector $\overrightarrow{1}=(1\dots 1)$, $p_{\overrightarrow{1}}\left(x\right)=x-⟨x,\overrightarrow{1}⟩\overrightarrow{1}/||\overrightarrow{1}|{|}^2=x-\left(\frac{1}{d}{\sum }_i{x}_i\right)\overrightarrow{1}=(x_j-\frac{1}{d}{\sum }_i{x}_i{)}_j$.

Then$\frac{x-E\left[x\right]}{\sqrt{Var\left[x\right]}}=\frac{x-E\left[x\right]}{\sqrt{E\left[\right(x-E\left[x\right]{)}^2]}}=\frac{p_1\left(x\right)}{\sqrt{\frac{1}{d}{\sum }_i{p}_1(x{)}_i^2}}=\sqrt{d}\frac{p_1\left(x\right)}{||p_1\left(x\right)||}=\sqrt{d}{p}_S\left(p_1\right(x\left)\right)$, where $p_S$ is the projection on the unit sphere.

This gives us $\frac{x-E\left[x\right]}{\sqrt{Var\left[x\right]}}=\sqrt{d}{p}_S\left(p_1\right(x\left)\right)$.

Therefore, LayerNorm is just projecting on the hyperplane orthogonal to $\overrightarrow{1}$, and then projecting again on the unit sphere (of the hyperplane orthogonal to $\overrightarrow{1}$), times $\sqrt{d}$. These two projections are the same as projecting a point to its closest point on the unit sphere of the hyperplane orthogonal to $\overrightarrow{1}$^[3].

For example, in dimension 3, LayerNorm is the same as projecting a point to the point of the black ring below closest to it.

This helps me see geometrically what $\text{LayerNorm}\left(R^d\right)$ is: it's the unit sphere of the hyperplane orthogonal to $1$.

This also gives me a geometrical intuition of why it might help (though the usual formula works just as well), though it is quite speculative. First, projecting on the hypersphere clearly solves the problem of exploding or vanishing activations. Second, the projection on the $\overrightarrow{1}$ vector pushes you away from the quadrants where ReLU is boring. Indeed, the $\overrightarrow{1}$ vector points towards the quadrant where all coordinates are positive, where ReLU = id, and points away from the quadrant where all coordinates are negative, where ReLU = 0. In all other quadrants, ReLU does something a bit more interesting: it zeros out some coordinates and leaves others intact.

What is missing from this geometrical point of view: It's hard to understand high dimensions. In particular, it's not easy to see that the projection on the hyperplane does almost nothing to high dimensional vectors: it only changes one coordinate among thousands. Therefore, the cosine similarity between a vector $x$ and $\text{LayerNorm}\left(x\right)$ is almost always very close to 1. Indeed, if ${\hat{x}}_i$ are the coordinates of $x$ in a basis which has the $1$ vector (normalized) as first vector, $\frac{⟨x,\text{LayerNorm}\left(x\right)⟩}{||x||||\text{LayerNorm}\left(x\right)||}=\frac{{\sum }_{i=2}^d{\hat{x}}_i^2}{\sqrt{\left({\sum }_{i=2}^d{\hat{x}}_i^2\right)\left({\sum }_{i=1}^d{\hat{x}}_i^2\right)}}=\sqrt{1-\frac{{\hat{x}}_1^2}{{\sum }_{i=1}^d{\hat{x}}_i^2}}\approx 1$

Appendix: Solutions to the Simple Questions Using the Geometric Interpretation of SVD

• What is a geometric interpretation of a symmetric matrix? Why is the inverse of an invertible symmetric matrix always symmetric?

A symmetric matrix is, according to the spectral theorem, a matrix of the form $U\text{diag}\left(\lambda \right)U^T$ where U is an orthogonal matrix. Therefore, a symmetric matrix is a matrix which can be decomposed as a sum of transformation of the form $x\mapsto \lambda ⟨x,u⟩u$. A symmetric matrix is the matrix of a linear transformation, which writes where it reads! Therefore, inverting a symmetric matrix is easy: if the ${\lambda }_i$ are all non-zero, just read where you just wrote (in the direction of $u_i$), scale by $1/{\lambda }_i$, and then write back along $u_i.$ The transformation I just described to invert the action of a symmetric matrix also writes where it reads, so the inverse of a symmetric matrix is also symmetric. (You can check, that because there is no double read nor double write, what I described is legit, though the formal proof with usual linear algebra is much faster than the formal proof using geometry.)

• What is the geometric interpretation of transposing a linear transformation ?

$\left(U\text{diag}\right(\lambda )V^T{)}^T=V\text{diag}(\lambda )U^T$, therefore M transposed is the same as M, except it reads where M writes, and writes where M reads (the simple rank-1 operations are "swapped").

• Why are ${\lambda }_i^2$ the eigenvalues of $M{M}^{\text{T}}$ and why are its eigenvectors $u_i$? Why are ${\lambda }_i^2$ the eigenvalues of $M^{\text{T}}M$ and why are its eigenvectors $v_i$?

$M{M}^T$ is the composition of two linear transformations. A first one (the transposed of M, see above) which reads along $u_i$ scales by ${\lambda }_i$ and writes along $v_i$, and a second one which reads along $v_i$, scales by ${\lambda }_i$, and writes along $u_i$. Therefore, $M{M}^T$ reads along $u_i$, scales by ${\lambda }_i^2$ and writes along $u_i$. Therefore, it is symmetric (it reads where it writes), and the $u_i$ are eigenvectors with eigenvalues ${\lambda }_i^2$ because if it read $u_i$, it will write ${\lambda }_i^2{u}_i$ (there is no double read nor double writes). The same reasoning works for $M^{T}M$.

 

1. ^{^}

   Toy Models of Superposition states something similar: "It's possible to have $\exp \left(n\right)$ many "almost orthogonal" ($<ϵ$ cosine similarity) vectors in high-dimensional spaces. See the Johnson–Lindenstrauss lemma." But this lemma does not directly state this property, and rather tells us that there is a linear map to a space with $\log n$ dimensions which almost preserves L2-distances between points. I prefer the theorem I present in this post which is directly about how many almost orthogonal vectors can fit in high-dimensional spaces. 

2. ^{^}

   For numerical stability reasons, people also usually add a small $ϵ$ to the denominator.

3. ^{^}

   Using the L2 distance, for a given point $x$, if y is the closest point to $x$ on the unit sphere of the hyperplane $H$ orthogonal to the $1$ vector, and if $p_H\left(x\right)$ is the orthogonal projection of $x$ on $H$, then by the Pythagorean theorem, $d(x,y{)}^2=d(x,p_H\left(x\right){)}^2+d\left(p_H\right(x),y{)}^2$, which is minimal when y is the projection of $p_H\left(x\right)$ on the unit sphere. This proves that projecting on the unit sphere of $H$ is the same as first projecting on $H$ and then projecting on the unit sphere.

4 comments

Comments sorted by top scores.