Posts

week 11,12 小平学得很辛苦， 不懂的证明反复再三地看， 还抄在笔记上背下来。这么一来好像懂了。 ——《游里工夫独造微，小平邦彦传》 这句话其实适合上一章的内容：对于我贫乏的脑子来说很抽象的东西，抄几遍好像就懂了。虽然说这一章比较简单，但是抄书还是有帮助的。况且，从前学的时候，概率相关的很多东西当成数学课来学，对于我现在的脑子来说，motivation也不知道，对知识结构的划分和重要性的判断都很差，近乎于没有。讲义是物理学家的角度写下来的，我个人觉得写得不错，抄一遍可以厘清这些东西。 另外，kunihiko貌似是氼畚儿国一个很常见的男性用名。Kunihiko Kaneko 和 Kunihiko Kodaira，光我听说过的学者就有两个。 Monte Carlo Sampling 动机 从概率分布里面抽取iid（独立同分布）的sample，主要是有以下几个应用场合： 积分的数值结果 算Bayesian posterior 数值优化 计算物理的一些别的场景。 特别的，考虑到电脑里头伪随机数的生成特点，很重要的是怎样把任意的分布的sampling转化为均匀分布的sampling。 概率复习 从相空间体积元不变的想法，可以写出 $p_{Y}\left(y_{1}, \ldots, y_{n}\right)d\mathbf{y}=p_{X}\left(x_{1}(\mathbf{y}), \ldots, x_{n}(\mathbf{y})\right)d\mathbf{x}$ 因此 $p_{Y}\left(y_{1}, \ldots, y_{n}\right)=p_{X}\left(x_{1}(\mathbf{y}), \ldots, x_{n}(\mathbf{y})\right)\left|J\left(y_{1}, \ldots, y_{n} ; x_{1}, \ldots, x_{n}\right)\right|^{-1}$ 其中 $J\left(y_{1}, \ldots, y_{n} ; x_{1}, \ldots, x_{n}\right)=\left|\begin{array}{cccc}{\frac{\partial y_{1}}{\partial x_{1}}} & {\frac{\partial y_{1}}{\partial x_{2}}} & {\cdots} & {\frac{\partial y_{1}}{\partial x_{n}}} \\ {\frac{\partial y_{2}}{\partial x_{1}}} & {\frac{\partial y_{2}}{\partial x_{2}}} & {\cdots} & {\frac{\partial y_{2}}{\partial x_{n}}} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {\frac{\partial y_{n}}{\partial x_{1}}} & {\frac{\partial y_{n}}{\partial x_{2}}} & {\cdots} & {\frac{\partial y_{n}}{\partial x_{n}}}\end{array}\right|$...

week 9,10 气氛突然数学起来。 这次讲的基本上就是张量——张量积，张量的分解（CP-Decomposition， HOSVD）。之前我们处理矩阵，用的是SVD和eigenset的分解，动机是在低维上把握矩阵的行为，进而把握这些矩阵对应的高维数据集的性质。对于张量，很容易想到如法炮制。但是不幸的是，尽管矩阵的分解是一个相对容易的套路，张量的decomposition却是一个NP-hard的问题。 何为张量 有三种定义。 free vector space中的等价类。——QM里面，用的是这个定义。我们在这个讲义里用的也是这个定义。 basis变换时满足某种特定变换规则的对象。——GR里面我学到的就是这个。这也是我在课上唯一听懂的部分。 “linearizer of multilinear maps”——一个数学家可能会喜欢的说法。与本课的内容和我的兴趣都无关。 对于我不幸的大脑来说，这些定义都太数学了。况且，我不像许多其他同学一样学过许多高明的量子场论。因此，在了解这些定义的具体内容之前，不妨先产生一个模糊的概念：张量是线性映射之间的线性映射。 第一个定义的解释 取$n_{1}, \dots, n_{k}$维欧氏空间$V_{1}, \ldots, V_{k}$，令$\mathcal{F}$代表这些空间的cartesian积生成的所谓"free vector space"，这就是说，Cartesian积得到的$\sum n_i$维空间中的每一个元素都是该空间的一个basis（现在，忘掉直和空间中的线性性）。一开始，我还以为$V_{1} \times V_{2} \times \ldots \times V_{k}$就是$\mathcal{F}$呢。实际上，Cartesian Product弄出来的这东西叫直和，维数是$\sum n_i$；直积得到的空间，维数是$\prod n_i$。 令$\mathcal{M}$是由形如 $\left(x_{1}, \ldots, x_{i-1}, x_{i}+y_{i}, x_{i+1}, \ldots, x_{k}\right)-\left(x_{1}, \ldots, x_{i-1}, x_{i}, x_{i+1}, \ldots, x_{k}\right)-\left(x_{1}, \ldots, x_{i-1}, y_{i}, x_{i+1}, \ldots, x_{k}\right)$ 和 $\alpha\left(x_{1}, \ldots, x_{i-1}, x_{i}, x_{i+1}, \ldots, x_{k}\right)-\left(x_{1}, \ldots, x_{i-1}, \alpha x_{i}, x_{i+1}, \ldots, x_{k}\right)$ 的元素构成的子空间。那么，直积$V_{1} \otimes \cdots \otimes V_{k}$就是商空间$\mathcal{F} / \mathcal{M}$。商空间的意思就是说，对于$\mathcal{F}$中的元素F, f，$F=f+m,m\in\mathcal{M}$，那么这两个元素属于同一个等价类，这些等价类的集合就是商空间。一个简单的例子。取$V_1$，$V_2$。他们的基是$\{v_k\}$，$\{w_k\}$。$V_1\times V_2$的基底是$\{(v_i,0)+(0,w_j)\}$。$V_1\otimes V_2$的基底是$\{(v_i, w_j)\}$。...

关于PDE，我的问题是缺乏一种系统的把握。我所有的训练都是在数理方程的课上得到的，这些训练只告诉我某些十分特定的方程的解是某些特殊函数，至于这些方程的特定究竟特定到了什么程度，具体是怎样的条件，虽然也讲，但并不重视，主要重视的是造成这些方程的物理问题。所以就形成一个对物理问题的解的感觉。但是这个感觉现在也已经消退了。所以要重新从这些基础的东西学起。

…

week 7, 8 lecture 10.8 不小心翘掉了一节课。所幸，此课时基本上没有说什么特别重要而我又不太知道，并且没有在今天的summary中覆盖到的部分。 现在开始搞RKHS了。关于这个东西的定义和一些理论，都写在notes 0里面了，包括Moore-Aronszajn定理，Cauchy Sequence，Completion of Hilbert space 等等。基本上，上节课讲的东西的主要内容，就是在有限维空间的情况下证明Moore-Aronszajn定理。为了叙事的连贯性，我还是在这个文件里把必要的地方都说明一下吧。 RK是如此的一个kernel，即满足 $$ \bullet \forall x \in \mathcal{X}, \quad k(\cdot, x) \in \mathcal{H} \\ \bullet \forall x \in \mathcal{X}, \forall f \in \mathcal{H}, \quad\langle f, k(\cdot, x)\rangle_{\mathcal{H}}=f(x) $$ 者。它有一个重要的等价性质，是说evaluation functional在对应的这个RKHS里面连续。这个性质同时也正是RKHS的定义。 可以首先在有限维的情况下考虑RKHS的性质。比如说取一个建立了内积的$V\subset\mathbb{R}^m$。那么这时候一个核实际上可以被写成是（作用在基的函数）上的双线性函数$K\in\mathbb{R}^{m\times m}$。上节课给出如下结论，以下诸命题等价： K是V上的RK。 存在V上一组正交归一基u使得$K=\sum u_iu_i^t$。 $\text{columnspan}(K)=V$并且$K_{ij}=\langle k_i,k_j\rangle$。 这看上去是可以接受的。我无意追寻具体的证明。接下来，可以用这结论证明简单版的MA定理。 内容全在讲义里。 reading material lecture notes: RKHS and kernel regression RKHS: 定义；性质。RKHS是一个很重要的概念，虽然它的实际用处在这个阶段还没有显现出来。 我们将会证明， 对于一个函数$\kappa: X \times X \rightarrow\mathbb{R}$，以下命题等价： 它是半正定的 它是X上一个RKHS的RK 它是一个kernel 我们先考察有限维空间上的RK，再推广到无穷维的情况。这时对evaluation的定义比较简单，令$E_{i}(v)=e_{i}^{t} v, \forall v \in \mathbb{R}^{X}$即可。考虑到RK的定义，我们这个时候不妨把k直接当做是一个半正定的矩阵。这个时候，可以把Riesz表示定理写成...

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