SVD分解(二):为什么SVD意味着聚类?
By 苏剑林 | 2017-01-26 | 74334位读者 |提前祝各位读者新年快乐,2017行好运~
这篇文章主要想回答两个“为什么”的问题:1、为啥我就对SVD感兴趣了?;2、为啥我说SVD是一个聚类过程?回答的内容纯粹个人思辨结果,暂无参考文献。
为什么要研究SVD? #
从2015年接触深度学习到现在,已经研究了快两年的深度学习了,现在深度学习、数据科学等概念也遍地开花。为什么在深度学习火起来的时候,我反而要回去研究“古老”的SVD分解呢?我觉得,SVD作为一个矩阵分解算法,它的价值不仅仅体现在它广泛的应用,它背后还有更加深刻的内涵,即它的可解释性。在深度学习流行的今天,不少人还是觉得深度学习(神经网络)就是一个有效的“黑箱”模型。但是,仅用“黑箱”二字来解释深度学习的有效性显然不能让人满意。前面已经说过,SVD分解本质上与不带激活函数的三层自编码机等价,理解SVD分解,能够为神经网络模型寻求一个合理的概率解释。
近来,我尝试做一些较为复杂的模型,比如问答系统、聊天机器人,我越来越感觉到,刚开始上手的时候,最近大放异彩的seq2seq之类的深度学习模型基本没法用。我基本上是从最基本的概率模型$P(A|Q)$出发,逐步简化,最后得到一个复杂度可以接受的模型。这样得到的模型意义清晰、可控性强。但是其中的一部分是基于统计来做的,纯粹的统计没法得到真正“智能”的结果,而前面说过,SVD分解可以在统计结果的基础上带来初步的智能。这给我强烈的感觉,一个是模型的可解释性尤其是概率解释是很重要的,另外一个是更好理解了SVD之后,对神经网络模型的意义和应用都更有感觉了。
SVD分解是怎么聚类的? #
为什么SVD分解是聚类?其实这里边是一个很简单的概率模型。
给定矩阵$M_{m\times n}$,不失一般性,假设它每个元素都是非负数,这样我们就可以对每一行做归一化,这样,得到的矩阵可以表示一个转移概率
$$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}$$
归一化条件是
$$\sum_{j=1}^n p(b_j|a_i)=1, \quad i=1,2,\dots,m$$
所谓$p(b_j|a_i)$,即$a_i$后接$b_j$的概率,这种概率模型是很常见的,比如二元语言模型。
现在我们假设各个$a_i$可以聚为$l$个类,分别为$c_1,c_2,\dots,c_l$;而各$b_i$可以聚为$k$个类,分别为$d_1,d_2,\dots,d_k$;我们要研究$a_i$后接$b_j$的规律,事实上可以简化为类别之间的规律(一个典型的小案例就是:我们将词语分为动词、名词、形容词等,然后发现动词后面可以接名词构成短语,“动词+名词”就是我们大脑发现的聚类规律了)。这就是SVD分解的唯一假设了。更清晰地,假设包括:
1、$a_i$和$b_i$都可以聚为若干个类;
2、$a_i$和$b_i$之间的连接规律可以简化为两者所属的类的连接规律。
这时候根据概率公式,就得到
$$p(b_j|a_i) = \sum_{k,l}p(b_j|d_k)p(d_k|c_l)p(c_l|a_i)$$
每一项都有非常清晰的概率意义:
$p(c_l|a_i)$是$a_i$表现为类别$c_l$的概率;
$p(d_k|c_l)$是类别$c_l$后接类别$d_k$概率;
$p(b_j|d_k)$是已知类别$d_k$时,元素为$b_j$的概率。
这样自然有$p(b_j|a_i) = \sum_{k,l}p(b_j|d_k)p(d_k|c_l)p(c_l|a_i)$,也就是说,只要假设成立,那么这个公式是精确成立的。而这个运算,正好是三个矩阵的乘法:
$$P(B|A)=P(B|D)\times P(D|C)\times P(C|A)$$
也就是说,一个矩阵分解为三个维度更低的矩阵相乘,这不就是SVD分解吗?当然,细致上的区别是,如果是概率分解,则需要有归一化要求,这部分内容属于主题模型中pLSA模型的内容,而SVD分解本身不需要归一化约束,但这不影响本质思想,即矩阵分解蕴含了聚类的意义在里边。
这样,我们就通过矩阵分解,来对行与列进行了聚类。我们不需要告诉计算机聚成哪些类(比如,不需要告诉计算机要将词语分为名词、动词、形容词等),而是直接矩阵分解来完成(试想一下,只要用“大声公”喊一声“集合啦,要聚类啦”,大家自动分好类,不用我们告诉它怎么做。)。或者反过来说,我们通过概率模型,为SVD分解赋予了聚类意义。
新年快乐 #
额...本来感觉一两句话可以讲清楚的事情,又扯了那么多文字,希望读者不要觉得我哆嗦^_^
再次祝大家新年快乐啦,年年都是那句:希望大家多多捧场!
转载到请包括本文地址:https://www.spaces.ac.cn/archives/4216
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Jan. 26, 2017). 《SVD分解(二):为什么SVD意味着聚类? 》[Blog post]. Retrieved from https://www.spaces.ac.cn/archives/4216
@online{kexuefm-4216,
title={SVD分解(二):为什么SVD意味着聚类?},
author={苏剑林},
year={2017},
month={Jan},
url={\url{https://www.spaces.ac.cn/archives/4216}},
}
December 25th, 2017
解释的真不错呀
May 9th, 2019
写得很有启发性,但是我还是有点疑问:
***
正好是三个矩阵的乘法:
P(B|A)=P(B|D)×P(D|C)×P(C|A)
***
关于上面这一段,svd的sigema矩阵是对角矩阵,而P(D|C)不是对角矩阵
这么解释好像存在一定的问题
其实我当初理解的SVD是优化角度的,即对于矩阵$\boldsymbol{A}$,找到矩阵$\boldsymbol{B},\boldsymbol{C},\boldsymbol{D}$,使得$\Vert \boldsymbol{A} - \boldsymbol{B}\boldsymbol{C}\boldsymbol{D}\Vert_F$最小化。这样一来$\boldsymbol{C}$就未必是对角形式了~
这对svd 一种聚类方向的解释吧,确实能够解释为什么选每一行最大值所在列作为数据的类别这个问题。
不过svd本质还是线性变换吧,n为空间到m 维空间的变换,本质还是纯数学的吧,这样更加严谨。
我们老师讲svd说了svd 可以聚类,但是就说这样就可以,不知道为什么,博主给了一个解释,挺有启发的。
July 11th, 2019
挺有意思的,苏神是否可以讲讲 SVD对二分图进行聚类,找到k类具有紧密关系结构的子图
September 26th, 2019
感谢分享,文中“近来,我尝试做一些较为复杂的模型,比如问答系统、聊天机器人,我越来越感觉到,刚开始上手的时候,最近大放异彩的seq2seq之类的深度学习模型基本没法用。” 想问下苏神,为什么seq2seq之类的模型不能胜任QA、chatbot之类的复杂任务?还有类似这些复杂的任务一般用什么模型来做呢?
seq2seq可控性很差。当然这是当年的评价了,现在已经有长足的进步了。
October 7th, 2019
p(bj|ai)=∑k,lp(bj|dk)p(dk|cl)p(cl|ai) 这个公式是怎么推到出来的呢?
这个公式就是两个假设的等价写法,不是推导出来的。
July 19th, 2020
“对每一行做归一行”应该是“归一化”。
done. thanks.
November 15th, 2021
很受启发!
December 27th, 2021
想请问下 p(bj|ai)=∑k,lp(bj|dk)p(dk|cl)p(cl|ai) 这里可以这么用吗,是否需要bj与cl, ai无关的假设呢?
严格来说是需要声明。但这里很明显,只是解决转移概率的类比来为矩阵乘法赋予一个形象的意义,从而为SVD赋予一个形象的意义,所以get到思想就行了,不必要纠结细节,因为本来就不是什么严格的证明。
好的,谢谢您~