week 5,6

lecture

  • 9.24

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

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

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

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

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

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

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

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

        • $\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|}$
        • $\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(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/(\overline{cut}+cut)$，后者更自然。我们接下来证明，前者对应L，后者对应$L_{rw}$，因此L不如$L_{rw}$。

        令

        $f_{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.$

        则有

        $\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的优化对应于$f^tLf$在约束（可以观察得到）$f \perp \mathbb{1},\|f\|=\sqrt{n}$下的优化问题，而对这我们已经熟悉了。

        同理，令

        $f_{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.$

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

  • 10.1

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

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

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

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

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

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

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

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