Wishing all readers a Happy New Year in advance, and good luck in 2017!
This article mainly aims to answer two "why" questions: 1. Why did I become interested in SVD? 2. Why do I say SVD is a clustering process? The content of the answers is purely the result of personal reflection, with no references for now.
Why Research SVD?
Since I first encountered deep learning in 2015, I have been studying it for nearly two years. Now, concepts like deep learning and data science are blossoming everywhere. Why, at a time when deep learning is so popular, would I go back to study the "ancient" SVD decomposition? I believe that as a matrix decomposition algorithm, the value of SVD is reflected not only in its wide range of applications but also in its deeper connotation: its interpretability. In today’s era of popular deep learning, many people still feel that deep learning (neural networks) is just an effective "black box" model. However, explaining the effectiveness of deep learning solely with the term "black box" is clearly unsatisfactory. As mentioned earlier, SVD decomposition is essentially equivalent to a three-layer autoencoder without activation functions. Understanding SVD decomposition can help seek a reasonable probabilistic explanation for neural network models.
Recently, I have been trying to build some more complex models, such as question-answering systems and chatbots. I have increasingly felt that when starting out, deep learning models like seq2seq, which have recently shone brightly, are basically unusable. I basically start from the most fundamental probability model P(A|Q), simplify it step by step, and finally obtain a model with acceptable complexity. Models obtained this way have clear meanings and strong controllability. However, part of it is based on statistics; pure statistics cannot yield truly "intelligent" results, and as mentioned before, SVD decomposition can bring preliminary intelligence on top of statistical results. This gives me a strong feeling: one is that the interpretability of the model, especially the probabilistic explanation, is very important; the other is that after better understanding SVD, I have a better sense of the meaning and application of neural network models.
How Does SVD Decomposition Perform Clustering?
Why is SVD decomposition clustering? Actually, there is a very simple probabilistic model inside.
Given a matrix M_{m\times n}, without loss of generality, assume each of its elements is non-negative. This allows us to normalize each row, so the resulting matrix can represent a transition probability: P(B|A)=\begin{pmatrix}p(b_1|a_1) & p(b_2|a_1) & \dots & p(b_n|a_1)\\ p(b_1|a_2) & p(b_2|a_2) & \dots & p(b_n|a_2)\\ \vdots & \vdots & \ddots & \vdots\\ p(b_1|a_m) & p(b_2|a_m) & \dots & p(b_n|a_m)\end{pmatrix} The normalization condition is: \sum_{j=1}^n p(b_j|a_i)=1, \quad i=1,2,\dots,m The term p(b_j|a_i) refers to the probability of b_j following a_i. This kind of probabilistic model is very common, such as the bigram language model.
Now we assume that each a_i can be clustered into l categories, denoted as c_1, c_2, \dots, c_l; and each b_i can be clustered into k categories, denoted as d_1, d_2, \dots, d_k. To study the pattern of b_j following a_i, we can actually simplify it to the patterns between categories (a typical small case is: we classify words into verbs, nouns, adjectives, etc., and then find that verbs can be followed by nouns to form phrases; "verb + noun" is the clustering pattern discovered by our brains). This is the sole assumption of SVD decomposition. More clearly, the assumptions include:
1. Both a_i and b_i can be clustered into several categories;
2. The connection patterns between a_i and b_i can be simplified to the connection patterns between the categories they belong to.
At this point, according to the probability formula, we get: p(b_j|a_i) = \sum_{k,l}p(b_j|d_k)p(d_k|c_l)p(c_l|a_i)
Each term has a very clear probabilistic meaning:
p(c_l|a_i) is the probability that a_i manifests as category c_l;
p(d_k|c_l) is the probability that category c_l is followed by category d_k;
p(b_j|d_k) is the probability of element b_j given category d_k.
Thus, naturally, p(b_j|a_i) = \sum_{k,l}p(b_j|d_k)p(d_k|c_l)p(c_l|a_i). That is to say, as long as the assumptions hold, this formula is exactly correct. And this operation is precisely the multiplication of three matrices: P(B|A)=P(B|D)\times P(D|C)\times P(C|A) In other words, a matrix decomposed into the product of three lower-dimensional matrices—isn’t that exactly SVD decomposition? Of course, the subtle difference is that if it were a probabilistic decomposition, there would be normalization requirements (this part of the content belongs to the pLSA model within topic modeling), while SVD decomposition itself does not require normalization constraints. However, this does not affect the core idea: that matrix decomposition inherently contains the meaning of clustering.
In this way, we perform clustering on rows and columns through matrix decomposition. We don’t need to tell the computer which categories to cluster into (for example, we don’t need to tell the computer to classify words into nouns, verbs, adjectives, etc.), but rather complete it directly through matrix decomposition. (Imagine just shouting "Assemble, it’s time to cluster!" through a megaphone, and everyone automatically sorts themselves into groups without us telling them how to do it.) Or to put it another way, we have endowed SVD decomposition with clustering meaning through a probabilistic model.
Happy New Year
Uh... I originally felt this could be explained in a sentence or two, but I ended up writing so much text. I hope readers don’t find me too long-winded ^_^
Happy New Year once again, and as I say every year: I hope everyone continues to support me!
When reposting, please include the address of this article: https://kexue.fm/archives/4216
For more detailed reposting matters, please refer to: Scientific Space FAQ