线代复习+降维与度量学习

线代复习+降维与度量学习

PART1
在此之前，我们最好复习一下线性代数的知识：以下内容基于ckc 的线代2（H）课程，实际上这个课完全脱离了行列式体系，更适合计科以及更抽象的学科的要求，比如物理。
chap5：
主要是本征值方面的问题：
T v = λ v Tv=lambda v Tv=λv
这个v就是本征向量 λ 则 是 本 征 值 lambda 则是本征值 λ则是本征值
不同特征值对应的特征向量线性无关
存在上三角矩阵等价 T v j ∈ s p a n ( v 1 , . . . , v j ) Tv_jin span(v1,...,vj) Tvj​∈span(v1,...,vj)等价于 s p a n ( v 1 , . . . v j ) span(v1,...vj) span(v1,...vj) 在T下不变
对角化会用到这5个等价
1、 设 不 变 子 空 间 有 ： V 1 , V 2 , , , V n , d i m V 1 , d i m V 2 , , , d i m V n 设不变子空间有：V1,V2,,,Vn,dimV1,dimV2,,,dimVn 设不变子空间有：V1,V2,,,Vn,dimV1,dimV2,,,dimVn
则分别对应有
本 征 向 量 ： λ 1 − > d i m V 1 个 , λ 2 − > d i m V 2 个 , , , λ n − > d i m V n 个 本征向量：lambda1->dimV1个,lambda2->dimV2个,,,lambda n->dimVn个 本征向量：λ1−>dimV1个,λ2−>dimV2个,,,λn−>dimVn个
2、各个不变子空间的直和等于V
3、V在在T下的dimV个一维不变子空间
4、V可分解为各个本征空间的直和
更强一点的直接就是有dimV个互异本征值
再补充一下商空间，以前一直没有理解
v + U : { v + u : u ∈ U } v+U:{v+u:uin U} v+U:{v+u:u∈U}
举个例子， v = ( v 1 , v 2 , v 3 ) , U = { ( x , y , 0 ) : x , y ∈ R } v=(v1,v2,v3),U={(x,y,0):x,yin R} v=(v1,v2,v3),U={(x,y,0):x,y∈R}
这个时候呢就是过（v1,v2,v3)的平面，所有的v+u构成商空间，就是U的所有仿射子集的集合，在这里就是所以平行于U的平面
商空间维数：
d i m ( V / U ) = d i m V − d i m U dim(V/U)=dimV-dimU dim(V/U)=dimV−dimU
chap6现在才差不多进入主要部分
内积：正定性，第一位置可加和齐次，共轭对称
内积出现的动机是 R 2 R^2 R2中的范数
我们重新定义范数（不同于简单的欧式距离，实际上我们的内积也不只是欧式内积）
∣ ∣ v ∣ ∣ = < v , v > ||v||=sqrt{<v,v>} ∣∣v∣∣=<v,v> ​
之后我们引入了正交性和正交分解
正交分解关键是把v的成分提取出来： c = < u , v > ∣ ∣ v ∣ ∣ 2 c=frac{<u,v>}{||v||^2} c=∣∣v∣∣2<u,v>​
接下来是规范正交基：实际上我们看一下(1,0,0),(0,1,0),(0,0,1)的性质：范数1（规范），自己和自己内积为1，不同的内积为0（正交），这个性质很好，有种类似筛选的作用
性质不提了，没忘
来个容易忘的：格拉姆-施密特过程其实也还好，通过式子我们这样记：新的vj要扣除前面j-1个向量的成分

e j = v j − < v j , e 1 > e 1 − < v j , e 2 > e 2 − . . . − < v j , e j − 1 > e j − 1 ∣ ∣ v j − < v j , e 1 > e 1 − < v j , e 2 > e 2 − . . . − < v j , e j − 1 > e j − 1 ∣ ∣ e_j=frac{vj-<vj,e1>e1-<vj,e2&-<vj,e_j-1>e_j-1}{||vj-<vj,e1>e1-<vj,e2&-<vj,e_j-1>e_j-1||} ej​=∣∣vj−<vj,e1>e1−<vj,e2>e2−...−<vj,ej​−1>ej​−1∣∣vj−<vj,e1>e1−<vj,e2>e2−...−<vj,ej​−1>ej​−1​

schur定理：有限维复向量空间的算子T，T关于V的某个规范正交基有上三角矩阵
线性泛函：举个例子： φ ( z i , z 2 , z 3 ) = 2 z 1 − 3 z 2 + 5 z 3 varphi(zi,z2,z3)=2z1-3z2+5z3 φ(zi,z2,z3)=2z1−3z2+5z3其中
z = ( z 1 , z 2 , z 3 ) z=(z1,z2,z3) z=(z1,z2,z3)
引入正交补：V中与子集U中的向量都垂直的向量组成的集合 V = U ⨁ U ⊥ V=Ubigoplus U^perp V=U⨁U⊥
正交投影问题： v = u + w , w ∈ U ⊥ , u ∈ U v=u+w,win U^perp ,uin U v=u+w,w∈U⊥,u∈U那么我们经过正交投影算子投影到U上的只有u这一部分
其实我们可以用正交分解来估计这一部分的值
正交补和正交投影的性质可以自行推导，利用这些理论我们也可以证明一系列的最短问题的结论
chap7
伴随（复习一下） T ∈ L ( V , W ) , 伴 随 指 的 是 这 样 的 函 数 : T ∗ : W − > V : 对 所 有 的 v ∈ V , w ∈ W , 有 < T v , w > = < v , T ∗ w > Tin L(V,W),伴随指的是这样的函数: T^*:W->V:对所有的vin V,win W,有<Tv,w>=<v,T^*w> T∈L(V,W),伴随指的是这样的函数:T∗:W−>V:对所有的v∈V,w∈W,有<Tv,w>=<v,T∗w>
既然在线代里面出现，那这个当然有线性性了
实际上这个和曾经讲过的转置比较类似，有个值得注意的性质提一下：
S , T ∈ L ( V , W ) , ( S + T ) ∗ = S ∗ + T ∗ S,Tin L(V,W),(S+T)^*=S^*+T^* S,T∈L(V,W),(S+T)∗=S∗+T∗
关于伴随的range和null也很有意思
n u l l T ∗ = r a n g e ( T ⊥ ) null T^*=range(T^perp) nullT∗=range(T⊥)
核心证明思想是这个：
w = 0 = > T ∗ w = 0 = > < v , T ∗ ∗ w > = 0 = > < T v , w > = 0 w=0=>T^*w=0=><v,T**w>=0=><Tv,w>=0 w=0=>T∗w=0=><v,T∗∗w>=0=><Tv,w>=0
对 于 L ( V , W ) , V , W 的 规 范 正 交 基 e 1 , , , , e n , f 1 , , , , f n , 所 构 成 的 矩 阵 M ( T ) 有 ， M ( T ∗ ) 等 于 M ( T ) 的 共 轭 转 置 对于L(V,W),V,W的规范正交基e1,,,,en,f1,,,,fn,所构成的矩阵M(T)有，M(T^*)等于M(T)的共轭转置 对于L(V,W),V,W的规范正交基e1,,,,en,f1,,,,fn,所构成的矩阵M(T)有，M(T∗)等于M(T)的共轭转置
有趣的来了，自伴算子和正规算子
自伴性： < T v , w > = < v , T ∗ w > <Tv,w>=<v,T^*w> <Tv,w>=<v,T∗w>自伴算子本征值都是实的（其他结论貌似后面不太会用到，都涉及代数证明的技巧）
正规性要弱一些，实际上它描述的是可交换性: T T ∗ = T ∗ T TT^*=T^*T TT∗=T∗T
正规算子有个性质： ∣ ∣ T v ∣ ∣ = ∣ ∣ T ∗ v ∣ ∣ ||Tv||=||T^*v|| ∣∣Tv∣∣=∣∣T∗v∣∣证明过程基于： < ( T T ∗ − T ∗ T ) v , v > = 0 推 出 < T v , T v > = < T ∗ v , T ∗ v > <(TT^*-T^*T)v,v>=0推出<Tv,Tv>=<T^*v,T^*v> <(TT∗−T∗T)v,v>=0推出<Tv,Tv>=<T∗v,T∗v>
正规算子 T 和 T ∗ 有 相 同 的 对 应 的 相 共 轭 的 本 征 值 的 本 征 向 量 T和T^*有相同的对应的相共轭的本征值的本征向量 T和T∗有相同的对应的相共轭的本征值的本征向量
( T − λ I ) 正 规 (T-lambda I)正规 (T−λI)正规
于是有 0 = ∣ ∣ ( T − λ I ) v ∣ ∣ = ∣ ∣ ( T − λ I ) ∗ v ∣ ∣ = ∣ ∣ ( T ∗ − λ _ ) v ∣ ∣ 0=||(T-lambda I)v||=||(T-lambda I)^*v||=||(T^*-lambda^_)v|| 0=∣∣(T−λI)v∣∣=∣∣(T−λI)∗v∣∣=∣∣(T∗−λ_)v∣∣
还有个性质也很有用：
相对于不同本征值的本征向量是正交的
我们设：
T u = a u , T ∗ v = b v Tu=au,T^*v=bv Tu=au,T∗v=bv
( a − b ) < u , v > = < a u , v > − < u , b _ v > = < T u , v > − < u , T ∗ v > begin{array}{ll} &(a-b)<u,v>\&=<au,v>-<u,b^_v>\&=<Tu,v>-<u,T^*v> end{array} ​(a−b)<u,v>=<au,v>−<u,b_v>=<Tu,v>−<u,T∗v>​
对角矩阵的福利来了，谱定理：
先是复谱定理
等价三互推：
存在本征向量组成的规范正交基；T是正规的；T关于V的某个规范正交基具有对角矩阵
证明过程比上三角矩阵有关知识那里的数学归纳法简明多了
先利用schur表示定理证明存在上三角矩阵之后
利用 ∣ ∣ T e 1 ∣ ∣ 2 = ∣ a 1 , 1 ∣ ∗ 2 , ∣ ∣ T ∗ e 1 ∣ ∣ 2 = ∣ a 1 , 1 ∣ 2 + ∣ a 2 , 1 ∣ 2 + , , , + ∣ a 1 , n ∣ 2 ||Te1||^2=|a_{1,1}|*2,||T^*e1||^2=|a_{1,1}|^2+|a_{2,1}|^2+,,,+|a_{1,n}|^2 ∣∣Te1∣∣2=∣a1,1​∣∗2,∣∣T∗e1∣∣2=∣a1,1​∣2+∣a2,1​∣2+,,,+∣a1,n​∣2我们很自然的有除了 a 1 , 1 a_{1,1} a1,1​外都是0，同理可以证明对其他行也成立
自伴的情况下，不变子空间U的不变性可以传到其正交补上，本身的自伴性也可以传递到两者上去。
由此我们可以导出实谱定理：
三个等价：T自伴性；V有由本征向量组成的规范正交基；T关于V的某个规范正交基有对角矩阵
看看后面还有什么幺蛾子，好像还挺多，完了成线代2（H）复习贴了
正算子（为之后的xxx分解做铺垫，好像还有我们喜欢的QAQ‘分解？）
正算子： 自 伴 + < T v , v > ≥ 0 自伴+<Tv,v>geq 0 自伴+<Tv,v>≥0
R 2 = T , T 为 正 算 子 , 则 R 为 称 作 T 的 平 方 根 R^2=T,T为正算子,则R为称作T的平方根 R2=T,T为正算子,则R为称作T的平方根
莽一点的，5个等价：
T是正的；T自伴且本征值大于0；T有正的平方根；T有自伴的平方根；有R满足 T = R R ∗ T=RR^* T=RR∗
(这里基本上基于本征值+伴随的性质来证明）
实际上每个正算子都有唯一的正平方根，证明类似
等距同构->保持范数
这块最好的证明就是利用正交的性质，平方，正交分解之类的好用极了
等距同构的性质：
等7价（丧心病狂）
1、s等距同构
2、<Su,Sv>=<u,v>(用定义来推导）
3、对V中任意规范正交的向量组，经过等距同构后也是规范正交的
4、V有规范正交基在等距同构后也是规范正交的
5、 S S ∗ = S ∗ S = I SS^*=S^*S=I SS∗=S∗S=I
6、S*等距同构
7、 S − 1 = S ∗ S^{-1}=S^* S−1=S∗（个人感觉这点很重要，以前线代1的正交变换）
重要的来了
极分解：
思路来源：用向量方向上的单位向量乘上范数来表示本来的向量
于是单位向量对应到了等距同构S，我们有 T = S T ∗ T T=Ssqrt{T^*T} T=ST∗T ​
(证明较复杂）
SVD分解
首 先 奇 异 值 就 是 T ∗ T 的 本 征 值 首先奇异值就是sqrt{T^*T}的本征值 首先奇异值就是T∗T ​的本征值
并 且 每 个 本 征 值 λ 需 要 重 复 d i m ( λ , T ∗ T ) 次 并且每个本征值lambda需要重复dim(lambda,sqrt{T^*T})次 并且每个本征值λ需要重复dim(λ,T∗T ​)次实际上奇异值可以用 T ∗ T 的 本 征 值 的 平 方 根 T^*T的本征值的平方根 T∗T的本征值的平方根来描述
我们的奇异值分解如下;
T ∈ L ( V ) , 奇 异 值 s 1 , s 2 , , , , s n , V 有 两 个 规 范 正 交 基 e 1 , e 1 , , , , e n , f 1 , f 2 , , , , , f n , 满 足 T v = s 1 < v , e 1 > f 1 + s 2 < v , e 2 > f 2 + , , , , + s n < v , e n > f n Tin L(V),奇异值s1,s2,,,,sn,V有两个规范正交基e1,e1,,,,en,f1,f2,,,,,fn,满足Tv=s1<v,e1>f1+s2<v,e2>f2+,,,,+sn<v,en>fn T∈L(V),奇异值s1,s2,,,,sn,V有两个规范正交基e1,e1,,,,en,f1,f2,,,,,fn,满足Tv=s1<v,e1>f1+s2<v,e2>f2+,,,,+sn<v,en>fn
实际上这样的好处就是我们把两个不同标准正交基集中起来了，那么它们的属性能就可以被很好的利用起来，特别是处理数据、降维等方面。
PART2
一、k近邻学习
懒惰学习:lazy learning
核心：定义度量距离，根据度量距离找出最邻近的k个样本，利用样本的信息来预测。
给定测试样本x，近邻样本z，出错概率为：
p ( e r r ) = 1 − ∑ P ( c ∣ x ) P ( c ∣ z ) ≤ 1 − P 2 ( c ∗ ∣ x ) ≤ 2 ( 1 − P ( c ∗ ∣ x ) begin{array}{ll} &p(err)=1-sum P(c|x)P(c|z)\ &leq1-P^2(c^*|x)\&leq2(1-P(c^*|x) end{array} ​p(err)=1−∑P(c∣x)P(c∣z)≤1−P2(c∗∣x)≤2(1−P(c∗∣x)​

从而泛化错误率不到贝叶斯最优分类器错误率的两倍
二、低维嵌入
我们在高维的情况下数据量严重不足，所以我们希望用一个低维的空间嵌入进去后进行讨论。有点类似不变子空间的想法？也有点像商映射？
运用的是多维缩放（Multiple Dimensional Scaling)
我们的想法是把m个样本的距离矩阵D:m *m，降为内积矩阵B：d *m(d<m)
核心思想，类似于全部求和把特性糅合在一起的想法：
∑ i = 1 m ∑ j = 1 m d i s t i j = 2 m t r ( B ) d i s t i j 2 = ∣ ∣ z 1 ∣ ∣ 2 + ∣ ∣ z j ∣ ∣ 2 − 2 z i T z j = b i i + b j j − 2 b i j d i s t i . = 1 m ∑ j = 1 m d i s t i j 2 , 对 称 情 况 同 理 d i s t . . 2 = 1 m 2 ∑ i = 1 m ∑ j = 1 m d i s t i j 2 b i j = − 1 2 ( d i s t i j 2 − d i s t i . 2 − d i s t . j 2 + d i s t . . 2 ) begin{array}{ll} &sum^m_{i=1}sum^m_{j=1} dist_{ij}=2m tr(B)\ \&dist_{ij}^2=||z_1||^2+||z_j||^2-2z_i^Tz_j\&=b_{ii}+b_{jj}-2b_{ij}\&dist_{i.}=frac{1}{m}sum^m_{j=1} dist^2_{ij},对称情况同理\&dist^2_{..}=frac{1}{m^2}sum^m_{i=1} sum^m_{j=1} dist_{ij}^2\&b_{ij}=-frac{1}{2}(dist_{ij}^2-dist_{i.}^2-dist_{.j}^2+dist_{..}^2) end{array} ​∑i=1m​∑j=1m​distij​=2mtr(B)distij2​=∣∣z1​∣∣2+∣∣zj​∣∣2−2ziT​zj​=bii​+bjj​−2bij​disti.​=m1​∑j=1m​distij2​,对称情况同理dist..2​=m21​∑i=1m​∑j=1m​distij2​bij​=−21​(distij2​−disti.2​−dist.j2​+dist..2​)​
从而我们做特征分解
Z = V A V T A 为 特 征 值 构 成 的 对 角 矩 阵 , 对 于 其 中 的 非 0 特 征 值 构 成 A ∗ ， 有 Z = A ∗ 1 2 ⊂ R d × m begin{array}{ll} &Z=VAV^T\&A为特征值构成的对角矩阵,对于其中的非0特征值构成A^*，有\&Z=A^{*frac{1}{2}}subset R^{dtimes m} end{array} ​Z=VAVTA为特征值构成的对角矩阵,对于其中的非0特征值构成A∗，有Z=A∗21​⊂Rd×m​实际过程中我们使用最大的d个特征值即可
实际上可以通过线性变换来降维
三、主成分分析
Principal Component Analysis(PCA)
主要想法:样本点x到超平面尽可能近，投影尽可能分开，
step1:样本去中心化
∑ i x i = 0 sum_i x_i=0 i∑​xi​=0
step2：投影变化后的坐标系为W，舍弃部分坐标，得到新的坐标系Z，将维度降低。
step3：在新的坐标系下表示样本的坐标,重构样本点坐标

∑ i = 1 m ∣ ∣ ∑ j = 1 d ′ z i j w j − x i ∣ ∣ 2 2 = ∑ i = 1 m z i T z i − 2 ∑ i = 1 m z i T W T x i + c o n s t = k ( − t r ( W T ( ∑ i = 1 m x i x i T ) W ) ) begin{array}{ll} sum ^m_{i=1}||sum ^{d'}_{j=1}z_{ij}w_{j}-x_i||^2_2=sum ^m_{i=1}z_i^Tz_i-2sum^m_{i=1}z_i^TW^Tx_i+const\=k(-tr(W^T(sum^m_{i=1}x_ix_i^T)W)) end{array} ∑i=1m​∣∣∑j=1d′​zij​wj​−xi​∣∣22​=∑i=1m​ziT​zi​−2∑i=1m​ziT​WTxi​+const=k(−tr(WT(∑i=1m​xi​xiT​)W))​
step4:考虑到样本点离超平面应该最近，我们的优化目标应该为：
m i n ( − t r ( W T X X T X ) ) W T W = I begin{array}{ll} min (-tr(W^TXX^TX))\W^TW=I end{array} min(−tr(WTXXTX))WTW=I​
实际上我们还可以这样想：样本投影后方差为： ∑ i W T x i x i T W sum _i W^Tx_ix_i^TW i∑​WTxi​xiT​W样本点分得较开：方差较大，因此有：
m a x ( t r ( W T X X T X ) ) begin{array}{ll} max (tr(W^TXX^TX)) end{array} max(tr(WTXXTX))​
最后我们使用拉格朗日乘子法：
X X T W = k W XX^TW=kW XXTW=kW
step5:对协方差矩阵 X X T XX^T XXT进行特征值分解，取前d‘个特征值对应的特征向量构成主成分分析的解。
四、核化线性降维
线性降维的问题：我们不能保证降维时低维的结构不被破坏
实际上我们有：核化线性降维——核主成分分析的方法
有点奇怪，我们先把x映射到高维空间的z，在把z映射到超平面W上
( ∑ i = 1 m z i z i T ) W = λ W α i = 1 λ z i T W , z i = ϕ ( x i ) W = ∑ i = 1 m ϕ ( x i ) α i 再 引 入 核 函 数 , 因 为 我 们 往 往 不 知 道 这 个 映 射 函 数 ϕ , k ( x i , x j ) = ϕ ( x i ) T ϕ ( x i ) 化 解 后 得 到 : K A = λ A begin{array}{ll} &(sum ^m_{i=1} zizi^T)W=lambda W\&alpha i=frac{1}{lambda}z_i^TW,z_i=phi(x_i)\&W=sum_{i=1}^m phi(x_i)alpha_i\&再引入核函数,因为我们往往不知道这个映射函数\&phi,k(xi,xj)=phi(xi)^Tphi(xi)\&化解后得到:KA=lambda A end{array} ​(∑i=1m​ziziT)W=λWαi=λ1​ziT​W,zi​=ϕ(xi​)W=∑i=1m​ϕ(xi​)αi​再引入核函数,因为我们往往不知道这个映射函数ϕ,k(xi,xj)=ϕ(xi)Tϕ(xi)化解后得到:KA=λA​
K为核函数对应的核矩阵，A的列向量为 α i alpha_i αi​
对于新样本x，其投影后第j维坐标为：
z j = w j T ϕ ( x ) = ∑ i = 1 m α i j k ( x i , x j ) begin{array}{ll} &z_j\&=w_j^Tphi(x)\&=sum_{i=1}^malpha_i^j k(x_i,x_j) end{array} ​zj​=wjT​ϕ(x)=∑i=1m​αij​k(xi​,xj​)​
最后我只记得这个开销很大，反正我又不手动实现这个算法，知道个原理就行。
四、流形学习
流形：在局部与欧式空间同胚的空间，在局部具有欧式空间的性质，这样我们可以在低维流形嵌入到高维空间时，仍然只研究局部上的欧式空间的性质，然后在局部建立降维映射关系，最后将局部关系推广到全局
为什么高维中直接计算距离不合适：想象一个曲面，虫子不能穿过曲面爬行，只能沿着曲面爬行，那么很显然地我们最好不使用高维空间地直线距离
而计算测地线距离，也即是我们地本真距离，anyway我们可以用近邻地距离来近似
step1；在局部上基于欧式空间性子找出邻近点，连接起来形成我们的近邻连接图
step2：在近邻图用DIJKSTRA来计算任意两点的最短路径（floyd也行，不想动脑还是O(n^2)个DIJKSRTA吧）
step3：用MDS低维嵌入解决
至此我们只是解决了低维坐标的问题，想不到吧！
（近邻图可以用k也可以用通过选择距离小于 ϵ epsilon ϵ的点来构建）
后面的部分打了很多，但是发布的时候突然要登录，把内容给卡没了，草