- 取得連結
- 以電子郵件傳送
- 其他應用程式
ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第十三講 Deep Learning
首先，先定義以下條件
移除常數項 \(x_0=1\) 和 +1 那項，因不方便定義 \(E_{in}\)，如下，無法一連貫寫出式子
$$ \begin{align*} \mathbf{x}^*_{\widetilde{d}\times 1}&=\mathbf{W}_{\widetilde{d}\times (d+1)}^{(1)}\mathbf{x}_{(d+1)\times 1}\\ \widehat{\mathbf{x}}_{d\times 1}&=\mathbf{W}_{d\times (\widetilde{d}+1)}^{(2)} \begin{bmatrix} 1\\ \mathbf{x}^*_{\widetilde{d}\times 1}\\ \end{bmatrix} \end{align*} $$ 並令兩邊的權重一樣，也就是 regularization 的作用
且 \(\widetilde{d}<d\)，不然會失去壓縮的本意
$$ \begin{align*} \mathbf{x}^*_{\widetilde{d}\times 1}&=\mathbf{W}_{\widetilde{d}\times d}^{(1)}\mathbf{x}_{d\times 1}\\ \widehat{\mathbf{x}}_{d\times 1}&=\mathbf{W}_{d\times \widetilde{d}}^{(2)} \mathbf{x}^*_{\widetilde{d}\times 1}\\ &=\mathbf{W}_{d\times \widetilde{d}}^{(2)} \mathbf{W}_{\widetilde{d}\times d}^{(1)}\mathbf{x}_{d\times 1}\\ [\because w_{ij}^{(1)}=w_{ij}^{(2)}=w_{ji}]&=\mathbf{W}_{d\times \widetilde{d}} (\mathbf{W}_{d \times \widetilde{d}})^T\mathbf{x}_{d\times 1}\\ \end{align*} $$ 故可得
$$ E_{in}(\mathbf{W})=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{x}_n-\mathbf{W}_{d\times \widetilde{d}} \mathbf{W}_{\widetilde{d}\times d}^T\mathbf{x}_n \right \|^2 $$ 又因為 SVD，其實 SVD 可被視為變換矩陣 A 的三個分解步驟：旋轉 \(\mathbf{V}^T\)，伸縮 \(\Sigma\)，再旋轉 \(\mathbf{U}\)
可參考 奇異值分解 (SVD)
$$ \begin{align*} \mathbf{W}_{d \times \widetilde{d}}&=\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T\\ \mathbf{W}_{d\times \widetilde{d}}\mathbf{W}_{\widetilde{d}\times d}^T &= \mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} \mathbf{V}_{\widetilde{d}\times \widetilde{d}}^T(\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T)^T\\ &= \mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} \mathbf{V}_{\widetilde{d}\times \widetilde{d}}^T\mathbf{V}_{\widetilde{d}\times \widetilde{d}}(\boldsymbol\Sigma_{d\times \widetilde{d}}) ^T(\mathbf{U}_{d\times d})^T\\ [\because \mathbf{V}_{\widetilde{d}\times \widetilde{d}}^T\mathbf{V}_{\widetilde{d}\times \widetilde{d}}=\mathbf{I}] &= \mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\boldsymbol\Sigma_{d\times \widetilde{d}}) ^T(\mathbf{U}_{d\times d})^T\\ &= \mathbf{U}_{d\times d}\boldsymbol\Gamma _{d\times d}(\mathbf{U}_{d\times d})^T \end{align*} $$ 重新定義 \(E_{in}\)
$$ \begin{align*} E_{in}(\mathbf{W})&=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{x}_n-\mathbf{W}_{d\times \widetilde{d}} \mathbf{W}_{\widetilde{d}\times d}^T\mathbf{x}_n \right \|^2\\ &=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{x}_n-\mathbf{U}_{d\times d}\boldsymbol\Gamma _{d\times d}(\mathbf{U}_{d\times d})^T\mathbf{x}_n \right \|^2\\ &=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}\mathbf{I} \mathbf{U}^T\mathbf{x}_n-\mathbf{U}\boldsymbol\Gamma \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}(\mathbf{I}-\boldsymbol\Gamma) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ \\ \underset{\mathbf{W}}{min}\ E_{in}&=\underset{\mathbf{U}}{min}\ \underset{\mathbf{\boldsymbol\Gamma }}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}(\mathbf{I}-\boldsymbol\Gamma) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ \end{align*} $$ 跟 \(\boldsymbol\Gamma\) 有關的，只有 \((\mathbf{I}-\boldsymbol\Gamma)\)，然後該如何最小化呢？
因 \(\mathbf{U}\) 是單位向量的集合，所以前面的 \(\mathbf{U}\) 不影響最後結果的距離
所以可以簡化來看
$$ \underset{\mathbf{\boldsymbol\Gamma }}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|(\mathbf{I}-\boldsymbol\Gamma) (some\ vector) \right \|^2\\ $$ 可以發現，當 \((\mathbf{I}-\boldsymbol\Gamma)\) 相減時，越多 0 超好
但因為 \(\boldsymbol\Gamma\) 是對角線矩陣，且 rank \(\le \widetilde{d}\)
所以可得
$$ \boldsymbol\Gamma= \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} $$ 重新寫下 \(E_{in}\)
$$ \begin{align*} \underset{\mathbf{W}}{min}\ E_{in}&=\underset{\mathbf{U}}{min}\ \underset{\boldsymbol\Gamma}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}(\mathbf{I}-\boldsymbol\Gamma) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\underset{\mathbf{U}}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}\left (\mathbf{I}_{d\times d}- \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \right ) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\underset{\mathbf{U}}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U} \begin{bmatrix} \mathbf{0}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{I}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\underset{\mathbf{U}}{max}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U} \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2\\ \\ &subject\ to\ \mathbf{u}_n^T\mathbf{u}_n=1 \end{align*} $$ 利用 Lagrange 乘數法，且同之前，前面的 \(\mathbf{U}\) 不影響最後結果的距離
$$ \begin{align*} L(\mathbf{U},\lambda_1,\lambda_2,\cdots,\lambda_d)&= \frac{1}{N}\sum_{n=1}^{N}\left \| \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2 +\lambda_1 (1-\mathbf{u}_1^T\mathbf{u}_1)+\lambda_2 (1-\mathbf{u}_2^T\mathbf{u}_2=1)+\cdots+\lambda_d (1-\mathbf{u}_d^T\mathbf{u}_d)\\ \\ \frac{\partial L(\mathbf{U},\lambda_1,\lambda_2,\cdots,\lambda_d)}{\partial \mathbf{u}_n} &= 0 \\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\sum_{n=1}^{N}\left \| \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2 +\lambda_1 (1-\mathbf{u}_1^T\mathbf{u}_1)+\lambda_2 (1-\mathbf{u}_2^T\mathbf{u}_2=1)+\cdots+\lambda_d (1-\mathbf{u}_d^T\mathbf{u}_d) \right )\\ [\because only\ consider\ \mathbf{u}_m]&= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\sum_{n=1}^{N}\left \| \mathbf{u}_m^T\mathbf{x}_n \right \|^2 +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\sum_{n=1}^{N} \mathbf{u}_m^T\mathbf{x}_n \mathbf{x}_n^T\mathbf{u}_m +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\mathbf{u}_m^T\left (\sum_{n=1}^{N} \mathbf{x}_n \mathbf{x}_n^T \right )\mathbf{u}_m +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\mathbf{u}_m^T \mathbf{XX}^T\mathbf{u}_m +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &=\frac{1}{N}\cdot 2\mathbf{XX}^T\mathbf{u}_m-2 \lambda_m\mathbf{u}_m\\ &=0\\ \end{align*} $$
$$ \begin{align*} \frac{1}{N}\cdot 2\mathbf{XX}^T\mathbf{u}_m&=2 \lambda_m\mathbf{u}_m\\ \frac{1}{N}\cdot \mathbf{XX}^T\mathbf{u}_m&=\lambda_m\mathbf{u}_m\\ \end{align*} $$ 故 \(\mathbf{u}_m\) 是 \(\mathbf{XX}^T\) 的 eigenvector
基於最大化要挑選前 \(\widetilde{d}\) 大的 \(\lambda_m\)，也就是 top eigenvectors
因 \(\mathbf{W}_{d \times \widetilde{d}}=\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T\)
\(\mathbf{V}\) 任意，過程中可發現並不影響最佳值，故選擇 \(\mathbf{I}\)
\(\boldsymbol\Sigma_{d\times \widetilde{d}}(\boldsymbol\Sigma_{d\times \widetilde{d}}) ^T =\Gamma _{d\times d}\) 實際 \(1^2=1\)
所以 \(\boldsymbol\Sigma\) 也只是看 \(\Gamma\) 有幾個 1 就有多少個 1
故得 \(\mathbf{W}\)
$$ \begin{align*} \mathbf{W}_{d \times \widetilde{d}}&=\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T\\ &=\begin{bmatrix} eigenV^{(1)}_{\mathbf{XX}^T} & \cdots & eigenV^{(\widetilde{d})}_{\mathbf{XX}^T} & \mathbf{0}_{1\times (d-\widetilde{d})} \end{bmatrix}_{d\times d}\begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}}\\ \mathbf{0}_{(d-\widetilde{d})\times \widetilde{d}} \end{bmatrix}_{d\times \widetilde{d}} (\mathbf{I}_{\widetilde{d}\times \widetilde{d}})^T\\ &=\begin{bmatrix} eigenV^{(1)}_{\mathbf{XX}^T} & \cdots & eigenV^{(\widetilde{d})}_{\mathbf{XX}^T} \end{bmatrix}_{d\times \widetilde{d}} \end{align*}\\ $$ 事實上，這與 PCA 很類似
PCA 求的是最大化 \(\Sigma (variance\ after\ projection)\)
而 linear autoencoder 求的是最大化 \(\Sigma (maginitude\ after\ projection)^2\)
所以若將輸入資料先扣掉平均 \(\mathbf{x}_n \leftarrow \mathbf{x}_n-\overline{\mathbf{x}}\)
丟進 linear autoencoder 不就是 PCA 了
即然如此，干脆就回傳特徵轉換 \(\Phi (\mathbf{x})=\mathbf{W}(\mathbf{x}-\color{Red}{\overline{\mathbf{x}}})\)
記得 linear autoencoder 為了跟 PCA 一致，有做了一些處理，像是移掉常數項之類的
所以兩者還是有點差異
而實務上 PCA 比較好一點，因有統計上的背景
Neural networks [6.4] : Autoencoder - linear autoencoder
主成分分析與低秩矩陣近似
Singular value decomposition
sklearn.decomposition.PCA
Package：scikit-learn
課程：機器學習技法
簡介：第十三講 Deep Learning
比較
- Shallow NNet
- 較少的 hidden layers
- 較有效率訓練
- 較簡單的架構
- 理論上足夠強大
- Deep NNet
- 非常多的 hidden layers
- 難以訓練
- 難以決定架構
- 非常強大，理論上可做到任何想做的事
- layer 較有意義
- 因很多層，每層可只做簡單的事
從簡單的 features 慢慢組合成 複雜的 features
像是辨識數字，從 pixels -> 簡單筆畫 -> 部分區塊 -> 數字
Deep NNet Challenges
- 如何決定架構
- validation
- 對問題的了解，例如： convolutional NNet 在影像上的運用
- model 複雜度高
- 通常不是問題，資料量通常夠多
- regularization
- dropout
- 當一些神經元壞掉時，仍可正常工作
- denoising
- 輸入資料壞掉時，仍可正常工作
- 架構加上 constraints ，例 CNN(convolutional NNet)
- weight elimination
- early stopping
- 最佳化困難
- pre-training
- 小心地決定初始值，防止 local minimum
- 計算複雜，特別是資料量太多
- 更進步的硬體與計算架構，例如：平行處理 mini-batch with GPU
Autoencoder
- 可用在 pre-training，
- unsupervised learning technique
- \(d-\widetilde{d}-d\ \mathrm{NNet}\) 令 \(g_i(\mathbf{x})\approx x_i\)
- \(\widetilde{d}<d\)：壓縮資料維度
- 近似 identity function
- error function \(\sum_{i=1}^{d}(g_i(\mathbf{x})-x_i)^2\)
- \(w_{ij}^{(1)}\)：encoding weights
\(w_{ji}^{(2)}\)：dencoding weights - 通常令 \(w_{ij}^{(1)}=w_{ji}^{(2)}\) for regularization
weights 表示如何做特徵轉換，也算是一種 encoding，將之編碼成另一種表現方式
pre-training 時，並不希望 weights 會讓資料失真，導致下一層只能針對更少的特徵做處理
所以好的 weights 應當保留資料訊息，只是將之換個方式表達
故可訓練一個 \(d-\widetilde{d}-d\ \mathrm{NNet}\) 令 \(g(\mathbf{x})\approx \mathbf{x}\)，也就是 identity function
而 error function 為 \(\sum_{i=1}^{d}(g_i(\mathbf{x})-x_i)^2\)
因希望壓縮資料，所以令 \(\widetilde{d}<d\)
因為資料並不需要 \(\mathbf{y}\)，所以 Autoencoder 被歸類在 unsupervised learning technique
並設定 regularization 為 \(w_{ij}^{(1)}=w_{ji}^{(2)}\)，但計算 backprop 務必考慮進去
利用這些特性
然後在 \(d-d^{(1)}-d^{(2)}-d^{(3)}-1\) deep NNet 執行 pre-training
時間共需要 \(c(dd^{(1)}+d^{(1)}d^{(2)}+ d^{(2)}d^{(3)}+ d^{(3)})\) 秒
pre-training 時，並不希望 weights 會讓資料失真，導致下一層只能針對更少的特徵做處理
所以好的 weights 應當保留資料訊息，只是將之換個方式表達
故可訓練一個 \(d-\widetilde{d}-d\ \mathrm{NNet}\) 令 \(g(\mathbf{x})\approx \mathbf{x}\)，也就是 identity function
而 error function 為 \(\sum_{i=1}^{d}(g_i(\mathbf{x})-x_i)^2\)
因希望壓縮資料，所以令 \(\widetilde{d}<d\)
因為資料並不需要 \(\mathbf{y}\)，所以 Autoencoder 被歸類在 unsupervised learning technique
並設定 regularization 為 \(w_{ij}^{(1)}=w_{ji}^{(2)}\)，但計算 backprop 務必考慮進去
利用這些特性
- supervised learning
- \(w_{ij}^{(1)}\) 可運用在 pre-traning
- unsupervised learning
- \(g(\mathbf{x})\approx \mathbf{x}\) 的相似度
- density estimation
- outlier detection
- \(\widetilde{d}\) 的輸出結果可用來分類
然後在 \(d-d^{(1)}-d^{(2)}-d^{(3)}-1\) deep NNet 執行 pre-training
時間共需要 \(c(dd^{(1)}+d^{(1)}d^{(2)}+ d^{(2)}d^{(3)}+ d^{(3)})\) 秒
denoising autoencoder
資料為 \(\left \{ (\widetilde{\mathbf{x}}_1,\mathbf{y}_1=\mathbf{x}_1),(\widetilde{\mathbf{x}}_2,\mathbf{y}_2=\mathbf{x}_2),\cdots,(\widetilde{\mathbf{x}}_N,\mathbf{y}_N=\mathbf{x}_N) \right \}\) 在 autoencoder 上訓練
且 \(\widetilde{\mathbf{x}}_n=\mathbf{x}_n+noise\)
且 \(\widetilde{\mathbf{x}}_n=\mathbf{x}_n+noise\)
noise 也是 overfitting 的主因之一
可參考 [ML] 機器學習基石：第十三講 Hazard of Overfitting
那麼有沒有辦法減少 noise 呢？
比較直覺的想法是，移除有 noise 的資料不就好了
如果反其道而行，加入 noise 呢？聽起來很瘋狂
但也許可以利用 autoencoder 來做到這件事
將 autoencoder 訓練成非常 robust
不只可以 \(g(\mathbf{x})\approx \mathbf{x}\)，還可以 \(g(\widetilde{\mathbf{x}})\approx \mathbf{x}\)，\(\widetilde{\mathbf{x}}\) 只是跟 \(\mathbf{x}\) 略有不同而已
故加入資料並訓練之 \(\left \{ (\widetilde{\mathbf{x}}_1,\mathbf{y}_1=\mathbf{x}_1),(\widetilde{\mathbf{x}}_2,\mathbf{y}_2=\mathbf{x}_2),\cdots,(\widetilde{\mathbf{x}}_N,\mathbf{y}_N=\mathbf{x}_N) \right \}\)
\(\widetilde{\mathbf{x}}_n=\mathbf{x}_n+noise\)，noise 來自人造的 noise
而這正是一種 regularization：data hinting
可參考 [ML] 機器學習基石：第十三講 Hazard of Overfitting
那麼有沒有辦法減少 noise 呢？
比較直覺的想法是，移除有 noise 的資料不就好了
如果反其道而行，加入 noise 呢？聽起來很瘋狂
但也許可以利用 autoencoder 來做到這件事
將 autoencoder 訓練成非常 robust
不只可以 \(g(\mathbf{x})\approx \mathbf{x}\)，還可以 \(g(\widetilde{\mathbf{x}})\approx \mathbf{x}\)，\(\widetilde{\mathbf{x}}\) 只是跟 \(\mathbf{x}\) 略有不同而已
故加入資料並訓練之 \(\left \{ (\widetilde{\mathbf{x}}_1,\mathbf{y}_1=\mathbf{x}_1),(\widetilde{\mathbf{x}}_2,\mathbf{y}_2=\mathbf{x}_2),\cdots,(\widetilde{\mathbf{x}}_N,\mathbf{y}_N=\mathbf{x}_N) \right \}\)
\(\widetilde{\mathbf{x}}_n=\mathbf{x}_n+noise\)，noise 來自人造的 noise
而這正是一種 regularization：data hinting
Principal Component Analysis
Linear Autoencoder or PCA
紅色表示兩者的差異
紅色表示兩者的差異
- 令 \(\overline{\mathbf{x}}=\frac{1}{N}\sum_{n=1}^{N}\mathbf{x}_n\)
且修正 \(\mathbf{x}_n \leftarrow \mathbf{x}_n-\overline{\mathbf{x}}\) - 計算 \(\mathbf{X}^T\mathbf{X}\) 的 \(\widetilde{d}\) 個 top eigenvectors \(\mathbf{w}_1,\mathbf{w}_2,\cdots ,\mathbf{w}_{\widetilde{d}}\)
- 回傳特徵轉換 \(\Phi (\mathbf{x})=\mathbf{W}(\mathbf{x}-\color{Red}{\overline{\mathbf{x}}})\)
移除常數項 \(x_0=1\) 和 +1 那項，因不方便定義 \(E_{in}\)，如下，無法一連貫寫出式子
$$ \begin{align*} \mathbf{x}^*_{\widetilde{d}\times 1}&=\mathbf{W}_{\widetilde{d}\times (d+1)}^{(1)}\mathbf{x}_{(d+1)\times 1}\\ \widehat{\mathbf{x}}_{d\times 1}&=\mathbf{W}_{d\times (\widetilde{d}+1)}^{(2)} \begin{bmatrix} 1\\ \mathbf{x}^*_{\widetilde{d}\times 1}\\ \end{bmatrix} \end{align*} $$ 並令兩邊的權重一樣，也就是 regularization 的作用
且 \(\widetilde{d}<d\)，不然會失去壓縮的本意
$$ \begin{align*} \mathbf{x}^*_{\widetilde{d}\times 1}&=\mathbf{W}_{\widetilde{d}\times d}^{(1)}\mathbf{x}_{d\times 1}\\ \widehat{\mathbf{x}}_{d\times 1}&=\mathbf{W}_{d\times \widetilde{d}}^{(2)} \mathbf{x}^*_{\widetilde{d}\times 1}\\ &=\mathbf{W}_{d\times \widetilde{d}}^{(2)} \mathbf{W}_{\widetilde{d}\times d}^{(1)}\mathbf{x}_{d\times 1}\\ [\because w_{ij}^{(1)}=w_{ij}^{(2)}=w_{ji}]&=\mathbf{W}_{d\times \widetilde{d}} (\mathbf{W}_{d \times \widetilde{d}})^T\mathbf{x}_{d\times 1}\\ \end{align*} $$ 故可得
$$ E_{in}(\mathbf{W})=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{x}_n-\mathbf{W}_{d\times \widetilde{d}} \mathbf{W}_{\widetilde{d}\times d}^T\mathbf{x}_n \right \|^2 $$ 又因為 SVD，其實 SVD 可被視為變換矩陣 A 的三個分解步驟：旋轉 \(\mathbf{V}^T\)，伸縮 \(\Sigma\)，再旋轉 \(\mathbf{U}\)
可參考 奇異值分解 (SVD)
$$ \begin{align*} \mathbf{W}_{d \times \widetilde{d}}&=\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T\\ \mathbf{W}_{d\times \widetilde{d}}\mathbf{W}_{\widetilde{d}\times d}^T &= \mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} \mathbf{V}_{\widetilde{d}\times \widetilde{d}}^T(\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T)^T\\ &= \mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} \mathbf{V}_{\widetilde{d}\times \widetilde{d}}^T\mathbf{V}_{\widetilde{d}\times \widetilde{d}}(\boldsymbol\Sigma_{d\times \widetilde{d}}) ^T(\mathbf{U}_{d\times d})^T\\ [\because \mathbf{V}_{\widetilde{d}\times \widetilde{d}}^T\mathbf{V}_{\widetilde{d}\times \widetilde{d}}=\mathbf{I}] &= \mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\boldsymbol\Sigma_{d\times \widetilde{d}}) ^T(\mathbf{U}_{d\times d})^T\\ &= \mathbf{U}_{d\times d}\boldsymbol\Gamma _{d\times d}(\mathbf{U}_{d\times d})^T \end{align*} $$ 重新定義 \(E_{in}\)
$$ \begin{align*} E_{in}(\mathbf{W})&=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{x}_n-\mathbf{W}_{d\times \widetilde{d}} \mathbf{W}_{\widetilde{d}\times d}^T\mathbf{x}_n \right \|^2\\ &=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{x}_n-\mathbf{U}_{d\times d}\boldsymbol\Gamma _{d\times d}(\mathbf{U}_{d\times d})^T\mathbf{x}_n \right \|^2\\ &=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}\mathbf{I} \mathbf{U}^T\mathbf{x}_n-\mathbf{U}\boldsymbol\Gamma \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}(\mathbf{I}-\boldsymbol\Gamma) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ \\ \underset{\mathbf{W}}{min}\ E_{in}&=\underset{\mathbf{U}}{min}\ \underset{\mathbf{\boldsymbol\Gamma }}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}(\mathbf{I}-\boldsymbol\Gamma) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ \end{align*} $$ 跟 \(\boldsymbol\Gamma\) 有關的，只有 \((\mathbf{I}-\boldsymbol\Gamma)\)，然後該如何最小化呢？
因 \(\mathbf{U}\) 是單位向量的集合，所以前面的 \(\mathbf{U}\) 不影響最後結果的距離
所以可以簡化來看
$$ \underset{\mathbf{\boldsymbol\Gamma }}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|(\mathbf{I}-\boldsymbol\Gamma) (some\ vector) \right \|^2\\ $$ 可以發現，當 \((\mathbf{I}-\boldsymbol\Gamma)\) 相減時，越多 0 超好
但因為 \(\boldsymbol\Gamma\) 是對角線矩陣，且 rank \(\le \widetilde{d}\)
所以可得
$$ \boldsymbol\Gamma= \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} $$ 重新寫下 \(E_{in}\)
$$ \begin{align*} \underset{\mathbf{W}}{min}\ E_{in}&=\underset{\mathbf{U}}{min}\ \underset{\boldsymbol\Gamma}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}(\mathbf{I}-\boldsymbol\Gamma) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\underset{\mathbf{U}}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U}\left (\mathbf{I}_{d\times d}- \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \right ) \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\underset{\mathbf{U}}{min}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U} \begin{bmatrix} \mathbf{0}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{I}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2\\ &=\underset{\mathbf{U}}{max}\ \frac{1}{N}\sum_{n=1}^{N}\left \|\mathbf{U} \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2\\ \\ &subject\ to\ \mathbf{u}_n^T\mathbf{u}_n=1 \end{align*} $$ 利用 Lagrange 乘數法，且同之前，前面的 \(\mathbf{U}\) 不影響最後結果的距離
$$ \begin{align*} L(\mathbf{U},\lambda_1,\lambda_2,\cdots,\lambda_d)&= \frac{1}{N}\sum_{n=1}^{N}\left \| \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2 +\lambda_1 (1-\mathbf{u}_1^T\mathbf{u}_1)+\lambda_2 (1-\mathbf{u}_2^T\mathbf{u}_2=1)+\cdots+\lambda_d (1-\mathbf{u}_d^T\mathbf{u}_d)\\ \\ \frac{\partial L(\mathbf{U},\lambda_1,\lambda_2,\cdots,\lambda_d)}{\partial \mathbf{u}_n} &= 0 \\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\sum_{n=1}^{N}\left \| \begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})}\\ \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} & \mathbf{0}_{(d-\widetilde{d})\times (d-\widetilde{d})} \end{bmatrix}_{d\times d} \mathbf{U}^T\mathbf{x}_n \right \|^2 +\lambda_1 (1-\mathbf{u}_1^T\mathbf{u}_1)+\lambda_2 (1-\mathbf{u}_2^T\mathbf{u}_2=1)+\cdots+\lambda_d (1-\mathbf{u}_d^T\mathbf{u}_d) \right )\\ [\because only\ consider\ \mathbf{u}_m]&= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\sum_{n=1}^{N}\left \| \mathbf{u}_m^T\mathbf{x}_n \right \|^2 +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\sum_{n=1}^{N} \mathbf{u}_m^T\mathbf{x}_n \mathbf{x}_n^T\mathbf{u}_m +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\mathbf{u}_m^T\left (\sum_{n=1}^{N} \mathbf{x}_n \mathbf{x}_n^T \right )\mathbf{u}_m +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &= \frac{\partial }{\partial \mathbf{u}_m} \left (\frac{1}{N}\mathbf{u}_m^T \mathbf{XX}^T\mathbf{u}_m +\lambda_m (1-\mathbf{u}_m^T\mathbf{u}_m) \right )\\ &=\frac{1}{N}\cdot 2\mathbf{XX}^T\mathbf{u}_m-2 \lambda_m\mathbf{u}_m\\ &=0\\ \end{align*} $$
$$ \begin{align*} \frac{1}{N}\cdot 2\mathbf{XX}^T\mathbf{u}_m&=2 \lambda_m\mathbf{u}_m\\ \frac{1}{N}\cdot \mathbf{XX}^T\mathbf{u}_m&=\lambda_m\mathbf{u}_m\\ \end{align*} $$ 故 \(\mathbf{u}_m\) 是 \(\mathbf{XX}^T\) 的 eigenvector
基於最大化要挑選前 \(\widetilde{d}\) 大的 \(\lambda_m\)，也就是 top eigenvectors
因 \(\mathbf{W}_{d \times \widetilde{d}}=\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T\)
\(\mathbf{V}\) 任意，過程中可發現並不影響最佳值，故選擇 \(\mathbf{I}\)
\(\boldsymbol\Sigma_{d\times \widetilde{d}}(\boldsymbol\Sigma_{d\times \widetilde{d}}) ^T =\Gamma _{d\times d}\) 實際 \(1^2=1\)
所以 \(\boldsymbol\Sigma\) 也只是看 \(\Gamma\) 有幾個 1 就有多少個 1
故得 \(\mathbf{W}\)
$$ \begin{align*} \mathbf{W}_{d \times \widetilde{d}}&=\mathbf{U}_{d\times d}\boldsymbol\Sigma_{d\times \widetilde{d}} (\mathbf{V}_{\widetilde{d}\times \widetilde{d}})^T\\ &=\begin{bmatrix} eigenV^{(1)}_{\mathbf{XX}^T} & \cdots & eigenV^{(\widetilde{d})}_{\mathbf{XX}^T} & \mathbf{0}_{1\times (d-\widetilde{d})} \end{bmatrix}_{d\times d}\begin{bmatrix} \mathbf{I}_{\widetilde{d}\times \widetilde{d}}\\ \mathbf{0}_{(d-\widetilde{d})\times \widetilde{d}} \end{bmatrix}_{d\times \widetilde{d}} (\mathbf{I}_{\widetilde{d}\times \widetilde{d}})^T\\ &=\begin{bmatrix} eigenV^{(1)}_{\mathbf{XX}^T} & \cdots & eigenV^{(\widetilde{d})}_{\mathbf{XX}^T} \end{bmatrix}_{d\times \widetilde{d}} \end{align*}\\ $$ 事實上，這與 PCA 很類似
PCA 求的是最大化 \(\Sigma (variance\ after\ projection)\)
而 linear autoencoder 求的是最大化 \(\Sigma (maginitude\ after\ projection)^2\)
所以若將輸入資料先扣掉平均 \(\mathbf{x}_n \leftarrow \mathbf{x}_n-\overline{\mathbf{x}}\)
丟進 linear autoencoder 不就是 PCA 了
即然如此，干脆就回傳特徵轉換 \(\Phi (\mathbf{x})=\mathbf{W}(\mathbf{x}-\color{Red}{\overline{\mathbf{x}}})\)
記得 linear autoencoder 為了跟 PCA 一致，有做了一些處理，像是移掉常數項之類的
所以兩者還是有點差異
而實務上 PCA 比較好一點，因有統計上的背景
程式碼
PCA Demo
1import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from sklearn import datasets
from sklearn.decomposition import PCA
# import some data to play with
iris = datasets.load_iris()
X = iris.data[:, :2] # we only take the first two features.
y = iris.target
x_min, x_max = X[:, 0].min() - .5, X[:, 0].max() + .5
y_min, y_max = X[:, 1].min() - .5, X[:, 1].max() + .5
plt.figure(2, figsize=(8, 6))
plt.clf()
# 畫出原始資料
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Set1, edgecolor='k')
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
plt.xticks(())
plt.yticks(())
fig = plt.figure(1, figsize=(8, 6))
# 設定 3D 圖
# elev 為看向 z plane 的仰角，此為 45度
# azim 為 xy 平面轉的角度，此為 80度
ax = Axes3D(fig, elev=45, azim=80)
# 訓練並回傳 reduction 後的結果
X_reduced = PCA(n_components=3).fit_transform(iris.data)
ax.scatter(X_reduced[:, 0], X_reduced[:, 1], X_reduced[:, 2], c=y,
cmap=plt.cm.Set1, edgecolor='k', s=40)
ax.set_title("First three PCA directions")
ax.set_xlabel("1st eigenvector")
ax.w_xaxis.set_ticklabels([])
ax.set_ylabel("2nd eigenvector")
ax.w_yaxis.set_ticklabels([])
ax.set_zlabel("3rd eigenvector")
ax.w_zaxis.set_ticklabels([])
plt.show()1
參考
PCA and linear autoencoders: a better proofNeural networks [6.4] : Autoencoder - linear autoencoder
主成分分析與低秩矩陣近似
Singular value decomposition
sklearn.decomposition.PCA
留言
張貼留言