胡振威，汪廷華，周慧穎

贛南師范大學 數(shù)學與計算機科學學院，江西 贛州 341000

在人工智能領(lǐng)域，特別是機器學習[1-3]和數(shù)據(jù)挖掘領(lǐng)域中[4-5]，現(xiàn)實世界的應(yīng)用數(shù)據(jù)通常被表示為高維特征向量，直接利用這些高維數(shù)據(jù)往往會導致諸多嚴重問題：首先，會增加分類的計算成本和復雜性，這種現(xiàn)象被稱為“維度詛咒”[6]；其次，降低了分類器的泛化能力；第三，很難分析理解特征在決策過程中的作用，因為從專家的角度來看，只有一小部分特征與決策相關(guān)，其他無關(guān)特征極大影響了數(shù)據(jù)分析的性能與結(jié)果。因此，對于有監(jiān)督學習中的分類問題，在執(zhí)行分類任務(wù)之前，重要的是應(yīng)用合適的特征選擇方法，選擇與類別相關(guān)的特征。作為分類的預處理步驟，特征選擇[7-9]可以降低學習算法的時間和空間要求，緩解“維度詛咒”所帶來的過擬合問題，解決無關(guān)特征和冗余特征帶來的性能不佳問題。此外，特征選擇不僅能降低數(shù)據(jù)的維度，從而有助于數(shù)據(jù)的理解和可視化，而且通常能生成更緊湊的、具有更強泛化能力的模型。特征選擇的主要思想是獲得代表數(shù)據(jù)集的良好特征子集，消除提供少量信息的特征，在不影響類分布、不顯著降低分類精度的情況下達到降維目的。

近年來，核方法[10-12]被廣泛應(yīng)用于各種機器學習問題。它將樣本數(shù)據(jù)從原空間映射到特征空間，即高維再生核希爾伯特空間（reproducing kernel Hilbert space，RKHS），使得即使是如線性方法般簡單的算法都能獲得優(yōu)秀的性能。核方法成功的關(guān)鍵在于可以通過指定一個核函數(shù)來計算特征空間中數(shù)據(jù)點之間的內(nèi)積，從而唯一確定映射到特征空間中的內(nèi)容。換言之，核函數(shù)隱式定義了從原空間到特征空間的非線性映射，通過計算核函數(shù)來避免在高維特征空間中的昂貴計算。因此，核方法的核心問題之一是核的選擇。許多核統(tǒng)計相關(guān)性度量已經(jīng)被提出用于統(tǒng)計推斷，用來捕捉隨機變量之間的依賴性[13-16]，如核廣義方差[17]、核約束協(xié)方差[18]和希爾伯特-施密特獨立性準則（Hilbert-Schmidt independence criterion，HSIC）[16]等，這些度量在總結(jié)協(xié)方差算子及其使用的規(guī)范化方式上有所不同。其中，HSIC應(yīng)用最為廣泛[19]，它由RKHS之間的交叉協(xié)方差算子的希爾伯特-施密特范數(shù)（HS范數(shù)）的經(jīng)驗估計組成，Gretton等人[16]已經(jīng)證明了當且僅當隨機變量相互獨立時，HSIC為零。因此，它不僅被廣泛用于統(tǒng)計獨立性測試，而且還被應(yīng)用于各種學習問題[20-23]。與其他經(jīng)典分布度量相比，HSIC有以下的優(yōu)勢[16]：首先，HSIC的經(jīng)驗估計計算簡單，只需要計算Gram矩陣乘積的跡，且不需要額外定義正則化項。其次，HSIC收斂速率快，經(jīng)驗估計值以1/m的速率收斂于總體估計值，其中m是樣本總量。因此，基于HSIC的獨立性檢驗不存在學習速率慢的問題。特別地，隨著樣本量的增加，可以保證以高概率檢測到任何現(xiàn)有的依賴關(guān)系。最后，HSIC的經(jīng)驗估計值的有限樣本偏差為O(m-1)，與有限樣本波動相比可以忽略不計。

本文系統(tǒng)綜述了基于HSIC的特征選擇方法的基本模型，將HSIC引入特征選擇過程中，應(yīng)用于學習任務(wù)，給特征選擇算法的研究與發(fā)展提供了豐富的設(shè)計思路和廣泛的應(yīng)用前景。在分析各種方法的特點，總結(jié)其研究現(xiàn)狀的基礎(chǔ)上，進一步凝煉其發(fā)展方向。

1 特征選擇概述

根據(jù)不同的標準，特征選擇有不同的分類方法。根據(jù)數(shù)據(jù)集中的標簽信息是否可用，特征選擇方法可以分為有監(jiān)督[24-25]、半監(jiān)督[26]和無監(jiān)督[27]三種。三種方法的區(qū)別在于訓練過程中使用了多少標記的訓練樣本。監(jiān)督方法一般需要一組完全的標簽數(shù)據(jù)來識別和選擇相關(guān)特征，數(shù)據(jù)集中每個樣本的標簽信息可以是有序值、真實值或者類別信息（視具體分類任務(wù)而定）；半監(jiān)督方法對只有有限數(shù)量標簽樣本的數(shù)據(jù)集進行操作[28]；無監(jiān)督方法則不需要標簽數(shù)據(jù)。當標簽實際可用時，通常優(yōu)先選擇監(jiān)督學習方法，因為標簽中含有特征和標簽之間依賴關(guān)系的附加信息。然而，現(xiàn)實世界產(chǎn)生的數(shù)據(jù)中標簽數(shù)據(jù)通常很少，人工標記相當昂貴，而未標記的數(shù)據(jù)要豐富得多。因此，無監(jiān)督特征選擇[29-31]在實踐中很重要，并在科學界引起了極大的關(guān)注。此外，無監(jiān)督特征選擇方法有兩個重要的優(yōu)勢[32-33]：（1）它們是無偏的，并且在先驗知識不可用時有良好的表現(xiàn)；（2）與可能無法處理新的類別數(shù)據(jù)的監(jiān)督特征選擇方法相比，它們可以降低過擬合的風險。

根據(jù)與學習算法的關(guān)系，特征選擇方法可以分為三種[7-8，25]：（1）過濾式（fliter）方法，特征選擇過程獨立于具體的學習算法，通過數(shù)據(jù)本身選擇最相關(guān)的特征，即基于數(shù)據(jù)的內(nèi)在屬性來評估特征，不需要使用任何可以指導相關(guān)特征搜索的學習算法。因此，特征選擇過程與后續(xù)學習器無關(guān)。過濾式方法的主要特點是效率和可擴展性。信息增益[34-35]、Fisher評分[36]、Pearson相關(guān)系數(shù)[37]、卡方檢驗[38]和互信息[39]是用于捕捉特征重要性的常用統(tǒng)計度量。（2）包裝式（wrapper）方法，可以理解為將特征選擇過程和分類器封裝在一起，以分類器的交叉驗證結(jié)果來評估特征子集的優(yōu)劣。目前學者們已經(jīng)提出許多包裝式方法[40-41]，實驗結(jié)果表明特征經(jīng)過包裝式方法處理后，學習算法的準確率一般比過濾式方法處理后的結(jié)果好。但算法在特征子集空間中進行窮舉搜索，因此更耗時，且僅限與特定的分類算法結(jié)合使用，當樣本不足時，容易過擬合[42]。（3）嵌入式（embedded）方法[43-45]，試圖利用兩種方法（過濾式和包裝式）的特性，在計算效率和有效性（使用所選特征時相關(guān)目標任務(wù)的質(zhì)量）之間取得良好的折衷。嵌入式方法克服了計算的復雜性。在該方法中，特征選擇和模型學習同時進行，并且在模型的訓練階段選擇特征。因此，與包裝式方法相比，嵌入式方法的計算成本明顯更低，同時避免每次開始選擇新的特征時對模型的訓練過程[32，46]。每種特征選擇方法都有各自的優(yōu)點和缺點，就計算速度而言，過濾式方法比嵌入式方法快，而嵌入式方法又比包裝式方法快。包裝式方法中過擬合的可能性比嵌入式方法更大，過濾式方法最小。由于過濾式方法不依賴于任何特定的學習方法，它們更受歡迎，也更具可操作性[47]。

2 希爾伯特-施密特獨立性準則

本章簡要描述了RKHS之間互協(xié)方差算子所必需的功能分析背景[13]，并介紹了互協(xié)方差算子的HS范數(shù)，最后給出關(guān)于HSIC的初步概述。

2.1 基于核方法的獨立性度量

HSIC是一種基于核的獨立性度量方法，該方法原理是在RKHS上定義互協(xié)方差算子，再從這些算子中推導出合適度量獨立性的統(tǒng)計量來計算獨立性的大小。HSIC采用的是Hilbert-Schmidt互協(xié)方差算子，通過對算子范數(shù)的經(jīng)驗估計得到獨立性判斷準則。

考慮一個從X→?的函數(shù)，設(shè)F為該函數(shù)的再生核希爾伯特空間，其中X是一個可分的度量空間。對于點x,x′∈X，對應(yīng)元素φ(x),φ(x′)∈F（稱φ:X→F為特征映射），使得，其中k:X×X→?是一個相關(guān)的再生核，這里要求F是可分的（它必須有一個完整的正交系統(tǒng)）。同樣地，還定義了第二個可分度量空間Y的RKHS G，它也具有特征映射φ和核

設(shè)Pxy(x,y)是(X×Y)上的聯(lián)合測度，相應(yīng)的邊緣測度分別被記為Px(x)、Py(y)，則協(xié)方差矩陣Cxy被定義為：

其中，Exy、Ex、Ey分別是關(guān)于聯(lián)合測度Pxy、邊緣測度Px、Py的期望值，yT是y的轉(zhuǎn)置。協(xié)方差矩陣能夠編碼隨機變量之間的所有二階相關(guān)性。文獻[13]定義了一個能有效總結(jié)隨機變量x和y之間線性相關(guān)性的統(tǒng)計量——Cxy的Frobenius范數(shù)（也稱為HS范數(shù)）：

其中，σi是協(xié)方差矩陣的奇異值（singular value），tr(·)表示跡運算。當且僅當x和y之間不存在線性相關(guān)性時（不等同于線性獨立），等于零。因此該方法僅限判斷隨機變量間的線性相關(guān)性。然而，當處理的數(shù)據(jù)類型未知或者不僅僅是線性依賴關(guān)系時，這種方法的作用是非常有限的[21]。根據(jù)核方法理論[12，48-49]，在低維空間中非線性可分問題可以轉(zhuǎn)化為高維空間中的線性可分問題，因此利用核方法可在已有線性算法的基礎(chǔ)上解決非線性問題。

給定兩個特征映射φ:X→F和φ:Y→G,其中F和G分別是核函數(shù)k和l對應(yīng)的RKHS，可以將φ和φ之間的互協(xié)方差算子定義為線性算子Cxy:G→F：

其中，?表示張量積，對于任意f∈F和g∈G，有f?g:G→F：

此外，根據(jù)HS范數(shù)的定義，可以計算出f?g：

由此，HSIC就被定義為互協(xié)方差算子的HS范數(shù)的平方：

這里Ex,x′,y,y′表示從Pxy中提取的獨立對(x,y)和(x′,y′)的期望值。文獻[16]證明了這個表達式，并表明當核k和l有界時，Cxy的HS范數(shù)存在。

核函數(shù)起著簡化問題的作用，事實上不需要描述特征映射φ(·)和φ(·)的顯式構(gòu)造（可能是未知的或相當復雜），也不需要描述RKHS（可能具有相當高的維數(shù)，甚至是無限維）。原空間中核函數(shù)計算隱式地對應(yīng)于RKHS中的運算，且計算量與其維數(shù)無關(guān)，因此避免了在更高維特征空間內(nèi)的運算。

2.2 HSIC的經(jīng)驗估計

設(shè)Z={(x1,y1),(x2,y2),…,(xm,ym)}∈(X×Y)表示從聯(lián)合分布Pxy中提取出的m個獨立觀測值。Gretton等人[16]提出了具有O(m-1)偏差的HSIC估計量，在給定有限個觀測值的情況下對HSIC進行近似估計，證明了這個估計量在適當?shù)那闆r下是集中的：

其中，K,L∈?m×m是包含元素為Kij=k(xi,xj)和Lij=l(yi,yj)的核矩陣，H=Im-m-111T∈?m×m是一個中心化矩陣，其中1∈?m是m維全1列向量。估計量HSIC0具有偏差：

這種偏差來自于HSIC0中的自相互作用項。也就是說，HSIC0中仍存在估計量為O(m)的形式為KijLil和KjiLli的項，導致了O(m-1)的偏差。為了解決這個問題，Song等人[50]提出了一種無偏估計量HSIC1，在確保適當歸一化的同時消除了額外的項：

這樣就能通過簡單的核矩陣K和L的計算來估計隨機變量x和y之間的相關(guān)性，而不需要執(zhí)行其他的復雜計算操作（如密度估計等）。另外，HSIC0和HSIC1都不需要任何顯式的正則化參數(shù)，正則化隱含在核的選擇中，這與早期的核依賴估計工作都不同。

3 基于HSIC的特征選擇

特征選擇是離散空間上的NP-hard組合優(yōu)化問題，對2d（d為特征數(shù)）種可能的特征子集展開窮舉搜索在計算上是不切實際的。許多算法通過在維度上引入權(quán)重將特征選擇問題表述為連續(xù)優(yōu)化問題[51-54]。這些方法對于線性可分問題固然表現(xiàn)良好，但對于非線性可分問題，優(yōu)化通常變成非凸的，局部最優(yōu)不一定能提供最好的結(jié)果?？紤]到評估經(jīng)驗HSIC不依賴于特定的學習器，通常有兩種方法來執(zhí)行高效的特征選擇：一是應(yīng)用貪婪或隨機搜索策略來搜索最優(yōu)特征子集。二是引入權(quán)重將問題表述為連續(xù)優(yōu)化問題。前者除了核函數(shù)參數(shù)外不需要其他的參數(shù)，因此計算效率高，但容易陷入局部最優(yōu)解；后者引入權(quán)重將離散問題表述為連續(xù)優(yōu)化問題，從而找到全局最優(yōu)解，但加入了正則化參數(shù)，使得算法計算復雜度增加，總體計算成本變高。

基于HSIC的特征選擇方法流程圖如圖1所示。其中虛線框內(nèi)的部分需要循環(huán)執(zhí)行，當HSIC值符合某一條件時，循環(huán)結(jié)束，得到滿足用戶需求的特征子集。

3.1 貪婪方法

BAHSIC（backward elimination using HSIC）是Song等人[50，55-56]提出的一種基于后向消除的監(jiān)督特征選擇算法。關(guān)鍵想法是好的特征應(yīng)該高度依賴于標簽，獲得這種依賴之后，它利用后向消除來選擇最相關(guān)的特征子集。具體來說，用集合S表示全部特征，BAHSIC通過生成一個列表S*來工作，該列表中包含相關(guān)性遞增的特征。在每一步中，S*從S中附加一個不包含在S*中的特征（該特征對集合S的依賴性最?。?。算法遞歸地產(chǎn)生S*，從S中刪除最不相關(guān)的特征，并在每次迭代時將它們添加到S*的末尾。這樣，特征選擇問題可以通過簡單地從S*中取出最后t個特征來解決。然而，當集合S中存在大量不相關(guān)的特征時，從S中刪除單個特征的效率顯然是很低的，但一次性刪除太多特征則會有丟失相關(guān)特征的風險。實驗發(fā)現(xiàn)算法的速率和所選特征質(zhì)量之間一個很好的折衷是在每次迭代中移除10%的當前特征。在BAHSIC中，標簽核矩陣L在整個過程中是固定的，如果需要，可以預先計算并存儲以加速。因此，BAHSIC主要的計算來自于對降維數(shù)據(jù)核矩陣K的重復計算。此外，與大多數(shù)其他特征選擇方法只為二進制分類或回歸問題而制定不同，BAHSIC不僅直接適用于二進制、多類和回歸問題，而且封裝了許多著名的特征選擇標準，如Pearson相關(guān)系數(shù)、均值差及其變體、最大均值差（maximum mean difference，MMD）、核目標對齊（kernel target alignment，KTA）、嶺回歸（ridge regression）、二次互信息和支持向量回歸消除等[21]。除此之外，缺少標簽數(shù)據(jù)的無監(jiān)督特征選擇也可使用BAHSIC的變體形式來解決。在這種情況下，目標是選擇可用的特征子集，使其與完整數(shù)據(jù)集密切相關(guān)。換言之，BAHSIC的變體想找到數(shù)據(jù)本身的壓縮表示，希望對后續(xù)學習任務(wù)有幫助，BAHSIC通過簡單地使用完整的數(shù)據(jù)集作為標簽來實現(xiàn)這一點。

與試圖每次刪除特征來盡可能增加所選特征子集與結(jié)果之間相關(guān)性的后向消除技術(shù)相反，使用HSIC的前向選擇（forward selection using HSIC，F(xiàn)OHSIC）嘗試盡可能為每次包含的特征實現(xiàn)這一點。它建立一個相關(guān)度遞減的特征序列，通過一次添加一個特征到使用HSIC作為依賴性度量標準獲得的特征集合中，來實現(xiàn)增加特征子集與結(jié)果之間的相關(guān)性。為了能夠更快地選擇特征，可以選擇一組特征而不是單個特征（例如，固定比例a），并將它們一次性加入到S*中。這樣，特征選擇問題可以通過簡單地從S*中取出前t個特征來解決。

Liaghat和Mansoori[30]提出了一種基于特征刪除前后的樣本相似度矩陣相關(guān)性最大化的無監(jiān)督特征選擇框架，該框架采用HSIC方法，通過后向消除不相關(guān)或冗余特征來進行特征選擇。為了獲得更好的HSIC估計，嘗試使用自適應(yīng)技術(shù)處理對角占優(yōu)矩陣，然后針對未標記數(shù)據(jù)集提出了一種基于此估計的特征選擇方法。文獻[57]為標記數(shù)據(jù)提供了平衡對角占優(yōu)相似矩陣值的方法。這是一種非線性轉(zhuǎn)換，因此值較大的變量比較小的變量減少更多，并且矩陣值的動態(tài)范圍減小。除了保持樣本的相對成對相似性外，核矩陣中的數(shù)值范圍也被縮小，對角優(yōu)勢消失或大大減弱。該方法使用文獻[57]中處理核矩陣中大對角線的技巧，互協(xié)方差算子Cxy被改寫為：

其中，G表示d個特征的集合（m個樣本是d維的），G′表示被選擇的特征集合，KG和LG′表示使用核函數(shù)k和l計算的樣本相似矩陣。然后根據(jù)‖ ‖Cxy2使用不完全Cholesky估計，HSIC估計為：

其中，σi是矩陣(KG)qH(LG′)qH的第i個特征值。根據(jù)HSIC2，提出一種無監(jiān)督的特征選擇方法，稱為相似性保持BAHSIC（SP-BAHSIC），用于識別具有對角占優(yōu)相似矩陣數(shù)據(jù)集的信息特征。該方法在樣本數(shù)相對較少、特征數(shù)較多的數(shù)據(jù)集上取得了較好的結(jié)果（即m?d）。為了提高SP-BAHSIC的性能，降低計算量和時間復雜度，提出了基于聚類的SP-BAHSIC方法SPC-BAHSIC，它使用k-means聚類算法[58]來選擇所需數(shù)量的特征。在SPC-BAHSIC中，每個聚類簇只評估一個特征，因此它比SP-BAHSIC更快。然而SP-BAHSIC和SPC-BAHSIC方法都是使用后向消除搜索策略，當需要少量信息特征時，搜索階段使用正向選擇更為合適。因此，Liaghat和Mansoori提出了SP-FOHSIC算法，用于找到最大化HSIC2的特征子集。同樣的，提出了SPC-BAHSIC算法來加速SP-FOHSIC的計算效率。最后值得注意的一點，在后向消除的步驟中，刪除的特征無法再進行選擇，前向選擇也是一樣，已經(jīng)被選擇的特征無法再被刪除。因此，在搜索階段使用增l減r策略[59-61]，能夠有效地緩解這個問題。當l＞r時其工作原理類似于正向選擇，但區(qū)別在于在每個階段都有可能刪除之前選擇的特征。同樣的，當l＜r時，增l減r方法的工作原理類似于反向消除，但在每一步中，都有可能從之前刪除的特征中進行選擇。由于增l減r策略能夠降低算法陷入局部最優(yōu)的風險，Liaghat和Mansoori由此提出了SP-LRHSIC和SPC-LRHSIC方法。在一些合成數(shù)據(jù)集和真實數(shù)據(jù)集（特別是在小樣本和高維的數(shù)據(jù)集中）上的實驗結(jié)果證明了這些方法的有效性。

使用HSIC，可以執(zhí)行特征的前向選擇和后向消除，特別是對數(shù)據(jù)使用線性核（對標簽無此要求）時，前向選擇和后向消除是等價的。盡管FOHSIC在計算上的效率更高，但BAHSIC往往能夠選擇質(zhì)量更優(yōu)的特征，因為這些特征都是在其他所有特征都存在的背景下評估得到的。例如，在文獻[50]中，在對數(shù)據(jù)集hepatitis的處理結(jié)果中顯示，BAHSIC的分類錯誤率在(13.8±3.5)%范圍內(nèi)，F(xiàn)OHSIC的分類錯誤率在(15.0±2.5)%范圍內(nèi)，基于互信息方法的分類錯誤率在(15.0±4.1)%范圍內(nèi)，Relief的分類錯誤率在(17.5±2.0)%范圍內(nèi)。由此可以看出，雖然BAHSIC是一種過濾方法，但與人工和真實世界數(shù)據(jù)中更專業(yè)的方法相比，它仍然表現(xiàn)出良好的性能，并且在運行效率方面也非常有競爭力。后向消除和正向選擇等貪婪搜索策略容易產(chǎn)生局部最優(yōu)解，為了解決這一限制，隨機搜索策略，如遺傳算法[62]、蝙蝠算法[63]等，被用于搜索全局最優(yōu)的特征子集[22，64]，在搜索過程中增加一些隨機性來幫助擺脫局部最優(yōu)解。

3.2 加權(quán)方法

除貪婪方法外，使用HSIC的特征選擇還可以通過將特征選擇問題轉(zhuǎn)換成連續(xù)優(yōu)化問題來解決。在數(shù)據(jù)的維度上引入權(quán)重w=(w1,w2,…,wd)T∈?d：x?w?x，其中?表示對應(yīng)元素的乘積，由此，使用HSIC的特征選擇變成了關(guān)于w的優(yōu)化問題：

其中，w要求是稀疏的，HSIC(w)是w關(guān)于HSIC的函數(shù)。為了獲得所選特征的稀疏解，Song等人[50]將l0范數(shù)與目標函數(shù)結(jié)合：

其中，λ是控制特征選擇標準HSIC(w)和稀疏性之間權(quán)衡的懲罰系數(shù)，計算w中非零元素的數(shù)量，通過對具有大量非零元素的標準施加更重的懲罰來實現(xiàn)稀疏性。然而，l0范數(shù)不是一個連續(xù)的函數(shù)，但它可以用凹函數(shù)來近似：

實驗表明，當α=5時在實踐中的效果很好。

在Jordan算法的啟發(fā)下，Gangeh等人[65]提出了一種稀疏奇異值分解（SVD）方法來誘導稀疏性。該方法使用一種完全不同的方式來執(zhí)行基于HSIC的特征選擇：將HSIC與矩陣稀疏分解的快速技術(shù)結(jié)合使用，以確定DNA微陣列特征的稀疏投影。只有一小部分基因在提取的投影向量中具有非零權(quán)重，因此被識別為給定響應(yīng)變量的相關(guān)基因。所提出的特征選擇算法包括兩個主要步驟：一是找到依賴于響應(yīng)變量y的最大化投影s，s=uTX；二是確保投影空間是稀疏的，使得只有該空間中的顯著特征具有非零表示。其中uTX是所有特征的線性組合，u中的元素決定了每個特征的重要性或權(quán)重。如果u是一個稀疏向量，那么某些無關(guān)特征的權(quán)重為零，權(quán)重非零的特征子集就是期望最大預測信息的特征子集，僅選擇最顯著的特征（具有非零系數(shù)），即最具代表性的特征。在所提出的算法中，一次必須檢查數(shù)據(jù)矩陣的一行，因此該方法可擴展到大型數(shù)據(jù)集，但該方法不適用于較高維數(shù)據(jù)。

Masaeli等人[66]提出了一種使用l1/l∞正則化誘導矩陣稀疏性的方法。在該方法中，設(shè)W=(w1,w2,…,wd)T∈?d×d是數(shù)據(jù)X?WX上大小為d×d的變換矩陣（其中wj,j=1,2,…,d表示權(quán)重向量），特征選擇可以描述為：

其中，wj是矩陣W的第j行，代表wj的無窮范數(shù)，λ是正則化參數(shù)。其基本是想是：設(shè)wjk為變換矩陣W的元素，若特征fj沒有被算法選擇，則W的第j行的所有元素應(yīng)該為零（即?k,wjk=0），特征fj對特征選擇標準HSIC(W)沒有貢獻。如果fj被算法選擇，這意味著對于fj來說，W的第j行至少有一個元素是非零的，fj對HSIC(W)是有貢獻的。因此，強制W具有更多的零行可以解釋為選擇更少的特征。利用這個思想，通過添加l1/l∞正則化來加強矩陣W行的稀疏性，以符合特征選擇標準HSIC(W)。l∞范數(shù)表示向量wj元素絕對值的最大值，l1范數(shù)可以導致矩陣稀疏[67-68]。原則上，該方法誘導每行元素最大絕對值的稀疏性。正則化參數(shù)λ控制著HSIC(W)和稀疏性之間的權(quán)衡，增加λ意味著迫使更多的行為零，這將移除更多的特征。λ=0的極端情況下，會選擇所有特征，相反，對于趨于無窮大的λ，則不會選擇任何特征(W≡0)。因此，控制λ從零到無窮大的范圍可以理解為所選特征數(shù)量從d到零的范圍。此外，通過允許W的非對角元素非零，不僅可以選擇最相關(guān)特征，而且還能自動消除冗余。該方法是非凸的，因此需要從許多不同的初始點重新啟動以選擇良好的特征，這在計算上是昂貴的。

為了獲得特征的稀疏性，Yamada等人[69]在Lasso回歸模型[67]的基礎(chǔ)上提出了一種基于HSIC Lasso的特征選擇方法。該方法使用一組核函數(shù)來選擇信息量最大的非冗余特征，通過解決Lasso問題找到解決方案。其具體形式為：

此外，許多學者提出了一些擴展技術(shù)，用來改進HSIC Lasso模型。Ren等人[71]提出一種新的方法，稱為基于HSIC-Lasso的Granger因果分析模型（HSIC-Lasso-GC），用于揭示多元時間序列之間的非線性因果關(guān)系。該方法可以同時獲得多個輸入變量到輸出變量的因果關(guān)系分析結(jié)果。此外，將輸入和輸出變量映射到RKHS中，通過RKHS揭示非線性因果關(guān)系。模型中有許多未知參數(shù)需要確定，如核函數(shù)參數(shù)、正則化參數(shù)等，從而使得算法復雜度變高，系統(tǒng)運行成本增加，算法不具備普適性等問題。Yamada等人[72]提出一種稱為最小角度非線性分布（least angle non-linear distribution，LAND）的特征選擇方法，將最小角度回歸（least angle regression，LARS）和HSIC結(jié)合起來，能夠有效地利用非線性特征的依賴關(guān)系。該方法擴展了新的HSIC Lasso模型，以處理超高維和大規(guī)模數(shù)據(jù)集，并通過利用參數(shù)空間稀疏的LARS算法的非負變量來有效地找到全局最優(yōu)解。此外，該方法保證了以最小的冗余度找到最大預測特征的最優(yōu)子集，從而獲得更高的預測能力和更好的可解釋性，但不可避免地增加了算法的運行成本且算法不具備普適性。Damodaran等人[73]在RKHS中開發(fā)了一種新的基于代理核和HSIC的類可分性矩陣，設(shè)計了一個基于Lasso的框架，將所提出的類可分性矩陣和Lasso模型耦合到一個稱為HSIC-SK Lasso（HSIC-surrogate kernel Lasso）的統(tǒng)一框架中執(zhí)行特征選擇。該框架可以選擇特征子集，增加類別可分性信息，同時避免了在選擇類別、鑒別特征時所涉及的計算密集的子集搜索操作。它通過基于類的數(shù)量而不是訓練樣本的數(shù)量來修改輸入和輸出項及其長度，從而提高HSIC Lasso的計算效率，但因為訓練集的變化而產(chǎn)生不穩(wěn)定的特征往往會影響模型的穩(wěn)定性。SpHSIC（sparse HSIC regression）[74]是一種基于HSIC的通用非線性特征選擇算法，是著名的最小冗余最大相關(guān)特征選擇算法的連續(xù)優(yōu)化變體。具體來說，SpHSIC由兩部分組成，一方面是凸HSIC損失函數(shù)，另一方面是正則化項。在稀疏性假設(shè)下，該方法提出了由一個懲罰模型來恢復準確的稀疏支持，即關(guān)鍵特征，其中懲罰集由Lasso[67]、Bridge[75]、MCP[76]和SCAD[77]給出，除了Lasso外，其余都是非凸的。這也改進了HSIC Lasso模型。

這些算法都是在特征選擇標準中引入權(quán)重來獲得特征的稀疏性，從而選擇最優(yōu)的特征子集。但是方法（14）和方法（16）都是非凸優(yōu)化問題，要找到最優(yōu)解的計算量很大。通過引入Lasso技術(shù)來將問題轉(zhuǎn)化為凸優(yōu)化問題，可以有效地計算全局最優(yōu)解。

3.3 其他方法

除了上述方法，許多學者也提出一些其他方法進行特征選擇，主要分為基于HSIC變體的方法和引入正則化項的方法，分別闡述如下。

對于使用HSIC變體形式的特征選擇方法，Yamada等人[78]提出一種稱為aHSIC（additive HSIC）的檢測度量，用于解決高維時間序列數(shù)據(jù)變化點檢測問題。aHSIC的一個新穎之處在于，若設(shè)置適當?shù)膮?shù)α，則可以僅僅基于與輸出相關(guān)的特征來進行依賴性測量。因此，與傳統(tǒng)的檢測方法相比，aHSIC在噪聲特征方面比現(xiàn)有方法更具魯棒性，適用于高維時間序列數(shù)據(jù)，但同時也使得算法訓練時間變長，系統(tǒng)運行成本增加。Kong等人[79]提出一種用于圖形分類的多標簽特征選擇方法（gMLC），用于有效地搜索具有多標簽圖對象的最優(yōu)子圖特征。該方法首先基于給定的具有多個標簽的圖數(shù)據(jù)集，推導出一個子圖特征的評估準則，稱為gHSIC，用來估計子圖特征與圖的多個標簽之間的依賴性。然后，為了避免子圖特征的窮舉，提出一種分支定界算法，通過使用多個標簽修剪子圖搜索空間來有效地搜索最優(yōu)子圖特征。但該算法只使用簡單的策略構(gòu)造標簽核矩陣，如何選擇其他類型的標簽核來更有效地利用標簽之間的相關(guān)性仍需進一步探索。與最大化特征和類標簽之間的HSIC值的方法相反，Camps-Valls等人[80]提出通過最小化HSICp-value來選擇特征。因為作為衡量特征與標簽獨立性大小的標準，p-value比HSIC經(jīng)驗估計更加敏感。p-value越大則說明特征與標簽之間的獨立性越強，反之，說明兩者的獨立性越弱。該方法在多光譜、高光譜和SAR數(shù)據(jù)的處理上表現(xiàn)出良好性能，特別適合于每個維度標記樣本數(shù)量相對較少的情況，但對于更多的標記樣本則表現(xiàn)不佳。Xu[81]指出非對角元素本質(zhì)上描述了特征的線性條件冗余，并利用HSIC矩陣中的所有元素定義了兩個新的多標簽特征選擇準則：HSIC-avg和HSIC-max。對于候選特征，該方法最大化其相關(guān)性并最小化其平均或最大冗余，通過將特征排序和順序正向選擇相結(jié)合，構(gòu)成一種高效的混合搜索策略。前者根據(jù)特征之間的相關(guān)性對所有特征進行降序排序，而后者通過相關(guān)性最大化和冗余最小化來找出最具鑒別能力的特征。在多個數(shù)據(jù)集上的實驗結(jié)果表明，該方法是高效的。該方法具備多種算法的優(yōu)點，在冗余特征的處理上有顯著的效果，可以提高模型的泛化性能和精度，但不可避免地帶來了算法運行時間成本增加且普適性不高等問題。

對于在目標函數(shù)中引入正則化項的特征選擇方法，Jiang等人[82]提出了一種基于稀疏正則化和相關(guān)性最大化的半監(jiān)督多標簽特征選擇方法（FSSRDM），將半監(jiān)督學習、l2,1范數(shù)和HSIC集成到一個框架中，在這個框架中，標記和未標記的數(shù)據(jù)都被用于特征的選擇，而且同時考慮了特征與標簽之間的依賴性和標簽與標簽之間的相關(guān)性。該方法利用HSIC來捕獲特征和標簽之間的依賴關(guān)系，并試圖最大化這種依賴性，以便利用這種依賴關(guān)系和有限的標簽訓練數(shù)據(jù)。此外，該方法還采用了l2,1范數(shù)來選擇最相關(guān)的特征，防止過擬合，但不可避免地增加了算法的參數(shù)個數(shù)，造成算法的運行時間變長，復雜度更高。Liu等人[83]提出了一種廣義多視圖無監(jiān)督特征選擇方法（gMUFS），同時探索多視圖的互補性以及聚類結(jié)構(gòu)與所選特征之間的復雜相關(guān)性。具體地說，通過學習多視圖一致性偽標簽矩陣，利用HSIC在核空間中最大化一致性簇結(jié)構(gòu)與所選特征之間的依賴關(guān)系，選擇最有價值的特征。得益于不同視圖的互補性，該方法可以很好地識別潛在的聚類結(jié)構(gòu)。為了簡單高效，該算法采用內(nèi)積核函數(shù)，考慮更多核函數(shù)來獲得更好的性能值得進一步探索。

3.4 算法性能比較

每種算法都存在自身的優(yōu)缺點，上述所提出的幾種算法在特征選擇問題上的性能總結(jié)如表1所示。

表1 基于HSIC的特征選擇算法性能比較Table 1 Performance comparison of HSIC-based feature selection algorithms

基于HSIC的優(yōu)點，使用其進行特征選擇的一個重要特性是其通用性。各種基于HSIC及其變體的特征選擇方法在實際應(yīng)用中的效果不同，其中最常用的是貪婪或隨機搜索策略，Song等人通過選擇不同的核函數(shù)，使得BAHSIC以一種原則性的方式容納二分類、多類和回歸等問題于一身，但無論是BAHSIC還是FOHSIC等都只能處理較小規(guī)模數(shù)據(jù)。為了解決大規(guī)模數(shù)據(jù)下的特征選擇問題，提出了其他的方法，包括LAND、稀疏SVD等。此外，諸如aHSIC、gHSIC、HSIC p-value等HSIC的變體形式也擴展了HSIC在特征選擇領(lǐng)域的應(yīng)用。

4 結(jié)束語

作為一種典型的依賴性度量方法，HSIC能夠在核空間中評估兩個變量之間的相關(guān)性，不需要密度估計，并且具有良好的一致性收斂保證，這比在原始空間中測量相關(guān)性更為有效和靈活。此外，HSIC方法是一種非參數(shù)方法，不要求數(shù)據(jù)符合某種特定分布，不依賴先驗知識庫，這使得HSIC方法具有很好的推廣性。同時，核方法的使用還能帶來計算上的高效性，且豐富的核選擇可以直接應(yīng)用于輸入數(shù)據(jù)和標簽。此外，HSIC的經(jīng)驗估計的計算復雜度是O(m2)，只需要計算核矩陣K和L，不涉及密度估計。因此，HSIC給特征選擇算法提供了豐富的設(shè)計思路和廣泛的應(yīng)用前景，進一步推動了特征選擇的研究與發(fā)展。本文系統(tǒng)闡述了幾種典型的基于HSIC的特征選擇方法，希望能夠為后來的研究者提供有效的參考，從中獲得新的啟發(fā)。盡管基于HSIC的特征選擇方法應(yīng)用廣泛，但仍存在一些有待解決的問題，可以從以下幾個方面進行概述：

（1）HSIC不僅廣泛應(yīng)用于統(tǒng)計獨立性測試，還被廣泛應(yīng)用于各種學習問題，如特征選擇、降維、聚類和其他學習范式，核函數(shù)應(yīng)根據(jù)當前的任務(wù)進行預定義，即由于沒有實用的核函數(shù)選擇方法，需要研究者手動選擇核函數(shù)。雖然已經(jīng)有多種通用核函數(shù)可供沒有先驗知識時使用（如高斯核函數(shù)等），但對于特定的學習任務(wù)和實際應(yīng)用，研究如何選擇能使模型高效學習的核函數(shù)仍是非常重要和有價值的。

（2）根據(jù)現(xiàn)有的文獻，大多數(shù)特征選擇方法都需要指定超參數(shù)，例如特征數(shù)量、最優(yōu)子集數(shù)量或每種方法使用的特征選擇技術(shù)固有的其他參數(shù)，對于模型參數(shù)的選擇尚無明確的理論依據(jù)，且在不同的數(shù)據(jù)集上有不同的表現(xiàn)，在大多數(shù)情況下不可能知道每個數(shù)據(jù)集的最佳參數(shù)值。雖然已經(jīng)提出了許多優(yōu)化方法來改進學習模型，但如何高效學習模型的最優(yōu)組合參數(shù)仍需進一步探索。且實際問題中的數(shù)據(jù)規(guī)模較大，研究出一種高效且穩(wěn)定的算法來優(yōu)化特征選擇模型，仍具有挑戰(zhàn)性。

（3）在現(xiàn)實問題中混合數(shù)據(jù)非常常見，例如在生物醫(yī)學和醫(yī)療保健、社會經(jīng)濟學和商業(yè)、軟件成本評估等領(lǐng)域，在由混合數(shù)據(jù)描述的問題中，如何選擇相關(guān)特征是一個重要的問題。目前大多數(shù)方法僅針對數(shù)值數(shù)據(jù)設(shè)計，因此對于混合數(shù)據(jù)，有開發(fā)新的特征選擇算法的空間。

（4）目前基于HSIC的無監(jiān)督特征選擇方向的研究略少，而現(xiàn)實世界產(chǎn)生的數(shù)據(jù)中標簽數(shù)據(jù)通常很少，人工標記相當昂貴，且未標記的數(shù)據(jù)包含的信息要豐富得多。因此，無監(jiān)督特征選擇在實踐中很重要，設(shè)計出高效且穩(wěn)定的基于HSIC的無監(jiān)督特征選擇模型是一個值得研究的方向。