Dimensionality Reduction - Week_8_part2

Motivation

Motivation I: Data Compression

我們在處理非監督式學習的演算法的時候，會遇到降低維度的問題，會使用降低維度這方式的原因有以下幾個：一個原因是要讓數據壓縮，維度壓縮不僅可以讓資料壓縮還可以讓演算法加速，首先我們先介紹降低維度這件事，下面我們透過幾個例子來說明降低維度。

上述兩種不同的儀器來測量一些東西尺寸時，其中一個儀器的單位是英吋，另一個儀器測量的結果是釐米，我們希望將測量的結果當作機器學習的特徵，現在問題是若將兩者都作為特徵會有些重複，因此我們希望將這個二維的資料降低成一維的資料。

我們會找出一條合適的直線，將二維的數據點都投射到該直線上，然後用z⁽ⁱ⁾當作標示，這樣我們完成了二維數據x⁽ⁱ⁾向一維數據z⁽ⁱ⁾的映射，這樣新的特徵只是原有特徵的近似，但這樣將我們的儲存、記憶體占用量減半，並且使我們要使用這些資料的算法可以運行的更快。

同樣的若需要將數據從三維降至二維，就需要將三維向量投射到二維的平面上，迫使所有數據都在同一個平面上，降至二維的特徵向量。

--------------------------------------------------------------------------------------------------------------------------

Motivation II:Data Visualization

在許多機器學習問題中，如果我們能將資料可視化，我們可以找到一個更好解決方案，降為可以幫助我們。

假設我們有關於許多不同國家的數據，每一個特徵向量都有50個特徵(ex/ GDP、人均GDP、平均壽命等)，如果要將這個50維度的資料可視化是不可能的。使用降維的方法將其降至二維，我們便將其可視化。這樣做的問題在於，降維的算法只負責減少維度，新產生的特徵的意義必需由我們去發現。


--------------------------------------------------------------------------------------------------------------------------

Principal Component Analysis

Principal Component Analysis Problem Formulation

主要成分分析(Principal Component Analysis, PCA)是最常見的降維算法，在PCA演算法中，我們要做的是找到一個方向向量(Vector Direction)，當我們把所有數據都投射到該向量時，我們希望投射平均均方誤差能盡可能的最小化，方向向量是一個經過原點的向量，而投射誤差是從特徵向量向該方向向量作垂線的長度。

主成分分析問題的描述：

1. 問題要將n維數據降至k維
2. 目標是要找到向量u⁽¹⁾,u⁽²⁾,...,u^(k)使得投射誤差的總和最小化

有很多人會問說主成分分析和線性回歸是否不同，他們的差異點是在哪裡。主成分分析最小化的是投射誤差，而線性回歸嘗試的是最小化預測誤差。線性回歸的目的是預測結果，而主成分分析不作任何預測，如下圖所示，左邊是線性回歸的誤差，右邊則是主成分分析的誤差。

--------------------------------------------------------------------------------------------------------------------------

Principal Component Analysis Algorithm

在我們進行主成分分析前，要先進行資料的前處理，平均正規化(mean normalization)或特徵縮放(feature scaling)，第一步是要計算出所有特徵的平均，然後另x_j = x_j - 𝜇_j。如果是特徵在不同的數量級上，我們還需要將其除以標準差𝞂²。

第二步是計算協方差矩陣(covariance matrix)，第三步是計算協方差矩陣的特徵向量(eigenvectors)，我們可以利用奇異值求解(singular value decomposition)來求解。

對於一個n x n維度的矩陣，上式中的U是一個具有與數據之間最小投射誤差的方向向量構成的矩陣，即是特徵向量(eigenvectors)。如果我們希望將數據從 n 維降至 k 維，我們需要從U矩陣中選取前 k 個向量，獲得一個 n x k 維度的矩陣，我們用 U_reduce表示，然後通過如下計算獲得要求的新特徵向量z⁽ⁱ⁾，z⁽ⁱ⁾  =  U^T_reduce * x⁽ⁱ⁾，其中 x 是 n x 1 維，因此z結果為 k x 1 維度。

P.S 矩陣寫法：Z = X * U_reduce(:,1:K)

Z = m * k 的矩陣(m代表樣本個數，k代表特徵個數或維度，這邊的k代表降維後的維度)，X = m * n 的矩陣(m代表樣本個數，n代表特徵個數或維度，這邊的n代表降維後的維度)，U = n * n 的矩陣(這邊的n代表降維後的維度)。

--------------------------------------------------------------------------------------------------------------------------

Applying PCA

Reconstruction from Compressed Representation

在前面章節我們就紹如何將高維度的資料降成為度較低的資料，進行主成分分析，但在此章節我們要講如何將低維度的資料還原成高維度的資料，我們可以透過 x_approx^(l)  = U_reduce * z⁽¹⁾還原資料維度。

P.S 矩陣的寫法：X_approx = Z * U_reduce(:,1:K)'

Z = m * k 的矩陣(m代表樣本個數，k代表特徵個數或維度，這邊的k代表還原前的維度)，X = m * n 的矩陣(m代表樣本個數，n代表特徵個數或維度，這邊的n代表還原後的維度)，U = n * n 的矩陣(這邊的n代表還原前的維度)。

--------------------------------------------------------------------------------------------------------------------------

Choosing the Number of Principal Components

主要成分分析是減少投射的平均均方誤差如下：

訓練集的變異數如下：

主要我們怎麼去選擇k值這個主成分數呢?!依據常見的經驗法則，我們會選擇平均均方投射誤差和訓練集的變異數的比例小於0.01的最小k值，也就是說保留了99%的差異性。

如果我們希望這個比例小於1%，這就代表的原本數據的偏差有99%都保留下來，如果我們選擇保留95%的偏差，便能非常顯著地降低模型中特徵的維度。那要怎麼去計算出k值呢?!我們可以先令k = 1 ，然後進行主成分分析，獲得Ureduce和z，然後計算比例是否小於1%，如果不是再令 k = 2，如此類推，直到找到可以使得該比例小於1%的最小k值(原因是各個特徵之間通常情況存在某種相關性)。

當然還有一些更好的方式來選擇k值，當我們在octave中使用svd該函數的時候，我們獲得三個參數[U, S, V] = svd(sigma)。其中的S矩陣，只有對角線上有值，而其他單元都是0，我們可以利用這個矩陣來計算平均均方誤差和訓練集方差的比例：

換句話說也就是下圖的意思：

--------------------------------------------------------------------------------------------------------------------------

Advice for Applying PCA

本章會針對主成分分析的應用提出點建議，假設我們正針對一張100x100像素的圖片進行某個計算機視覺的機器學習，即總共有10000個特徵。

1. 第一步是運用主要成分分析將數據壓縮至1000個特徵
2. 對訓練資料集進行模型訓練
3. 在預測時，採用之前學習而來的U_reduce將輸入的特徵 x 轉換成特徵向量 z，然後進行預測

假設我們有交叉驗證集，也採用訓練及學習而來的U_reduce。

使用主成分分析的建議：

一個使用主成分分析常見的錯誤，將其用於減少過擬合(減少了特徵的數量)。這樣做非常不好，不如嘗試正規化(mean normalization)，原因在於主要成分分析只是近似地丟棄掉一些特徵，他並不考慮任何與結果變數有關的資訊，因此可能丟失非常重要的特徵，然而當我們進行正規化處理時，也會考慮到結果變量，並不會丟掉重要的訊息。

另一個常見的錯誤，把主要成分分析作為機器學習過程中的一部份，這雖然很多時候有效果，但最好還是從所有原始特徵開始，只在有必要的時候(算法運行太慢或者佔用太多內存)，才考慮採用主要成分分析。