ML笔记(3)

week 5,6

lecture

  • 9.24

    • 今天讲的是无向图的spectral clustering。开了个头。

    • 记号:图G=(V,E)G=(V, E),其各边权重w,各点degree为权重之和d。子图A,其补集Aˉ\bar{A}。那么有两种方式定义一个子图的size:

      A:=|A| := the number of vertices in AA
      vol(A):=iAdi\operatorname{vol}(A) :=\sum_{i \in A} d_{i}

    • Graph laplacian的性质。首先,ftLf=12i,j=1nwij(fifj)2f^{t} L f=\frac{1}{2} \sum_{i, j=1}^{n} w_{i j}\left(f_{i}-f_{j}\right)^{2},L半正定,具有trivial的本征值0和本征向量I\mathbb{I}。假设其具有互不连通的子图{Ai}\{A_i\},那么ker(L)=span(IAi)ker(L)=span(\mathbb{I}_{A_i})

    • Clustering。步骤是确定的:首先从feature构建图(比如最近邻或距离范围),确定希望聚成k类,然后求出L的前(对应最小的一些本征值)k个本征向量V=(v0,,vk1)V=(v_0, \cdots, v_{k-1}),该矩阵的第i行就是Rk\mathbb{R}^k中embed的第i个点的坐标。最后,用k-means或者别的算法在欧氏空间中聚类。

    • 为什么使用LrwL_{rw}优于L,LsymL,L_{sym}?

      • LsymL_{sym}的问题在于,其本征向量并非L的本征向量viv_i,而是D1/2viD^{1/2}v_i。这样的话,degree小了容易吃亏,被embed的太靠近原点(而其本身未必如此),所以必须对每行归一化,这也不是没有损失的。

      • L的问题要复杂一些。首先,我们考虑一个问题:**图的分割。**我们想把图切成两部分,它们之间联系尽量少。定义图的一个割是cut(A,B)=iA,jBwij\operatorname{cut}(A, B)=\sum_{i \in A, j \in B} w_{i j},为了避免只切下来一个点这种trivial的错误,我们实际上minimized的不少一个cut,而是

        • RatioCut(A1,,Ak)=i=1kcut(Ai,Ai)Ai\operatorname{RatioCut}\left(A_{1}, \ldots, A_{k}\right)=\sum_{i=1}^{k} \frac{\operatorname{cut}\left(A_{i}, \overline{A}_{i}\right)}{\left|A_{i}\right|}
        • Ncut(A1,,Ak)=i=1kcut(Ai,Ai)vol(Ai)\operatorname{Ncut}\left(A_{1}, \ldots, A_{k}\right)=\sum_{i=1}^{k} \frac{\operatorname{cut}\left(A_{i}, \overline{A}_{i}\right)}{\operatorname{vol}\left(A_{i}\right)}

        其中N代表归一化。我们觉得后者在原理上更优,是因为考虑到vol(Ai)=lAidl=lAikAiwlk+lAikAiwlkvol(A_i)=\sum_{l\in A_i}d_l=\sum_{l\in A_i}\sum_{k\in A_i}w_{lk}+\sum_{l\in A_i}\sum_{k\notin A_i}w_{lk},所以cut/vol=cut/(cut+cut)cut/vol=cut/(\overline{cut}+cut),后者更自然。我们接下来证明,前者对应L,后者对应LrwL_{rw},因此L不如LrwL_{rw}

        fi={A/A if viAA/A if viAf_{i}=\left\{\begin{array}{ll}{\sqrt{|\overline{A}| /|A|}} & {\text { if } v_{i} \in A} \\ {-\sqrt{|A| /|\overline{A}|}} & {\text { if } v_{i} \in \overline{A}}\end{array}\right.

        则有

        fLf=i,j=1nwij(fifj)2=iA,jAwij(AA+AA)2+iA,jAwij(AAAA)2=2cut(A,A)(AA+AA+2)=2cut(A,A)(A+AA+A+AA)=2VRatioCut(A,A)\begin{aligned} f^{\prime} L f &=\sum_{i, j=1}^{n} w_{i j}\left(f_{i}-f_{j}\right)^{2} \\ &=\sum_{i \in A, j \in \overline{A}} w_{i j}(\sqrt{\frac{|\overline{A}|}{|A|}}+\sqrt{\frac{|A|}{|\overline{A}|}})^{2}+\sum_{i \in \overline{A}, j \in A} w_{i j}(-\sqrt{\frac{|\overline{A}|}{|A|}}-\sqrt{\frac{|A|}{|\overline{A}|}})^{2} \\ &=2 \operatorname{cut}(A, \overline{A})\left(\frac{|\overline{A}|}{|A|}+\frac{|A|}{|\overline{A}|}+2\right) \\ &=2 \operatorname{cut}(A, \overline{A})\left(\frac{|A|+|\overline{A}|}{|A|}+\frac{|A|+|\overline{A}|}{|\overline{A}|}\right) \\ &=2|V| \cdot \operatorname{Ratio} \operatorname{Cut}(A, \overline{A}) \end{aligned}

        因此,RatioCut的优化对应于ftLff^tLf在约束(可以观察得到)f1,f=nf \perp \mathbb{1},\|f\|=\sqrt{n}下的优化问题,而对这我们已经熟悉了。

        同理,令

        fi={vol(A)volA if iAvol(A)vol(A) if iAf_{i}=\left\{\begin{array}{ll}{\sqrt{\frac{\operatorname{vol}(\overline{A})}{\operatorname{vol} A}}} & {\text { if } i \in A} \\ {-\sqrt{\frac{\operatorname{vol}(A)}{\operatorname{vol}(\overline{A})}}} & {\text { if } i \in \overline{A}}\end{array}\right.

        则有: ftLf=2vol(V)Ncut(A,A)f^tLf=2\operatorname{vol}(V) \operatorname{Ncut}(A, \overline{A}),受约束Df1,fDf=vol(V)D f \perp \mathbb{1}, f^{\prime} D f=\operatorname{vol}(V)。从我们对于Rayleigh Quotient的知识可以知道,这对应的广义本征值问题就是Lf=λDfLf=\lambda Df,即Lrwf=λfL_{rw}f=\lambda f

  • 10.1

    • 今天讲了两个东西:SNE和t-SNE。后者是对前者的改进。SNE是stochastic neighbor embedding,是从概率分布的角度建立的一种数据降维的方法。具体来说,找一个高维的数据集S={x1xn}S=\{\vec{x_1}\cdots\vec{x_n}\},取从xi到xj的概率为pji=1Zexp(xixj22/2σi)p_{j|i}=\frac{1}{Z}\exp(-||x_i-x_j||_2^2/2\sigma_i),其中Z=j,jiexp(xixj22/2σi)Z=\sum_{j,j\neq i}\exp(-||x_i-x_j||_2^2/2\sigma_i),这是一个先验的分布。现在我们把x\vec{x}嵌入低维的y\vec{y}。取在低维的先验分布是qjiexp(yiyj22)q_{j|i}\propto\exp(-||y_i-y_j||_2^2),我们利用梯度下降法优化两个优化之间的KL散度Cost:=C=KL(PQ)=EP(log(P/Q))Cost:=C=KL(P|Q)=E_P(log(P/Q)),取得最好的{y}\{\vec{y}\}。具体来说,yiC=2ji(pjiqji+pijqij)(yiyj)\nabla_{y_i}C=2\sum_{j\neq i}(p_{j|i}-q_{j|i}+p_{i|j}-q_{i|j})(\vec{y_i}-\vec{y_j})

    • 优化过程中,还有一些超参数值得讨论。例如先验分布的参数σi\sigma_i。优化的办法是基于实践的:我们从熵的定义,约认为Perplexity(Pi)=2jplogpPerplexity(P_i)=2^{-\sum_j p\log p}代表系统的自由度,我们取σi\sigma_i,使得先验分布的自由度在10左右。另外还应该讨论梯度下降的学习率η\eta,但并没有讲。

    • SNE也有它的一些问题,比如

      • KL是不对称的。在这个情境下,这可能会导致把离得较远的x给map到离得较近的y上。

        但是这可以通过选取对称的jensen-shannon散度(JSD(PQ)=12D(PM)+12D(QM)\mathrm{JSD}(P \| Q)=\frac{1}{2} D(P \| M)+\frac{1}{2} D(Q \| M),其中M=12(P+Q)M=\frac{1}{2}(P+Q))来部分的解决。

      • 梯度下降一个方向一次要计算四个概率,很伤。

    • t-SNE是一种改进。具体来说,主要就是把在低维的先验分布扽出一个肥尾,变成t分布,qi,j(1+yiyj22)1q_{i,j}\propto(1+||y_i-y_j||_2^2)^{-1}。另外,在高维的情况下,先验分布的配分函数改成Z=j,i,jiexp(xixj22/2σ)Z=\sum_{j,i,j\neq i}\exp(-||x_i-x_j||_2^2/2\sigma)。这时候

      • yiC=4ji(pijqij)(yiyj)(1+yiyj2)1\nabla_{y_i}C=4\sum_{j\neq i}(p_{ij}-q_{ij})(y_i-y_j)(1+||y_i-y_j||^2)^{-1}。注意最后一项,它会通过惩罚离得太近的点避免SNE的第一个问题。
      • 它一次只要计算两个概率。
    • 在实际应用中,我们一般用PCA这样的方法来发现feature,用t-SNE这样的方法来发现community structure。具体来说,后者在聚类方面表现不错,但是其坐标轴的旋转是不会改变结果的,因为我们一直在处理2-norm。也就是说,我们没办法确定哪些是feature代表的方向。

reading material

  • Laurens van der Maaten et Geoff Hinton, t-SNE, 2008

    这是 Hinton 2008年提出t-SNE的文章。

    • 首先指出,以往的主流数据降维方法大多数是线性的,例如PCA,MDS等。这些方法落到操作上都是在矩阵的谱上做文章。然而,属于新时代的数据集呈现出越来越高维的特点,它们一般都处在一个高维的、非线性的流形上,因此,对这些数据集的降维需要更有效的手段。作者指出,一个指导思想是聚焦于clustering,保持离得较近的点仍然离得较近。

    • SNE的介绍与缺陷。值得注意的是,SNE同样是Hinton提出来的。。。

      除了lecture部分提到的不对称带来的问题之外,还要考虑crowding问题:在高维,例如十维空间,可以有11个点,其两两等距。因此,我们现在假设有一个半径适中的九维球面,上有分布得较稀疏的点。直接降维到二维之后,如果还是和球心离得这么近,这些点一下子被挤在一起,非常密集,cluster结构就没有了。如果调大半径,一下子被弄得非常远,Cost的梯度又不答应。这个问题除了SNE,很多类似的降维方法都深受其害。

    • 改进的思路。

      • SNE里面的配分函数本来是k,kiexp(xixk2/2σi2)\sum_{k,k \neq i} \exp \left(-\left\|x_{i}-x_{k}\right\|^{2} / 2 \sigma_{i}^{2}\right),现在我们把它变成对称的klexp(xkxl2/2σ2)\sum_{k \neq l} \exp \left(-\left\|x_{k}-x_{l}\right\|^{2} / 2 \sigma^{2}\right)。这依然有问题,因为一个离群的x对应的p将会非常小,对于Cost几乎没有影响,这是我们不希望看到的。
      • 我们可以换一种做法,pij=pji+pij2np_{i j}=\frac{p_{j | i}+p_{i | j}}{2 n},避免这个问题,同时保证配分函数仍然是对称的。
      • 为了解决crowding problem,我们可以让低维的分布更均匀些,或是尾巴更肥些,这样避免优化Cost的时候把球面上的那些点全挤在一起。于是,就选中t分布,取参数最简单的一种情形。