本章主要讲解第二类无监督学习问题——降维。
Motivation I: Data Compression
本节课主要讲解降维的第一个作用——数据压缩。
数据压缩不仅能够降低对内存或磁盘空间的占用，更重要的是能加快我们的学习算法。
假设我们有两个特征，\(x_1\)用厘米表示，\(x_2\)用英寸表示，显然这两个特征是存在冗余的，所以我们可以将其投影到斜线上，这样我们就实现了把2维的特征值压缩成1维。
假设我们有三个特征\(x_1,x_2,x_3\)，第一幅图可能不是很明显，但实际上这些点大概都是处在同一个平面内的，所以我们可以将其投影到二维平面上，这样我们就实现了把3维的特征压缩成2维。
Motivation II: Data Visualization
本节课主要讲解降维的第二个作用——数据可视化。
数据可视化能够帮助我们在学习问题中找到更好的解决方法，而降维就能够帮助我们进行数据可视化。
假如我们拥有许多不同国家的数据，每一个数据有50个特征（维度）。如果要将这些50D的数据进行可视化是不可能的，这就需要我们使用降维的方法了。
假如我们把50D的数据降维到2D，分别用\(z_1\)和\(z_2\)进行表示。那么我们就能将其可视化在一个二维平面上。
假如\(z_1\)大概代表一个国家的整体指标，比如GDP，\(z_2\)大概代表一个国家的人均指标，比如人均GDP，那么我们就能通过这个二维图表发现一些国家之间的关系。
Principal Component Analysis problem formulation
本节课主要介绍了最常见的降维算法——主成分分析（PCA）。
Principal Component Analysis (PCA) problem formulation
如下图例子所示，PCA要做的就是找到一条直线能够把所有数据投影到上面，使得每个数据点和投影后的数据点之间的距离平方（投影误差）最小，在下图中找的可能就是红色直线，而如果是粉红色直线，那么投影误差就会非常大。
对PCA问题的描述：
- 将数据从2D降维到1D：找到一个方向（向量\(u^{(1)}\)），在其上投影数据以最小化投影误差。E.g.在左图中可能是\(u^{(1)}\)或者\(-u^{(1)}\)。
- 将数据从nD降维到kD：找到一个方向（向量\(u^{(1)},u^{(2)},\cdots,u^{(k)}\)），在其上投影数据以最小化投影误差。E.g.在右图中可能是\(u^{(1)},u^{(2)}\)确定的二维平面。
PCA is not linear regression
PCA和线性回归两者似乎有一定的相似之处，但是其本质上是完全不同的算法。PCA最小化的是投影误差，而线性回归是预测误差。
Principal Component Analysis algorithm
本节课主要讲解PCA算法的实现。
Data preprocessing
进行PCA之前需要先进行数据预处理，需要计算所有特征的均值\(\mu_j\)，然后另\(x_j=x_j-\mu_j\)，如果特征值不在同一个数量级，还需要进行特征缩放。
Principal Component Analysis (PCA) algorithm
把数据从n维降低到k维度：
-
计算协方差矩阵（covariance matrix）：\(\Sigma = \frac{1}{m} \sum_{i=1}^n (x^{(i)}) (x^{(i)})^T\)
注意：协方差矩阵用大些的Sigma符号表示，而不是求和符号。
\(x^{(i)}\)是一个\(n \times 1\)矩阵，\((x^{(i)})^T\)是一个\(1 \times n\)矩阵，所以协方差是一个\(n \times n\)矩阵。
-
计算协方差矩阵的特征向量（eigenvectors），利用奇异值分解求解\([U,S,V]\)，\(U\)是一个\(n \times n\)矩阵，我们选取其前\(k\)列记做\(n \times k\)矩阵\(U_{reduce}\)，然后通过如下计算得到新的特征向量\(z^{(i)}\)：
\[z^{(i)} = U_{reduce}^Tx^{(i)} \]
Principal Component Analysis (PCA) algorithm summary
总结如下：
Reconstruction from compressed representation
我们之前讨论的内容是把PCA作为一个压缩算法，把高维数据压缩成低维数据，本节课主要讲解如何还原，也就是把低维数据恢复到原有的高维数据。
我们通过方程\(z=U_{reduce}^Tx\)把\(x\)降维到\(z\)，相反的方程是：
\[x_{approx} = U_{reduce}z \approx x \]这就是从低维表示\(z\)回到未压缩的表示\(x\)的方程。
注意：这里是近似的，也就是解压是有损的。
Choosing the number of principal components
本节课主要讲解如何选择主成分的数量\(k\)。
先介绍两个概念：
- 平均投影误差平方（Average squared projection error）：\(\frac{1}{m} \sum_{i=1}^m \| x^{(i)} - x_{approx}^{(i)} \|^2\)
- 数据集总方差（Total variation in the data）：\(\frac{1}{m} \sum_{i=1}^m \| x^{(i)} \|^2\)
通常情况下，我们会选择使得下面式子成立的最小的\(k\)作为主成分的数量：
\[\frac{\frac{1}{m} \sum_{i=1}^m \| x^{(i)} - x_{approx}^{(i)} \|^2}{\frac{1}{m} \sum_{i=1}^m \| x^{(i)} \|^2} \le 0.01 \]这种情况也称为“保留了99%的方差”（99% of variance is retained）。
注意：并不一定要选择0.01，也可以选择其它合适的数字，E.g. 0.05，那么就称为保留了95%的方差。
如何求出\(k\)呢？
我们可以先令\(k=1\)，然后计算\(U_{reduce},z,x_{approx}\)，判断是否满足条件；如果不满足则继续计算\(k=2\)的情况，以此类推，直到找到可以使得条件满足的最小的\(k\)。
更好的计算方法其实是通过矩阵\(S\)来进行计算，原理和上面的方法类似，同样是找到使得条件满足的最小的\(k\)，即为主成分的数量。
Advice for applying PCA
本节课主要讲解应用PCA算法的一些建议。
Supervised learning speedup
以一个简单的例子讲解如何用PCA加快监督学习算法：
- 假设我们的训练集：\((x^{(1)}, y^{(1)}),(x^{(2)}, y^{(2)}), \cdots ,(x^{(m)}, y^{(m)})\)
- 抽取出特征值\(x_{(1)},x_{(2)},\cdots,x_{(m)} \in \R^{10000}\)
- 通过PCA算法将特征值降维成\(z_{(1)},z_{(2)},\cdots,z_{(m)} \in \R^{1000}\)
- 这样我们就得到了新的训练集：\((z^{(1)}, y^{(1)}),(z^{(2)}, y^{(2)}), \cdots ,(z^{(m)}, y^{(m)})\)
- 最后，采用新的训练集训练学习算法
注意：我们只能通过训练集得到$x^{(i)} \rarr z^{(i)} \(的映射关系\)U_{reduce}$，在验证集和测试集上面也采用相同的映射关系即可，不需要重新学习。
Application of PCA
PCA算法的常见应用：
- Compression
- Reduce memory/disk needed to store data
- Speed up learning algorithm
- Visualization
Bad use of PCA: To prevent overfitting
PCA常见的一个错误应用是用于防止过拟合。
错误做法：使用\(z^{(i)}\)替代\(x^{(i)}\)，减少特征值，降低过拟合的可能性。
这种方式也许是有效的，但这并不是解决过拟合的好方法，更好的方法是采用正则化。原因在于PCA会丢失一些特征，并不考虑任何与结果变量有关的信息，而正则化则会考虑到结果变量。
另一个常见的错误是，在罗列机器学习计划时默认地把PCA当作学习过程的一部分。更合理的做法是考虑——在不使用PCA的情况下怎么做呢？
在使用PCA之前，首先应该尝试使用原始数据\(x^{(i)}\)，只有在必要的时候才考虑使用PCA把数据降维成\(z^{(i)}\)。因为无论如何，PCA总是会使得特征值的信息丢失，导致训练误差增加，所以只有在有必要的情况下才使用。