查看“︁稀疏字典學習”︁的源代码

{{refimprove|time=2018-12-15T02:19:38+00:00}}
{{Machine learning bar}}
'''稀疏[[字典]][[学习]]'''是一种[[表征学习]]方法，其目的在於找出一組[[基本元素]]讓輸入-{zh-cn:信号;zh-tw:訊號}-[[映射]]到這組基本元素時具有[[稀疏矩阵|稀疏]]表达式。我們稱這些基本元素為“[[原子]]”，這些原子的組合則為“[[字典]]”。字典裡的“原子”並不需要滿足[[正交基]]這一特性，且往往它們會是過完備的[[生成集合]]。過多的原子除了可以讓我們在敘述一個[[信号 (信息论)|訊號]]的時候可以由很多種[[表達式]]，同時也提升了整個表達式的[[稀疏矩阵|稀疏]]性，讓我們可以以較簡單的[[表達式]]來詮釋[[訊號]]。

稀疏字典學習最主要應用在[[壓縮感知]]及[[信号检测理论|訊號還原]]上。在壓縮感知上，當你的[[訊號]]具有稀疏或者接近稀疏特質時，那麼只需要對訊號進行幾次的[[随机抽样|隨機取樣]]就可以把高維度的訊號描述出來。但在現實世界中，並不是全部訊號都具有稀疏這一特性，所以我們需要把找出這些訊號的稀疏表達式，轉換方式有很多種，根據不同的訊號有不同的轉換方式。當高維度的訊號轉換至稀疏訊號时，那麼就可以透過少次數的線性取樣，並利用一些還原[[演算法]]如：基追踪（Basis Pursuit)、CoSaMP<ref>{{Cite journal|title=CoSaMP: Iterative signal recovery from incomplete and inaccurate samples|url=https://linkinghub.elsevier.com/retrieve/pii/S1063520308000638|last=Needell|first=D.|last2=Tropp|first2=J.A.|date=2009-05|journal=Applied and Computational Harmonic Analysis|issue=3|doi=10.1016/j.acha.2008.07.002|volume=26|pages=301–321|issn=1063-5203|access-date=2018-11-18|archive-date=2018-10-24|archive-url=https://web.archive.org/web/20181024232137/https://linkinghub.elsevier.com/retrieve/pii/S1063520308000638|dead-url=no}}</ref>、[[匹配追蹤|正交匹配追踪]](Orthogonal Matching Pursuit)等方法來對訊號進行還原。

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

== 问题定义 ==
假設輸入訊號[[集合 (数学)|集合]]<math>X = [x_1, ..., x_K], x_i \in \mathbb{R}^d</math>，

我們希望找到一個字典<math>\mathbf{D} \in \mathbb{R}^{d \times n}: D = [d_1, ..., d_n]</math>和一個表達式<math>R = [r_1,...,r_K], r_i \in \mathbb{R}^n</math>，讓<math>\|X-\mathbf{D}R\|^2_F</math>最小化，且其表達式 <math>r_i</math>足夠稀鬆。

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

<math>\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</math><ref>{{Cite web |title=稀疏表示以及字典學習 - 程式人生 |url=https://www.796t.com/content/1548021623.html |website=www.796t.com |language=zh-tw |access-date=2022-09-26 |archive-date=2022-09-29 |archive-url=https://web.archive.org/web/20220929024114/https://www.796t.com/content/1548021623.html |dead-url=no }}</ref>，而

<math>\mathcal{C} \equiv \{\mathbb{D} \in \mathbb{R}^{d \times n}: \|d_i\|_2 \leq 1 \,\, \forall i =1,...,n \}</math>，<math>\lambda>0</math>

這裡需要 <math>\mathcal{C}</math>來限制 <math>\mathbf{D}</math>的原子不會因 <math>r_i </math>的值非常小而變得[[无穷大|無窮大]]。<math>\lambda</math>這裡則是控制稀鬆性，<math>\lambda</math>越大，稀鬆性越大，<math>\lambda</math>越小，稀鬆性越小，但稀鬆性越大代表還原的誤差也會越大，<math>\lambda</math>的取值常常伴隨著稀鬆性與還原[[误差|誤差]]之間的取捨。

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

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

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

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

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

<math>\min_{\mathbf{D}, R}\{\|X-\mathbf{D}R\|^2_F\} \,\, \text{s.t.}\,\, \forall i \,\,\|r_i\|_0 \leq T </math>

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

==== K-SVD ====


{{tsl|en|K-SVD|K-SVD}} 主要是以[[奇异值分解|奇異值分解]]為核心來更新稀鬆字典的“原子”。它會讓輸入訊號<math>x_i</math>以不超過<math>T_0 </math>的元素以[[线性组合|線性組合]]的方式表示，整個過程與MOD類似：

<math>\min_{\mathbf{D}, R}\{\|X-\mathbf{D}R\|^2_F\} \,\, \text{s.t.}\,\, \forall i \,\,\|r_i\|_0 \leq T_0 </math>

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

<math>
\|X - \mathbf{D}R\|^2_F =  \left| X - \sum_{i = 1}^K d_i x^i_T\right|^2_F = \| E_k - d_k x^k_T\|^2_F
</math>

== 相关应用 ==
整个字典学习的[[架构]]，其实就是对我们的输入讯号进行线性分解，分解到字典里的少数“原子”，并具有稀松特性。而这些“原子”是由本身的讯号产生，或学习得出来的。稀松字典学习可以应用在[[影像]]或者是[[影像處理|影片处理]]。这个技术也常常被应用在[[分类问题]]上，我们可以针对不同的分类来对字典进行设计，透过输入讯号映射到字典的稀松表达式，我们可以较容易的把该讯号进行有效的分类。

此外，字典学习还有一个性质，那就是在[[杂讯 (通讯学)|杂讯]]去除上非常有效。这时因为字典在学习时会找出输入讯号相似的特性，这时候具有意义的讯号会被学习到字典，而不具意义的讯号则会被排除在字典之外。那么，当输入讯号映射到字典时，由于字典不含有[[雜訊|杂讯]]的“原子”，所以该讯号在还原回来时不会有杂讯。

== 参考资料 ==
<references />

[[Category:机器学习]]