機器學習——字典學習/稀疏編碼學習筆記

以下資料是小編學習字典學習/稀疏編碼時，整理的高質量的網路博客，供大家參考。歡迎留言交流，批評指正理解不足。

最Highlight的地方

基於數據驅動，可以自適應的去學習基（字典），而不需要預先假設，在處理model free的任務上很有優勢；

字典D是自己預先設定的大小；字典的係數X是儘可能讓D稀疏且表達目標Y的時候自身稀疏（自己的理解）

研究歷史

字典學習（Dictionary Learning）和稀疏表示（Sparse Representation）在學術界的正式稱謂應該是稀疏字典學習（Sparse Dictionary Learning）。該演算法理論包含兩個階段：字典構建階段（Dictionary Generate）和利用字典（稀疏的）表示樣本階段（Sparse coding with a precomputed dictionary）。

參考資料：

Mallat, S.G. & Zhang, Z. 1993.Matching pursuit in a time-frequency dictionary. IEEE Transactions on Signal Processing 41(12): 3397–3415

Aharon M, Elad M, Bruckstein A. K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11):4311-4322.

問題1：我們為什麼需要字典學習？

無論人類的知識有多麼浩繁，也無論人類的科技有多麼發達，一本新華字典或牛津字典足以表達人類從古至今乃至未來的所有知識，那些知識只不過是字典中字的排列組合罷了！直到這裡，我相信相當一部分讀者或許在心中已經明白了字典學習的第一個好處（1）它實質上是對於龐大數據集的一種降維表示，或者說是信息的壓縮（2）正如同字是句子最質樸的特徵一樣，字典學習總是嘗試學習蘊藏在樣本背後最質樸的特徵（假如樣本最質樸的特徵就是樣本最好的特徵）。

這兩條原因同時也是這兩年深度學習之風日盛的情況下字典學習也開始隨之升溫的原因。

問題2：我們為什麼需要稀疏表示？

[腦功能研究的啟發]義大利羅馬大學的Fabio Babiloni教授

回答這個問題毫無疑問就是要回答「稀疏字典學習」中稀疏兩字的來歷。不妨再舉一個例子。相信大部分人都有這樣一種感覺，當我們在解涉及到新的知識點的數學題時總有一種累心（累腦）的感覺。但是當我們通過艱苦卓絕的訓練將新的知識點牢牢掌握時，再解決與這個知識點相關的問題時就不覺得很累了。這是為什麼呢？義大利羅馬大學的Fabio Babiloni教授曾經做過一項實驗，他們讓新飛行員駕駛一架飛機並採集了他們駕駛狀態下的腦電，同時又讓老飛行員駕駛飛機並也採集了他們駕駛狀態下的腦電。

結論是熟練者的大腦（右圖）可以調動儘可能少的腦區消耗儘可能少的能量進行同樣有效的計算（所以熟悉知識點的你，大腦不會再容易覺得累了），並且由於調動的腦區很少，大腦計算速度也會變快，這就是我們稱熟練者為熟練者的原理所在。站在我們所要理解的稀疏字典學習的角度上來講就是大腦學會了知識的稀疏表示。

稀疏表示的本質：用儘可能少的資源表示儘可能多的知識，這種表示還能帶來一個附加的好處，即計算速度快。

適應性（泛化能力）和稀疏性之間找平衡，最優取決於代價函數。

這裡再扯兩點：

1）特徵選擇(Feature Selection)

大家對稀疏規則化趨之若鶩的一個關鍵原因在於它能實現特徵的自動選擇。一般來說，xi的大部分元素（也就是特徵）都是和最終的輸出yi沒有關係或者不提供任何信息的，在最小化目標函數的時候考慮xi這些額外的特徵，雖然可以獲得更小的訓練誤差，但在預測新的樣本時，這些沒用的信息反而會被考慮，從而干擾了對正確yi的預測。稀疏規則化運算元的引入就是為了完成特徵自動選擇的光榮使命，它會學習地去掉這些沒有信息的特徵，也就是把這些特徵對應的權重置為0。

2）可解釋性(Interpretability)

另一個青睞於稀疏的理由是，模型更容易解釋。例如患某種病的概率是y，然後我們收集到的數據x是1000維的，也就是我們需要尋找這1000種因素到底是怎麼影響患上這種病的概率的。假設我們這個是個回歸模型：y=w1*x1+w2*x2+…+w1000*x1000+b（當然了，為了讓y限定在[0,1]的範圍，一般還得加個Logistic函數）。通過學習，如果最後學習到的w*就只有很少的非零元素，例如只有5個非零的wi，那麼我們就有理由相信，這些對應的特徵在患病分析上面提供的信息是巨大的，決策性的。也就是說，患不患這種病只和這5個因素有關，那醫生就好分析多了。但如果1000個wi都非0，醫生面對這1000種因素，累覺不愛。

參考Deep Learning（深度學習）學習筆記整理系列之（二）（四、關於特徵）

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

稀疏字典學習在計算機視覺領域的發展

1995 年前後，Bruno Olshausen和 David Field 兩位學者任職 Cornell University，他們試圖同時用生理學和計算機的手段，雙管齊下，研究視覺問題。

他們收集了很多黑白風景照片，從這些照片中，提取出400個小碎片，每個照片碎片的尺寸均為 16x16 像素，不妨把這400個碎片標記為 S[i], i = 0,.. 399。接下來，再從這些黑白風景照片中，隨機提取另一個碎片，尺寸也是 16x16 像素（思考：為什麼定為16*16呢？64*64行嗎？，相信原文有解答），不妨把這個碎片標記為 T。

我的理解：很多張圖片的壓縮才可能用到稀疏。表達最好的應該是1*1的基，最稀疏的矩陣應該是圖像本身；大小為5*5還是50*50是一種權衡，取決於具體的任務。

原文：Olshausen, Bruno A., and David J. Field. "Emergence of simple-cell receptive field properties by learning a sparse code for natural images." Nature 381.6583 (1996): 607.

他們提出的問題是，如何從這400個碎片中，選取一組碎片，S[k], 通過疊加的辦法，合成出一個新的碎片，而這個新的碎片，應當與隨機選擇的目標碎片 T，儘可能相似，同時，S[k] 的數量儘可能少。用數學的語言來描述，就是：

Sum_k (a[k] * S[k]) --> T, 其中 a[k] 是在疊加碎片 S[k] 時的權重係數。

為解決這個問題，Bruno Olshausen和 David Field 發明了一個演算法，稀疏編碼（Sparse Coding）。(此處衍生了好幾種演算法？有何異同呢？)

稀疏編碼是一個重複迭代的過程，每次迭代分兩步：

1）選擇一組 S[k]，然後調整 a[k]，使得Sum_k (a[k] * S[k]) 最接近 T。

2）固定住 a[k]，在 400 個碎片中，選擇其它更合適的碎片S』[k]，替代原先的 S[k]，使得Sum_k (a[k] * S』[k]) 最接近 T。

經過幾次迭代後，最佳的 S[k] 組合，被遴選出來了。令人驚奇的是，被選中的 S[k]，基本上都是照片上不同物體的邊緣線，這些線段形狀相似，區別在於方向。

Bruno Olshausen和 David Field 的演算法結果，與 David Hubel 和Torsten Wiesel 的生理髮現，不謀而合！

也就是說，複雜圖形，往往由一些基本結構組成。比如下圖：一個圖可以通過用64種正交的edges（可以理解成正交的基本結構）來線性表示。比如樣例的x可以用1-64個edges中的三個按照0.8,0.3,0.5的權重調和而成。而其他基本edge沒有貢獻，因此均為0。

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

K-SVD簡述--字典學習，稀疏編碼 - Rachel Zhang的專欄 - 博客頻道 - CSDN.NET

K-SVD演算法簡介

K-SVD中每個信號是用多個原子的線性組合來表示的。K-SVD通過構建字典來對數據進行稀疏表示，經常用於圖像壓縮、編碼、分類等應用。

主要問題

參考：Dictionary Learning(字典學習、稀疏表示以及其他)這篇博客從視覺生理角度給予解釋

（什麼叫完備？）完備性_百度百科

在希爾伯特空間(Hilbert space））中（或者略一般地，在線性內積空間（inner product space）中），一組標準正交基（orthonormal basis）就是一個完全而且正交的集合。

簡單說：Hilbert空間就是定義了完備的內積空間。簡單理解：不可能再多添加一個元素，基是獨立的，所以叫完備。

（為什麼要過完備？）

字典矩陣中所謂過完備性，指的是字典元素的個數遠遠大於信號y的長度(其長度很是n)，即n<<k（D矩陣的列數）。（這個表述理解怪怪的？簡單理解：基是不獨立的，不正交（為了更好的簡潔，稀疏的表示信號），過完備）

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

我們的目的是找到讓X盡量稀疏的D。

上面的式子本質上是相通的，只是表述形式不一樣罷了。

尋找最優解(X最稀疏)是NP-Hard問題。

用追蹤演算法(Pursuit Algorithm)得到的次優解代替。

MatchingPursuit (MP)

OrthogonalMatching Pursuit (OMP)

BasisPursuit (BP)

FocalUnderdetermined System Solver (FOCUSS)

參考MP演算法和OMP演算法及其思想 - 逍遙劍客的專欄 - 博客頻道 - CSDN.NET（對演算法解釋的很詳細）

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

幾點擴充思考：

*自己能定義部分字典基，再去和學習的基進行學習嗎？

*字典學習和深度神經網路的區別在於哪兒？

它僅在於線性表示，而DNN是非線性的表示。

*在線字典學習怎麼設計？

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

更多精彩內容，歡迎支持下面的Live，點開有驚喜！

（1）小白跨界入門深度學習的那些事（478名小夥伴已經參與）

知乎 Live入口（點我、點我）

（2）手把手教你申請專利的實用攻略（212名小夥伴已經參與，高中生也可以）

知乎 Live 入口（點我、點我）

（3）想了解更多人工智慧在醫療領域的應用（190名小夥伴已經參與）

知乎 Live 入口 （點我、點我）

~小編秉承分享乾貨，科普常識的理念做live掙買書學習的錢。

老司機歡迎多交流，勿鄙視，拒絕撕逼。。

喜歡點個贊再走吧！

推薦閱讀：