獨立于算法的機器學習

第十一章獨立于算法的機器學習.11.1模式識別中的哲學這里討論的是一些獨立于具體識別算法的一般性原理，但可以適用于任何一個特定的識別方法：沒有免費午餐定理；丑小鴨定理；Occam剃刀原理。沒有免費的午餐定理

〔NFL,NoFreeLunchTheorem〕不存在一個與具體應用無關的，普遍適用的“最優(yōu)分類器〞；學習算法必須要作出一個與問題領域有關的“假設〞，分類器必須與問題域相適應。丑小鴨定理〔UglyDuckling〕不存在與問題無關的“最優(yōu)〞的特征集合或屬性集合；也同樣不存在與問題無關的模式之間的“相似性度量〞。Occam剃刀原理設計者不應該選用比“必要〞更加復雜的分類器，“必要〞是由訓練數據的擬合情況決定的；在對訓練數據分類效果相同時，“簡單的〞分類器往往優(yōu)于“復雜的〞分類器；根據“沒有免費午餐定理〞，不能說“簡單的〞分類器對“復雜的〞分類器具有天生的優(yōu)越性，但在現實世界中遇到的各種問題，這種優(yōu)越性往往是存在。11.2分類設計的重采樣技術分類器設計的重采樣技術也被稱為“自適應的權值重置和組合〔arcing,adaptivereweightingandcombining〕；這類方法的主要思想是利用同一個訓練樣本集合構造多個分類器，然后以某種方式將這些分類器組合成一個分類器；主要方法包括：bagging算法和boosting算法bagging算法從大小為n的原始數據集D中獨立隨機地抽取n’個數據(n’<n)，形成一個自助數據集；重復上述過程，產生出多個獨立的自助數據集；利用每個自助數據集訓練出一個“分量分類器〞；最終的分類結果由這些“分量分類器〞各自的判別結果投票決定。boosting算法boosting算法同樣是利用訓練樣本集合構造多個分量分類器，它只要求這個分量分類器是一個弱分類器—準確率比平均性能好即可。2類問題，3個分量分類器的訓練算法：在數量為n的原始樣本集D中隨機選取n1個樣本構成D1，利用D1訓練出一個分類器C1；在樣本集D-D1中選擇被C1正確分類和錯誤分類的樣本各一半組成樣本集D2，用D2訓練出一個分類器C2；將樣本集D-D1-D2中所有C1和C2分類結果不同的樣本組成樣本集D3，訓練出一個分類器C3；boosting的分類算法對新的樣本x進行分類，如果C1和C2判別結果相同，那么將x判別為此類別，否那么以C3的結果作為x的類別；原始樣本集分量分類器組合分類器AdaBoost方法AdaBoost(adaptiveboosting)是boosting方法的一個重要變形，一般所說的boosting方法均是指AdaBoost；AdaBoost方法中，設計者可以不斷地增加分量分類器，直到到達足夠小的錯誤率為止；總體分類結果是由各分量分類器加權平均得到，權重由分量分類器的錯誤率確定。AdaBoost方法begininitializeD,kmax,W1(i)

1/n,i=1,…,n；

k0;dokk+1

訓練使用按照Wk(i)采樣D的弱分類器Ck；

Ek

用Wk(i)采樣D的樣本集測量Ck的訓練誤差；

untilk=kmax；

endAdaBoost方法算法中Wk(i)為每一步迭代中對每個樣本的加權，Zk是歸一化因子，Ck為第k個分量分類器，αk為對Ck的加權；總體的判別函數由各分量分類器的加權平均得到： 其中為Ck分類器給出的判別結果。AdaBoost方法的推廣能力AdaBoost方法實際上是增加了分類器的復雜程度，但實踐說明此方法出現“過擬合〞的現象極少，這是此方法最吸引人的地方。針對特征的Boosting算法特征選擇：就是從一組數量為n的特征中選擇出數量為m的最優(yōu)特征；最優(yōu)特征組合的評價標準；選擇出最優(yōu)特征組合的算法；Boosting可以作為特征選擇的方法。AdaBoost特征選擇算法Givenexamples(x1,y1),…,(xn,yn),whereyi=0,1fornegativeandpositiveexamplesrespectively;Initializeweightsw1,i=1/2m,1/2lforyi=0,1respectively,wheremandlarethenumberofnegativesandpositivesrespectively;Fort=1,…,T:Normalizetheweights: sothatwtisaprobabilitydistribution.AdaBoost特征選擇算法Foreachfeature,j,trainaclassifierhjwhichisrestrictedtousingasinglefeature.Theerrorisevaluatedwithrespecttowt,Choosetheclassifierht,withthelowesterrorUpdatetheweights: whereei

=0ifexamplexiisclassifiedcorrectly,ei

=1otherwise,andThefinalclassifieris:11.3分類器的評價和比較在分類器設計好后，我們只能計算出分類器在訓練樣本集上的錯誤率，而不能計算出在測試樣本集上的錯誤率；可以采用統(tǒng)計量估計中的重采樣技術來對測試樣本錯誤率進行估計，具體方法有：交叉驗證；刀切法；自助法；交叉驗證(CrossValidation)簡單驗證：將數量為n的訓練樣本集D分成兩局部，一局部作為訓練集，用于訓練分類器，另一局部作為驗證集，用于估計測試錯誤率；m-重交叉驗證：將D分成m個集合，每個集合包含n/m個樣本，每次用m-1個集合的樣本訓練分類器，用剩余的一個集合測試，最后將m個測試結果平均，作為測試錯誤率的估計；刀切法〔Jackknife〕刀切法實際上是m=n時的m-重交叉驗證。在數量為n的樣本集D中每次留一個樣本，用其它樣本訓練分類器，用留下的一個樣本測試錯誤率，測試錯誤率為： p