ML笔记（4）

发表于 更新于 分类于 ， Waline： 本文字数： 13k 阅读时长 ≈ 12 分钟

week 7, 8

lecture

  • 10.8

    不小心翘掉了一节课。所幸，此课时基本上没有说什么特别重要而我又不太知道，并且没有在今天的summary中覆盖到的部分。

    现在开始搞RKHS了。关于这个东西的定义和一些理论，都写在notes 0里面了，包括Moore-Aronszajn定理，Cauchy Sequence，Completion of Hilbert space 等等。基本上，上节课讲的东西的主要内容，就是在有限维空间的情况下证明Moore-Aronszajn定理。为了叙事的连贯性，我还是在这个文件里把必要的地方都说明一下吧。

    • RK是如此的一个kernel，即满足

      ∙∀x∈X,k(⋅,x)∈H∙∀x∈X,∀f∈H,⟨f,k(⋅,x)⟩H=f(x)\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⊂RmV\subset\mathbb{R}^m。那么这时候一个核实际上可以被写成是（作用在基的函数）上的双线性函数K∈Rm×mK\in\mathbb{R}^{m\times m}。上节课给出如下结论，以下诸命题等价：

      • K是V上的RK。
      • 存在V上一组正交归一基u使得K=∑uiuitK=\sum u_iu_i^t。
      • columnspan(K)=V\text{columnspan}(K)=V并且Kij=⟨ki,kj⟩K_{ij}=\langle k_i,k_j\rangle。

      这看上去是可以接受的。我无意追寻具体的证明。接下来，可以用这结论证明简单版的MA定理。

    内容全在讲义里。

reading material

  • lecture notes: RKHS and kernel regression

    • RKHS: 定义；性质。RKHS是一个很重要的概念，虽然它的实际用处在这个阶段还没有显现出来。

    • 我们将会证明，

      对于一个函数κ:X×X→R\kappa: X \times X \rightarrow\mathbb{R}，以下命题等价：

      • 它是半正定的
      • 它是X上一个RKHS的RK
      • 它是一个kernel

      我们先考察有限维空间上的RK，再推广到无穷维的情况。这时对evaluation的定义比较简单，令Ei(v)=eitv,∀v∈RXE_{i}(v)=e_{i}^{t} v, \forall v \in \mathbb{R}^{X}即可。考虑到RK的定义，我们这个时候不妨把k直接当做是一个半正定的矩阵。这个时候，可以把Riesz表示定理写成

      线性泛函ϕ∈V∗\phi \in V^{*}可以被表示成⟨⋅,v⟩\langle\cdot, v\rangle，其中v=∑i=1nϕ(ei)eiv=\sum_{i=1}^{n} \phi\left(e_{i}\right) e_{i}。

      然而，在无穷维的情况下，这结论只对连续的线性泛函成立。以后我们将看到，对无穷维HS，加上这种限制的对偶空间叫topological dual，而由所有线性泛函组成的叫algebraic dual。

      在特定的operator norm下，V和V*构成isometric isomorphism：

      ∥ψ(v)∥V,1=sup⁡∥w∥V=1∣ψ(v)(w)∣=sup⁡∥w∥V=1∣⟨w,v⟩∣≤sup⁡∥w∥V=1∥w∥V∥v∥V=∥v∥V\|\psi(v)\|_{V, 1}=\sup _{\|w\|_{V}=1}|\psi(v)(w)|=\sup _{\|w\|_{V}=1}|\langle w, v\rangle| \leq \sup _{\|w\|_{V}=1}\|w\|_{V}\|v\|_{V}=\|v\|_{V}

    • 下面讨论（有限维情况下）RK的构造。

      我们可以证明，

      内积空间V。以下等价：

      • K是V上的RK
      • K=∑j=1nujujtK=\sum_{j=1}^{n} u_{j} u_{j}^{t}，其中U是一组幺正基
      • columnspan(K)=V\text{columnspan}(K)=V并且Kij=⟨κi,κj⟩K_{ij}=\langle \kappa_i,\kappa_j\rangle

      有了HS，我们就有了RK。反过来呢？

      有定理：

      对正定m维方阵K，存在唯一的带内积的V∈RmV \in \mathbb{R}^{m}使得K为其RK。

      张开K的columns，这空间里元素都可写成是v=Kαv=K \alpha的格式。现在定义内积⟨v,w⟩≡αtKβ\langle v, w\rangle \equiv \alpha^{t} K \beta。需要证明，这个内积不会因为v可以被表为不同的KαK\alpha和Kα′K\alpha'而变化——事实的确如此。这时候，很容易知道⟨ki,kj⟩=Kij\left\langle k_{i}, k_{j}\right\rangle= K_{i j}也是满足的，因此K确实是RK。唯一性是因为无论如何V都是K的columnspan，并且其中的内积也一样。

    • Intrinsic和Extrinsic坐标。

      V的元素v=(v1, …vm)（v∈V⊂RXv \in V \subset \mathbb{R}^{X}）可以表示成函数v作用在给定的数据集X={x1,⋯ ,xm}X=\{x_1, \cdots, x_m\}上的结果。不过，如果V只是欧氏空间的一个真子集，函数v的值域有可能超出V。因此，使用这一套extrinsic坐标参数化V并不好。

      但是，如果使用K，那么v=Kαv=K \alpha，所有的α∈Rm\alpha \in \mathbb{R}^{m}都会被映到V里面。

    • 无穷维的情况

      先讨论一些背景。量子力学里面，关键的假设是ψ(x)=∑k=1αkψk(x)\psi(x)=\sum_{k=1} \alpha_{k} \psi_{k}(x)收敛。用数学的话说，fn=∑k=1nαkψkf_{n}=\sum_{k=1}^{n} \alpha_{k} \psi_{k} 是一个cauchy sequence。回忆曾经在lecture notes中第一章看到的，如果所有柯西列都收敛到本空间内的点，那么这空间就算是完备的；完备赋范，谓之banach；完备内积，谓之hilbert。如果一个HS有可数的幺正基，那么就算是separable的。所有separable的HS都isometrically isomorphic to Rn,\mathbb{R}^{n}, for some n≥0,n \geq 0, or to ℓ2\ell^{2}。

      其中，ℓ2\ell^2指的是∑n=1∞fn2<∞\sum_{n=1}^{\infty} f_{n}^{2}<\infty的序列的集合，其内积定义为⟨{fn},{gn}⟩=∑n=1∞fngn\left\langle\left\{f_{n}\right\},\left\{g_{n}\right\}\right\rangle=\sum_{n=1}^{\infty} f_{n} g_{n}。

      这样一来，就把同为HS的 L2[a,b]L^2[a,b](是波函数生活的空间，对应薛定谔的波动力学)和ℓ2\ell^2（对应矩阵力学）对应起来。

      注意到，L2L^2并非RKHS，而ℓ2\ell^{2}却是，这并不违反什么，只是说明RKHS的RK性质在HS上加了一层结构，这个额外的结构可以用feature space X来表示。

      Moore-Aronszajn定理（无穷维）的证明与有限维的情况类似，从feature space里面取X，H0=span⁡{k(⋅,x)}x∈X\mathcal{H}_{0}=\operatorname{span}\{k(\cdot, x)\}_{x \in X}，那么把V中的元素类似地写成f=∑i=1nαiK(⋅,xi)f=\sum_{i=1}^{n} \alpha_{i} K\left(\cdot, x_{i}\right)，内积也类似地定义为

      ⟨f,g⟩=∑i=1n∑j=1mαiK(xi,xj)βj\langle f, g\rangle=\sum_{i=1}^{n} \sum_{j=1}^{m} \alpha_{i} K\left(x_{i}, x_{j}\right) \beta_{j}，

      那么就得到pre-Hilbert space。然后，作completion，得到我们想要的HS。

    • 关于kernel construction，基本上已经在notes 0里面写过了。Mercer Kernel还没有写，故在此补充一下。有定理

      T:H→HT: \mathcal{H} \rightarrow \mathcal{H}是separable HS上的紧的算子。那么，存在两组不一定完备的幺正基和一组正实数，满足

      T=∑n=1Nλnϕn⟨ψn,⋅,⟩T=\sum_{n=1}^{N} \lambda_{n} \phi_{n}\left\langle\psi_{n}, \cdot,\right\rangle

      这个式子的意义就是无穷维HS的奇异值分解，这组正实数也就叫奇异值。

      进一步的，如果T还是自伴的，那么ϕ\phi和ψ\psi就是同一组，而且还完备，对应的本征值有n→∞n\to\infty时λn→0\lambda_n\to0。

      Mercer的定理：

      X是n维欧氏空间的紧的子集。K:X×X→RK: X \times X \rightarrow \mathbb{R}是一对称，连续，半正定函数，那么有核

      K(x,y)=∑nλnϕn(x)ϕn(y)K(x, y)=\sum_{n} \lambda_{n} \phi_{n}(x) \phi_{n}(y)

      对应T(f)(x)=∫XK(x,y)f(y)dyT(f)(x)=\int_{X} K(x, y) f(y) d y，其中λ\lambda和ϕ\phi对应的是T的eigenset。

      关于应用和例子，写在lecture部分了，因为这块lecture稍微多讲了一点。

    • 线性回归：普通线性回归

      假如我们有随机变量(X1,…,Xn)∈Rn\left(X_{1}, \ldots, X_{n}\right) \in \mathbb{R}^{n}，我们想通过它们预测 response Y。现在，我们规定（由MLE可以推出来）损失函数是E[(Y−f(X1,…,Xn))2]E\left[\left(Y-f\left(X_{1}, \ldots, X_{n}\right)\right)^{2}\right]，其中predictor f是f(x1,…,xn)=E[Y∣X1=x1,…,Xn=xn]f\left(x_{1}, \ldots, x_{n}\right)=E\left[Y | X_{1}=x_{1}, \ldots, X_{n}=x_{n}\right]。

      在线性回归中，我们认为Y服从以βX\beta X为均值，σ2\sigma^2为方差（各向同性）的高斯分布。写出来就是

      Y=(y1y2⋮ym),X=(1x11x12⋯x1n1x21x22⋯x2n⋮⋮⋮⋮⋮1xm1xm2⋯xmn)\boldsymbol{Y}=\left(\begin{array}{c}{y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{m}}\end{array}\right), \boldsymbol{X}=\left(\begin{array}{ccccc}{1} & {x_{11}} & {x_{12}} & {\cdots} & {x_{1 n}} \\ {1} & {x_{21}} & {x_{22}} & {\cdots} & {x_{2 n}} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {1} & {x_{m 1}} & {x_{m 2}} & {\cdots} & {x_{m n}}\end{array}\right) \quad and β=(β0β1⋮βn)\boldsymbol{\beta}=\left(\begin{array}{c}{\beta_{0}} \\ {\beta_{1}} \\ {\vdots} \\ {\beta_{n}}\end{array}\right)

      Y=Xβ+e\boldsymbol{Y}=\boldsymbol{X} \boldsymbol{\beta}+\boldsymbol{e}

      Y∣X∼N(Xβ,σ2Im×m)e∼N(0,σ2Im×m)\begin{aligned} \boldsymbol{Y} | \boldsymbol{X} & \sim \mathcal{N}\left(\boldsymbol{X} \boldsymbol{\beta}, \sigma^{2} \boldsymbol{I}_{m \times m}\right) \\ \boldsymbol{e} & \sim \mathcal{N}\left(0, \sigma^{2} \boldsymbol{I}_{m \times m}\right) \end{aligned}

      用MLE，可以求出来最优的β^=(XTX)−1XTY\hat{\boldsymbol{\beta}}=\left(\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T} \boldsymbol{Y}。我们对此比较熟悉。如果XTX\boldsymbol{X}^{T} \boldsymbol{X}不可逆，那么用MP伪逆代替。

      E[β^]=(XTX)−1XTE[Y]=(XTX)−1XTXβ=βE[\hat{\boldsymbol{\beta}}]=\left(\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T} E[\boldsymbol{Y}]=\left(\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T} \boldsymbol{X} \boldsymbol{\beta}=\boldsymbol{\beta}

      所以是无偏估计。这过程里面，X看做是给定的，测出来的；Y是随机变量。

      类似的，

      var⁡(β^)=(XTX)−1XTvar⁡(Y)X(XTX)−1=(XTX)−1σ2\operatorname{var}(\hat{\boldsymbol{\beta}})=\left(\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T} \operatorname{var}(\boldsymbol{Y}) \boldsymbol{X}\left(\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1}=\left(\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \sigma^{2}

      在几何上，线性回归的结果的意义如下：

      Y^=X(XTX)−1XTY=HY\hat{\boldsymbol{Y}}=\boldsymbol{X}\left(\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T} \boldsymbol{Y}=\boldsymbol{H} \boldsymbol{Y}

      其中H满足对称和幂等的性质，是投影算符。H把Y投影到X的列张成的空间上。

      误差和prediction满足

      Y^∼N(Xβ,σ2H)\hat{\boldsymbol{Y}} \sim \mathcal{N}\left(\boldsymbol{X} \boldsymbol{\beta}, \sigma^{2} \boldsymbol{H}\right)
      e^∼N(0,σ2(I−H))\hat{\boldsymbol{e}} \sim \mathcal{N}\left(0, \sigma^{2}(\boldsymbol{I}-\boldsymbol{H})\right)

      并且cov⁡[e^,Y^]=(I−H)σ2H=0\operatorname{cov}[\hat{\boldsymbol{e}}, \hat{\boldsymbol{Y}}]=(\boldsymbol{I}-\boldsymbol{H}) \sigma^{2} \boldsymbol{H}=0。

    • 贝叶斯回归/岭回归

      见lecture，不写这个的话周二的lecture没得写了

    • Kernel regression

      β^=(XtX+αIn×n)−1XtY\hat{\boldsymbol{\beta}}=\left(\boldsymbol{X}^{t} \boldsymbol{X}+\alpha \boldsymbol{I}_{n \times n}\right)^{-1} \boldsymbol{X}^{t} \boldsymbol{Y}可以写成

      β^=Xt(XXt+αIm×m)−1Y\hat{\boldsymbol{\beta}}=\boldsymbol{X}^{t}\left(\boldsymbol{X} \boldsymbol{X}^{t}+\alpha \boldsymbol{I}_{m \times m}\right)^{-1} \boldsymbol{Y}，于是

      Y^=Xβ^=XXt(XXt+αIm×m)−1Y\hat{\boldsymbol{Y}}=\boldsymbol{X} \hat{\boldsymbol{\beta}}=\boldsymbol{X} \boldsymbol{X}^{t}\left(\boldsymbol{X} \boldsymbol{X}^{t}+\alpha \boldsymbol{I}_{m \times m}\right)^{-1} \boldsymbol{Y}

      对于一个点来说，就是

      y^=xXt(XXt+αIm×m)−1Y\hat{y}=x \boldsymbol{X}^{t}\left(\boldsymbol{X} \boldsymbol{X}^{t}+\alpha \boldsymbol{I}_{m \times m}\right)^{-1} \boldsymbol{Y}

      所谓kernel trick 就是用K代替复杂的gram矩阵XXtXX^t，这时有y^=κ(x,⋅)(K+αIm×m)−1Y\hat{y}=\kappa(x, \cdot)\left(\boldsymbol{K}+\alpha \boldsymbol{I}_{m \times m}\right)^{-1} \boldsymbol{Y}。

      一个比较常见的选择是κ(x1,x2)=exp⁡(−(x1−x2)2/2σ2)\kappa\left(x_{1}, x_{2}\right)=\exp \left(-\left(x_{1}-x_{2}\right)^{2} / 2 \sigma^{2}\right)。

  • lecture notes: Multilayer graphs and grassmannian manifolds

    • spectral embedding只能处理一张图的嵌入。如果有多张图怎么办？这讲义只讨论这一个问题，并给出行之有效的recipe。

    • Spectral Embedding 可以叙述为：最小化tr⁡(VtLV)\operatorname{tr}\left(V^{t} L V\right)，其中VtV=Ik×kV^{t} V=I_{k \times k}。V的行给出欧式空间中的嵌入。

      在此情形之下，一个想当然的推广是最小化

      tr⁡(∑i=1ℓVtLiV)=tr⁡(Vt(∑i=1ℓLi)V)\operatorname{tr}\left(\sum_{i=1}^{\ell} V^{t} L_{i} V\right)=\operatorname{tr}\left(V^{t}\left(\sum_{i=1}^{\ell} L_{i}\right) V\right)

      但是，如果LiL_i的scale区别很大，这个过程就会沦为对某一张图的嵌入。这是不行的。

    • Stiefel和Grassmannian流形。定义Stiefel Manifold V(k,n)V(k,n)是Rn\mathbb{R}^{n}上所有k-frame的集合，frame就是一组有序的幺正基。令W是一个给定的n×kn \times k矩阵，其列为幺正基，那么

      ∀W′∈V(k,n),∃U∈O(n),\forall W^{\prime} \in V(k, n), \exists U \in O(n), such that W′=UWW^{\prime}=U W。注意到，U的选取不是唯一的：任何在⊥W\perp W的部分旋转的U都不会改变什么东西。这部分空间共n−kn-k维。所以

      V(k,n)≅O(n)/O(n−k)V(k, n) \cong O(n) / O(n-k)

      其中，O(n)O(n)的维数是Cn2C_n^2。因为一个旋转对应一个平面。

      定义格拉斯曼流形Gr⁡(k,n)\operatorname{Gr}(k, n)为Rn\mathbb{R}^n上所有k维子空间的集合。在子空间内部的旋转当然也不会搞出一个新的子空间来，所以

      Gr(k,n)=V(k,n)/O(n)=O(n)/(O(n−k)×O(k))G r(k, n)=V(k, n) / O(n)=O(n) /(O(n-k) \times O(k))

      我觉得可以把这玩意当成是旋转的一种推广。

    • Principle Angles

      取A,B∈Gr(k,n)A, B \in G r(k, n)。递归定义主向量

      (pi,qi)=arg⁡max⁡ptq\left(p_{i}, q_{i}\right)=\arg \quad \quad \max \quad \quad p^{t} q
      p∈A,q∈Bp \in A, q \in B
      p⊥pj,q⊥qj,j=1,…,i−1p \perp p_{j}, q \perp q_{j}, j=1, \ldots, i-1
      ∥p∥2=1,∥q∥2=1\|p\|_{2}=1,\|q\|_{2}=1

      然后，principle angle 为θi=cos⁡−1(pitqi),i=1,…,k\theta_{i}=\cos ^{-1}\left(p_{i}^{t} q_{i}\right), i=1, \ldots, k。

      取A∈Gr⁡(k,n)A \in \operatorname{Gr}(k, n) and B∈Gr⁡(l,n)B \in \operatorname{Gr}(l, n)。那么，可以用矩阵把他们表示为A∈Rn×kA \in \mathbb{R}^{n \times k} and B∈Rn×lB \in \mathbb{R}^{n \times l}。写下

      AtB=UΣVtA^{t} B=U \Sigma V^{t}

      那么这个SVD分解出来的奇异值σ1≥σ2≥…σr≥0\sigma_{1} \geq \sigma_{2} \geq \ldots \sigma_{r} \geq 0（r=min⁡(k,l)r=\min (k, l)）就对应主角θi=cos⁡−1σi,i=1,…,r\theta_{i}=\cos ^{-1} \sigma_{i}, \quad i=1, \ldots, r。这件事情从原则上是可以理解的，所以我就不证明它了。

      定义 Chordal(Projection) 距离：

      dc(A,B)=∑i=1rsin⁡2θid_{c}(A, B)=\sqrt{\sum_{i=1}^{r} \sin ^{2} \theta_{i}}——

    • ——那么，就可以进行multilayer的spectral clustering。取lagrangian

      L=tr⁡(Vt(∑i=1ℓLi)V)+α∑i=1ℓdc2(V,Vi)\mathcal{L}=\operatorname{tr}\left(V^{t}\left(\sum_{i=1}^{\ell} L_{i}\right) V\right)+\alpha \sum_{i=1}^{\ell} d_{c}^{2}\left(V, V_{i}\right)

      可以证明，

      L=tr⁡(Vt(∑i=1ℓLi)V)+α∑i=1ℓ(k−tr⁡(VtViVitV))=tr⁡(Vt[∑i=1ℓ(Li−αViVit)]V)+αkℓ\begin{aligned} \mathcal{L} &=\operatorname{tr}\left(V^{t}\left(\sum_{i=1}^{\ell} L_{i}\right) V\right)+\alpha \sum_{i=1}^{\ell}\left(k-\operatorname{tr}\left(V^{t} V_{i} V_{i}^{t} V\right)\right) \\ &=\operatorname{tr}\left(V^{t}\left[\sum_{i=1}^{\ell}\left(L_{i}-\alpha V_{i} V_{i}^{t}\right)\right] V\right)+\alpha k \ell \end{aligned}

      这里面α\alpha是超参数，一般也是用cross-validation之类的办法确定的。实际上，这个recipe看上去还是挺随意，它的合法性基本上是它的效用决定的。

    • Courant-Fischer 定理说，M是n×nn \times n的对称阵。它有由小到大排列的本征值λ1,…,λn\lambda_{1}, \ldots, \lambda_{n}。那么，

      λk=min⁡V∈Gr⁡(k,n)(max⁡v∈V\{0}vtMvvtv)=max⁡V∈Gr⁡(n−k+1,n)(min⁡v∈V\{0}vtMvvtv)\lambda_{k}=\min _{V \in \operatorname{Gr}(k, n)}\left(\max _{v \in V \backslash\{0\}} \frac{v^{t} M v}{v^{t} v}\right)=\max _{V \in \operatorname{Gr}(n-k+1, n)}\left(\min _{v \in V \backslash\{0\}} \frac{v^{t} M v}{v^{t} v}\right)。

      从这里，可以知道，对于对称阵M，

      min⁡V∈Rn×k,VtV=Ik×ktr⁡(VtMV)=∑i=1kλi\min _{V \in \mathbb{R}^{n \times k}, V^{t} V=I_{k \times k}} \operatorname{tr}\left(V^{t} M V\right)=\sum_{i=1}^{k} \lambda_{i}。原因是：

      取vi=arg⁡max⁡v∈S,∥v∥2=1,v⊥vi+1,…,vkvtMvv_{i}=\arg \max _{v \in S,\|v\|_{2}=1, v \perp v_{i+1}, \ldots, v_{k}} v^{t} M v，

      由于求迹对旋转不变，tr⁡(VtMV)=∑i=1kvitMvi\operatorname{tr}\left(V^{t} M V\right)=\sum_{i=1}^{k} v_{i}^{t} M v_{i}。

      由Courant-Fischer, vitMvi≥λiv_{i}^{t} M v_{i} \geq \lambda_{i}。

    • Pareto优化：

      对于所有图，用某种方式算某个特定嵌入的loss。如果嵌入1在所有图的表现都不差于嵌入2，且至少在一个图表现更好，那么就说1比2好。现有生成的一大堆嵌入，若不存在比嵌入3更好的，就说3在pareto front上。由此构建pareto front。