模式識(shí)別第11章獨(dú)立于算法的機(jī)器學(xué)習(xí)

第十一章獨(dú)立于算法的機(jī)器學(xué)習(xí)11.1模式識(shí)別中的哲學(xué)這里討論的是一些獨(dú)立于具體識(shí)別算法的一般性原理，但可以適用于任何一個(gè)特定的識(shí)別方法：沒有免費(fèi)午餐定理；丑小鴨定理；Occam剃刀原理。沒有免費(fèi)的午餐定理

（NFL,NoFreeLunchTheorem）不存在一個(gè)與具體應(yīng)用無關(guān)的，普遍適用的“最優(yōu)分類器”；學(xué)習(xí)算法必須要作出一個(gè)與問題領(lǐng)域有關(guān)的“假設(shè)”，分類器必須與問題域相適應(yīng)。丑小鴨定理（UglyDuckling）不存在與問題無關(guān)的“最優(yōu)”的特征集合或?qū)傩约?；也同樣不存在與問題無關(guān)的模式之間的“相似性度量”。Occam剃刀原理設(shè)計(jì)者不應(yīng)該選用比“必要”更加復(fù)雜的分類器，“必要”是由訓(xùn)練數(shù)據(jù)的擬合情況決定的；在對(duì)訓(xùn)練數(shù)據(jù)分類效果相同時(shí)，“簡(jiǎn)單的”分類器往往優(yōu)于“復(fù)雜的”分類器；根據(jù)“沒有免費(fèi)午餐定理”，不能說“簡(jiǎn)單的”分類器對(duì)“復(fù)雜的”分類器具有天生的優(yōu)越性，但在現(xiàn)實(shí)世界中遇到的各種問題，這種優(yōu)越性往往是存在。11.2分類性能評(píng)價(jià)方法使用什么樣本測(cè)試分類器的性能？如何劃分樣本集?兩分法：隨機(jī)地將樣本集D劃分為不相交的兩個(gè)集合Dl和Dt，分別用于學(xué)習(xí)分類器和測(cè)試分類器性能。訓(xùn)練樣本集(Dl)測(cè)試樣本集(Dt)分類性能評(píng)價(jià)方法交叉驗(yàn)證：將樣本集D隨機(jī)地劃分為互不相交的k個(gè)子集：使用k-1個(gè)子集的樣本訓(xùn)練一個(gè)分類器；測(cè)試沒有參與訓(xùn)練子集的樣本；重復(fù)k次取平均。留一法（刀切法）：k=nD1…D2Dk-1DkDlDt分類性能評(píng)價(jià)方法Bootstrap方法（自助法）:從樣本集D中有放回地抽取n個(gè)樣本用于訓(xùn)練；從樣本集D中有放回地抽取n個(gè)樣本用于測(cè)試；重復(fù)k次取平均。樣本集D樣本集Dl樣本集Dt11.3分類設(shè)計(jì)的重采樣技術(shù)分類器設(shè)計(jì)的重采樣技術(shù)也被稱為“自適應(yīng)的權(quán)值重置和組合（arcing,adaptivereweightingandcombining）；這類方法的主要思想是利用同一個(gè)訓(xùn)練樣本集合構(gòu)造多個(gè)分類器，然后以某種方式將這些分類器組合成一個(gè)分類器；主要方法包括：bagging算法和boosting算法bagging算法從大小為n的原始數(shù)據(jù)集D中獨(dú)立隨機(jī)地抽取n’個(gè)數(shù)據(jù)(n’<n)，形成一個(gè)自助數(shù)據(jù)集；重復(fù)上述過程，產(chǎn)生出多個(gè)獨(dú)立的自助數(shù)據(jù)集；利用每個(gè)自助數(shù)據(jù)集訓(xùn)練出一個(gè)“分量分類器”；最終的分類結(jié)果由這些“分量分類器”各自的判別結(jié)果投票決定。boosting算法boosting算法同樣是利用訓(xùn)練樣本集合構(gòu)造多個(gè)分量分類器，它只要求這個(gè)分量分類器是一個(gè)弱分類器—準(zhǔn)確率比平均性能好即可。2類問題，3個(gè)分量分類器的訓(xùn)練算法：在數(shù)量為n的原始樣本集D中隨機(jī)選取n1個(gè)樣本構(gòu)成D1，利用D1訓(xùn)練出一個(gè)分類器C1；在樣本集D-D1中選擇被C1正確分類和錯(cuò)誤分類的樣本各一半組成樣本集D2，用D2訓(xùn)練出一個(gè)分類器C2；將樣本集D-D1-D2中所有C1和C2分類結(jié)果不同的樣本組成樣本集D3，訓(xùn)練出一個(gè)分類器C3；boosting的分類算法對(duì)新的樣本x進(jìn)行分類，如果C1和C2判別結(jié)果相同，則將x判別為此類別，否則以C3的結(jié)果作為x的類別；原始樣本集分量分類器組合分類器AdaBoost方法AdaBoost(adaptiveboosting)是boosting方法的一個(gè)重要變形，一般所說的boosting方法均是指AdaBoost；AdaBoost方法中，設(shè)計(jì)者可以不斷地增加分量分類器，直到達(dá)到足夠小的錯(cuò)誤率為止；總體分類結(jié)果是由各分量分類器加權(quán)平均得到，權(quán)重由分量分類器的錯(cuò)誤率確定。AdaBoost方法begininitializeD,kmax,W1(i)1/n,i=1,…,n；

k0;dokk+1

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

Ek用Wk(i)采樣D的樣本集測(cè)量Ck的訓(xùn)練誤差；

untilk=kmax；

endAdaBoost方法算法中Wk(i)為每一步迭代中對(duì)每個(gè)樣本的加權(quán)，Zk是歸一化因子，Ck為第k個(gè)分量分類器，αk為對(duì)Ck的加權(quán)；總體的判別函數(shù)由各分量分類器的加權(quán)平均得到： 其中為Ck分類器給出的判別結(jié)果。AdaBoost方法的推廣能力AdaBoost方法實(shí)際上是增加了分類器的復(fù)雜程度，但實(shí)踐表明此方法出現(xiàn)“過擬合”的現(xiàn)象極少，這是此方法最吸引人的地方。針對(duì)特征的Boosting算法特征選擇：就是從一組數(shù)量為n的特征中選擇出數(shù)量為m的最優(yōu)特征；最優(yōu)特征組合的評(píng)價(jià)標(biāo)準(zhǔn)；選擇出最優(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,with