一起來讀《機器學習》：第十一章 特徵選擇與稀疏學習

1. 章節主要內容

1）子集搜索和評價

特徵選擇和降維計算一樣，都能有效的減輕維數災難問題，事實上，特徵選擇和降維計算是處理高維數據的兩大主流技術。但與降維將高維屬性投影嵌入到低維空間不同，特徵選擇是直接將無關的屬性去除，這會有效降低學習任務的難度，就像偵探破案一樣，將繁雜的因素抽絲剝繭，只留下關鍵信息，則真相往往更容易看清。

不過需注意的是特徵選擇過程必須確保不丟失關鍵信息，否則後續學習過程會由於丟失重要信息而無法獲得好的性能。

那麼我們如何很好的從初始的特徵集合中選取一個包含了所有重要信息的特徵子集呢？最保險的方法是遍歷所有子集可能，然後分別評估性能並選出性能最好的特徵子集，但是這在計算上不可行，會導致組合爆炸（如果窮舉法能用的話，還需要設計什麼算法呢）。所以和其它任何計算機算法思考邏輯一樣，無法確定找到最優解的情況下，我們只能使用貪婪算法找到局部最優，然後通過各種策略使得這個局部最優儘可能的貼近全局最優解。

具體做法是選擇一個“候選子集”，然後評價它的好壞，然後基於評價結果產生下一個候選子集，持續這個循環直到沒有更好的候選子集為止。顯然這裡特徵選擇涉及兩個關鍵環節：如何根據反饋來獲取下一個特徵子集（子集搜索 subset search）？如何評價候選特徵子集的好壞（子集評價 subset evaluation）？

子集搜索可以以一個屬性開始進行“前向”搜索，首先，找到性能最好的單個屬性，然後在該屬性基礎上在剩下的屬性中進行尋找，找到下一個屬性使得兩個屬性的集合性能最好，以此類推直到沒有屬性可以添加進入屬性子集中使得性能更優時停止。 相對應的，我們也可以以全量屬性進行“後向”搜索，每次嘗試去掉一個無關屬性。

子集評價可以使用“信息增益”（詳情請查看第四章決策樹）來評估，其本質是比較特徵子集 A 對數據集的劃分與實際標記信息 Y 對數據集的劃分的差別，其它能判斷兩個劃分差異的機制都能用於特徵子集評價

不同的特徵選擇方法實際上是顯式或隱式的結合了某種或多種子集搜索和子集評價機制。

例如將前向搜索與信息熵結合起來的特徵選擇過程就和決策樹類似。實際上決策樹可用於特徵選擇，樹結點的劃分屬性所組成的集合就是選擇出的特徵子集。

常見的特徵選擇方法大致可分為三類：過濾式（filter）、包裹式（wrapper）和嵌入式（embedding）

2）過濾式特徵選擇

過濾式方法先對數據集進行特徵選擇，然後再訓練學習器，特徵選擇過程與後續學習器無關；即先對特徵進行“過濾”，然後用過濾後的特徵來訓練模型。

Relief（Relevant Features）是一種著名的過濾式特徵選擇方法，該方法設計了一個“相關統計量”來度量特徵的重要性。

具體做法是對每個訓練樣本 xi 找到和它同一個分類的最近鄰樣本 xj，以及和它不是一個分類的最近鄰樣本 xk。如果 diff(xi, xj)t 表示 xi 和 xj 在屬性 t 上的差值，那麼相關統計量計算的就是：diff(xi, xk)的平方 與 diff(xi, xj)的平方的差值在所有樣本上的平均

很直觀的，一個重要的屬性應該使得樣本在這個屬性上與自己同一分類的樣本儘可能接近，而與不同分類的樣本儘可能遠。所以相關統計量在一個屬性上的值越大則說明該屬性的分類性能越強

過濾式特徵選擇的處理邏輯如下圖所示：

3）包裹式特徵選擇

包裹式選擇直接把最終將要使用的學習器性能作為特徵子集的評價標準；根據學習器選擇最有利於性能、“量身打造”的特徵子集

一般而言，由於包裹式特徵選擇方法直接針對給定學習器進行優化，因此從最終的學習性能來看，包裹式方法比過濾式方法更好，當另一方面，由於在特徵選擇過程中需多次訓練學習器，因此包裹式選擇的計算開銷一般要比過濾式選擇大得多

LVW（Las Vegas Wrapper）是一個典型的包裹式特徵選擇算法。它在拉斯維加斯算法（Las Vegas Method）框架下使用隨機策略來進行子集搜索，並以最終分類器的誤差作為特徵子集評價準則。

具體做法(簡化)是：

［1］設置初始最優誤差 E 為無窮大，目前最優特徵子集為屬性全集 A，重複次數 t = 0

［2］隨機產生一組特徵子集 A'，計算使用該特徵子集時分類器的誤差 E'

［3］如果 E' 比 E 小，則令 A' = A, E' = E 並重復［2］、［3］步；否則 t++，當 t 大於等於停止控制參數 T 時跳出循環。

LVW算法簡單明瞭，但是由於是使用隨機子集篩選，並且每次篩選都要重新計算學習器誤差，若 A 和 T 很大時，算法可能會長時間都達不到停止條件。即若有運行時間限制，則可能會得不到解。

包裹式特徵選擇的處理邏輯如下圖所示：

4）嵌入式特徵選擇

不同於前兩種特徵選擇方式將特徵的選擇過程和學習器的訓練過程分開，嵌入式特徵選擇是將特徵選擇過程與學習器訓練過程融為一體，兩者在同一個優化過程中完成；即在學習器訓練過程中自動化的進行了特徵選擇。

比如決策樹在分枝的過程中，就是使用的嵌入式特徵選擇方法，其內在還是根據某個度量指標對特徵進行排序。

5）稀疏表示與字典學習

數據集可以以矩陣表示，每一行為一個樣本，每一列為一個屬性。特徵選擇所考慮的問題是特徵具有“稀疏性”，即矩陣中的許多列與當前學習任務無關，我們需要通過特徵選擇去除這些列。

我們現在考慮另一種稀疏性：在數據集 D 所對應的矩陣中存在很多零元素，但這些零元素並不是以整列、整行形式存在的。當樣本具有稀疏表示時，對學習任務有不少好處，比如稀疏表示的數據更容易線性可分。同時，稀疏表示的數據在存儲上的負擔不大。

那麼我們可以通過將數據轉換為“恰當稀疏”的形式，獲得稀疏表示的好處，簡化學習任務。這種為普通稠密表達的樣本找到合適的字典，將樣本轉化為稀疏表示形式，從而使學習任務得以簡化，模型複雜度得以降低，通常稱為“字典學習”（dictionary learning），亦稱“稀疏編碼”（sparse coding）。

這兩個稱謂稍有差別，“字典學習”更側重於學得字典的過程，而“稀疏編碼”更側重於將樣本稀疏表達的過程，不過這兩者都是算法同一個優化求解過程中完成的，因此可以不做進一步區分。

稀疏表示的具體的過程簡單描述如下：

［1］確定映射字典的詞彙量 k，並初始化字典 B，d＊k，其中 d 為樣本屬性數

［2］固定住字典 B，求得樣本集 X 通過字典映射後的稀疏表示 Z

［3］固定住 Z 來更新字典 B

［4］反覆第［2］、［3］步，最終可得合適的字典 B 和樣本 X 的稀疏表示 Z

在上述字典學習過程中，用戶能通過設置詞彙量 k 的大小來控制字典的規模，從而影響稀疏程度

6）壓縮感知（compressed sensing）

在現實任務中，我們常希望能根據部分信息來恢復全部信息。會擁有這種需求的原因是因為，在實踐中為了便於數據的傳輸、存儲，人們通常會將數據進行壓縮，這有可能會損失一部分信息，而傳輸的過程中又可能會丟失一部分信息。這時候擁有根據接收到的受損的數據來恢復全部數據的能力就很重要了，而壓縮感知為解決此類問題提供了新思路。

壓縮感知的核心思想是：一般來說丟失了部分信息的數據是無法恢復為原始數據的，但是如果將原始數據通過字典學習表示成稀疏表示時，卻可以比較好的進行復原。這是因為稀疏性使得未知因素的影響大大的減少。

與特徵選擇、稀疏表示不同，壓縮感知關注的是如何利用信號本身的稀疏性，從部分觀測樣本中恢復原信號。通常認為，壓縮感知分為“感知測量”和“重構恢復”這兩個階段。

“感知測量”關注如何對原始信號進行處理以獲得其稀疏表示，這方面涉及我們前邊提的特徵選擇、稀疏表示等內容

“重構恢復”關注的是如何從少量觀測中恢復原信號，這才是壓縮感知的精髓，當我們談到壓縮感知時，通常是指這部分。

2. 基礎知識

1）拉斯維加斯方法

拉斯維加斯方法是一類隨機方法的統稱。這類方法是通過隨機採樣和一個評估函數來進行數據篩選的，本章介紹的 LVW 算法就是基於該方法的具體實現。它的特點是，隨著採樣次數的增多，得到的正確結果的概率逐漸加大，如果隨機採樣過程中已經找到了正確結果，該方法可以判別並報告，但在放棄隨機採樣，而採用類似全採樣這樣的確定性方法之前，不保證能找到任何結果（包括近似結果）

2）奈奎斯特採樣定理

如果對某一時間連續信號（模擬信號）進行採樣，當採樣速率達到被測信號最大頻率的兩倍時，那麼，根據這些採樣值就能準確地確定原信號

3. 總結

1）特徵選擇和降維計算是處理高維數據的兩大主流技術

2）特徵選擇涉及兩個關鍵環節：如何根據反饋來獲取下一個特徵子集（子集搜索 subset search）？如何評價候選特徵子集的好壞（子集評價 subset evaluation）

3）子集搜索是通過貪婪算法每次以一定的策略對特徵子集進行添加或刪除以使得新的子集能對性能進行提升。當沒有更好的選擇能使性能提升時，停止子集搜索過程

4）子集評價的本質是比較特徵子集 A 對數據集的劃分與實際標記信息 Y 對數據集的劃分的差別，其它能判斷兩個劃分差異的機制都能用於特徵子集評價

5）不同的特徵選擇方法實際上是顯式或隱式的結合了某種或多種子集搜索和子集評價機制

6）過濾式方法先對數據集進行特徵選擇，然後再訓練學習器，特徵選擇過程與後續學習器無關；即先對特徵進行“過濾”，然後用過濾後的特徵來訓練模型

7）包裹式選擇直接把最終將要使用的學習器性能作為特徵子集的評價標準；根據學習器選擇最有利於性能、“量身打造”的特徵子集

8）從學習性能上來看，包裹式特徵選擇比過濾式特徵選擇好許多，但是計算開銷前者要比後者大得多

9）這種為普通稠密表達的樣本找到合適的字典，將樣本轉化為稀疏表示形式，從而使學習任務得以簡化，模型複雜度得以降低，通常稱為“字典學習”（dictionary learning），亦稱“稀疏編碼”（sparse coding）

10）壓縮感知的核心思想是：將原始數據通過字典學習表示成稀疏表示時，可以比較好的利用其稀疏性復原原始數據進