Posts

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....

week 3,4 lecture 9.10 今天首先提了一些零碎的点，可以略去。 讲了算子的连续性和有界性，以及矩阵的范数。上一周已经看过讲义了，不再重复。 一点应用。实际上就是奇异值分解的应用动机。假设$X$是random vector，将其标准化，取mean=0，std=1。令$\Sigma=Cov(X)=(Cov(x_i, x_j))$，为了理解数据，我们经常要降维，并且我们希望低维下数据尽可能稀疏。取模长为1的向量w作为降维“平面”的第一个轴的方向，要求$var(w^tX)=w^t\Sigma w$取最大值，而由于奇异值分解可以给出$\Sigma=\sum\lambda_iv_iv_i^t$，$\lambda_i=\sigma_i^2$，我们知道$w^t\Sigma w=\sum\lambda_i(v_iw)^2$，其中$\sum(v_i^tw)^2=const.$，这样，低维“平面”首先确立的一个轴肯定就是最大的奇异值对应的v的方向，第二个轴就是次大的奇异值对应的方向（因为要求垂直于上一个轴），诸如此类。 补充（9.17）从作业题目中意识到，在均值为零的情形下，由勾股定理，低维下数据最稀疏（或说方差最大）意味着向低维投影的过程中损失的最少（或说各数据点离低维平面的距离平方和最小）。 9.12 PCA的主要精神是保 similarity （最大化variance）。作为对照，今天引出的另外一个降维手段 multidim scaling 的主要精神是保距离（的序）。这些东西的目的都是把数据可视化的牺牲降到最低。我们需要数据可视化，因为我们现在对高维数据的性质的理解还不完全，特别是对物理学家而言，他们的思维需要一个实在的处理对象。 Rayleigh Quotient。定义为$R(v)=\frac{x^tAx}{x^tBx}$，一个主要的问题是maximize它，例如$A=\Sigma, B=I$时，最大化RQ的过程也就是做PCA的过程。对于scaling系数$\alpha\neq0$，RQ具有 scaling 不变性，因此我们令分母为1，定义一个Lagrangian $\mathcal{L}=x^tAx-\lambda(x^tBx-1)$。求导，得到$Ax=\lambda Bx$，这个叫 general eigenvalue equation。解法是先得出$B^{-1}Ax=\lambda x$，然后写成$(B^{-1/2}AB^{-1/2})(B^{1/2}x)=\lambda(B^{1/2}x)$，然后转化成人们熟练的sym mat的本征值问题（因为sym mat的本征向量才确保正交）。解出来之后，考虑到$R(v_i)=\lambda_i$，我们找到$\lambda_1$对应的$v_1$即可。 Kernalized PCA。假使我们有数据集$X=(\vec{x_1}, \cdots\vec{x_m})^t$，我们的数据有n个feature，m个sample。现在，常常出现的一个情况是$m\ll n$。比如说，人有2e4个基因，但是一次实验一般只能测到1e2个人。对一个上万甚至是上百万维的矩阵做SVD是有困难的，我们可以使用kernel trick绕开这一困难。 假使我们的PC为$v_i=\frac{X^tw_i}{\sqrt{\lambda_i}}$，那么数据点x的第i个分量将会是$\sum_j\frac{x^t\vec{x_j}(w_i)_j}{\sqrt{\lambda_i}}$。我们选取kernel $K:\mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}$。我们将内积$x^ty$换成hilbert space中的一个内积$K(x,y)=\langle\phi(x),\phi(y)\rangle$。我们将本征值和本征向量$\sqrt{\lambda_i},w_i$换成矩阵$(K(x_i,x_j))$的相关参数。这样，我们就不需要处理一个$m\times n$矩阵的SVD，只需要处理一个$m\times m$矩阵的本征值问题。 9/17补充：这个操作在动机上合法，是因为 Gram Matrix $XX^t$本来就具有一个内积的形式，而我们做的所有替换，不过是把定义在 feature space 上的内积换成了嵌入 hilbert space 之后的内积（kernel）而已。但是具体为什么合法，细节上的缘由，我并不十分清楚。 Multidimensional Scaling。 9.17 今天的内容基本上都放在讲义部分了。 等距同构嵌入。除了讲义上内容以外，补充了一条引理，表明一组m个p维欧氏空间中的数据点（距离按2-norm定义）可以被等距同构地嵌入到m-1维欧氏空间。显然，这个进步太小了，人们需要别的办法。 cMDS（approximation）。 metric MDS：开了个头。 9.19 Metric MDS的一个具体的例子。一般做mMDS的时候，令变换$T(\delta_{ij})=a+b\delta_{ij}(i\neq j)$。这个的作用是考虑到由于 $\min_a\min_X||B(a)-XX^t||^2=\min_a(\sum_{i=1}^n\bar{\lambda_i}^2(a)+\sum_{i=n+1}^m)\lambda_i^2$ 如果我们把B弄成正定的，那么所有的$\bar{\lambda_i}^2$都是0，所以我们把a调到$a\gg b$，这样可以保证B正定。 Spectral Clustering。 Spectral Embedding。主要内容记在讲义部分了。最后落到最小化作用量$E=2\tau^tL\tau$上，$\tau$就是从feature space到欧氏空间的映射，它的分量由L的谱决定（这大概就是spectral的来历），所以说如果L的谱在某处有一个跃变（实际上很常见），我们就可以把显著更小的那一部分本征值摘出来，其数目（减一，考虑到trivial的本征值0应该除去）作为被嵌入的欧氏空间的维度是很自然的。...

争取两周一更。

就是一个简单的note，有比没有好

19世纪20年代，鞋匠老约翰-布尔在生意上遇到了一些困难，他节省花销的重要手段之一，就是暂停了家里大儿子的学业。

一时兴起，跑去成都待两天。

把 Sheldon Axler 的 Linear Algebra Done Right 复习了一遍。

2019-7-28 先更到前八章

…

前面一段时间，我好久没有更新这网站了。这主要是因为遇到了一些现实的问题，致使心理状态不很好的缘故。这一周来，大概算是突然闲下来了一些，可以暂时逃避许多事情，躺在屋里傻乐。然后今天就又要忙起来，现在的阳光还是很不舒适的，我不由得又怕了。