Deep Learning論文筆記之（一）K-means特征學習

Deep Learning（17） 

計算機視覺（72） 

機器學習（45） 

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

Deep Learning論文筆記之（一）K-means特征學習

zouxy09@QQ.com

http://blog.csdn.net/zouxy09

         自己平時看了一些論文，但老感覺看完過后就會慢慢的淡忘，某一天重新拾起來的時候又好像沒有看過一樣。所以想習慣地把一些感覺有用的論文中的知識點總結整理一下，一方面在整理過程中，自己的理解也會更深，另一方面也方便未來自己的勘察。更好的還可以放到博客上面與大家交流。因為基礎有限，所以對論文的一些理解可能不太正確，還望大家不吝指正交流，謝謝。

        本文的論文來自：

Learning Feature RePResentations with K-means, Adam Coates and Andrew Y. Ng. In Neural Networks: Tricks of the Trade, Reloaded, Springer LNCS, 2012

         下面是自己對其中的一些知識點的理解：

《Learning Feature Representations with K-means》

         自從Deep Learning之風盛起之時到現在，江湖上誕生了很多都可以從無標簽數據中學習到深度的分級的特征的算法。大部分情況，這些算法都涉及到一個多層網絡，而訓練和調整這個網絡需要很多tricks。最近，我們發現K-means聚類算法也可以被作為一個非常快的訓練方法。它的優點是快！容易實現！當然了，K-means也不是萬能神丹，它也存在自身的局限性。在本文中，我們就關注K-means的方方面面。總結了最近的K-means算法的效果和介紹使用k-means來有效地學習圖像的特征的一些技巧。

一、概述

         非監督學習的一般流程是：先從一組無標簽數據中學習特征，然后用學習到的特征提取函數去提取有標簽數據特征，然后再進行分類器的訓練和分類。之前說到，一般的非監督學習算法都存在很多hyper-parameters需要調整。而，最近我們發現對于上面同樣的非監督學習流程中，用K-means聚類算法來實現特征學習，也可以達到非常好的效果，有時候還能達到state-of-the-art的效果。亮瞎了凡人之俗眼。

         托“bag of features ”的福，K-means其實在特征學習領域也已經略有名氣。今天我們就不要花時間迷失在其往日的光芒中了。在這里，我們只關注，如果要K-means算法在一個特征學習系統中發揮良好的性能需要考慮哪些因素。這里的特征學習系統和其他的Deep Learning算法一樣：直接從原始的輸入（像素灰度值）中學習并構建多層的分級的特征。另外，我們還分析了K-means算法與江湖中其他知名的特征學習算法的千絲萬縷的聯系（天下武功出少林，哈哈）。

         經典的K-means聚類算法通過最小化數據點和最近鄰中心的距離來尋找各個類中心。江湖中還有個別名，叫“矢量量化vector quantization”（這個在我的博客上也有提到）。我們可以把K-means當成是在構建一個字典D?R^nxk，通過最小化重構誤差，一個數據樣本x⁽ⁱ⁾ ?Rⁿ可以通過這個字典映射為一個k維的碼矢量。所以K-means實際上就是尋找D的一個過程：

       這里，s⁽ⁱ⁾就是一個與輸入x⁽ⁱ⁾對應的碼矢量。D^(j)是字典D的第j列。K-means畢生的目標就是尋找滿足上面這些條件的一個字典D和每個樣本x⁽ⁱ⁾對應的碼矢量s⁽ⁱ⁾。我們一起來分析下這些條件。首先，給定字典D和碼矢量s⁽ⁱ⁾，我們需要能很好的重構原始的輸入x⁽ⁱ⁾。數學的表達是最小化x⁽ⁱ⁾和它的重構D s⁽ⁱ⁾。這個目標函數的優化需要滿足兩個約束。首先，|| s⁽ⁱ⁾||₀<=1，意味著每個碼矢量s⁽ⁱ⁾被約束為最多只有一個非零元素。所以我們尋找一個x⁽ⁱ⁾對應的新的表達，這個新的表達不僅需要更好的保留x⁽ⁱ⁾的信息，還需要盡可能的簡單。第二個約束要求字典的每列都是單位長度，防止字典中的元素或者特征變得任意大或者任意小。否則，我們就可以隨意的放縮D^(j)和對應的碼矢量，這樣一點用都木有。

         這個算法從精神層面與其他學習有效編碼的算法很相似，例如sparse coding：

         Sparse coding也是優化同樣類型的重構。但對于編碼復雜度的約束是通過在代價函數中增加一個懲罰項λ|| s⁽ⁱ⁾||₁，以限制s⁽ⁱ⁾是稀疏的。這個約束和K-means的差不多，但它允許多于一個非零值。在保證s⁽ⁱ⁾簡單的基礎上，可以更準確的描述x⁽ⁱ⁾。

         雖然Sparse coding比K-means性能要好，但是Sparse coding需要對每個s⁽ⁱ⁾重復的求解一個凸優化問題，當拓展到大規模數據的時候，這個優化問題是非常昂貴的。但對于K-means來說，對s⁽ⁱ⁾的優化求解就簡單很多了：

         這個求解是很快的，而且給定s求解D也很容易，所以我們可以通過交互的優化D和s（可以了解下我博客上的EM算法的博文）來快速的訓練一個非常大的字典。另外，K-means還有一個讓人青睞的地方是，它只有一個參數需要調整，也就是要聚類的中心的個數k。

二、數據、預處理和初始化

         這里我們采用的是包含很多小的圖像patches的數據集，每個patch是16x16的灰度圖，對每個patch樣本我們將其拉成一個256維的列向量。這些patches可以在無標簽圖像中隨機的裁剪得到。為了建立一個“完備complete”的字典（至少有256個類中心的字典），我們需要保證有足夠的用以訓練的patches，這樣每個聚類才會包含一定合理數量的輸入樣本。對于16x16的灰度patch來說，樣本數m=100,000個是足夠的。實際上，訓練一個k-means字典比其他的算法（例如sparse coding）需要的訓練樣本個數要多，因為在k-means中，一個樣本數據只會貢獻于一個聚類的中心，換句話說一個樣本只能屬于一個類，與其他類就毫無瓜葛了，該樣本的信息全部傾注給了它的歸宿（對應類的中心）。

2.1、預處理 Pre-processing

         在訓練之前，我們需要對所有的訓練樣本patches先進行亮度和對比度的歸一化。具體做法是，對每個樣本，我們減去灰度的均值和除以標準差。另外，在除以標準差的時候，為了避免分母為0和壓制噪聲，我們給標準差增加一個小的常數。對于[0, 255]范圍的灰度圖，給方差加10一般是ok的：

         對訓練數據進行歸一化后，我們就可以在上面運行k-means算法以獲得相應的聚類中心了（字典D的每一列），可視化在圖a中，可以看到，k-means趨向于學習到低頻的類邊緣的聚類中心。但不幸的是，這樣的特征不會有比較好的識別效果，因為鄰域像素的相關性（圖像的低頻變化）會很強。這樣K-means就會產生很多高度相關的聚類中心。而不是分散開聚類中心以更均勻的展開訓練數據。所以我們需要先用白化來去除數據的相關性，以驅使K-means在正交方向上分配更多的聚類中心。

       圖a是由k-means從沒有經過白化處理的自然圖像中學習到的聚類中心。圖b展示了沒有和有白化的效果。左邊是沒有經過白化的，因為數據存在相關性，所以聚類中心會跑偏。右邊是經過白化后的，可以看到聚類中心是更加正交的，這樣學習到的特征才會不一樣。圖c展示的是從經過白化后的圖像patches學習到的聚類中心。

         實現whitening白化一個比較簡單的方法是ZCA白化（可以參考UFLDL）。我們先對數據點x的協方差矩陣進行特征值分解cov(x)=VDV^T。然后白化后的點可以表示為：

        ?_zca是一個很小的常數。對于對比度歸一化后的數據，對16x16的patch，可以設?_zca=0.01，對8x8的patch，可以設?_zca=0.1 。需要注意的一點是，這個常數不能太小，如果太小會加強數據的高頻噪聲，會使特征學習更加困難。另外，因為數據的旋轉對K-means沒有影響，所以可以使用其他的白化變換方法，例如PCA白化（與ZCA不同只在于其旋轉了一個角度）。

         在白化后的數據中運行k-means可以得到清晰的邊緣特征。這些特征和sparse coding啊，ICA啊等等方法學到的初級特征差不多。如圖c所示。另外，對于新的數據，可能需要調整歸一化的參數?和白化的參數?_zca，以滿足好的效果（例如，圖像patches具有高對比度，低噪聲和少低頻波動）。

2.2、初始化 Initialization

         一般的K-means聚類算法存在一個比較常見的問題，就是會出現空的聚類。通俗的講，就是它聚類后的一個類里面居然沒有樣本（接近于沒有）。那么很明顯，這個類就一點意義都沒有，留著反而還會危害人間。這我們當然得做些努力來避免這種情況的發生了。那就得找原因了吧。其實這一定情況下可以認為是中心的初始化的不恰當導致的。常用的中心初始化方法就是隨機地從樣本中挑k個出來作為k個初始的聚類中心。但這不是個明智的選擇。它有可能會導致圖像趨于稠密聚集某些區域，因為如果隨機選擇的patches，也就是訓練樣本本身就在某個區域分布非常密，那么我們隨機去選擇聚類中心的時候，就會出現就在這個數據分布密集的地方被選出了很多的聚類中心（因為原數據分布密集，所以被選中的概率會大）。這是不好的，因為本身這個密集的區域，一個聚類中心才是好的，你硬搞出幾個聚類中心，好好的隊伍就會被強拆了，還搞得其他比較分散的數據點找不到歸宿，因為聚類中心離它好遙遠，大部分的聚類中心都讓富二代給占有了，社會資源分配不當啊，哈哈。這樣還會出現一種情況，就是如果樣本分布密集的話，它們都幾乎從屬于一個聚類中心，那么其他聚類中心就幾乎沒有樣本屬于它。這樣也不好。所以，一個比較好的初始化方式就是從一個正態分布中隨機初始化聚類中心，然后歸一化他們到單位長度。另外，因為經過了白化的階段，我們期望我們的數據的主要成分已經在一定程度上被組織為球面spherical分布了，而在一個球面上隨機地選取一些向量結果就顯得溫柔多了。

         另外，還存在一些啟發性的方法去改善k-means的這個問題。例如啟發性得重新初始化空的聚類中心。實踐中證明，這種方法對圖像數據的效果比較好。當空類出現的時候，我們再隨機挑選樣本來替代這個空類中心，一般都是足夠有效的。但好像一般也沒啥必要。事實上，對于一個足夠規模的實現來說，我們會訓練很多的聚類中心，如果一個聚類中心包含的數據點太少了，我們直接拋棄它就好了，不要這個聚類中心了，因為俺們的聚類中心夠多，多你一個不多，少你一個不少的。

         還有一種改善的方法叫做聚類中心的抑制更新damped updates。它在每次的迭代中，都會根據以下方式更新聚類中心：

         需要注意的是，這種形式的抑制并不會對“大”的聚類有很大的影響（因為XS^T的第j列會比D_old的第j列要大得多），它只能防止小的聚類在一次的迭代過程中被拉得太遠（就像濾波的方法一樣，新的值不僅受當前值的影響，還受歷史值的影響，這樣就會防止這個值出現突變。例如a_old=1，新的值為5，那么a_new=0.5*5+0.5*a_old=3，也就是a_new會跳到3而不是一下子跳到5，當然還取決于前面的權值0.5，看我們更信任新值還是歷史值。但如果新值很大，那就沒有特別大的效果了。例如新值為99，那么a_new=50，它還是比a_old=1要大多了）。我們將這個k-means訓練算法概括如下：

三、與稀疏特征學習的比較

         上面我們提到，K-means能像ICA，sparse coding一樣學習到方向性的邊緣特征。那我們會懷疑，這是偶然嗎（因為邊緣太常見了，所以一般的學習模型都可以發現它們）？！還是說這隱含著K-means本身就具有和ICA相似的稀疏分解的能力。因為每個s⁽ⁱ⁾只能包含一個非零元素（相應的聚類中心），所以k-means會嘗試去學習一個可以很好的描述整個輸入圖像的聚類中心。因此，它也無法保證一定可以學到和ICA或者sparse coding學到的濾波器一樣。這些算法可以學習到真正的“分布式”描述，因為一張圖像可以通過一個字典的幾列來聯合描述，而不是只通過一列。盡管如此，k-means在天時地利人和的時候依然能發現數據的稀疏投影，雖然作為一個聚類方法它好像沒有明確的通過公式告訴我們它還能做這個。所以我們看到的結果也不是幻覺或者偶然。

         雖然k-means和ICA和sparse coding有著經驗性的相似，但它有一個很大的缺點：它發現數據稀疏投影方向的能力很大程度上取決于輸入數據的維數和數量。如果數據的維數增加，我們就需要增加大量的樣本，才能得到好的結果。這點就比較難伺候了。例如，在實驗中，對64x64的patch，我們用了500,000個樣本來訓練k-means，結果還是很爛。我們只學習到了很少的邊緣。在這種情況下，就會存在很多的接近空數據點的聚類，所以就需要非常多的數據才能讓k-means發揮光與熱。所以，這就存在一個折衷了，是否要采用k-means，就要看我們的數據有多少維，我們能提供多少數據（一般要達到相同的結果，比sparse coding要多很多）。對于適當的維度（例如100維），使用k-means的訓練速度比其他算法快那么多，那么我情愿花點力氣去提供更多的樣本給它。但對于很高維的數據，采用其他算法例如sparse coding會比k-means性能要好，甚至速度也要更快。

4、在圖像識別上的應用

         在這里沒什么好說的，k-means就作為一種學習特征的方法，取代一般的非監督學習過程里面的特征學習那塊就好了。可以參考UFLDL中的“卷積特征提取”和“池化”。另外，文中也介紹了一些選擇參數的方法，很多論文也可以看到，這里也不說了。這里比較有趣的一點是，文中說到，根據觀測的結果，如果我們的識別系統設計有大量有效的有標簽訓練數據的話，那么選擇一個簡單的快速的前向編碼器（特征映射函數）的話，效果都可以挺好。但如果我們的有標簽訓練數據不多，那么采用一個復雜的編碼函數會更好。例如，在大規模情況下，采用軟閾值非線性函數:

就可以工作的比較好。其中，ɑ是個可調的常數。相反，復雜的sigmoid非線性函數效果就沒那么好了：

5、構建深度網絡

         在上面一個章節中，我們是先從一些無標簽數據中隨機提取一些patches，然后用k-means來學習其中的特征，得到一個字典。然后對于一個大的圖像，我們用這個字典（特征提取器）去卷積圖像的每個局部感受野，從而提取整幅圖像的特征。然后我們再通過一個pooling步驟去對提取到的特征進行絳維。當然了，如果我們可以通過上面這些提取到的特征去學習更高層的特征，那就更好了。最簡單的方法就是，對無標簽數據集X中，我們通過上面的方法得到pooling后的特征后，然后得到新的數據集Z，我們再在這個數據庫Z中用同樣的特征學習過程去學習新的特征。從而得到第二層的特征。但這有個問題，就是這個Z一般都是非常高維的，所以需要用非常大的特征字典來學習（例如k=10000甚至更多）。但這樣，對k-means的要求也高了，我們需要提供更多的樣本來訓練。

         該文提出了一種pair-wise “dependency test"的方法來改善這個問題。我們通過一個“能量相關”來定義數據集Z中兩個特征z_j和z_k的依賴性。我們需要在Z的特征表達之上學習更高級的特征。使用“dependency test"，我們可以以一種相對簡單的方式來選擇合理的感受野：我們挑了一個特征z₀，然后使用“dependency test"來尋找和z₀具有很強依賴性的R特征。然后只用這R特征作為k-means算法的輸入。如果我們選取的R足夠小（例如100或者200），那么歸一化和白化過后，再用k-means來訓練一般都可以達到好的效果。因為輸入的維數很小，所以我們只需要訓練一百個左右的聚類中心，這樣使用少量的訓練樣本就可以運行k-means了。

         詳細的算法介紹和效果見原論文。

六、總結

         本文中，我們討論了用k-means來搭建特征學習系統的一些關鍵點，現在總結如下：

1、需要先對數據進行均值和對比度的歸一化。

2、使用白化來消去數據的相關性。注意白化參數的選擇。

3、通過高斯噪聲和歸一化來初始化k-means的聚類中心。

4、使用抑制更新來避免空聚類和增加穩定性。

5、注意數據的維數和稀疏的影響。K-means通過尋找數據分布的”heavy-tailed"方向來找到輸入數據的稀疏投影。但如果數據沒有經過適當的白化，或者數據維數太高了，或者存在無效的數據，那么效果往往是不好的。

6、對于高維數據，k-means需要增加大量的樣本來能得到好的效果。

7、一些外在的參數（例如pooling，編碼方法的選擇等等）對于系統性能的影響比學習算法本身要大。所以最好先化時間和成本在通過更多的交叉檢驗的方法來挑選好的參數比花更多的成本在學習算法上要明智的多。

8、對于圖像識別來說，更多的聚類中心往往是有幫助的。當然，前提是我們要有足夠的訓練樣本。

9、當有標簽數據多的時候，采用一個簡單的編碼器。如果標簽數據有限（例如每類只有百來個訓練樣本），那么采用一個復雜的編碼器會更好。

10、盡可能地使用局部感受野。K-means是否成功，其瓶頸在于輸入數據的維數。越低越好。如果無法手動的選擇好的局部感受野，那么嘗試去通過一個自動的依賴性測試dependency test來幫助從數據中挑選出一組低維的數據。這對于深度網絡來說是很有必要的。