第十一章：特征選擇與稀疏學(xué)習(xí)特征特征描述物體的屬性特征的分類相關(guān)特征:對當(dāng)前學(xué)習(xí)任務(wù)有用的屬性無關(guān)特征:與當(dāng)前學(xué)習(xí)任務(wù)無關(guān)的屬性冗余特征*:其所包含信息能由其他特征推演出來*為簡化討論，本章暫不涉及冗余特征例子：西瓜的特征西瓜的特征顏色紋理觸感根蒂聲音相關(guān)特征無關(guān)特征好瓜壞瓜當(dāng)前任務(wù)：西瓜是否是好瓜特征選擇特征選擇從給定的特征集合中選出任務(wù)相關(guān)特征子集必須確保不丟失重要特征原因減輕維度災(zāi)難：在少量屬性上構(gòu)建模型降低學(xué)習(xí)難度：留下關(guān)鍵信息例子：判斷是否好瓜時的特征選擇西瓜的特征顏色紋理觸感根蒂聲音相關(guān)特征無關(guān)特征好瓜壞瓜當(dāng)前任務(wù)：西瓜是否是好瓜特征選擇：選擇當(dāng)前任務(wù)相關(guān)特征特征選擇的一般方法遍歷所有可能的子集計算上遭遇組合爆炸，不可行可行方法產(chǎn)生初始候選子集評價候選子集的好壞基于評價結(jié)果產(chǎn)生下一個候選子集兩個關(guān)鍵環(huán)節(jié)：子集搜索和子集評價子集搜索前向搜索：逐漸增加相關(guān)特征后向搜索：從完整的特征集合開始，逐漸減少特征雙向搜索：每一輪逐漸增加相關(guān)特征，同時減少無關(guān)特征用貪心策略選擇包含重要信息的特征子集特征集合

當(dāng)前最優(yōu)子集優(yōu)于上一輪最優(yōu)子集？YN前向搜索最優(yōu)子集初始為空集，特征集合初始時包括所有給定特征結(jié)束子集評價特征子集確定了對數(shù)據(jù)集的一個劃分每個劃分區(qū)域?qū)?yīng)著特征子集的某種取值樣本標(biāo)記對應(yīng)著對數(shù)據(jù)集的真實劃分通過估算這兩個劃分的差異，就能對特征子集進(jìn)行評價；與樣本標(biāo)記對應(yīng)的劃分的差異越小，則說明當(dāng)前特征子集越好用信息熵進(jìn)行子集評價

常見的特征選擇方法常見的特征選擇方法大致分為如下三類：過濾式包裹式嵌入式將特征子集搜索機(jī)制與子集評價機(jī)制相結(jié)合，即可得到特征選擇方法過濾式選擇Relief(RelevantFeatures)方法[KiraandRendell,1992]為每個初始特征賦予一個“相關(guān)統(tǒng)計量”，度量特征的重要性特征子集的重要性由子集中每個特征所對應(yīng)的相關(guān)統(tǒng)計量之和決定設(shè)計一個閾值，然后選擇比閾值大的相關(guān)統(tǒng)計量分量所對應(yīng)的特征或者指定欲選取的特征個數(shù)，然后選擇相關(guān)統(tǒng)計量分量最大的指定個數(shù)特征如何確定相關(guān)統(tǒng)計量？先用特征選擇過程過濾原始數(shù)據(jù)，再用過濾后的特征來訓(xùn)練模型；特征選擇過程與后續(xù)學(xué)習(xí)器無關(guān)Relief方法中相關(guān)統(tǒng)計量的確定

Relief方法的多類拓展

Relief方法是為二分類問題設(shè)計的，其擴(kuò)展變體Relief-F[Kononenko,1994]能處理多分類問題

包裹式選擇包裹式特征選擇的目的就是為給定學(xué)習(xí)器選擇最有利于其性能、“量身定做”的特征子集包裹式選擇方法直接針對給定學(xué)習(xí)器進(jìn)行優(yōu)化，因此從最終學(xué)習(xí)器性能來看，包裹式特征選擇比過濾式特征選擇更好包裹式特征選擇過程中需多次訓(xùn)練學(xué)習(xí)器，計算開銷通常比過濾式特征選擇大得多包裹式選擇直接把最終將要使用的學(xué)習(xí)器的性能作為特征子集的評價準(zhǔn)則LVW包裹式特征選擇方法基本步驟在循環(huán)的每一輪隨機(jī)產(chǎn)生一個特征子集在隨機(jī)產(chǎn)生的特征子集上通過交叉驗證推斷當(dāng)前特征子集的誤差進(jìn)行多次循環(huán)，在多個隨機(jī)產(chǎn)生的特征子集中選擇誤差最小的特征子集作為最終解*

*若有運行時間限制，則該算法有可能給不出解LVW（LasVegasWrapper）[LiuandSetiono,1996]在拉斯維加斯方法框架下使用隨機(jī)策略來進(jìn)行子集搜索，并以最終分類器的誤差作為特征子集評價準(zhǔn)則嵌入式選擇

嵌入式特征選擇是將特征選擇過程與學(xué)習(xí)器訓(xùn)練過程融為一體，兩者在同一個優(yōu)化過程中完成，在學(xué)習(xí)器訓(xùn)練過程中自動地進(jìn)行特征選擇嶺回歸

(ridgeregression)[TikhonovandArsenin,1977]易獲得稀疏解，是一種嵌入式特征選擇方法

等值線即取值相同的點的連線

近端梯度下降（ProximalGradientDescend，簡稱PGD）解法[BoydandVandenberghe,2004]L1正則化問題的求解(2)

L1正則化問題的求解(3)

稀疏表示將數(shù)據(jù)集考慮成一個矩陣，每行對應(yīng)一個樣本，每列對應(yīng)一個特征矩陣中有很多零元素，且非整行整列出現(xiàn)稀疏表達(dá)的優(yōu)勢：文本數(shù)據(jù)線性可分存儲高效能否將稠密表示的數(shù)據(jù)集轉(zhuǎn)化為“稀疏表示”，使其享受稀疏表達(dá)的優(yōu)勢？字典學(xué)習(xí)

為普通稠密表達(dá)的樣本找到合適的字典，將樣本轉(zhuǎn)化為稀疏表示，這一過程稱為字典學(xué)習(xí)字典學(xué)習(xí)的解法(2)

為了不破壞的稀疏性，僅保留非零元素，僅保留與非零元素的乘積項壓縮感知數(shù)據(jù)傳輸中，能否利用接收到的壓縮、丟包后的數(shù)字信號，精確重構(gòu)出原信號？壓縮感知(compressivesensing)

[Cándesetal.,2006,Donoho,2006]

為解決此類問題提供了新的思路.能否利用部分?jǐn)?shù)據(jù)恢復(fù)全部數(shù)據(jù)？

如傅里葉變換，余弦變換，小波變換等限定等距性

壓縮感知的優(yōu)化目標(biāo)和解法

矩陣補(bǔ)全客戶對書籍的喜好程度的評分“矩陣補(bǔ)全”技術(shù)解決此類問題能否將表中已經(jīng)通過讀者評價得到的數(shù)據(jù)當(dāng)作部分信號