特征選擇與稀疏學(xué)習(xí)
原理
11.1 子集搜索與評(píng)價(jià)
- 對(duì)一個(gè)學(xué)習(xí)任務(wù)來(lái)說(shuō)，給定屬性集，其中有些屬性可能很關(guān)鍵、很有用，另一些屬性則可能沒(méi)什么用。我們將屬性稱為“特征”(feature)，對(duì)當(dāng)前學(xué)習(xí)任務(wù)有用的屬性稱為“相關(guān)特征”(relevant feature)、沒(méi)什么用的屬性稱為“無(wú)關(guān)特征”(irrelevant feature)、從給定的特征集合中選擇出相關(guān)特征子集的過(guò)程，稱為“特征選擇”(feature selection)。
- 特征選擇是一個(gè)重要的“數(shù)據(jù)預(yù)處理”(data preprocessing)過(guò)程，在現(xiàn)實(shí)機(jī)器學(xué)習(xí)任務(wù)中，獲得數(shù)據(jù)之后通常先進(jìn)行特征選擇，此后再訓(xùn)練學(xué)習(xí)器，那么，為什么要進(jìn)行特征選擇呢？
- 首先，我們?cè)诂F(xiàn)實(shí)任務(wù)中經(jīng)常會(huì)遇到維數(shù)災(zāi)難問(wèn)題，這是由于屬性過(guò)多而造成的，若能從中選擇出重要的特征，使得后續(xù)學(xué)習(xí)過(guò)程僅需在一部分特征上構(gòu)建模型，則維數(shù)災(zāi)難問(wèn)題會(huì)大為減輕。從這個(gè)意義上說(shuō)，特征選擇與降維有著相似的動(dòng)機(jī)；事實(shí)上，它們是處理高維數(shù)據(jù)的兩大主流技術(shù)。
- 第二個(gè)原因是，去除不相關(guān)特征往往會(huì)降低學(xué)習(xí)任務(wù)的難度，這就像偵探破案一樣，若將紛繁復(fù)雜的因素抽絲剝繭，只留下關(guān)鍵因素，則真相往往更易看清。
- 需注意的是，特征選擇過(guò)程必須確保不丟失重要特征，否則后續(xù)學(xué)習(xí)過(guò)程會(huì)因?yàn)橹匾畔⒌娜笔Ф鵁o(wú)法獲得好的性能。給定數(shù)據(jù)集，若學(xué)習(xí)任務(wù)不同，則相關(guān)特征很可能不同。因此，特征選擇中所謂的“無(wú)關(guān)特征”是指與當(dāng)前學(xué)習(xí)任務(wù)無(wú)關(guān)。有一類特征稱為“冗余特征”(redundant feature)，它們所包含的信息能從其他特征中推演出來(lái)。冗余特征在很多時(shí)候不起作用，去除它們會(huì)減輕學(xué)習(xí)過(guò)程的負(fù)擔(dān)。但有時(shí)冗余特征會(huì)降低學(xué)習(xí)任務(wù)的難度，更確切地說(shuō)，若某個(gè)冗余特征恰好對(duì)應(yīng)了完成學(xué)習(xí)任務(wù)所需的“中間概念”，則該冗余特征是有益的。
- 欲從初始的特征集合中選取一個(gè)包含了所有重要信息的特征子集，若沒(méi)有任何領(lǐng)域知識(shí)作為先驗(yàn)假設(shè)，那就只好遍歷所有可能的子集了；然而這在計(jì)算上卻是不可行的，因?yàn)檫@樣做會(huì)遭遇組合爆炸，特征個(gè)數(shù)稍多就無(wú)法進(jìn)行?？尚械淖龇ㄊ钱a(chǎn)生一個(gè)“候選子集”，評(píng)價(jià)出它的好壞，基于評(píng)價(jià)結(jié)果產(chǎn)生下一個(gè)候選子集，再對(duì)其進(jìn)行評(píng)價(jià)，……這個(gè)過(guò)程持續(xù)進(jìn)行下去，直到無(wú)法找到更好的候選子集為止。顯然，這里涉及兩個(gè)關(guān)鍵環(huán)節(jié)：如何根據(jù)評(píng)價(jià)結(jié)果獲取下一個(gè)候選特征子集？如何評(píng)價(jià)候選特征子集的好壞？
- 第一個(gè)環(huán)節(jié)是“子集搜索”(subset search)問(wèn)題。給定特征集合 {a1, a2, .., ad}，我們可將每個(gè)特征看作一個(gè)候選子集，對(duì)這 d 個(gè)候選單特征子集進(jìn)行評(píng)價(jià)，假定 {a2} 最優(yōu)，于是將 {a2} 作為第一輪的選定集；然后，在上一輪的選定集中加入一個(gè)特征，夠成包含兩個(gè)特征的候選子集，假定在這 d -1 個(gè)候選兩特征子集中 {a2, a4} 最優(yōu)，且優(yōu)于 {a2}，于是將 {a2, a4} 作為本輪的選定集；……假定在第 k + 1 輪時(shí)，最優(yōu)的候選 (k + 1) 特征子集不如上一輪的選定集，則停止生成候選子集，并將上一輪選定的 k 特征集合作為特征選擇結(jié)果。這樣逐漸增加相關(guān)特征的策略稱為“前向”(forward)搜索。類似的，若我們從完整的特征集合開(kāi)始，每次嘗試去掉一個(gè)無(wú)關(guān)特征，這樣逐漸減少特征的策略稱為“后向”(backward)搜索。還可將前向與后向搜索結(jié)合起來(lái)，每一輪逐漸增加選定相關(guān)特征(這些特征在后續(xù)輪中將確定不會(huì)被去除)、同時(shí)減少無(wú)關(guān)特征，這樣的策略稱為“雙向”(bidirectional)搜索。顯然，上述策略都是貪心的，未必能得到最優(yōu)解。
- 第二個(gè)環(huán)節(jié)是“子集評(píng)價(jià)”(subset evaluation)問(wèn)題。信息增益 Gain(A)越大，意味著特征子集 A 包含的有助于分類的信息越多。于是，對(duì)于每個(gè)候選特征子集，我們可基于訓(xùn)練集 D 來(lái)計(jì)算其信息增益，以此作為評(píng)價(jià)準(zhǔn)則。
- 將特征子集搜索機(jī)制與子集評(píng)價(jià)機(jī)制相結(jié)合，即可得到特征選擇方法。例如將前向搜索與信息熵相結(jié)合，這顯然與決策樹(shù)算法非常相似。事實(shí)上，決策樹(shù)可用于特征選擇，樹(shù)結(jié)點(diǎn)的劃分屬性所組成的集合就是選擇出的特征子集。
- 常見(jiàn)的特征選擇方法大致可分為三類：過(guò)濾式(filter)、包裹式(wrapper)和嵌入式(embedding)。
11.2 過(guò)濾式
- 過(guò)濾式方法先對(duì)數(shù)據(jù)集進(jìn)行特征選擇，然后再訓(xùn)練學(xué)習(xí)器，特征選擇過(guò)程與后續(xù)學(xué)習(xí)器無(wú)關(guān)。這相當(dāng)于先用特征選擇過(guò)程對(duì)初始特征進(jìn)行“過(guò)濾”，再用過(guò)濾后的特征來(lái)訓(xùn)練模型。
- Relief (Relevant Features) 是一種著名的過(guò)濾式特征選擇方法，該方法設(shè)計(jì)了一個(gè)“相關(guān)統(tǒng)計(jì)量”來(lái)度量特征的重要性。該統(tǒng)計(jì)量是一個(gè)向量，其每個(gè)分量分別對(duì)應(yīng)于一個(gè)初始特征，而特征子集的重要性則是由子集中每個(gè)特征所對(duì)應(yīng)的相關(guān)統(tǒng)計(jì)量分量之和來(lái)決定。于是，最終只需指定一個(gè)閾值 t，然后選擇比 t 大的相關(guān)統(tǒng)計(jì)量分量所對(duì)應(yīng)的特征即可；也可指定欲選取的特征個(gè)數(shù) k， 然后選擇相關(guān)統(tǒng)計(jì)分量最大的 k 個(gè)特征。
11.3 包裹式選擇
- 與過(guò)濾式特征選擇不考慮后續(xù)學(xué)習(xí)器不同，包裹式特征選擇直接把最終將要使用的學(xué)習(xí)器的性能作為特征子集的評(píng)價(jià)標(biāo)準(zhǔn)。換言之，包裹式特征選擇的目的就是為給定學(xué)習(xí)器選擇最有利于其性能、“量身定做”的特征子集。
- 一般而言，由于包裹式特征選擇方法直接針對(duì)給定學(xué)習(xí)器進(jìn)行優(yōu)化，因此從最終學(xué)習(xí)器性能來(lái)看，包裹式特征選擇比過(guò)濾式特征選擇更好，但另一方面，由于在特征選擇過(guò)程中需多次訓(xùn)練學(xué)習(xí)器，因此包裹式特征選擇的計(jì)算開(kāi)銷通常比過(guò)濾式特征選擇大得多。
- LVW (Las Vegas Wrapper) 是一個(gè)典型的包裹式特征選擇方法。它在拉斯維加斯方法(Las Vegas method)框架下使用隨機(jī)策略來(lái)進(jìn)行子集搜索，并以最終分類器的誤差為子集評(píng)價(jià)準(zhǔn)則。
11.4 嵌入式與L1正則化
- 在過(guò)濾式和包裹式特征選擇方法中，特征選擇過(guò)程與學(xué)習(xí)器訓(xùn)練過(guò)程有明顯的分別；與此不同，嵌入式特征選擇是將特征選擇過(guò)程與學(xué)習(xí)器訓(xùn)練過(guò)程融為一體，兩者在同一個(gè)優(yōu)化過(guò)程中完成，即在學(xué)習(xí)器訓(xùn)練過(guò)程中自動(dòng)進(jìn)行了特征選擇。
- L1范數(shù)和L2范數(shù)正則化都有助于降低過(guò)擬合風(fēng)險(xiǎn)，但前者還會(huì)帶來(lái)一個(gè)額外的好處：它必后者更易于獲得“稀疏”(sparse)解，即它求得的 w 會(huì)有更少的非零分量。
11.5 稀疏表示與字典學(xué)習(xí)
- 不妨把數(shù)據(jù)集 D 考慮成一個(gè)矩陣，其每行對(duì)應(yīng)于一個(gè)樣本，每列對(duì)應(yīng)于一個(gè)特征。特征選擇所考慮的問(wèn)題是特征具有“稀疏性”，即矩陣中的許多列與當(dāng)前學(xué)習(xí)任務(wù)無(wú)關(guān)，通過(guò)特征選擇去除這些列，則學(xué)習(xí)器訓(xùn)練過(guò)程僅需在較小的矩陣上進(jìn)行，學(xué)習(xí)任務(wù)的難度可能有所降低，涉及的計(jì)算和存儲(chǔ)開(kāi)銷會(huì)減少，學(xué)得模型的可解釋性也會(huì)提高。
- 現(xiàn)在我們來(lái)考慮另一種稀疏性：D 所對(duì)應(yīng)的矩陣中存在很多零元素，但這些零元素并不是以整列、整行形式存在的。當(dāng)樣本具有這樣的稀疏表達(dá)形式時(shí)，對(duì)學(xué)習(xí)任務(wù)來(lái)說(shuō)會(huì)有不少好處，例如線性支持向量機(jī)之所以能在文本數(shù)據(jù)上有很好的性能，恰是由于文本數(shù)據(jù)在使用上述的字頻表示后具有高度的稀疏性，使大多數(shù)問(wèn)題變得線性可分。同時(shí)，稀疏樣本并不會(huì)造成存儲(chǔ)上的巨大負(fù)擔(dān)，因?yàn)橄∈杈仃囈延泻芏喔咝У拇鎯?chǔ)方法。
- 那么，若給定數(shù)據(jù)集 D 是稠密的，即普通非稀疏數(shù)據(jù)，能否將其轉(zhuǎn)化為“稀疏表示”(sparse representation)形式，從而享有稀疏性所帶來(lái)的好處呢？需要注意的是，我們所希望的稀疏表示是“恰當(dāng)稀疏”，而不是“過(guò)度稀疏”。
- 顯然，在一般的學(xué)習(xí)任務(wù)中（例如圖像分類）并沒(méi)有《現(xiàn)代漢語(yǔ)常用詞表》可用，我們需學(xué)習(xí)出這樣一個(gè)“字典”。我普通稠密表達(dá)的樣本找到合適的字典，將樣本轉(zhuǎn)化為合適的稀疏表示形式，從而使學(xué)習(xí)任務(wù)得以簡(jiǎn)化，模型復(fù)雜度得以降低，通常稱為“字典學(xué)習(xí)”(dictionary learning)，亦稱“稀疏編碼”(sparse coding)。這兩個(gè)稱為稍有差別，“字典學(xué)習(xí)”更側(cè)重于學(xué)得字典的過(guò)程，而“稀疏編碼”則更側(cè)重于對(duì)樣本進(jìn)行稀疏表達(dá)的過(guò)程。
11.6 壓縮感知
- 在現(xiàn)實(shí)任務(wù)中，我們常希望根據(jù)部分信息來(lái)恢復(fù)全部信息。壓縮感知(compressed sensing)為解決此類問(wèn)題提供了新的思路。
- 與特征選擇、稀疏表示不同，壓縮感知關(guān)注的是如何利用信號(hào)本身所具有的稀疏性，從部分觀測(cè)樣本中恢復(fù)原信號(hào)。通常認(rèn)為，壓縮感知分為“感知測(cè)量”和“重構(gòu)恢復(fù)”這兩個(gè)階段?！案兄獪y(cè)量”關(guān)注如何對(duì)原始信號(hào)進(jìn)行處理以獲得稀疏樣本表示，這方面的內(nèi)容涉及傅里葉變換、小波變換以及字典學(xué)習(xí)、稀疏編碼等，不少技術(shù)在壓縮感知提出之前就已在信號(hào)處理領(lǐng)域有很多研究；“重構(gòu)恢復(fù)”關(guān)注的是如何基于稀疏性從少量觀測(cè)中恢復(fù)原信號(hào)，這是壓縮感知的精髓，當(dāng)我們談到壓縮感知時(shí)，通常是指該部分。
