ML笔记（1）

争取两周一更。

week 1, 2

lecture

• 8.29

  • spanning set和记号$\text{span}_\mathbb{R}\{x_i\}_n$。basis也可以此定义。
  • feature map。有一个“特征”的集合$\mathcal{X}=\{x_i\}_n$，它可以是quantitative也可以是categorical的。建立$\phi:\mathcal{X}\rightarrow\mathcal{H}$把它embed到HS上。这就是feature map。HS中具有由内积确定的几何结构，所以可以用$\langle\phi(x_i),\phi(x_j)\rangle$来度量$\mathcal{X}$中元素的相似度$s_{ij}=k(x_i, x_j)$。k就是kernel，$k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$。这个过程差不多可以理解为“线性化”空间。
  • 有一类HS叫RKHS（reproducing kernel hilbert space），具有一些我还不认识的好性质，例子：$L^2([0, L])$不是RKHS。在RKHS里，evaluation operator也在他里面。相反，$\delta(x)\notin L^2$。
  • function space $\mathbb{R}^X$。有$f:\mathbb{R}^X\rightarrow\mathbb{R}^n$确定isomorphism。
  • 内积->范数->度规。有内积一定有范数，反之不亦然。有范数一定有度规，反之不亦然。
  • linear map $V\rightarrow W$。如果像集是$\mathbb{R}$，那么这映射就是线性泛函。可以用内积表示为$\langle v,\cdot\rangle_V$。
  • V的基底是{e}，W的基底是{$\tilde{e}$}。 采取记号$L(e_i)=\tilde{e_j}L_{ji}$，把映射L写成$v_iL_{ji}\tilde{e_j}$。这个就可以写成矩阵表示了。
  • cokernel。coker(L)=$W/Im(L)\simeq Im(L)^\perp$。
  • 在W里有coker(L),Im(L)。在V里有ker(L),Im($L^T$)。人们可以感觉到，Im(L)对应（同胚？）于Im($L^T$)，ker(L)对应于coker($L^T$)。
  • L的秩就是dim(im(L))。容易知道$dim(W)=rank(L)+dim(coker(L)),dim(V)=rank(L^T)+dim(ker(L))$。这个叫dimension theorem。
  • algebraic dual。就是V上的线性泛函的空间$V^*$。还有一个topological dual，要求线性泛函得连续。（在有限维的情况下，必然连续，二者没区别）
  • Riesz表示。线性泛函可以用和V中一个元素的内积来表示。具体地，先用$e_i^*(e_j)=\delta_{ij}$定义出来dual空间的基底，那么$e_j^*=\langle e_j,\cdot\rangle$。（要求V的基底是正交归一的，但这很容易做到）

• 9.3

  • 又重新讲了一下我们这个切入点的图景：*我们想要把feature set X里面的similarity很好的在hilbert space里面表示出来，所以我们建立feature map，并且树立其核心为kernel函数$\mathcal{K}(x_i, x_j)=\langle\phi(x_i), \phi(x_j)\rangle_{\mathcal{H}}$。分别考虑在$x_i,x_j$的evaluation下的写法：$\mathcal{K}(x_i, x_j)=\delta_{x_i}(\mathcal{K}(\cdot, x_j))=\delta_{x_j}(\mathcal{K}(x_i, \cdot))$。$\mathcal{K}(\cdot, x_j)$是一个hilbert空间的向量，而从Riesz表示定理，因为某一点的evaluation是一个泛函，所以可以写出$\mathcal{K}(x_i, x_j)=\langle\mathcal{K}(\cdot, x_j), \mathbb{I}_{x_i}\rangle=\langle\mathcal{K}(x_i, \cdot),\mathbb{I}_{x_j}\rangle$。 如果说K是一个reproducing kernel，我们就由RK的性质知道$\mathcal{K}(\cdot, x)=\mathbb{I}_x=\phi(x)$。*因为riesz表示针对的是连续的泛函，所以RKHS要求evaluation（delta function, in some sense）有界。
  • 以上的那个$\mathbb{I}$叫representer，实际上，在riesz表示里面和原向量做内积得到原向量在某泛函下的像的那个向量就叫representer。我差不多很久以前就知道delta function是一个functional，但是直到今天才理解。
  • 本征值，本征向量，Gershgorin圆定理，许多讲义上的内容。。。
  • 为什么要搞gershgorin，power method之类的。因为高阶矩阵的特征多项式超过5次没法因式分解。
  • 为什么定义graph laplacian为D-W。考虑一维的laplacian即$\lim_{\epsilon\to0}\frac{f(x+\epsilon)-2f(x)+f(x-\epsilon)}{\epsilon^2}$ ，它可以说是对应W-D。为了保证positive semidefiniteness， 我们加一个负号。
  • 为什么要搞矩阵的内积和范数。因为我们先验地相信，我们拿到的乱糟糟的矩阵实际上可能rank要低得多，只是因为有noise才乱。所以一般就是规定一个低rank然后找到该rank下和这矩阵差距最小的矩阵。这就要求我们有一个范数来衡量差距。
  • 讲义内容，此处省略（到估计方阵的dominant eigenvalue为止）

• 9.5

  • 奇异值分解（SVD）的图像。

    • 首先，考虑原空间在||$\cdot$||~2~-范数下的一个球面儿。一个方阵M会把它变化到像空间，把这个方阵对角化，就可以知道那些本征值的存在把球儿映射成了一个椭球面儿。

    • 现在，如果M不是个方阵。这个球面儿就得首先被拍扁到Im(M^t^)上，然后再被映射成一个低维椭球儿（包括它的内部）。

    • 我们说M,M^t^,MM^t^,M^t^M为 gram 矩阵。后两个肯定是方阵。现在，如果后者有一系列本征值$\lambda_i$和归一化的本征向量$v_i$，那么$Mv_i$就是前者的本征向量，并且有本征值$\lambda_i$。可以知道该本征向量的长度是$\sqrt{\lambda_i}$。就是这些东西决定了低维椭球儿的形状，它们叫奇异值，记做$\sigma_i$。我们把$Mv_i$归一化，记做$w_i$。那么，我们有奇异值分解

      $M=\sum\sigma_iw_iv_i^t$

  • Penrose-Moore 伪逆。又伪又逆，必须打倒！但思路是非常具有普遍性的：既然找不到x令Mx=y，我们就最小化$||Mx-y||_2$。我们把y投影到Im(M)上，然后求这个东西的逆。这样，P-M伪逆就有$M^\dagger=\sum v_i\sigma_i^{-1}w_i$。

  • PCA的思路。我们有一组数据$x_i=(x_i^{(j)})_m^T$，表示我们在时刻 i 测量了第 j 个物理量。现在假设我们有n组数据和m个物理量。为了知道物理量两两之间是否具有相关性，我们写出协方差矩阵

    $\Sigma=X^TX \\ \text{in which }X=\left(\begin{array}{ccc}{x_1^{(1)}-\bar{x^{(1)}}} & {\cdots} & {x_1^{(m)}-\bar{x^{(m)}}} \\ {\vdots} & {} & {} \\ {x_n^{(1)}-\bar{x^{(1)}}} & {\cdots} & {x_n^{(m)}-\bar{x^{(m)}}}\end{array}\right)$

    现在，对于阵X，我们可以找出它最大的几个奇异值（比如说，3个），保证它们显著比别人大。原则上，这时候对应的SVD的 $v_i$ 就叫做Principle component，因为它相当于像空间中椭球儿的长轴们。

    现在，对于阵X，我们可以找出它最大的几个奇异值（比如说，3个），保证它们显著比别人大。原则上，这时候对应的SVD的 $v_i$ 就叫做Principle component，因为它相当于像空间中椭球儿的长轴们。

  • 一个算法，找最大的奇异值。我们使用frobenius norm（见下material），希望$||M-\sigma wv^t||_F$能够最小化。我们先随机生成一个$v_0$，令长度为1。最小化 frobenius norm，令变量为$z=\sigma w$，知道$z=Mv$。这样，我们就可以照着$z=Mv_0,w_1=normalize(Mv_0),v_1=normalize(M^tw_1),\sigma_1=w_1^tMv_1$这样迭代来得到。基本思想和求方阵最大本征值的思想是差不多的。

reading material

三个阅读材料：RKHS；完备性；量子力学和hilbert space。外加一个讲义第一章。

• 讲义第一章差不多就是对lecture内容的扩充和系统化。此外，这一章的目的是带着人们复习（对我来说，怎么感觉像预习）线性代数的基本内容。

  • 关于什么是hamel基：首先，vector space basis 就是用span和线性无关定义的那一套basis。注意，向量空间的加法只提供有限个向量相加的结果，所以在无穷维下，可以有无穷个元素组成basis，但每个向量只能由有限个basis的元素表出。无穷维下的这种基就叫hamel基。注意，傅里叶基不是hamel基，因为表示随便一个函数经常需要动用无穷多个basis的元素。傅里叶基算是orthonormal基。zorn引理确保hamel基永远存在，不过，hamel基在不可数维空间下没法写出来，比如，无穷维hilbert空间。

  • 线性映射。线性映射保向量空间的代数结构，这就是说，像的和等于和的像，并且标量因子可以提到映射外面。

  • $\left\{\begin{array}{c}{\text { Classical Mechanics }} \\ {\text { Phase space } T^{*} X} \\ {\text { State }(x, p) \in T^{*} X} \\ {\text { Physical observables are functions on } T^{*} X} \\ {\text { Hamiltonian dynamics }}\end{array}\right\} \Rightarrow\left\{\begin{array}{c}{\text { Quantum Mechanics }} \\ {\text {Hilbert space } \mathcal{H} \subset\{f : X \rightarrow \mathbb{C}\}} \\ {\text { Wave function } \psi \in \mathcal{H}} \\ {\text { Self-adjoint Operators on } \mathcal{H}} \\ {\text { Schrödinger time evolution }}\end{array}\right\}$

  • 实际上，一般说矩阵的转置对应的映射不是$T^{t} : W \rightarrow V$，而是由内积$v^*:=\langle v, \cdot\rangle$对应的$V \simeq V^{*}$ and $W \simeq W^{*}$下的$T^{t} : W^{*} \rightarrow V^{*}$。

  • 行列式：

    $\operatorname{det}(M)=\sum_{i_{1}=1}^{n} \sum_{i_{2}=1}^{n} \cdots \sum_{i_{n}=1}^{n} \epsilon^{i_{1}, i_{2}, \ldots, i_{n}} M_{1 i_{1}} M_{2 i_{2}} \cdots M_{n i_{n}}$

  • $\operatorname{det}(T-\lambda I)=0$叫特征多项式。我已经忘了。。特征值的绝对值的最大值叫谱半径。

  • Gershgorin圆定理。矩阵有复的元素，那么在复平面上，矩阵的特征值位于以每个对角线元素为圆心，以每行非对角线元素之和的模为半径的一堆圆的并集里面。证明这个定理：把本征向量最大的元素归一化到1，那么$M u=\lambda u$的第i行给出$\sum_{j \neq i} m_{i j} u_{j}+m_{i i}=\lambda$。从这个差不多就能得到以上定理了。

  • n阶实对称阵的好性质：实本征值，完备、正交的本征向量。

  • 机器学习语境下，管$v^{t} M v \geq 0$叫半正定（按英文逻辑，为正半定），管$v^{t} M v \geq 0$且等号只能在v=0时取到叫正定。

  • 以下两两等价：$v^{t} M v \geq 0$；M没有负本征值；存在L使得$M=L L^{t}$；M的主余子式（principle minor，即对应对角元的余子式）没有负的。

  • diagonally dominant。就是说每一行元素，论绝对值，别的加起来也比不上对角元。一个这样的对称阵，如果其对角元都非负，从gershgorin圆定理知道，它肯定（半）正定。

  • graph laplacian。取$\delta_{i}=\sum_{j=1}^{n} w_{i j}$，$W=\left(w_{i j}\right)$，$D=diag(\delta)$，L=D-W。显然，这东西半正定。

  • projection。就是幂等矩阵。

  • 数值方法和矩阵的范数：

    • 估计一个矩阵绝对值最大的本征值（dominant eigenvalue）的power method。可以证明，$v_{k} \equiv M^{k} v$随着k越来越大，无限的趋于dominant eigenvalue对应的本征向量，前提是v不和这向量垂直。因此，dominant eigenvalue就是$\frac{v_{k}^{t} M v_{k}}{v_{k}^{t} v_{k}}$。

    • 奇异值分解。对于不是方阵的实算子M，我们可以构造对称的方阵$MM^T,M^TM$。这些方阵有很好的性质，比如半正定性，比如它们之间本征值的一致性

      $\left\{\begin{array}{c}{\text { orthogonal eigenvectors }} \\ {v_{1}, \ldots, v_{k}} \\ {\text { of } M^{t} M \text { with positive eigenvalues }} \\ {\lambda_{1}, \ldots, \lambda_{k}}\end{array}\right\} \Rightarrow\left\{\begin{array}{c}{\text { orthogonal eigenvectors }} \\ {M v_{1}, \ldots, M v_{k}} \\ {\text { of } M M^{t} \text { with positive eigenvalues }} \\ {\lambda_{1}, \ldots, \lambda_{k}}\end{array}\right\}$

      （如上，反之亦然）

      我们可以如下定义奇异值：把$\lambda_k$从大到小排列，$\sigma_k=\sqrt{\lambda_k}$。如果v是$M^{t} M$的单位本征向量，本征值是$\sigma^2$，那么$w=M v / \sigma$是$M M^{t}$的单位本征向量，它的本征值也是$\sigma^2$。证明时注意内积的性质$(Mv, Mv)=(v, M^tMv)$。我们得到奇异值分解

      $M=\left(w_{1} w_{2} \cdots w_{k}\right)\left(\begin{array}{cccc}{\sigma_{1}} & {0} & {\cdots} & {0} \\ {0} & {\sigma_{2}} & {\cdots} & {0} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {0} & {0} & {\cdots} & {\sigma_{k}}\end{array}\right)\left(\begin{array}{c}{v_{1}^{t}} \\ {v_{2}^{t}} \\ {\vdots} \\ {v_{k}^{t}}\end{array}\right)$

      w叫左奇异向量，v叫右奇异向量。

    • 矩阵对应的$\mathbb{R}^{m n}$上的一些操作。

      • $\langle M, N\rangle_{F}=\operatorname{tr}\left(M^{t} N\right)$为Frobenius内积。这个内积诱导的范数是frobenius norm。它很好理解，因为$\|M\|_{F}^{2}=\operatorname{tr}\left(M^{t} M\right)=\sum_{i=1}^{n} \lambda_{i}=\sum_{i=1}^{k} \sigma_{i}^{2}$。
      • 现在假如我们要找离M最近的rank 1矩阵。这就是找$\left\|M-\sigma u v^{t}\right\|_{F}$的最小值，也就是找最大的奇异值。这个时候找$M^kv$和$M^{tk}w$就能用power method解决问题。

    • 关于矩阵对应的算子的范数。考虑$l_p$范数：

      $\|M\|_{p}=\sup _{v \in V \backslash\{0\}} \frac{\|M v\|_{p}}{\|v\|_{p}}=\sup _{v \in V,\|v\|_{p}=1}\|M v\|_{p}$

      在这种情况下，可以推导出（此处只有结论，但是比较好推）：

      • $l_1$-norm：$\|M\|_{1}=\max _{j}\left\{\left\|m_{*, j}\right\|_{1}\right\}$
      • $l_2$-norm(即spectral norm)：$\|M\|_{2}=\sigma_{1}$
      • $l_\infty$-norm：$\|M\|_{\infty}=\max _{i}\left\{\left\|m_{i, *}\right\|_{1}\right\}$

      对于spectral radius即最大的本征值绝对值，有$\rho(M) \leq\left\|M^{k}\right\|^{\frac{1}{k}}$。这里还有 Gelfand 谱半径定理：$\lim _{k \rightarrow \infty}\left\|M^{k}\right\|^{\frac{1}{k}}=\rho(M)$。

      关于范数的等价性（equivalence）。$\exists c, C>0, s.t.\text{ }c\|v\|_{\alpha} \leq\|v\|_{\beta} \leq C\|v\|_{\alpha}, \forall v \in V$，这就代表等价性。有一个很强的定理，说有限维向量空间上的norm统统等价。这就引出引理，**说有限维向量空间之间的线性映射$L:V\to W$都是有界、连续的。实际上，V有限维就已经够了。**所以在有限维空间上，我们基本上不用操心以上所有这些概念，但是在无穷维空间上，我们将会十分感激这些性质的出现。一旦来了一个有界、连续的线性映射，我们就拿他定义一个RK，进而在对应的RKHS上处理问题。从课上我们知道，RK对应着evaluation这个泛函在riesz表示下的representer。

• 第一个材料 what is RKHS

  • convergent sequence，cauchy sequence。

  • 完备性。要求所有的cauchy seq在空间内部收敛。比如$\mathbb{Q}$里面搞一个趋向$\sqrt{2}$的 cauchy seq 就是个反例。

  • banach space：完备赋范向量空间

  • HS：有内积的BS。

  • 连续性。在normed 线性空间里，一个线性算子在一点连续等价于其在全空间连续，等价于其有界。

  • evaluation functional。取$f:\mathcal{X}\rightarrow\mathbb{R}$构成的HS，$\delta_x:f\rightarrow f(x)$就是（dirac）evaluation functional。

  • RKHS。就是evaluation functional连续的HS。如果$\lim _{n \rightarrow \infty}\left\|f_{n}-f\right\|_{\mathcal{H}}=0$，那么$\lim _{n \rightarrow \infty} f_{n}(x)=f(x), \forall x \in \mathcal{X}$。这是一个非常好的性质。现在想象一个反例：

    $\left\|f_{1}-f_{2}\right\|_{L_{2}([0,1])}=\left(\int_{0}^{1}\left|f_{1}(x)-f_{2}(x)\right|^{2} d x\right)^{1 / 2}$

    再考虑函数序列$\left\{x^n\right\}_{n=1}^{\infty}$。这个序列的norm收敛到0，可是在x=1这一点它还是1。

    RK是一个核，它满足性质$\forall x \in \mathcal{X}, \forall f \in \mathcal{H}, \quad\langle f, k(\cdot, x)\rangle_{\mathcal{H}}=f(x)$。还是那句话，RK对应着evaluation这个泛函在riesz表示下的representer。可以证明，RK的存在等价于这个HS是一个RKHS。

  • 正定函数与RKHS的对应。Moore-Aronszajn定理是说，每一个正定型$k : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$都对应唯一的RKHS$\mathcal{H} \subset \mathbb{R}^{\mathcal{X}}$，其RK就是k。我们这样证明这件事：首先，我们构造一个pre-RKHS $\mathcal{H}_{0}=\operatorname{span}\left[\{k(\cdot, x)\}_{x \in \mathcal{X}}\right]$，在它上赋予内积$\langle f, g\rangle_{\mathcal{H}_{0}}=\sum_{i=1}^{n} \sum_{j=1}^{m} \alpha_{i} \beta_{j} k\left(x_{i}, y_{j}\right)$，其中$f=\sum_{i=1}^{n} \alpha_{i} k\left(\cdot, x_{i}\right)$ 且 $g=\sum_{j=1}^{m} \beta_{j} k\left(\cdot, y_{j}\right)$，并证明该pre-RKHS具有两条性质：

    • evaluation有界
    • 任意逐点收敛到0的cauchy seq，其$\mathcal{H}_0$-norm也收敛到0

    随后，我们按照第二个材料的方法用cauchy seq把pre-RKHS完备化。我们用此前的内积定义$\mathcal{H}$上的内积，然后证明$\mathcal{H}$上evaluation也是连续的，再证明H是完备的。证明过程略（主要是我懒，况且我不喜欢证明）。

  • 这样，我们知道：正定->RK->肯定是个kernel->正定。三者等价！

  • 关于核的运算。核相加是核。核乘以非负数是核（核相减不是核）。核的hadamard积是核（这样一来，指数也是核，我们可以构造 gaussian kernel $\exp \left(-\sigma\left\|x-x^{\prime}\right\|^{2}\right)$）。

  • Mercer表示。（见下一个note）

• 第二个材料关于度量空间的完备化。

  • 完备性。completeness，指空间里所有的cauchy seq收敛到这个空间内。

  • 完备化。就是completion，把一个度量空间等距同构到另一个上面，而后者是完备的。

  • 具体操作：对于度量空间$(X, d)$，取其完备化

    $Y=\left\{\text { Cauchy sequences }\left\{x_{n}\right\} \subset X\right\} / \sim$

    其中$\left\{x_{n}\right\} \sim\left\{y_{n}\right\}$ ，如果 $d\left(x_{n}, y_{n}\right) \rightarrow 0$。Y上的度规定义为$D\left(\left\{x_{n}\right\},\left\{y_{n}\right\}\right)=\lim _{n \rightarrow \infty} d\left(x_{n}, y_{n}\right)$。那么$(Y, D)$是完备化的度量空间。

  • 粗略地说，可以认为这个完备化是唯一的。

• 第三个材料关于HS在QM里面的作用。感觉这个和课程的主要内容没有太大关系，但是了解一下总是好的。而且，看起来老师希望我们多了解一点泛函的知识，看这个材料也有帮助。我把这个材料的阅读放在下一个note里面。