Answers.Body: <p>You can find some material <a href="https://scikit-learn.org/stable/modules/decomposition.html#truncated-singular-value-decomposition-and-latent-semantic-analysis" rel="nofollow noreferrer">here</a> and <a href="https://arxiv.org/pdf/0909.4061.pdf" rel="nofollow noreferrer">here</a> but the idea (at least in this case) is the following: consider the full SVD decomposition of the symmetric matrix <span class="math-container">$A = W \Delta W^T$</span>. We want to calculate the cosine similarity between the <span class="math-container">$i$</span>-th column (aka word) <span class="math-container">$a_i$</span> and the <span class="math-container">$j$</span>-th column <span class="math-container">$a_j$</span> of <span class="math-container">$A$</span>. Then <span class="math-container">$a_k = A e_k$</span>, where <span class="math-container">$e_k$</span> is the <span class="math-container">$k$</span>-th vector of the canonical basis of <span class="math-container">$\mathbb{R}$</span>. Let's call <span class="math-container">$\cos(a_i,a_j)$</span> the cosine between <span class="math-container">$a_i,a_j$</span>. Then
  <span class="math-container">$$\cos(a_i,a_j) = \cos(Ae_i,Ae_j) = \cos(W \Delta W^T e_i,W \Delta W^T e_j) = \cos(\Delta W^T e_i,\Delta W^T e_j)$$</span></p>
  <p>where the last equality holds because <span class="math-container">$W$</span> is an orthogonal matrix (and so <span class="math-container">$W$</span> is <a href="https://en.wikipedia.org/wiki/Conformal_map" rel="nofollow noreferrer">conformal</a>, i.e. it preserves angles). So you can calculate the cosine similarity between the columns of <span class="math-container">$\Delta W^T$</span>. A <span class="math-container">$k$</span>-truncated SVD gives a well-enough approximation. In <a href="https://stats.stackexchange.com/q/134282/82135">general</a>, columns of <span class="math-container">$W \Delta$</span> and rows of <span class="math-container">$W$</span> have different meanings!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-16T13:41:16.683Z
Answers.Text: But isn't $W^T$ also orthogonal and therefore conformal? If yes, why can't we simply use the diagonal matrix?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-16T13:48:16.907Z
Answers.Text: Also $W^T$ is orthogonal and conformal, but you only "simplify" on the left: if $f$ is a conformal map, $g$ any function, then $\cos(f \circ g(x),f \circ g(y)) = \cos(g(x),g(y))$, but in general $\cos(g \circ f(x),g \circ f(y)) \neq \cos(g(x),g(y))$
Answers.UserDisplayName: dcolazin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-16T13:57:26.943Z
Answers.Text: @nbro for example, consider [this matrix](https://www.wolframalpha.com/input/?i=svd+%7B(1,0,1),(0,1,0),(1,0,1)%7D): $\cos(Me_1,Me_3) = 1 = \cos(\Sigma V^T e_1, \Sigma V^T e_3)$ but $\cos(\Sigma e_1,\Sigma e_3) = 0$ (cosine between different columns in a diagonal matrix is always $0$).
Answers.UserDisplayName: dcolazin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-16T00:17:06.180Z
Answers.LastActivityDate: 2021-01-03T20:30:01.217Z
Answers.LastEditDate: 2021-01-03T20:30:01.217Z
Answers.UserDisplayName: dcolazin
Body: <p>Two words can be similar if they co-occur "a lot" together. They can also be similar if they have similar vectors. This similarity can be captured using cosine similarity. Let <span class="math-container">$A$</span> be a <span class="math-container">$n \times n$</span> matrix counting how often <span class="math-container">$w_i$</span> occurs with <span class="math-container">$w_k$</span> for <span class="math-container">$i,k = 1, \dots, n$</span>. Since computing the cosine similarity between <span class="math-container">$w_i$</span> and <span class="math-container">$w_k$</span> might be expensive, we approximate <span class="math-container">$A$</span> using truncated SVD with <span class="math-container">$k$</span> components as: <span class="math-container">$$A \approx W_k \Sigma W^{T}_{k} = CD$$</span></p>
  
  <p>where <span class="math-container">$$C = W_{k} \Sigma \\ D = W^{T}_{k}$$</span></p>
  
  <p>Where are the cosine similarities between the words <span class="math-container">$w_i$</span> and <span class="math-container">$w_k$</span> captured? In the <span class="math-container">$C$</span> matrix or the <span class="math-container">$D$</span> matrix?</p>
  
Tags: <machine-learning><natural-language-processing><math>
Title: Which matrix represents the similarity between words when using SVD?
UserDisplayName: naturalguy_12
ThreadText: # Which matrix represents the similarity between words when using SVD?
  
  (Asked by: username_0 on 2019-03-15)
  
  Two words can be similar if they co-occur "a lot" together. They can also be similar if they have similar vectors. This similarity can be captured using cosine similarity. Let $A$ be a $n \times n$ matrix counting how often $w\_i$ occurs with $w\_k$ for $i,k = 1, \dots, n$. Since computing the cosine similarity between $w\_i$ and $w\_k$ might be expensive, we approximate $A$ using truncated SVD with $k$ components as: $$A \approx W\_k \Sigma W^{T}\_{k} = CD$$
  
  where $$C = W\_{k} \Sigma \\ D = W^{T}\_{k}$$
  
  Where are the cosine similarities between the words $w\_i$ and $w\_k$ captured? In the $C$ matrix or the $D$ matrix?
  
  **Tags:** machine-learning, natural-language-processing, math
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-16. Score: 0 | Accepted answer
  
  You can find some material [here](https://scikit-learn.org/stable/modules/decomposition.html#truncated-singular-value-decomposition-and-latent-semantic-analysis) and [here](https://arxiv.org/pdf/0909.4061.pdf) but the idea (at least in this case) is the following: consider the full SVD decomposition of the symmetric matrix $A = W \Delta W^T$. We want to calculate the cosine similarity between the $i$-th column (aka word) $a\_i$ and the $j$-th column $a\_j$ of $A$. Then $a\_k = A e\_k$, where $e\_k$ is the $k$-th vector of the canonical basis of $\mathbb{R}$. Let's call $\cos(a\_i,a\_j)$ the cosine between $a\_i,a\_j$. Then
  $$\cos(a\_i,a\_j) = \cos(Ae\_i,Ae\_j) = \cos(W \Delta W^T e\_i,W \Delta W^T e\_j) = \cos(\Delta W^T e\_i,\Delta W^T e\_j)$$
  
  where the last equality holds because $W$ is an orthogonal matrix (and so $W$ is [conformal](https://en.wikipedia.org/wiki/Conformal_map), i.e. it preserves angles). So you can calculate the cosine similarity between the columns of $\Delta W^T$. A $k$-truncated SVD gives a well-enough approximation. In [general](https://stats.stackexchange.com/q/134282/82135), columns of $W \Delta$ and rows of $W$ have different meanings!
  
  > **Comments:**
  > **username_2**: But isn't $W^T$ also orthogonal and therefore conformal? If yes, why can't we simply use the diagonal matrix?  
  > **username_1**: Also $W^T$ is orthogonal and conformal, but you only "simplify" on the left: if $f$ is a conformal map, $g$ any function, then $\cos(f \circ g(x),f \circ g(y)) = \cos(g(x),g(y))$, but in general $\cos(g \circ f(x),g \circ f(y)) \neq \cos(g(x),g(y))$  
  > **username_1**: @username_2 for example, consider [this matrix](https://www.wolframalpha.com/input/?i=svd+%7B(1,0,1),(0,1,0),(1,0,1)%7D): $\cos(Me_1,Me_3) = 1 = \cos(\Sigma V^T e_1, \Sigma V^T e_3)$ but $\cos(\Sigma e_1,\Sigma e_3) = 0$ (cosine between different columns in a diagonal matrix is always $0$).  
  
  ---
  
  