稀疏字典學習

稀疏字典學習是一種表徵學習方法，其目的在於找出一組基本元素讓輸入訊號映射到這組基本元素時具有稀疏表達式。我們稱這些基本元素為「原子」，這些原子的組合則為「字典」。字典裡的「原子」並不需要滿足正交基這一特性，且往往它們會是過完備的生成集合。過多的原子除了可以讓我們在敘述一個訊號的時候可以由很多種表達式，同時也提升了整個表達式的稀疏性，讓我們可以以較簡單的表達式來詮釋訊號。

稀疏字典學習最主要應用在壓縮感知及訊號還原上。在壓縮感知上，當你的訊號具有稀疏或者接近稀疏特質時，那麼只需要對訊號進行幾次的隨機取樣就可以把高維度的訊號描述出來。但在現實世界中，並不是全部訊號都具有稀疏這一特性，所以我們需要把找出這些訊號的稀疏表達式，轉換方式有很多種，根據不同的訊號有不同的轉換方式。當高維度的訊號轉換至稀疏訊號時，那麼就可以透過少次數的線性取樣，並利用一些還原演算法如：基追蹤（Basis Pursuit)、CoSaMP、正交匹配追蹤(Orthogonal Matching Pursuit)等方法來對訊號進行還原。

在這整個過程中，關鍵在於如何找到一個轉換方式把訊號轉換到具有稀疏表達式的域內，也就是如何建立一個字典，讓訊號投影在這個字典上時具有稀疏表達式。而稀疏字典學習就是利用學習的方式幫我們找出這個轉換方法，即稀疏字典。稀疏字典學習的興起是基於在訊號處理中，如何使用較少的元素來敘述一個訊號。在這之前，普遍上大家還是使用傅立葉轉換（Fourier Transform）及小波轉換（Wavelet Transform)。不過在某一些情境下，使用透過字典學習得到的字典來進行轉換，能有效的提高訊號的稀疏性。高稀疏性意味著訊號的可壓縮性越高，因此稀疏字典學習也被應用在資料分解、壓縮和分析。

問題定義

假設輸入訊號集合$X=[x_{1},...,x_{K}],x_{i}\in \mathbb {R} ^{d}$，

我們希望找到一個字典$\mathbf {D} \in \mathbb {R} ^{d\times n}:D=[d_{1},...,d_{n}]$和一個表達式$R=[r_{1},...,r_{K}],r_{i}\in \mathbb {R} ^{n}$，讓$\|X-\mathbf {D} R\|_{F}^{2}$最小化，且其表達式 $r_{i}$足夠稀鬆。

這個問題可以被視為是下面這個最佳化問題：

${\underset {\mathbf {D} \in {\mathcal {C}},r_{i}\in \mathbb {R} ^{n}}{\text{argmin}}}\sum _{i=1}^{K}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{0}$，而

${\mathcal {C}}\equiv \{\mathbb {D} \in \mathbb {R} ^{d\times n}:\|d_{i}\|_{2}\leq 1\,\,\forall i=1,...,n\}$，$\lambda >0$

這裡需要 ${\mathcal {C}}$來限制 $\mathbf {D}$的原子不會因 $r_{i}$的值非常小而變得無窮大。$\lambda$這裡則是控制稀鬆性，$\lambda$越大，稀鬆性越大，$\lambda$越小，稀鬆性越小，但稀鬆性越大代表還原的誤差也會越大，$\lambda$的取值常常伴隨著稀鬆性與還原誤差之間的取捨。

字典的性質

當n<d，上述定義的稀鬆字典$\mathbf {D}$被稱為低完備（Undercomplete）；當n>d，稀鬆字典$\mathbf {D}$則被稱為過完備（Overcomplete）。

低完備字典會讓輸入訊號投影到低維度空間，類似於降維(Dimension reduction)、主要成分分析。在投影到低完備的字典時，如何選擇重要的子空間（Subspace）是非常重要的，選擇對的子空間能夠讓訊號最大程度的被保留下來。使用低完備字典進行降維這個方法可以應用在資料分析或分類上。

過完備的字典由於由較多的「原子」組成，因此一般上擁有較豐富的表達式。此外，過完備的特性能讓訊號投影在到過完備字典時擁有稀鬆的特性。而透過學習得到的字典，即透過稀鬆字典學習而來的字典能讓訊號在投影過來之後擁有更加稀鬆的表達式。

演算法

在問題定義有提到，在找尋一個可以讓訊號投影至該空間並具有稀鬆特質的字典其實就是一種最佳化問題。這最佳化問題與稀鬆編碼以及字典相關，目前大部分演算法都是迭代式的相繼更新字典以及其表達式。

最佳方向法 Method of optimal directions (MOD)

最佳方向法是其中一個最早被提出用來解決稀鬆字典學習的方法。最佳方向法的核心理念是下面的最小化問題，在下面的最小化問題中，它的表達式只有固定數量的非零數值。

$\min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T$

在這裡，$F$為弗羅貝尼烏斯範數（Frobenius norm）。在整個演算法過程中，MOD使用匹配追縱（Matching Pursuit)來取得訊號的稀鬆編碼，隨即計算$\mathbf {D} =XR^{+}$的解析解（Analytic solution），這裡的$R^{+}$指的是摩爾－彭若斯廣義逆（Moore-Penrose pseudoinverse)。隨後這個更新後的$\mathbf {D}$會在再標準化（Renormalized）以達到我們的約束條件。這時，新的稀鬆編碼也會同時計算得到。這個過程會一直重複直到稀鬆字典$\mathbf {D}$以及稀鬆編碼$R$收斂為止。

K-SVD

K-SVD 主要是以奇異值分解為核心來更新稀鬆字典的「原子」。它會讓輸入訊號$x_{i}$以不超過$T_{0}$的元素以線性組合的方式表示，整個過程與MOD類似：

$\min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T_{0}$

整個演算法的過程在，一、先固定字典，找出滿足上述條件相對應的$R$（可以使用匹配追蹤)。然後固定$R$，利用下面的式子迭代式的更新字典。

$\|X-\mathbf {D} R\|_{F}^{2}=\left|X-\sum _{i=1}^{K}d_{i}x_{T}^{i}\right|_{F}^{2}=\|E_{k}-d_{k}x_{T}^{k}\|_{F}^{2}$

相關應用

整個字典學習的架構，其實就是對我們的輸入訊號進行線性分解，分解到字典里的少數「原子」，並具有稀鬆特性。而這些「原子」是由本身的訊號產生，或學習得出來的。稀鬆字典學習可以應用在影像或者是影片處理。這個技術也常常被應用在分類問題上，我們可以針對不同的分類來對字典進行設計，透過輸入訊號映射到字典的稀鬆表達式，我們可以較容易的把該訊號進行有效的分類。

此外，字典學習還有一個性質，那就是在雜訊去除上非常有效。這時因為字典在學習時會找出輸入訊號相似的特性，這時候具有意義的訊號會被學習到字典，而不具意義的訊號則會被排除在字典之外。那麼，當輸入訊號映射到字典時，由於字典不含有雜訊的「原子」，所以該訊號在還原回來時不會有雜訊。