SVD Decomposition (II): Why Does SVD Imply Clustering?

SVD分解(二)：为什么SVD意味着聚类？ 苏剑林 · 2017-01-26 · Machine Learning clustering SVD

Happy New Year in advance to all readers — may 2017 bring you good fortune!

This article aims to answer two "why" questions: 1) Why am I interested in SVD in the first place? 2) Why do I claim that SVD is essentially a clustering process? The content below is purely the result of my own reasoning, with no references to cite.

Why study SVD?

Since I first encountered deep learning in 2015, I've now been studying it for nearly two years, and concepts like deep learning and data science are blooming everywhere. So why, at a time when deep learning is so hot, would I turn back to study the "ancient" SVD decomposition instead? I think the value of SVD, as a matrix factorization algorithm, lies not just in its wide range of applications but in something deeper: its interpretability. Even today, with deep learning so popular, many people still regard deep learning (neural networks) as merely an effective "black box" model. But explaining the effectiveness of deep learning solely by invoking the phrase "black box" is clearly unsatisfying. As I mentioned before, SVD decomposition is, in essence, equivalent to a three-layer autoencoder without an activation function; understanding SVD decomposition can help us find a reasonable probabilistic interpretation for neural network models.

Recently, I've been trying to build some more complex models—question-answering systems, chatbots, and so on—and I've increasingly felt that, at the outset, the deep learning models currently in the spotlight, such as seq2seq, are basically unusable in practice. What I actually do is start from the most fundamental probabilistic model $P(A|Q)$, then progressively simplify it, eventually arriving at a model whose complexity is manageable. A model obtained this way has clear meaning and strong controllability. But part of this process is based on statistics, and pure statistics alone can't yield truly "intelligent" results. As I mentioned earlier, SVD decomposition can bring a rudimentary form of intelligence on top of statistical results. This gives me a strong sense that, on one hand, the interpretability of a model—especially its probabilistic interpretation—is extremely important, and on the other hand, once I better understood SVD, I gained a much better feel for the meaning and applications of neural network models as well.

How exactly does SVD decomposition perform clustering?

Why is SVD decomposition a form of clustering? In fact, behind it lies a very simple probabilistic model.

Given a matrix $M_{m\times n}$, without loss of generality, assume that all of its entries are non-negative. This allows us to normalize each row, so that 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}$$

with the normalization condition

$$\sum_{j=1}^n p(b_j|a_i)=1, \quad i=1,2,\dots,m$$

Here $p(b_j|a_i)$ denotes the probability that $a_i$ is followed by $b_j$. This kind of probabilistic model is very common—for instance, in bigram language models.

Now suppose that the various $a_i$ can be grouped into $l$ clusters, denoted $c_1,c_2,\dots,c_l$; and that the various $b_i$ can be grouped into $k$ clusters, denoted $d_1,d_2,\dots,d_k$. We want to study the pattern of $a_i$ being followed by $b_j$, and in fact this can be simplified into a pattern between categories (a typical small example: we divide words into verbs, nouns, adjectives, etc., and then discover that verbs can be followed by nouns to form phrases—"verb + noun" is exactly the clustering pattern our brains have discovered). This is the sole assumption underlying SVD decomposition. More precisely, the assumptions are:

1. Both $a_i$ and $b_i$ can be grouped into some number of clusters;
2. The connection pattern between $a_i$ and $b_i$ can be reduced to the connection pattern between the clusters they belong to.

Given this, by the rules of probability, we obtain

$$p(b_j|a_i) = \sum_{k,l}p(b_j|d_k)p(d_k|c_l)p(c_l|a_i)$$

Every term here 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 that, given category $d_k$, the element is $b_j$.

This naturally gives us $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, as long as the assumptions hold, this formula holds exactly. And this operation is precisely the product of three matrices:

$$P(B|A)=P(B|D)\times P(D|C)\times P(C|A)$$

In other words, a matrix is factored into the product of three lower-dimensional matrices—and isn't that exactly SVD decomposition? Of course, there's a technical distinction: a probabilistic decomposition requires a normalization constraint, which is the territory of the pLSA model in topic modeling, whereas SVD decomposition itself doesn't require such normalization constraints. But this doesn't affect the core idea—that matrix factorization inherently carries a clustering meaning within it.

In this way, through matrix factorization, we cluster both the rows and the columns. We don't need to tell the computer which categories to cluster into (for instance, we don't need to tell it to divide words into nouns, verbs, adjectives, and so on)—matrix factorization accomplishes this directly. (Imagine: all you need is a megaphone shouting "Gather round, time to cluster!" and everyone automatically sorts themselves into groups, without us telling them how.) Or, putting it the other way around: through a probabilistic model, we've endowed SVD decomposition with the meaning of clustering.

Happy New Year

Ah... what I thought could be explained in a sentence or two ended up taking this many words instead. I hope readers won't find me too long-winded ^_^

Once again, happy New Year to everyone. As always, year after year: thank you for your continued support!