发信人: tydsh(To unknown future...forge on), 信区: AI
标  题: 有关Spectral Algorithm (4) (over)
发信站: 饮水思源 (2007年09月23日22:44:28 星期天)

十一. 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. Processi
ng Systems 16 (NIPS 2003), 2003. 
其中的Theorem 1. 

十四. 匆匆结语
这两天第一次感觉到读paper应该有的态度：即集中一个问题，找很多篇paper来读；而不是东一点西一点。
老实说，这个review实在是写得不怎么样，东西都只是皮毛。之后还会继续看，继续推荐
大家有趣的文章和想法。
谢谢。

“我们在无穷无尽无解的问题之中穿行，如一头扎进不见五指的黑暗。
偶尔看到些亮光，便如飞蛾般扑将过去，品味这星星点点的温暖。
神说，人类是多么不自量力，想要用这些星点，去驱散整个夜晚。
可是我们是多么想要去光明的彼岸，去理解这个世界的巧妙，大脑的纷繁。
在重重迷雾之中，我们能够倚仗的，就只有已知的这些，人类迄今为止，一点一滴收集而
来，似乎可行的方案。”

参考文献：
[1] Ravi Kannan and Adrian Vetta, On clusterings: good, bad and spectral. Jour
nal 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 a
n 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-m
eans clustering. Advances in Neural Information Processing Systems 14 (NIPS 20
01). pp. 1057-1064, Vancouver, Canada. Dec. 2001. 
[5] M. Meila and J. Shi. A random walks view of spectral segmentation. Int'l W
orkshop 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 Mana
gement (CIKM 2001), pp.25-31, 2001, Atlanta. 
[9] M. Belkin and P. Niyogi. Laplacian Eigenmaps and Spectral Techniques for E
mbedding 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-cu
t and connections to spectral clustering. Tech Report CSD-03-1265, UC Berkeley
, 2003. 
--
。。。。。。
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 207.46.92.19]

※ 修改内容:·tydsh 于 09月23日22:45:55 修改本文·[FROM: 207.46.92.19]