譜聚類的consistency

02-12

這篇文章想談論的話題比較理論

是有關譜聚類方法

譜聚類方法是通過圖laplace的譜來做聚類的方法

如果把數據想像成在一個manifold上，那麼圖上laplace可以看成流形上laplace的逼近

譜聚類可以理解成在manifold上解類似laplace的特徵值問題

比如semi-supervised learning就可以把知道label的部分當成邊界條件，也就是知名的HARMONIC EXTENSION

比如這篇就用了pim方法來解harmonic extension

Harmonic extension on point cloud"

by Z. Shi, J. Sun and M. Tian, accepted by SIAM: Multiscale Modeling & Simulation, 2017.

[ .pdf ]

label propagation演算法就理解成冪法［不動點迭代］解方程

上面那篇的pim的是說傳統的graph laplacian對邊界的離散不對。。。。

流行上的laplace方程難解

所以

Andrea L. Bertozzi and Arjuna Flenner, Diffuse Interface Models on Graphs for Classification of High Dimensional Data, SIAM Review, 58(2), pp. 293-328, 2016.

在流形上用GL泛函做了laplace方程的逼近

今天主要講的Dejan Slep?evs home page 一系列工作

其實關於流形上laplace蒜子的收斂有很多工作

Asymptotic behavior of $ell_p$-based Laplacian regularization in semi-supervised learning. A. El Alaoui, X. Cheng, A. Ramdas, M. Wainwright and M. I. Jordan.Proceedings of the Conference on Computational Learning Theory (COLT), New York, NY, 2016.

"Convergence of Laplacian spectra from random samples"

by Zuoqiang Shi

[ .pdf | arXiv math.NA 1507.00151 ]

但是譜聚類是作為一個變分問題，我們需要的不是蒜子收斂是，變分問題最小值收斂，所以需要證明一個gamma收斂

第一篇工作就是這個方向

Continuum limit of total variation on point couds, Arch. Ration. Mech. Anal., Vol. 220, No. 1, (2016), pages 193-241. preprint, published

證明了點雲上TV蒜子gamma收斂到流形上的TV

最難的點雲和流形兩個定義域不一樣，怎麼定義收斂呢？

這裡用了非常非常聰明的idea，就是用了optimal transport的想法

知道optimal transport的同學，如果給兩個概率空間定義距離，就是做一個coupling然後極小化距離,coupling可以把兩個度量空間couple到一起，也就是找一個pi讓

${P_1}_#pi = mu, {P_2}_#pi = u$ （就是兩個軸上邊際分布分別是兩個測度

如果有兩個domain怎麼定義上面的蒜子的收斂呢,想法一樣，構造couple，讓x和y配上，然後再算函數的差，寫出來就是這樣

$d((mu,f),( u,g))= inf_piint(|x-y|^p+|f(x)-g(y)|^p)dpi(x,y)$

有了這個idea以後之後的證明就是分析的簡單套路了。。。。

然後做了圖的Cheeger cut的consistency

Consistency of Cheeger and ratio graph cuts, preprint

分析了譜聚類的consistency

A variational approach to the consistency of spectral clustering, Applied and Computational Harmonic Analysis, preprint, published

以及他們最近推廣到了lp和error rate了［我還沒看

Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator, preprint

Analysis of p-Laplacian regularization in semi-supervised learning ,preprint

其實我們可以想更多的問題

比如局部的low rank是不是對laplace的另外一種離散化呢？

這種pde的觀點對graph cnn的構建有沒有什麼幫助？