UC Berkeley提出特徵選擇新方法：條件協方差最小化

選自BAIR Blog

作者：Jianbo Chen、Mitchell Stern

機器之心編譯

參與：Nurhachu Null、路雪

UC Berkeley 近日提出了一種新型特徵選擇方法 CCM，該方法基於最小化條件協方差運算元的跡來進行特徵選擇。研究者的實驗證明該方法在多個合成和現實數據集上達到了不輸當前先進方法的性能。相關論文《Kernel Feature Selection via Conditional Covariance Minimization》被 NIPS 2017 接收。

論文鏈接：https://papers.nips.cc/paper/7270-kernel-feature-selection-via-conditional-covariance-minimization.pdf

GitHub 鏈接：https://github.com/Jianbo-Lab/CCM

降維可以增強模型的可解釋性，特徵選擇則是常用的降維方法。隨著大型數據集變得流行，近年來包括文本分類、微陣列數據中的基因選擇、人臉識別等現實任務見證了特徵選擇的廣泛使用。BAIR 研究了監督性特徵選擇的問題，監督特徵選擇需要尋找一個輸入特徵的子集來較好地解釋輸出結果。這個方法可以通過消除冗餘或者雜訊特徵來降低下遊學習（downstream learning）的計算成本，同時還能通過保留下來的特徵來提供對數據的洞見。

特徵選擇演算法通常可分為三個主要的類別：濾波器（filter）方法、封裝（wrapper）方法以及嵌入（embedded）方法。濾波器方法基於數據的本質屬性選擇特徵，與所用的學習演算法無關。例如，我們可以計算每個特徵和響應變數之間的相關性，然後選擇相關性最高的變數。相比之下，封裝方法就更加具體，它的目標是尋找能夠使某個預測器的性能最優化的特徵。例如，我們可以訓練多個支持向量機，每個支持向量機使用不同的特徵子集，然後選擇在訓練數據上損失最小的特徵子集。因為特徵子集的數量是指數規模的，所以封裝方法通常會使用貪心演算法。最後，嵌入方法是將特徵選擇和預測結合成一個問題的多目標技術，它通常會優化一個目標函數，這個目標函數結合了擬合優度和對參數數量的懲罰。一個例子就是構建線性模型的 LASSO 方法，它用?1 penalty 來表徵對參數數目的懲罰。

本文提出了條件協方差最小化（CCM）方法，這是一個統一前兩個觀點的特徵選擇方法。在以下部分中，BAIR 研究者首先描述了自己的方法。然後我們通過幾個綜合實驗證明該方法能夠捕獲特徵集之間的聯合非線性關係。最後，一系列現實任務證明，該演算法具有和其他幾種特徵選擇演算法相當或者優於它們的性能。

特徵選擇的公示表達

理解特徵選擇問題的一種方式是從依賴的角度來看。理想情況下，我們希望先確定一個大小為 m 的特徵子集 T，這樣剩下的特徵獨立於 T 的響應。然而，如果 m 太小，則這可能無法實現。所以我們使用某個指標來量化對剩餘特徵條件依賴的程度，並且在所有合適大小的特徵子集 T 上優化該指標。

或者，我們希望找到一個特徵子集 T，它能夠在特定的學習問題上最有效地預測輸出 Y。在我們的框架中，將樣本標籤和最佳分類器所做的預測之間的均方差定義為預測誤差。

方法

我們提出了一個可以在回歸中同時描述依賴性和預測誤差的標準。首先，我們分別介紹了在特徵子集 X_T的域和響應變數 Y 的域上的兩個函數空間。每個函數空間都是一個完全的內積空間（希爾伯特空間），這個函數空間有可以將整個空間進行延展的核函數，且具備「再生性」。這樣的函數空間被稱作「再生核希爾伯特空間」（Reproducing Kernel Hilbert Space，RKHS）。然後，我們將響應變數的域上的 RKHS 運算元定義為：在給定所選特徵的情況下，描述輸入數據上的響應變數的條件依賴。這個運算元叫做「條件協方差運算元」（conditional covariance operator）。我們用對應的經驗分布計算得到的條件協方差運算元的跡作為我們的優化標準，這也是最佳預測器在給定的輸入數據域上的 RKHS 中的估計回歸誤差。在特徵子集上直接最小化這個標準是很難計算的。相反，我們使用一個介於 0 和 1 之間的實值標量來對每個特徵進行加權，通過這個方式將其表達為一個鬆弛問題。該鬆弛問題的目標可以用核矩陣來表示，而且可以很容易地使用基於梯度的方法進行優化。

結果

我們分別在合成數據集和現實數據集上測評了我們的方法。我們比較了現有的幾個強大演算法，包括遞歸式特徵消除（RFE）、最小冗餘最大關聯（mRMR）、BAHSIC，以及使用互信息（MI）和皮爾遜相關係數（PC）的濾波器方法。RFE 是一個很流行的封裝方法，它基於從分類器收到的得分貪婪地選擇特徵。mRMR 選擇的特徵能夠捕獲彼此不同的信息，但是每一個都與響應變數有很大的相關性。BAHSIC 是一個核方法，它貪婪地優化所選特徵和響應變數之間的依賴。最後，濾波器方法使用互信息（MI）或者皮爾遜相關係數（PC）分別貪婪地優化所選特徵子集和響應之間的相應指標。

合成數據

我們使用以下的合成數據集：

二元分類（Friedman et al.）。當 Y=?1 時，10 個特徵 (X_1,…,X_10) 是相互獨立的標準隨機變數。當 Y=1 的時候，前 4 個特徵是標準正態隨機變數，它們滿足以下條件：

剩下的 6 個特徵 (X_5,…,X_10) 也是獨立的標準正態隨機變數。

三維異或作為四分類。三維超立方體有 8 個頂點，

通過元組 (v1v3,v2v3) 對它們進行分組，就得到了 4 組與各自的反面組成的成對向量

對類別 i 而言，樣本可以通過等概率選擇 v^(i) 或者?v^(i) 和添加雜訊來生成。每個樣本就額外增加 7 個標準正態雜訊特徵，得到的特徵集總共有 10 個特徵。

可加非線性回歸。考慮以下可加模型：

每個樣本額外有 6 個雜訊特徵，總共 10 個特徵。所有的特徵和雜訊 ε 都是從標準正態分布中生成的。

左：二元分類數據；右：二維異或

第一個數據集表示一個標準的非線性二分類任務。第二個數據集表示一個多類別分類任務，其中每個特徵都是和 Y 獨立的，但是三個特徵聯合起來會對 Y 產生影響。第三個數據集針對可加非線性回歸模型。

每個數據集的特徵維度 d=10，但是只有 m=3 或者 4 是真實特徵。因為這些真實特徵已經是已知的了，所以我們可以通過計算每種特徵選擇演算法給真實特徵賦予的中值等級來評估該演算法的性能，較低的中值等級意味著較好的性能。

上圖展示了模擬數據集上真實特徵的中值等級（y 軸）隨著樣本量（x 軸）的變化。中值等級越低，性能越好。點畫線代表最優的中值等級。

在二分類和四分類任務中，我們的方法比其他的演算法有著更優的性能，我們的方法在 50 個樣本以內就能夠鑒別出真實特徵，而其他的方法需要接近 100 個樣本或者最終都無法成功收斂。在可加非線性模型中，幾個演算法的性能都比較好，在所有的樣本大小中我們的演算法都不遜色。

現實數據

現在我們將注意力轉移到現實任務中，研究我們的方法和其他幾種非線性方法（mRMR、BAHSIC、MI）與核 SVM 結合使用時的下游分類性能。我們在 ASU 特徵選擇網站和 UCI 庫中的 12 個標準基準任務上進行了實驗。下表是對所用數據集的總結。

數據集來自多個領域，包括基因數據、圖像數據、聲音數據，而且高維度和低維度的都有。

對於每一個任務，我們運行並評估每個演算法，以獲取所有特徵的排序。然後基於前 m 個特徵訓練核 SVM，計算準確率，從而評估性能。下圖展示了我們的結果。

上圖展示了現實基準數據集中的準確率（y 軸）隨所選特徵數目（x 軸）的變化。準確率越高，性能越好。

與其他三種流行的非線性特徵選擇方法相比，我們的方法在大多數例子中都是最強大的，有時候會有特別大的差距，例如在 TOX-171 任務中。儘管我們的方法偶爾在開始時（所選特徵數目比較少時）性能會不太好，但最終還是會跟其他演算法的性能持平或超越它們（glass 任務除外）。

結論

在這篇文章中，我們提出了條件協方差最小化（CCM）方法，這個方法基於最小化條件協方差運算元的跡來進行特徵選擇。這個方法的思想是選擇能夠最大化預測基於協變數響應依賴的特徵。我們通過將很難處理的離散協變數響應依賴鬆弛化，以獲取適合基於梯度的優化的連續近似，從而完成該方法。我們在多個合成數據集和現實數據集上進行實驗，證明了該方法的有效性，發現我們的方法通常會優於目前最先進的演算法，包括另一個基於希爾伯特-施密特獨立性係數（Hilbert-Schmidt independence criterion）的核特徵選擇方法。

更多信息

關於演算法的更多信息，請參考鏈接中的內容：

論文：https://papers.nips.cc/paper/7270-kernel-feature-selection-via-conditional-covariance-minimization

代碼：https://github.com/Jianbo-Lab/CCM

論文：Kernel Feature Selection via Conditional Covariance Minimization

摘要：我們提出了一種特徵選擇方法，該方法利用基於核的獨立性估計找出協變數的子集，可最大化預測響應變數。我們基於之前的核降維研究構建該方法，展示了如何通過約束優化問題（涉及條件協方差運算元的跡）進行特徵選擇。我們證實了該步驟穩定一致的結果，同時還展示了該方法在多個合成和現實數據集上與其他先進演算法相比的優越性。

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

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

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！