9
$\begingroup$

My question is generally on Singular Value Decomposition (SVD), and particularly on Latent Semantic Indexing (LSI).

Say, I have $ A_{word \times document} $ that contains frequencies of 5 words for 7 documents.

A =  matrix(data=c(2,0,8,6,0,3,1,
                   1,6,0,1,7,0,1,
                   5,0,7,4,0,5,6,
                   7,0,8,5,0,8,5,
                   0,10,0,0,7,0,0), ncol=7, byrow=TRUE)
rownames(A) <- c('doctor','car','nurse','hospital','wheel')

I get the matrix factorization for $A$ by using SVD: $A = U \cdot D \cdot V^T $.

s = svd(A)
D = diag(s$d) # singular value matrix
S = diag(s$d^0.5 ) # diag matrix with square roots of singular values.

In 1 and 2, it is stated that:

$WordSim = U \cdot S$ gives the word similarity matrix, where the rows of $WordSim $ represent different words.

WordSim = s$u %*% S

$DocSim= S \cdot V^T$ gives the document similarity matrix where the columns of $DocSim$ represent different documents.

DocSim = S %*% t(s$v)

Questions:

  1. Algebraically, why are $WordSim$ and $DocSimS$ word/document similarity matrices? Is there an intuitive explanation?
  2. Based on the R example given, can we make any intuitive word count / similarity observations by just looking at $WordSim$ and $DocSim$ (without using cosine similarity or correlation coefficient between rows / columns)?

enter image description here

$\endgroup$
  • $\begingroup$ I know very little about LSI, but SVD of a matrix is at the core of linear dimensionality-reduction, mapping methods, such as Principal components, biplots, Correspondence analysis. The main "laws" of SVD is that $AV=UD$ = projection of rows of $A$ onto the principal axes; and $A'U=VD'$ = projection of columns of $A$ onto the principal axes. In a sense, it is "similarity" values between the points (rows or columns) and the principal axes. Whether it can be treated as similarity between the points themselves is dependent on the context, I think. $\endgroup$ – ttnphns Jul 16 '14 at 15:04
  • $\begingroup$ Ah.. I see in wikipedia that LSI is just correspondence analysis (CA). That's better. CA is the biplot of a specially prepared data table. The aforementioned projections or coordinates - you use them to plot row and column points in the space of the principal axes. Closeness between the row-row, col-col, and row-col points relate their similarity. However, the layout on the plot is dependent on how you spread inertia (variance) over the row and the col points. $\endgroup$ – ttnphns Jul 16 '14 at 15:12
  • $\begingroup$ @ttnphns. Thank you, can you give a reference on: "$AV=UD$ = projection of rows of A onto the principal axes; and $A ′ U=VD ′$ = projection of columns of A onto the principal axes"? I think that will clarify things for me. By principal axes, do you mean the eigen vectors corresponding to the top m singular values in $D$? I also came across: "For PCA,we need not compute the left singular vectors", but cannot wholly comprehend why this is the case. $\endgroup$ – Zhubarb Jul 16 '14 at 15:37
  • 2
    $\begingroup$ Your question could be improved by editing it to correctly reflect what that document states. On p. 22 it defines $S$ as containing the square roots of $D$, "restricted" to the largest ones. Therefore neither $UD$ nor $DV^\prime$ are involved, nor do they have interpretations as "similarity matrices." The relevant matrices are instead $US$ and $SV^\prime$. They can be used to reconstruct an approximation of $A=UDV^\prime\approx U(S^2)V^\prime=(US)(SV^\prime).$ $\endgroup$ – whuber Jul 16 '14 at 15:58
  • 1
    $\begingroup$ I assumed D=svd(A)$d in R returns the square roots of the non-zero eigen values, hence I used $UD$. I do not have a problem with the dimensionality reduction aspect, and I do understand a lower rank approximation of A can be formed as they describe. I found the answer on this link partially answers my question. $\endgroup$ – Zhubarb Jul 16 '14 at 16:10
2
$\begingroup$

Matrix factorization using SVD decomposes the input matrix into three parts:

  • The left singular vectors $U$. The first column of this matrix specifies on which axis the rows of the input matrix vary the most. In your case, the first column tells you which words vary together the most.
  • The singular values $D$. These are scalings. These are relative to each other. If the first value of $D$ is twice as big as the second it means that the first singular vector (in $U$ and $V^T$) explain twice as much variation as the seconds singular vector.
  • The right singular vectors $V^T$. The first row of this matrix specifies on which axis the columns of the input matrix vary the most. In your case, the first row tells you which documents vary together the most.

When words or documents vary together it indicates that they are similar. For example, if the word doctor occurs more often in a document, the word nurse and hospital also occur more. This is shown by the first scaled left singular vector, the first column of $WordSim$.You can validate this result by looking at the input data. Notice that when nurse does occur, hospital also occurs and when it does not occur, hospital also does not occur.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.