文章目录
- 降维
- 线性降维-主成分分析 PCA
- 损失函数
P22 (系列五) 降维1-背景
本文参考 B站UP: shuhuai008 🌹🌹
降维
我们知道,解决过拟合的问题除了正则化和添加数据之外,降维就是最好的方法。降维的思路来源于维度灾难的问题,我们知道 n n n 维球的体积为:
C R n CR^n CRn
那么在球体积与边长为 2 R 2R 2R 的超立方体比值为:
lim n → 0 C R n 2 n R n = 0 \lim\limits_{n\rightarrow0}\frac{CR^n}{2^nR^n}=0 n→0lim2nRnCRn=0
这就是所谓的维度灾难,在高维数据中,主要样本都分布在立方体的边缘,所以数据集更加稀疏。
降维的算法分为:
- 直接降维,特征选择
- 线性降维,PCA,MDS等
- 分线性,流形包括 Isomap,LLE 等
P23 (系列五) 降维2-样本均值 & 样本方差矩阵
D a t a : X = { x 1 , x 2 … … x N } N x p T = [ x 1 T x 2 T . . . x N T ] = [ x 11 x 12 ⋯ x 1 p x 21 x 22 ⋯ x 2 p ⋮ ⋱ ⋮ x n 1 ⋯ x n p ] N x p X i 属于 R P i = 1 , 2 … … N Data: X= \left\{ {x_1,x_2……x_N}\right\}_{Nxp}^{T}= \begin{bmatrix} x_1^T \\ x_2^T \\ ... \\ x_N^T \end{bmatrix} =\begin{bmatrix} x_{11} & x_{12} \cdots & x_{1p} \\ x_{21} & x_{22} \cdots & x_{2p}\\ \vdots & \ddots & \vdots \\ x_{n1} & \cdots & x_{np} \end{bmatrix}_{N x p}\\ X_i属于\mathbb{R}^P \\ i=1,2……N Data:X={x1,x2……xN}NxpT= x1Tx2T...xNT = x11x21⋮xn1x12⋯x22⋯⋱⋯x1px2p⋮xnp NxpXi属于RPi=1,2……N
为了方便,我们首先将协方差矩阵(数据集)写成中心化的形式:
S = 1 N ∑ i = 1 N ( x i − x ‾ ) ( x i − x ‾ ) T = 1 N ( x 1 − x ‾ , x 2 − x ‾ , ⋯ , x N − x ‾ ) ( x 1 − x ‾ , x 2 − x ‾ , ⋯ , x N − x ‾ ) T = 1 N ( X T − 1 N X T I N 1 I N 1 T ) ( X T − 1 N X T I N 1 I N 1 T ) T = 1 N X T ( E N − 1 N I N 1 I 1 N ) ( E N − 1 N I N 1 I 1 N ) T X = 1 N X T H N H N T X = 1 N X T H N H N X = 1 N X T H X \begin{align}S&=\frac{1}{N}\sum\limits_{i=1}^N(x_i-\overline{x})(x_i-\overline{x})^T\nonumber\\ &=\frac{1}{N}(x_1-\overline{x},x_2-\overline{x},\cdots,x_N-\overline{x})(x_1-\overline{x},x_2-\overline{x},\cdots,x_N-\overline{x})^T\nonumber\\ &=\frac{1}{N}(X^T-\frac{1}{N}X^T\mathbb{I}_{N1}\mathbb{I}_{N1}^T)(X^T-\frac{1}{N}X^T\mathbb{I}_{N1}\mathbb{I}_{N1}^T)^T\nonumber\\ &=\frac{1}{N}X^T(E_N-\frac{1}{N}\mathbb{I}_{N1}\mathbb{I}_{1N})(E_N-\frac{1}{N}\mathbb{I}_{N1}\mathbb{I}_{1N})^TX\nonumber\\ &=\frac{1}{N}X^TH_NH_N^TX\nonumber\\ &=\frac{1}{N}X^TH_NH_NX=\frac{1}{N}X^THX \end{align} S=N1i=1∑N(xi−x)(xi−x)T=N1(x1−x,x2−x,⋯,xN−x)(x1−x,x2−x,⋯,xN−x)T=N1(XT−N1XTIN1IN1T)(XT−N1XTIN1IN1T)T=N1XT(EN−N1IN1I1N)(EN−N1IN1I1N)TX=N1XTHNHNTX=N1XTHNHNX=N1XTHX
这个式子利用了中心矩阵 $ H$的对称性,这也是一个投影矩阵。
P24(系列五) 降维3-PCA-最大投影方差
线性降维-主成分分析 PCA
M e a n : x ‾ = 1 N ∑ i = 1 N x i = 1 N X T I N C o v a r i a n c e : S = 1 N ∑ i = 1 N ( x i − x ‾ ) ( x i − x ‾ ) T = 1 N X T H X Mean: \overline{x}=\frac{1}{N}\sum\limits_{i=1}^{N}x_i= \frac{1}{N}X^T\mathbb{I}_N \\ Covariance :S=\frac{1}{N}\sum\limits_{i=1}^{N}(x_i-\overline{x})(x_i-\overline{x})^T\nonumber\\=\frac{1}{N}X^THX Mean:x=N1i=1∑Nxi=N1XTINCovariance:S=N1i=1∑N(xi−x)(xi−x)T=N1XTHX
一个中心:原始特征重构
两个基本点:最大投影方差,最小重构距离
- x在u1上的投影。
损失函数
主成分分析中,我们的基本想法是将所有数据投影到一个字空间中,从而达到降维的目标,为了寻找这个子空间,我们基本想法是:
- 所有数据在子空间中更为分散
- 损失的信息最小,即:在补空间的分量少
- 指向量维度改变,而是只选取u1-uq这q个向量作为基,删掉uq+1到 u p u_p up,这样这q个p维向量所张成的线性空间维度
- 关于重构向量和原始向量的维度问题
P25 (系列五)降维4-PCA-最小重构代价
原来的数据很有可能各个维度之间是相关的,于是我们希望找到一组 p p p 个新的线性无关的单位基 u i u_i ui,降维就是取其中的 q q q 个基。于是对于一个样本 x i x_i xi,经过这个坐标变换后(开始重构):
x i ^ = ∑ i = 1 p ( u i T x i ) u i = ∑ i = 1 q ( u i T x i ) u i + ∑ i = q + 1 p ( u i T x i ) u i \hat{x_i}=\sum\limits_{i=1}^p(u_i^Tx_i)u_i=\sum\limits_{i=1}^q(u_i^Tx_i)u_i+\sum\limits_{i=q+1}^p(u_i^Tx_i)u_i xi^=i=1∑p(uiTxi)ui=i=1∑q(uiTxi)ui+i=q+1∑p(uiTxi)ui
对于数据集来说,我们首先将其中心化然后再去上面的式子的第一项,并使用其系数的平方平均作为损失函数并最大化:
J = 1 N ∑ i = 1 N ∑ j = 1 q ( ( x i − x ‾ ) T u j ) 2 = ∑ j = 1 q u j T S u j , s . t . u j T u j = 1 \begin{align}J&=\frac{1}{N}\sum\limits_{i=1}^N\sum\limits_{j=1}^q((x_i-\overline{x})^Tu_j)^2\nonumber\\ &=\sum\limits_{j=1}^qu_j^TSu_j\ ,\ s.t.\ u_j^Tu_j=1 \end{align} J=N1i=1∑Nj=1∑q((xi−x)Tuj)2=j=1∑qujTSuj , s.t. ujTuj=1
由于每个基都是线性无关的,于是每一个 u j u_j uj 的求解可以分别进行,使用拉格朗日乘子法:
a r g m a x u j L ( u j , λ ) = a r g m a x u j u j T S u j + λ ( 1 − u j T u j ) \mathop{argmax}_{u_j}L(u_j,\lambda)=\mathop{argmax}_{u_j}u_j^TSu_j+\lambda(1-u_j^Tu_j) argmaxujL(uj,λ)=argmaxujujTSuj+λ(1−ujTuj)
于是:
S u j = λ u j Su_j=\lambda u_j Suj=λuj
可见,我们需要的基就是协方差矩阵的本征矢。损失函数最大取在本征值前 q q q 个最大值。
下面看其损失的信息最少这个条件,同样适用系数的平方平均作为损失函数,并最小化:
J = 1 N ∑ i = 1 N ∑ j = q + 1 p ( ( x i − x ‾ ) T u j ) 2 = ∑ j = q + 1 p u j T S u j , s . t . u j T u j = 1 \begin{align}J&=\frac{1}{N}\sum\limits_{i=1}^N\sum\limits_{j=q+1}^p((x_i-\overline{x})^Tu_j)^2\nonumber\\ &=\sum\limits_{j=q+1}^pu_j^TSu_j\ ,\ s.t.\ u_j^Tu_j=1 \end{align} J=N1i=1∑Nj=q+1∑p((xi−x)Tuj)2=j=q+1∑pujTSuj , s.t. ujTuj=1
同样的:
a r g m i n u j L ( u j , λ ) = a r g m i n u j u j T S u j + λ ( 1 − u j T u j ) \mathop{argmin}_{u_j}L(u_j,\lambda)=\mathop{argmin}_{u_j}u_j^TSu_j+\lambda(1-u_j^Tu_j) argminujL(uj,λ)=argminujujTSuj+λ(1−ujTuj)
损失函数最小取在本征值剩下的个最小的几个值。数据集的协方差矩阵可以写成 S = U Λ U T S=U\Lambda U^T S=UΛUT,直接对这个表达式当然可以得到本征矢。