Home > Uncategorized > Spectral Algorithm

Spectral Algorithm


Spectral Algorithm

Spectral Algorithm[转自网络,参考用]

引自:http://bbs.sjtu.edu.cn/bbsdoc?board=AI&page=319

有关Spectral Algorithm

sigchi结束之后,这两天看了下spectral algorithm的一些相关的paper。现在给大家简要介绍一下。

有什么意见和建议板上提就好了。

一. 为什么选这个题目?

主要原因是去年在微软做的项目里用到了Spectral clustering,当时只是拿来用,并没有好好地看来龙去脉还有原理。

现在正好有空,补习一下。同时,这个方法是近年来相当热门的方法,大家比较关心,因此我想拿这个当topic应该不会冷场:)

二. 什么叫Spectral Algorithm

广义上来说,任何在算法中用到SVD/特征值分解的,都叫Spectral Algorithm。从很老很老的PCA/LDA,到比较近的Spectral Embedding/Clustering,都属于这类。

三. 为什么要用SVD/特征值分解

其实并不是为用而用,而是不得不用。目前在研究领域碰到的很多基础问题都是NP-hard的,找一个比较好的近似算法要费很大的精力;就算找到多项式的近似方法,也会出现实际使用上仍然太慢/解陷入局部极小等问题。

比如说用K-means聚类,建模本身已经够简单了,但它是NP-hard的,用传统的EM迭代作近似解会陷入局部极小。

反之,SVD理论上只有唯一解,算法速度相对又快,并且有大量理论结果及周边性质支持,可以 算是一个很理想地能将NP-hard问题“靠”上去的模型;它的另一个好处是,作为带约束二次规划的一种特殊情况,它对表达式为二次的目标函数的“兼容 性”比较好,“靠”所要求的数学技巧不高,任何人,任何方向都能拿来试试。

三. Spectral Algorithm的几个方向

传统的如PCA/LDA用来做线性降维,2000年左右的一些Spectral Embedding及Spectral Clustering,还有周边的一些,如Low-rank approximation等等。

四. PCA

PCA大家都很熟悉了,不过仍然有些最新的结果。

在这里(http://www.cc.gatech.edu/~vempala/spectral/spectral.pdf),一个问题被解答了:

为什么先做降维再做K-means,效果会更好呢?

另外,有趣的是K-means可以用PCA来做近似解。K-means是说找到K个点,使得所有点到这K个点的距离平方和最小;

而SVD是说找到一个子空间,使得所有点到这个子空间的距离平方和最小。于是这两者就建立了联系,K-means便relax到SVD上去了。

五. Spectral Clustering/Embedding

Spectral Clustering可算是Spectral Algorithm的重头戏。

所谓Clustering,就是说聚类,把一堆东西(合理地)分成两份或者K份。从数学上来说,

聚类的问题就相当于Graph Partition的问题,即给定一个图G = (V, E),如何把它的顶点集划分为不相交的子集,

使得这种划分最好。其难点主要有两个:

1. 这个“合理”其实相当难达到,随便设一个目标函数可能达不到希望的结果。大家可以看了看[1],这里详细地讨论了一下准则的选择问题。

2. 即使我们定义了一个相当好的聚类准则,如何优化它又是一个问题。

对于1,在Spectral Clustering这一块,各家有各家的想法。主要有以下几种:

a) 大名鼎鼎的Normalized Cut[2],还有一些变种如Ratio Cut/Minmax cut.

b) 和代数图论紧密相联的Minimum conductance[1].

c) 没有准则,但有证明的算法[3]

d) 不基于图,而是reformulate原来的聚类方法,使之变成SVD能解的问题[4]。

2则完全被1的选取所决定。

六. Normalized Cut

在图上,定义什么样的聚类最好,最简单的方法是圈定K个不相交顶点集之后,希望顶点集之间的边,其权值的和最小。

(边上的权值代表的是两头的顶点邻近的程度,或者说相似度)

这就是所谓MinCut(最小割)问题。二类分类的最小割不是NP-hard的,但是这不能让人感到开心,因为MinCut这个准则对于聚类不好。

具体来说,Mincut完全可能将离大部队过远的单个顶点与其它顶点分开, 形成两类。

事实上,我们不仅仅要让割边的权和最小,而且要让这K个顶点集都差不多大,这样才符合聚类给人的直观感觉。

于是在MinCut的基础上,出现了Normalized Cut. 思路很简单,将Cut normalize一下,除以表现顶点集大小的某种量度(如 vol A = 所有A中顶点集的度之和)。

也就是Normalize Cut(A, B) = Cut(A, B) / volA + cut(A, B) / volB

然而这样一改,NP-hard就来了。这几乎是所有组合优化问题的恶梦。

怎么办呢?把组合优化问题连续化,即所谓减少约束,进行适当的relax。那么为什么会和SVD扯上的呢?

很简单,聚类是东西分成不相交集,也就是有正交的含义在里面;只是分东西必须是0-1式的,这种离散化,就是np-hard的原因。

我们把正交约束保留,但把离散变成连续的,聚类就变成了寻找(列)正交阵的优化问题,那正是SVD的火力所在!

六. Normalized Cut (cont.)

就这样,通过这种巧妙的relax,NP-hard问题有了近似解。且不说这近似解的质量如何,这种方法是相当令人振奋的。

(关于Normalized Cut近似解的质量, 似乎没有什么文章能够给出严格的证明,只是实际效果不错就是了。)

值得一提的是,Normalized Cut还和图上的Markov chain有紧密的关系[5]。Normalized Cut这个量度,换成Markov chain的语言就是在图上随机游走,子集间相互“串门”的概率大小。相当有趣。

七. Minimum conductance

Minimum conductance是另一种Graph Partition的准则,和Normalized Cut看起来相当像,然而分析方法却完全不同。

Minimum conductance是图上的一种不变量,在代数图论中,它被称为Cheeger constant, 是指遍历所有的子集分划(A, B),边割除上min(vol A, vol B)的最小值。 vol是图上顶点集大小的量度(这个量度和Normalized Cut所用的量度是一样的)。

这个按理说比Normalized Cut所用的量度更难处理,因为有min函数。然而,有趣的是在代数图论中有这样的结论,图上的Laplace矩阵的第二小特征值(第一小是0)是Cheeger constant的一个估计[6]

2 * Cheeger constant <= \lambda <= (Cheeger constant)^2 / 2

OK,SVD再次登场,找到Laplace矩阵的第二小特征值,然后用相应特征向量做图的割,虽然差了点,但不会比Minimum conductance的割差到哪里去。并且差多少,是有理论界的[1]。

八. 没有准则,但有证明的算法

有时候写准则是很麻烦的,反过来说,不用准则直接给出算法及证明,难度更大然而更灵活。

[1]给出了一个递归算法,不断地把图分成两块,直到某个终止条件被满足,这样能做K类分类。

[1]还给出了证明,保证这样聚类出来的质量。相比之下,Normalized Cut对于对多类分类,无法给出这样的界,尽管它也是不断地二类分下去。

另外,[3]给出了一个能直接做多类分类的方法:先Spectral再K-mean. 它没有目标函数准则,却能用矩阵扰动理论,证明至少在稍许偏离理想情况下算法是work的。

[3]中提出的算法,正是我去年在项目中使用的算法的基础。

这种做法,给一直遵循从目标函数到算法这一步骤的我以很大的启发。原来自己走的路一直是很窄的啊。

九. Reformulate原来的聚类方法

或许Spectral Clustering给我们留下最重要的,并不是那么多算法,而是将SVD融入优化问题的思路,即所谓的spectral relaxation。

[4]正是使用了这条思路,将K-means重新建模,以离散化连续,relax成可以用SVD解的问题,并解之。

[4]就数学技巧而言只能说一般般,但是用上了,就会出来很有趣的东西。

十. 其它一些聚类方法

此外,还有其它的一些用到Spectral Algorithm的聚类方法。如[7]里面,Spectral Algorithm用来将点集分成树状,然后在树上以其它准则(如K-means) 将树叶合并回去,形成最终的聚类结果。在树上很多本来np-hard的问题就变成可以用动态规划解了。

十一. Spectral Embedding,一些非线性降维的方法

除了Spectral clustering, Spectral Embedding即用spectral algorithm来进行非线性降维,也是谱算法的应用之一。

这个和流形学习有一定联系,Salu大哥对此方面极为精通,呵呵。

Laplacian Eigenmap[9]是其中一个很有名的方法。它也是使用图的Laplace矩阵,优化一个二次函数,解SVD得到的。

只是这里不像聚类,没有relax的过程,因此得到的就是精确解。

十二. 一些周边

1. Low-rank approximation

目前来说,解SVD已经算相当快了,但是仍然满足不了某些应用的胃口。因此解SVD的方法也有了一些发展。用随机算法是一个趋势。

2. Semi-definite Programming(SDP)

作为Spectral algorithm的竞争对手,把一些聚类问题relax到SDP在理论上会有更好的结果,不过实验上看不出差别[11]。而且要命的是……实在太复杂了。

十三. 一些有用的资料和website

http://crd.lbl.gov/~cding/Spectral/

这个不用说了,查spectral clustering第一个就是它。不过页面上附的Tutorial实在不行,单看是几乎不懂的。还是老老实实看Selected References里的paper比较好。

http://www.cc.gatech.edu/~vempala/papers/spectral.html

某个从MIT跳到Gatech的大牛的主页。也是做spectral algorithm方面。与那些发在NIPS上的文章相比,数学味道还要重。个人觉得,这才是做理论的正道~~。

PS. 似乎有一篇NIPS在数学上有些问题,我今天早上发现的。大家有空可以看看。

F.R. Bach and M.I. Jordan. Learning spectral clustering. Neural Info. Processing Systems 16 (NIPS 2003), 2003.

其中的Theorem 1.

十四. 匆匆结语

这两天第一次感觉到读paper应该有的态度:即集中一个问题,找很多篇paper来读;而不是东一点西一点。

老实说,这个review实在是写得不怎么样,东西都只是皮毛。之后还会继续看,继续推荐大家有趣的文章和想法。

谢谢。

“我们在无穷无尽无解的问题之中穿行,如一头扎进不见五指的黑暗。

偶尔看到些亮光,便如飞蛾般扑将过去,品味这星星点点的温暖。

神说,人类是多么不自量力,想要用这些星点,去驱散整个夜晚。

可是我们是多么想要去光明的彼岸,去理解这个世界的巧妙,大脑的纷繁。

在重重迷雾之中,我们能够倚仗的,就只有已知的这些,人类迄今为止,一点一滴收集而

来,似乎可行的方案。”

参考文献:

[1] Ravi Kannan and Adrian Vetta, On clusterings: good, bad and spectral. Journal of the ACM (JACM) 51(3), 497–515, 2004.

[2] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE. Trans.on Pattern Analysis and Machine Intelligence, 22:888–905, 2000.

[3] A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Proc. Neural Info. Processing Systems (NIPS 2001), 2001.

[4] H. Zha, C. Ding, M. Gu, X. He, and H.D. Simon. Spectral relaxation for K-means clustering. Advances in Neural Information Processing Systems 14 (NIPS 2001). pp. 1057-1064, Vancouver, Canada. Dec. 2001.

[5] M. Meila and J. Shi. A random walks view of spectral segmentation. Int’l Workshop on AI & Stat (AI-STAT 2001).

[6] F.R.K. Chung. Spectral Graph Theory. Amer. Math. Society Press, 1997.

[7] A Divide-and-Merge Methodology for Clustering (D. Cheng, R. Kannan and G.Wang) Proc. of the ACM Symposium on Principles of Database Systems, 2005.

[8] H. Zha, X. He, C. Ding, M. Gu & H. Simon. Bipartite Graph Partitioning and Data Clustering, Proc. of ACM 10th Int’l Conf. Information and Knowledge Management (CIKM 2001), pp.25-31, 2001, Atlanta.

[9] M. Belkin and P. Niyogi. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Advances in Neural Information Processing Systems 14(NIPS 2001), pp: 585-591, MIT Press, Cambridge, 2002.

[10] E.P. Xing and M.I. Jordan. On semidefinite relaxation for normalized k-cut and connections to spectral clustering. Tech Report CSD-03-1265, UC Berkeley, 2003.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: