本章主要講解第二類無監督學習問題——降維。
本節課主要講解降維的第一個作用——資料壓縮。
資料壓縮不僅能夠降低對記憶體或磁盤空間的占用，更重要的是能加快我們的學習算法。
假設我們有兩個特征，\(x_1\)用厘米表示，\(x_2\)用英寸表示，顯然這兩個特征是存在備援的，是以我們可以将其投影到斜線上，這樣我們就實作了把2維的特征值壓縮成1維。
假設我們有三個特征\(x_1,x_2,x_3\)，第一幅圖可能不是很明顯，但實際上這些點大概都是處在同一個平面内的，是以我們可以将其投影到二維平面上，這樣我們就實作了把3維的特征壓縮成2維。
本節課主要講解降維的第二個作用——資料可視化。
資料可視化能夠幫助我們在學習問題中找到更好的解決方法，而降維就能夠幫助我們進行資料可視化。
假如我們擁有許多不同國家的資料，每一個資料有50個特征（次元）。如果要将這些50D的資料進行可視化是不可能的，這就需要我們使用降維的方法了。
假如我們把50D的資料降維到2D，分别用\(z_1\)和\(z_2\)進行表示。那麼我們就能将其可視化在一個二維平面上。
假如\(z_1\)大概代表一個國家的整體名額，比如GDP，\(z_2\)大概代表一個國家的人均名額，比如人均GDP，那麼我們就能通過這個二維圖表發現一些國家之間的關系。
本節課主要介紹了最常見的降維算法——主成分分析（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最小化的是投影誤差，而線性回歸是預測誤差。
本節課主要講解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
總結如下：
我們之前讨論的内容是把PCA作為一個壓縮算法，把高維資料壓縮成低維資料，本節課主要講解如何還原，也就是把低維資料恢複到原有的高維資料。
我們通過方程\(z=U_{reduce}^Tx\)把\(x\)降維到\(z\)，相反的方程是：
\[x_{approx} = U_{reduce}z \approx x
這就是從低維表示\(z\)回到未壓縮的表示\(x\)的方程。
注意：這裡是近似的，也就是解壓是有損的。
本節課主要講解如何選擇主成分的數量\(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\)，即為主成分的數量。
本節課主要講解應用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總是會使得特征值的資訊丢失，導緻訓練誤差增加，是以隻有在有必要的情況下才使用。