绿色健康小清新

耐得住寂寞,守得住繁华

李宏毅机器学习-19-Unsupervised Learning-02-PCA

Unsupervised Learning: PCA(Ⅰ)

本文将主要介绍PCA算法的数学推导过程

上一篇文章提到,PCA算法认为降维就是一个简单的linear function,它的input x和output z之间是linear transform,即z=Wxz=Wx,PCA要做的,就是根据xx把W给找出来(zz未知)

PCA for 1-D

为了简化问题,这里我们假设z是1维的vector,也就是把x投影到一维空间,此时w是一个row vector

z1=w1xz_1=w^1\cdot x,其中w1w^1表示ww的第一个row vector,假设w1w^1的长度为1,即w12=1||w^1||_2=1,此时z1z_1就是xxw1w^1方向上的投影

那我们到底要找什么样的w1w^1呢?

假设我们现在已有的宝可梦样本点分布如下,横坐标代表宝可梦的攻击力,纵坐标代表防御力,我们的任务是把这个二维分布投影到一维空间上

我们希望选这样一个w1w^1,它使得xx经过投影之后得到的z1z_1分布越大越好,也就是说,经过这个投影后,不同样本点之间的区别,应该仍然是可以被看得出来的,即:

  • 我们希望找一个projection的方向,它可以让projection后的variance越大越好

  • 我们不希望projection使这些data point通通挤在一起,导致点与点之间的奇异度消失

  • 其中,variance的计算公式:Var(z1)=1Nz1(z1z1ˉ)2,w12=1Var(z_1)=\frac{1}{N}\sum\limits_{z_1}(z_1-\bar{z_1})^2, ||w^1||_2=1z1ˉ\bar {z_1}z1z_1的平均值

下图给出了所有样本点在两个不同的方向上投影之后的variance比较情况

PCA for n-D

当然我们不可能只投影到一维空间,我们还可以投影到更高维的空间

z=Wxz=Wx来说:

  • z1=w1xz_1=w^1\cdot x,表示xxw1w^1方向上的投影
  • z2=w2xz_2=w^2\cdot x,表示xxw2w^2方向上的投影

z1,z2,...z_1,z_2,...串起来就得到zz,而w1,w2,...w^1,w^2,...分别是WW的第1,2,…个row,需要注意的是,这里的wiw^i必须相互正交,此时WW是正交矩阵(orthogonal matrix),如果不加以约束,则找到的w1,w2,...w^1,w^2,...实际上是相同的值

Lagrange multiplier

求解PCA,实际上已经有现成的函数可以调用,此外你也可以把PCA描述成neural network,然后用gradient descent的方法来求解,这里主要介绍用拉格朗日乘数法(Lagrange multiplier)求解PCA的数学推导过程

注:wiw^ixx均为列向量,下文中类似wixw^i\cdot x表示的是矢量内积,而(wi)Tx(w^i)^T\cdot x表示的是矩阵相乘

calculate w1w^1

目标:maximize (w1)TSw1(w^1)^TSw^1,条件:(w1)Tw1=1(w^1)^Tw^1=1

  • 首先计算出z1ˉ\bar{z_1}

    z1=w1xz1ˉ=1Nz1=1Nw1x=w11Nx=w1xˉ\begin{aligned} &z_1=w^1\cdot x\\ &\bar{z_1}=\frac{1}{N}\sum z_1=\frac{1}{N}\sum w^1\cdot x=w^1\cdot \frac{1}{N}\sum x=w^1\cdot \bar x \end{aligned}

  • 然后计算maximize的对象Var(z1)Var(z-1)

    其中Cov(x)=1N(xxˉ)(xxˉ)TCov(x)=\frac{1}{N}\sum(x-\bar x)(x-\bar x)^T

    Var(z1)=1Nz1(z1z1ˉ)2=1Nx(w1xw1xˉ)2=1N(w1(xxˉ))2=1N(w1)T(xxˉ)(xxˉ)Tw1=(w1)T1N(xxˉ)(xxˉ)Tw1=(w1)TCov(x)w1\begin{aligned} Var(z_1)&=\frac{1}{N}\sum\limits_{z_1} (z_1-\bar{z_1})^2\\ &=\frac{1}{N}\sum\limits_{x} (w^1\cdot x-w^1\cdot \bar x)^2\\ &=\frac{1}{N}\sum (w^1\cdot (x-\bar x))^2\\ &=\frac{1}{N}\sum(w^1)^T(x-\bar x)(x-\bar x)^T w^1\\ &=(w^1)^T\frac{1}{N}\sum(x-\bar x)(x-\bar x)^T w^1\\ &=(w^1)^T Cov(x)w^1 \end{aligned}

  • 当然这里想要求Var(z1)=(w1)TCov(x)w1Var(z_1)=(w^1)^TCov(x)w^1的最大值,还要加上w12=(w1)Tw1=1||w^1||_2=(w^1)^Tw^1=1的约束条件,否则w1w^1可以取无穷大

  • S=Cov(x)S=Cov(x),它是:

    • 对称的(symmetric)
    • 半正定的(positive-semidefine)
    • 所有特征值(eigenvalues)非负的(non-negative)
  • 使用拉格朗日乘数法,利用目标和约束条件构造函数:

    g(w1)=(w1)TSw1α((w1)Tw11)g(w^1)=(w^1)^TSw^1-\alpha((w^1)^Tw^1-1)

  • w1w^1这个vector里的每一个element做偏微分:

    g(w1)/w11=0g(w1)/w21=0g(w1)/w31=0...\partial g(w^1)/\partial w_1^1=0\\ \partial g(w^1)/\partial w_2^1=0\\ \partial g(w^1)/\partial w_3^1=0\\ ...

  • 整理上述推导式,可以得到:

    其中,w1w^1是S的特征向量(eigenvector)

    Sw1=αw1Sw^1=\alpha w^1

  • 注意到满足(w1)Tw1=1(w^1)^Tw^1=1的特征向量w1w^1有很多,我们要找的是可以maximize (w1)TSw1(w^1)^TSw^1的那一个,于是利用上一个式子:

    (w1)TSw1=(w1)Tαw1=α(w1)Tw1=α(w^1)^TSw^1=(w^1)^T \alpha w^1=\alpha (w^1)^T w^1=\alpha

  • 此时maximize (w1)TSw1(w^1)^TSw^1就变成了maximize α\alpha,也就是当SS的特征值α\alpha最大时对应的那个特征向量w1w^1就是我们要找的目标

  • 结论:w1w^1S=Cov(x)S=Cov(x)这个matrix中的特征向量,对应最大的特征值λ1\lambda_1

calculate w2w^2

在推导w2w^2时,相较于w1w^1,多了一个限制条件:w2w^2必须与w1w^1正交(orthogonal)

目标:maximize (w2)TSw2(w^2)^TSw^2,条件:(w2)Tw2=1,(w2)Tw1=0(w^2)^Tw^2=1,(w^2)^Tw^1=0

结论:w2w^2也是S=Cov(x)S=Cov(x)这个matrix中的特征向量,对应第二大的特征值λ2\lambda_2

  • 同样是用拉格朗日乘数法求解,先写一个关于w2w^2的function,包含要maximize的对象,以及两个约束条件

    g(w2)=(w2)TSw2α((w2)Tw21)β((w2)Tw10)g(w^2)=(w^2)^TSw^2-\alpha((w^2)^Tw^2-1)-\beta((w^2)^Tw^1-0)

  • w2w^2的每个element做偏微分:

    g(w2)/w12=0g(w2)/w22=0g(w2)/w32=0...\partial g(w^2)/\partial w_1^2=0\\ \partial g(w^2)/\partial w_2^2=0\\ \partial g(w^2)/\partial w_3^2=0\\ ...

  • 整理后得到:

    Sw2αw2βw1=0Sw^2-\alpha w^2-\beta w^1=0

  • 上式两侧同乘(w1)T(w^1)^T,得到:

    (w1)TSw2α(w1)Tw2β(w1)Tw1=0(w^1)^TSw^2-\alpha (w^1)^Tw^2-\beta (w^1)^Tw^1=0

  • 其中α(w1)Tw2=0,β(w1)Tw1=β\alpha (w^1)^Tw^2=0,\beta (w^1)^Tw^1=\beta

    而由于(w1)TSw2(w^1)^TSw^2是vector×matrix×vector=scalar,因此在外面套一个transpose不会改变其值,因此该部分可以转化为:

    注:S是symmetric的,因此ST=SS^T=S

    (w1)TSw2=((w1)TSw2)T=(w2)TSTw1=(w2)TSw1\begin{aligned} (w^1)^TSw^2&=((w^1)^TSw^2)^T\\ &=(w^2)^TS^Tw^1\\ &=(w^2)^TSw^1 \end{aligned}

    我们已经知道w1w^1满足Sw1=λ1w1Sw^1=\lambda_1 w^1,代入上式:

    (w1)TSw2=(w2)TSw1=λ1(w2)Tw1=0\begin{aligned} (w^1)^TSw^2&=(w^2)^TSw^1\\ &=\lambda_1(w^2)^Tw^1\\ &=0 \end{aligned}

  • 因此有(w1)TSw2=0(w^1)^TSw^2=0α(w1)Tw2=0\alpha (w^1)^Tw^2=0β(w1)Tw1=β\beta (w^1)^Tw^1=\beta,又根据

    (w1)TSw2α(w1)Tw2β(w1)Tw1=0(w^1)^TSw^2-\alpha (w^1)^Tw^2-\beta (w^1)^Tw^1=0

    可以推得β=0\beta=0

  • 此时Sw2αw2βw1=0Sw^2-\alpha w^2-\beta w^1=0就转变成了Sw2αw2=0Sw^2-\alpha w^2=0,即

    Sw2=αw2Sw^2=\alpha w^2

  • 由于SS是symmetric的,因此在不与w1w_1冲突的情况下,这里α\alpha选取第二大的特征值λ2\lambda_2时,可以使(w2)TSw2(w^2)^TSw^2最大

  • 结论:w2w^2也是S=Cov(x)S=Cov(x)这个matrix中的特征向量,对应第二大的特征值λ2\lambda_2

PCA-decorrelation

z=Wxz=W\cdot x

神奇之处在于Cov(z)=DCov(z)=D,即z的covariance是一个diagonal matrix,推导过程如下图所示

PCA可以让不同dimension之间的covariance变为0,即不同new feature之间是没有correlation的,这样做的好处是,减少feature之间的联系从而减少model所需的参数量

如果你把原来的input data通过PCA之后再给其他model使用,那这些model就可以使用简单的形式,而无需考虑不同dimension之间类似x1x2,x3x53,...x_1\cdot x_2,x_3\cdot x_5^3,...这些交叉项,此时model得到简化,参数量大大降低,相同的data量可以得到更好的训练结果,从而可以避免overfitting的发生

本文主要介绍的是PCA的数学推导,如果你理解起来有点困难,那下一篇文章将会从另一个角度解释PCA算法的原理~

-------------本文结束感谢您的阅读-------------
六经蕴籍胸中久,一剑十年磨在手

欢迎关注我的其它发布渠道