胡振威，汪廷華，周慧穎

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

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

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

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

1 特征選擇概述

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

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

2 希爾伯特-施密特獨(dú)立性準(zhǔn)則

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

2.1 基于核方法的獨(dú)立性度量

HSIC是一種基于核的獨(dú)立性度量方法，該方法原理是在RKHS上定義互協(xié)方差算子，再?gòu)倪@些算子中推導(dǎo)出合適度量獨(dú)立性的統(tǒng)計(jì)量來計(jì)算獨(dú)立性的大小。HSIC采用的是Hilbert-Schmidt互協(xié)方差算子，通過對(duì)算子范數(shù)的經(jīng)驗(yàn)估計(jì)得到獨(dú)立性判斷準(zhǔn)則。

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

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

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

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

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

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

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

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

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

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

2.2 HSIC的經(jīng)驗(yàn)估計(jì)

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

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

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

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

3 基于HSIC的特征選擇

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

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

3.1 貪婪方法

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

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

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

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

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

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

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

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

實(shí)驗(yàn)表明，當(dāng)α=5時(shí)在實(shí)踐中的效果很好。

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

Masaeli等人[66]提出了一種使用l1/l∞正則化誘導(dǎo)矩陣稀疏性的方法。在該方法中，設(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對(duì)特征選擇標(biāo)準(zhǔn)HSIC(W)沒有貢獻(xiàn)。如果fj被算法選擇，這意味著對(duì)于fj來說，W的第j行至少有一個(gè)元素是非零的，fj對(duì)HSIC(W)是有貢獻(xiàn)的。因此，強(qiáng)制W具有更多的零行可以解釋為選擇更少的特征。利用這個(gè)思想，通過添加l1/l∞正則化來加強(qiáng)矩陣W行的稀疏性，以符合特征選擇標(biāo)準(zhǔn)HSIC(W)。l∞范數(shù)表示向量wj元素絕對(duì)值的最大值，l1范數(shù)可以導(dǎo)致矩陣稀疏[67-68]。原則上，該方法誘導(dǎo)每行元素最大絕對(duì)值的稀疏性。正則化參數(shù)λ控制著HSIC(W)和稀疏性之間的權(quán)衡，增加λ意味著迫使更多的行為零，這將移除更多的特征。λ=0的極端情況下，會(huì)選擇所有特征，相反，對(duì)于趨于無窮大的λ，則不會(huì)選擇任何特征(W≡0)。因此，控制λ從零到無窮大的范圍可以理解為所選特征數(shù)量從d到零的范圍。此外，通過允許W的非對(duì)角元素非零，不僅可以選擇最相關(guān)特征，而且還能自動(dòng)消除冗余。該方法是非凸的，因此需要從許多不同的初始點(diǎn)重新啟動(dòng)以選擇良好的特征，這在計(jì)算上是昂貴的。

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

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

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

3.3 其他方法

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

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

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

3.4 算法性能比較

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

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

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

4 結(jié)束語

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

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

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

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

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