ML笔记(3)
week 5,6
lecture
-
9.24
-
今天讲的是无向图的spectral clustering。开了个头。
-
记号:图,其各边权重w,各点degree为权重之和d。子图A,其补集。那么有两种方式定义一个子图的size:
the number of vertices in
-
Graph laplacian的性质。首先,,L半正定,具有trivial的本征值0和本征向量。假设其具有互不连通的子图,那么。
-
Clustering。步骤是确定的:首先从feature构建图(比如最近邻或距离范围),确定希望聚成k类,然后求出L的前(对应最小的一些本征值)k个本征向量,该矩阵的第i行就是中embed的第i个点的坐标。最后,用k-means或者别的算法在欧氏空间中聚类。
-
为什么使用优于?
-
的问题在于,其本征向量并非L的本征向量,而是。这样的话,degree小了容易吃亏,被embed的太靠近原点(而其本身未必如此),所以必须对每行归一化,这也不是没有损失的。
-
L的问题要复杂一些。首先,我们考虑一个问题:**图的分割。**我们想把图切成两部分,它们之间联系尽量少。定义图的一个割是,为了避免只切下来一个点这种trivial的错误,我们实际上minimized的不少一个cut,而是
其中N代表归一化。我们觉得后者在原理上更优,是因为考虑到,所以,后者更自然。我们接下来证明,前者对应L,后者对应,因此L不如。
令
则有
因此,RatioCut的优化对应于在约束(可以观察得到)下的优化问题,而对这我们已经熟悉了。
同理,令
则有: ,受约束。从我们对于Rayleigh Quotient的知识可以知道,这对应的广义本征值问题就是,即。
-
-
-
10.1
-
今天讲了两个东西:SNE和t-SNE。后者是对前者的改进。SNE是stochastic neighbor embedding,是从概率分布的角度建立的一种数据降维的方法。具体来说,找一个高维的数据集,取从xi到xj的概率为,其中,这是一个先验的分布。现在我们把嵌入低维的。取在低维的先验分布是,我们利用梯度下降法优化两个优化之间的KL散度,取得最好的。具体来说,。
-
优化过程中,还有一些超参数值得讨论。例如先验分布的参数。优化的办法是基于实践的:我们从熵的定义,约认为代表系统的自由度,我们取,使得先验分布的自由度在10左右。另外还应该讨论梯度下降的学习率,但并没有讲。
-
SNE也有它的一些问题,比如
-
KL是不对称的。在这个情境下,这可能会导致把离得较远的x给map到离得较近的y上。
但是这可以通过选取对称的jensen-shannon散度(,其中)来部分的解决。
-
梯度下降一个方向一次要计算四个概率,很伤。
-
-
t-SNE是一种改进。具体来说,主要就是把在低维的先验分布扽出一个肥尾,变成t分布,。另外,在高维的情况下,先验分布的配分函数改成。这时候
- 。注意最后一项,它会通过惩罚离得太近的点避免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里面的配分函数本来是,现在我们把它变成对称的。这依然有问题,因为一个离群的x对应的p将会非常小,对于Cost几乎没有影响,这是我们不希望看到的。
- 我们可以换一种做法,,避免这个问题,同时保证配分函数仍然是对称的。
- 为了解决crowding problem,我们可以让低维的分布更均匀些,或是尾巴更肥些,这样避免优化Cost的时候把球面上的那些点全挤在一起。于是,就选中t分布,取参数最简单的一种情形。
-