CS229 Lesson 14 主成分分析法

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍因子分析的EM算法以及PCA。

4.针对因子分析的EM算法

E步骤的推导很简单。我们需要计算$Q_i(z^{(i)}) = p(z^{(i)}|x^{(i)};\mu,\Lambda,\Psi)​$。将均值和方差带入高斯分布的条件期望公式，我们发现$z^{(i)}|x^{(i)};\mu,\Lambda,\Psi \sim \mathcal N(\mu_{z^{(i)}|x^{(i)}}, \Sigma_{z^{(i)}|x^{(i)}})​$，其中

$$\begin{aligned} \mu_{z^{(i)}|x^{(i)}}&=\Lambda^T(\Lambda\Lambda^T+\Psi)^{-1}(x^{(i)}-\mu),\\ \Sigma_{z^{(i)}|x^{(i)}}&=I-\Lambda^T(\Lambda\Lambda^T+\Psi)^{-1}\Lambda \end{aligned}$$

所以，利用$\mu_{z^{(i)}|x^{(i)}}, \Sigma_{z^{(i)}|x^{(i)}}​$的定义，我们有

$$Q_i(z^{(i)}) =\frac{1}{(2\pi)^{\frac {k} 2}|\Sigma_{z^{(i)}|x^{(i)}}|^{\frac 1 2}} \exp\Big(-\frac{1}{2}(z^{(i)}-\mu_{z^{(i)}|x^{(i)}})^T \Sigma_{z^{(i)}|x^{(i)}}^{-1}(z^{(i)}-\mu_{z^{(i)}|x^{(i)}}) \Big)$$

​ 让我们开始处理M步骤。这里，我们需要关于$\mu,\Lambda,\Psi$最大化下式

$$\sum_{i=1}^m \int_{z^{(i)}} Q_i(z^{(i)}) \log \frac{p(x^{(i)},z^{(i)};\mu,\Lambda,\Psi)}{Q_i(z^{(i)})} dz^{(i)}$$

​ 首先关于$\Lambda​$进行优化，可以将上式简化为

$$\begin{aligned} & \sum_{i=1}^m \int_{z^{(i)}} Q_i(z^{(i)}) \big[\log{p(x^{(i)}|z^{(i)};\mu,\Lambda,\Psi)} +\log p(z^{(i)})-\log{Q_i(z^{(i)})} \big]dz^{(i)} \\ &=\sum_{i=1}^m \mathbb E_{z^{(i)}\sim Q_i}\big[\log{p(x^{(i)}|z^{(i)};\mu,\Lambda,\Psi)} +\log p(z^{(i)})-\log{Q_i(z^{(i)})} \big] \end{aligned}$$

这里，下标$z^{(i)}\sim Q_i$表示期望是关于从$Q_i$抽样的$z^{(i)}$求的。在随后的推导中，在没有歧义的情况下，我们将忽略这个下标。丢弃不依赖参数的项，可以发现我们需要最大化：

$$\begin{aligned} &\sum_{i=1}^m \mathbb E \big[\log{p(x^{(i)}|z^{(i)};\mu,\Lambda,\Psi)} \big]\\ &=\sum_{i=1}^m \mathbb E \Big[\log \frac{1}{(2\pi)^{\frac {n} 2}|\Psi|^{\frac 1 2}} \exp\Big(-\frac{1}{2}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})\Big)\Big]\\ &=\sum_{i=1}^m \mathbb E \Big[-\frac 1 2\log |\Psi| -\frac n 2 \log(2\pi)-\frac{1}{2}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})\Big] \end{aligned}$$

让我们关于$\Lambda$最大化上式。注意到只有最后一项依赖$\Lambda$。所以求导，然后利用

$$\text{trace}(a)=a(a\in \mathbb R)\\ \text{trace}(AB)=\text{trace}(BA)\\ \nabla_{A}\text{trace}(ABA^TC)=CAB+C^TAB\\ \nabla_A \text{trace}(AB) =B^T\\ \nabla_{A^T}f(A) =(\nabla_{A}f(A))^T$$

我们可以得到

$$\begin{aligned} &\nabla_{\Lambda}\sum_{i=1}^m -\mathbb E \Big[\frac{1}{2}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})\Big]\\ &=\sum_{i=1}^m \nabla_{\Lambda} \mathbb E\Big[ -\text{trace}(\frac 1 2 {z^{(i)}}^T\Lambda ^T\Psi^{-1}\Lambda z^{(i)} ) +\text{trace}({z^{(i)}}^T\Lambda^T \Psi^{-1}(x^{(i)}-\mu)) \Big]\\ &=\sum_{i=1}^m \nabla_{\Lambda} \mathbb E\Big[ -\text{trace}(\frac 1 2 \Lambda ^T\Psi^{-1}\Lambda z^{(i)}{z^{(i)}}^T ) +\text{trace}(\Lambda^T \Psi^{-1}(x^{(i)}-\mu){z^{(i)}}^T) \Big]\\ &=\sum_{i=1}^m \mathbb E\Big[ -\frac 1 2(\Psi^{-1}\Lambda z^{(i)}{z^{(i)}}^T +\Psi^{-1}\Lambda z^{(i)}{z^{(i)}}^T) + \Psi^{-1}(x^{(i)}-\mu){z^{(i)}}^T \Big] \end{aligned}$$

令上式为零并化简，我们可得

$$\sum_{i=1}^m \Lambda \mathbb E_{z^{(i)}\sim Q_i}\Big[z^{(i)}{z^{(i)}}^T \Big] =\sum_{i=1}^m (x^{(i)}-\mu)\mathbb E_{z^{(i)}\sim Q_i}\Big[{z^{(i)}}^T \Big]$$

因此，解出$\Lambda$，我们得到

$$\Lambda =\Big(\sum_{i=1}^m (x^{(i)}-\mu)\mathbb E_{z^{(i)}\sim Q_i}\Big[{z^{(i)}}^T \Big]\Big) \Big( \sum_{i=1}^m \mathbb E_{z^{(i)}\sim Q_i}\Big[z^{(i)}{z^{(i)}}^T \Big] \Big)^{-1}$$

注意到这个公式和最小二乘回归得到的正规方程有密切关系，

$$\theta^T=(y^T X)(X^TX)^{-1}$$

​ 为了完成M步骤的更新，让我们计算出上式的期望。因为我们定义$Q_i$服从均值为$\mu_{z^{(i)}|x^{(i)}}$，方差为$\Sigma_{z^{(i)}|x^{(i)}}$的高斯分布，我们可以很容易得到

$$\begin{aligned} \mathbb E_{z^{(i)}\sim Q_i}\Big[{z^{(i)}}^T \Big] &=\mu_{z^{(i)}|x^{(i)}}^T \\ \mathbb E_{z^{(i)}\sim Q_i}\Big[z^{(i)}{z^{(i)}}^T \Big]&=\mu_{z^{(i)}|x^{(i)}}\mu_{z^{(i)}|x^{(i)}}^T +\Sigma_{z^{(i)}|x^{(i)}} \end{aligned}$$

第二行的结果来自于如下事实：对于随机变量$Y$，$\text{Cov}(Y)= \mathbb E[YY^T]- \mathbb E[Y]\mathbb E[Y]^T$，因此$\mathbb E[YY^T]=\text{Cov}(Y)+ \mathbb E[Y]\mathbb E[Y]^T$。将以上结果带入，我们可以得到$\Lambda$的M步骤的更新公式：

$$\Lambda =\Big(\sum_{i=1}^m (x^{(i)}-\mu)\mu_{z^{(i)}|x^{(i)}}^T\Big) \Big( \sum_{i=1}^m \mu_{z^{(i)}|x^{(i)}}\mu_{z^{(i)}|x^{(i)}}^T +\Sigma_{z^{(i)}|x^{(i)}} \Big)^{-1}$$

​ 接着，关于$\mu$最大化，丢弃不依赖参数的项，我们需要最大化：

$$\sum_{i=1}^m \mathbb E \Big[-\frac{1}{2}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})\Big]$$

求导可得

$$\begin{aligned} &\nabla_{\mu}\sum_{i=1}^m -\mathbb E \Big[\frac{1}{2}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})\Big]\\ &=\sum_{i=1}^m \nabla_{\mu} \mathbb E \Big[-\frac{1}{2}\mu^T\Psi^{-1} \mu+ \mu^T\Psi^{-1} (x^{(i)}-\Lambda z^{(i)}) \Big]\\ &=\sum_{i=1}^m \mathbb E \Big[-\Psi^{-1} \mu + \Psi^{-1} (x^{(i)}-\Lambda z^{(i)}) \Big] \end{aligned}$$

令上式为零并化简，我们可得

$$\mu = \frac 1 m\sum_{i=1}^m x^{(i)} -\frac 1 m\sum_{i=1}^m \Lambda \mathbb E_{z^{(i)}\sim Q_i}\Big[z^{(i)} \Big]$$

利用下式

$$\mathbb E_{z^{(i)}\sim Q_i}\Big[{z^{(i)}} \Big] =\mu_{z^{(i)}|x^{(i)}}=\Lambda^T(\Lambda\Lambda^T+\Psi)^{-1}(x^{(i)}-\mu)$$

我们来计算$\sum_{i=1}^m \Lambda \mathbb E_{z^{(i)}\sim Q_i}\Big[z^{(i)} \Big]$

$$\begin{aligned} \sum_{i=1}^m \Lambda \mathbb E_{z^{(i)}\sim Q_i}\Big[z^{(i)} \Big] &=\sum_{i=1}^m \Lambda \Lambda^T(\Lambda\Lambda^T+\Psi)^{-1}(x^{(i)}-\mu) \\ &=\sum_{i=1}^m (\Lambda \Lambda^T +\Psi-\Psi)(\Lambda\Lambda^T+\Psi)^{-1}(x^{(i)}-\mu)\\ &=\sum_{i=1}^m (x^{(i)}-\mu) -\Psi(\Lambda\Lambda^T+\Psi)^{-1}\sum_{i=1}^m(x^{(i)}-\mu) \end{aligned}$$

带入之前的式子可得

$$\mu = \frac 1 m\sum_{i=1}^m x^{(i)} -\frac 1 m\Big(\sum_{i=1}^m (x^{(i)}-\mu) -\Psi(\Lambda\Lambda^T+\Psi)^{-1}\sum_{i=1}^m(x^{(i)}-\mu)\Big) \\ \Psi(\Lambda\Lambda^T+\Psi)^{-1}\sum_{i=1}^m(x^{(i)}-\mu) =0\\ \mu = \frac 1 m \sum_{i=1}^m x^{(i)}$$

因为上式和别的参数无关，所以$\mu$只要计算一次即可。

​ 最后，关于$\Psi$最大化，丢弃不依赖参数的项，我们需要最大化：

$$\sum_{i=1}^m \mathbb E \Big[\frac 1 2\log |\Psi^{-1}|-\frac{1}{2}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})\Big]$$

求导过程需要利用

$$\nabla_S \log |S|= \frac 1 {|S|} \nabla_S |S|=\frac 1 {|S|} |S| (S^{-1})^T = (S^{-1})^T \\ \nabla_A \text{trace}(AB) =B^T$$

为了求解方便，关于$\Psi^{-1}$求导可得

$$\begin{aligned} &\nabla_{\Psi^{-1}}\sum_{i=1}^m \mathbb E \Big[\frac 1 2\log |\Psi^{-1}|-\frac{1}{2}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})\Big] \\ &=\frac 1 2\sum_{i=1}^m \nabla_{\Psi^{-1}}\mathbb E \Big[ \log |\Psi^{-1}| - \text{trace}(x^{(i)}-\mu-\Lambda z^{(i)})^T \Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)}) \Big]\\ &=\frac 1 2 \sum_{i=1}^m \nabla_{\Psi^{-1}}\mathbb E \Big[\log |\Psi^{-1}|- \text{trace}(\Psi^{-1}(x^{(i)}-\mu-\Lambda z^{(i)})(x^{(i)}-\mu-\Lambda z^{(i)})^T ) \Big] \\ &=\frac 1 2 \sum_{i=1}^m \mathbb E \Big[\Psi - (x^{(i)}-\mu-\Lambda z^{(i)})(x^{(i)}-\mu-\Lambda z^{(i)})^T \Big] \end{aligned}$$

令上式为零并化简，我们可得

$$\begin{aligned} \Psi &=\frac 1 {m} \sum_{i=1}^m \mathbb E \Big[ (x^{(i)}-\mu-\Lambda z^{(i)})(x^{(i)}-\mu-\Lambda z^{(i)})^T \Big]\\ &=\frac 1 {m} \sum_{i=1}^m \mathbb E \Big[ x^{(i)} {x^{(i)}}^T-x^{(i)} \mu^T -x^{(i)}{z^{(i)}}^T\Lambda^T -\mu{x^{(i)}}^T+\mu \mu^T+\mu{z^{(i)}}^T\Lambda^T -\Lambda z^{(i)}{x^{(i)}}^T +\Lambda z^{(i)}\mu^T +\Lambda z^{(i)}{z^{(i)}}^T\Lambda^T \Big]\\ &=S_1+ S_2 \end{aligned}$$

其中

$$\begin{aligned} S_1 &= \frac 1 {m} \sum_{i=1}^m \mathbb E \Big[ x^{(i)} {x^{(i)}}^T -x^{(i)}{z^{(i)}}^T\Lambda^T -\Lambda z^{(i)}{x^{(i)}}^T +\Lambda z^{(i)}{z^{(i)}}^T\Lambda^T+\mu \mu^T \Big]\\ S_2&=\frac 1 {m} \sum_{i=1}^m \mathbb E \Big[ -x^{(i)} \mu^T-\mu{x^{(i)}}^T+\mu{z^{(i)}}^T\Lambda^T+\Lambda z^{(i)}\mu^T \Big] \end{aligned}$$

利用

$$\begin{aligned} \mathbb E_{z^{(i)}\sim Q_i}\Big[{z^{(i)}} \Big] &=\mu_{z^{(i)}|x^{(i)}} \\ \mathbb E_{z^{(i)}\sim Q_i}\Big[z^{(i)}{z^{(i)}}^T \Big]&=\mu_{z^{(i)}|x^{(i)}}\mu_{z^{(i)}|x^{(i)}}^T +\Sigma_{z^{(i)}|x^{(i)}} \end{aligned}$$

分别计算上述两式，首先计算$S_1$

$$S_1=\frac 1 {m} \sum_{i=1}^m \Big(x^{(i)} {x^{(i)}}^T -x^{(i)}\mu_{z^{(i)}|x^{(i)}}^T\Lambda^T -\Lambda \mu_{z^{(i)}|x^{(i)}}{x^{(i)}}^T +\Lambda (\mu_{z^{(i)}|x^{(i)}}\mu_{z^{(i)}|x^{(i)}}^T +\Sigma_{z^{(i)}|x^{(i)}})\Lambda^T+\mu \mu^T \Big)$$

接着计算$S_2​$

$$S_2=\frac 1 {m} \sum_{i=1}^m \Big(-x^{(i)} \mu^T-\mu{x^{(i)}}^T+\mu\mu_{z^{(i)}|x^{(i)}}^T\Lambda^T+\Lambda \mu_{z^{(i)}|x^{(i)}}\mu^T\Big)$$

注意到之前已经说明过的如下事实

$$\mu_{z^{(i)}|x^{(i)}}=\Lambda^T(\Lambda\Lambda^T+\Psi)^{-1}(x^{(i)}-\mu)$$

以及$\mu$的更新规则

$$\mu = \frac 1 m \sum_{i=1}^m x^{(i)}$$

所以

$$\sum_{i=1}^m \mu_{z^{(i)}|x^{(i)}} = 0$$

带入上式可得

$$\begin{aligned} S_2&=\frac 1 {m} \sum_{i=1}^m \Big(-x^{(i)} \mu^T-\mu{x^{(i)}}^T+\mu\mu_{z^{(i)}|x^{(i)}}^T\Lambda^T+\Lambda \mu_{z^{(i)}|x^{(i)}}\mu^T\Big)\\ &=\frac 1 {m} \Big( -2m\mu \mu^T \Big)\\ &=\frac 1 {m}\sum_{i=1}^m \Big(-2\mu \mu^T\Big) \end{aligned}$$

合并上述两式可得

$$\Psi =\frac 1 {m} \sum_{i=1}^m \Big(x^{(i)} {x^{(i)}}^T -x^{(i)}\mu_{z^{(i)}|x^{(i)}}^T\Lambda^T -\Lambda \mu_{z^{(i)}|x^{(i)}}{x^{(i)}}^T +\Lambda (\mu_{z^{(i)}|x^{(i)}}\mu_{z^{(i)}|x^{(i)}}^T +\Sigma_{z^{(i)}|x^{(i)}})\Lambda^T-2\mu \mu^T \Big)$$

注意$\Psi​$为对角阵，所以更新公式为

$$\Psi = \text{diag} \{\frac 1 {m} \sum_{i=1}^m \Big(x^{(i)} {x^{(i)}}^T -x^{(i)}\mu_{z^{(i)}|x^{(i)}}^T\Lambda^T -\Lambda \mu_{z^{(i)}|x^{(i)}}{x^{(i)}}^T +\Lambda (\mu_{z^{(i)}|x^{(i)}}\mu_{z^{(i)}|x^{(i)}}^T +\Sigma_{z^{(i)}|x^{(i)}})\Lambda^T-2\mu \mu^T \Big) \}$$

备注：这里的更新公式和讲义中不一样，但暂时还没找到问题。

Part XI 主成分分析

​ 在这部分讲义中，我们将学习一种新方法：主成分分析（PCA），这种方法尝试识别数据近似所在的子空间。不同于因子分析，PCA的做法更加直接，并且只需要计算特征向量，而不需要使用EM算法。

​ 假设我们有数据集$\{x^{(i)};i=1,…,m\}$，其中包含了$m$种汽车的数据，例如最大速度，转弯半径等等。假设对于每个$i$，$x^{(i)}\in \mathbb R^n$，其中$n\ll m$。我们不知道的是，两种不同属性——某个$x^{(i)}$和$x^{(j)}$——分别代表了汽车以英里每小时为单位的最大速度和以公里每小时为单位的最大速度。这两种属性因此几乎是线性相关的，只在对mph到kph的近似上有一些误差。因此，数据近似分布在一个$n-1$维子空间中。我们如何自动发现并且删除这种冗余呢？

​ 让我们再看一个例子，考虑一个来自无线电遥控直升机飞行员调查的数据，其中$x^{(i)}_1$是飞行员$i$的飞行技巧，$x^{(i)}_2$代表他/她有多热爱飞行。因为无线电遥控直升机很难操作，只有真正喜欢飞行的学生才会变成好的飞行员。所以，属性$x_1,x_2$密切相关。实际上，我们可以认为数据沿着对角线方向（$u_1$方向）捕捉到一个人对飞行的“动力”，只有少量噪音不在这个方向上。我们如何能够自动计算出$u_1$的方向呢？

​ 我们将很快介绍PCA算法。但是在运行PCA之前，我们将按如下方式预处理数据，用来正规化数据的均值和方差：

• 1.令$\mu=\frac 1 m \sum_{i=1}^m x^{(i)}$
• 2.用$x^{(i)}-\mu$代替$x^{(i)}$
• 3.令$\sigma_j^2 =\frac 1m \sum_{i}(x_j^{(i)})^2$
• 4.用$x_j^{(i)}/\sigma_j$代替$x_j^{(i)}$

​ 步骤(1-2)使得数据的均值为$0$，如果数据的均值为$0$，这两步可以忽略。步骤(3-4)对每个坐标进行伸缩，使得每个方向都有单位方差，这使得不同的属性以相同的“尺度”处理。如果我们事先知道数据的尺度一致，步骤(3-4)可以被忽略。

​ 现在，我们已经实施了正规化，我们应该如何计算“主要变异轴”$u$呢——即，数据近似所在的方向？一种解决这个问题的方法是找到单位向量$u$，使得当数据投影到$u$的方向上方差最大。直观地，数据一开始有一些方差/信息。我们想选择一个方向$u$，使得如果我们将数据投影到该方向/子空间，尽可能多的保留之前方差。

​ 考虑如下数据集，我们已经采取了正规化步骤：

​ 现在，假设我们按下图所示选择$u$的方向。圆点代表原始数据在该方向上的投影。

​ 我们可以看到投影数据仍然有相当大的方差，并且数据距离原点也比较远。相反的，假设我们选择了如下方法：

​ 这里，投影点的方差就小了很多，并且离原点很近。

​ 我们想自动选择第一幅同中的方向$u$。为了形式化这点，注意到给定单位向量$u$和点$x$，$x$在$u$上的投影长度为$x^Tu$。即，如果$x^{(i)}$是数据集中某一个点（图中的某个叉），那么它在$u$上的投影（图中的圈）是原点到$x^Tu$的距离。因此，为了最大化投影的方差，我们想选择单位向量$u$来最大化：

$$\begin{aligned} \frac 1 m \sum_{i=1}^m({x^{(i)}}^Tu)^2 &=\frac 1 m \sum_{i=1}^m u^Tx^{(i)}{x^{(i)}}^T u \\ &=u^T \Big( \frac 1 m \sum_{i=1}^m x^{(i)}{x^{(i)}}^T\Big)u \end{aligned}$$

我们可以很简单的发现，在$||u||_2=1$的条件下，求上式的最大值会得到$\Sigma=\frac 1 m \sum_{i=1}^m x^{(i)}{x^{(i)}}^T $特征向量，$\Sigma$是数据的协方差矩阵。（利用拉格朗日乘子法可以得到上述结果）

​ 来做一下总结，我们发现如果我们想找到1维子空间来近似数据，我们应该选择$u$为$\Sigma$的主特征向量。更一般的，如果我们想把数据投影到$k$维子空间($k<n$)，我们应该选择$u_1,…,u_k$为$\Sigma$的前$k$个特征向量。因为$\Sigma$为对称矩阵，$u_i$现在构成了数据新的正交基。

​ 现在，为了将$x^{(i)}$用这组基来表示，我们只需要计算相关向量

$$y^{(i)}=\left[ \begin{matrix} u_1^T x^{(i)} \\ u_2^T x^{(i)} \\ ...\\ u_k^T x^{(i)} \end{matrix} \right] \in \mathbb R^k$$

因此，只要$x^{(i)}\in \mathbb R^n$，向量$y^{(i)}$给出对$x^{(i)}$的一个$k$维近似。PCA因此也被认为是一个降维算法。向量$u_1,…,u_k$被称为数据的前$k$个主成分。