機器學習_學習筆記系列(63)：稀疏字典學習(Sparse Dictionary Learning)
在前幾個章節我們介紹了Principal Component Analysis相關的演算法，而今天我們要來介紹一個新的演算法「Sparse Dictionary Learning」。
對於Sparse Dictionary Learning根據WIKI的定義
Sparse Dictionary Learning是一種表徵學習(Representation Learning)方法，其目的在於找出一組基本元素讓輸入訊號映射到這組基本元素時具有稀鬆(Sparse)表達式。我們稱這些基本元素為「原子」，這些原子的組合則為「字典」。
而其實Sparse Dictionary Learning和PCA的概念很相似，假設我們有一組資料集
總共有n筆資料，m個特徵。我們希望能找的一個dictionary D∈R^(m x k)，使得我們的lost function
最小化。而在這邊可以看到Sparse Dictionary Learning其實和PCA不太一樣的地方就是PCA是從m個特徵選出k個，而Dictionary Learning是從n筆資料裡面選出k個。而對於我們的lost function可以寫成
所以我們的最佳化問題為
但是我們可以看到因為我們有兩個變數D和A，對於這樣的情況，我們的對策為先fix住D然後train出A，接著再fix住A然後train出D，持續這樣的步驟到兩者收斂為止。
所以對於訓練A我們，可以對L作微分
我們就可以利用梯度下降來更新我們的演算法。
接著當我訓練好A後我們就進入訓練D的部分，但因為D有設constraint所以我們必須把我們的最佳化問題轉為Lagrange Function
這裡我們希望我們能把D代換掉，所以我們將Lagrange Function對D作微分最後我們可以得到
重新帶進去我們的Lagrange Function就可以寫成
接下來我們就可以用牛頓法求出𝜆，所以其一次和二次微分為
接著我們就可以用這些數值來更新D。
而當我們D訓練完後，我們又會回到一開始，把D先固定訓練A，接著固定A訓練D，直到兩者收斂，就可以得到我們的答案。
Example
接著我們用人臉圖片實際來看看
原圖
k=10
k=50
k=100
我們可以看到隨著我們的k值越大，臉部的特徵就會越來越清晰。
Python Sample Code:
Github:
Reference:
[1] Lee, H., Battle, A., Raina, R., & Ng, A. Y. (2007). Efficient sparse coding algorithms. In Advances in neural information processing systems (pp. 801–808).
