胡振威,汪廷華,周慧穎
贛南師范大學 數(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ā)展方向。
根據(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]。
本章簡要描述了RKHS之間互協(xié)方差算子所必需的功能分析背景[13],并介紹了互協(xié)方差算子的HS范數(shù),最后給出關(guān)于HSIC的初步概述。
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)的運算。
設(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ù),正則化隱含在核的選擇中,這與早期的核依賴估計工作都不同。
特征選擇是離散空間上的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é)束,得到滿足用戶需求的特征子集。
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)解。
除貪婪方法外,使用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)解。
除了上述方法,許多學者也提出一些其他方法進行特征選擇,主要分為基于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ù)來獲得更好的性能值得進一步探索。
每種算法都存在自身的優(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)用。
作為一種典型的依賴性度量方法,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)督特征選擇模型是一個值得研究的方向。