1、統(tǒng)計(jì)形式識(shí)別問(wèn)題的根本理論統(tǒng)計(jì)形式識(shí)別問(wèn)題的根本理論1統(tǒng)計(jì)形式識(shí)別問(wèn)題簡(jiǎn)介統(tǒng)計(jì)形式識(shí)別問(wèn)題可以看作是一個(gè)更廣義的問(wèn)題的特例，就是基于數(shù)據(jù)的機(jī)器學(xué)習(xí)問(wèn)題?；跀?shù)據(jù)的機(jī)器學(xué)習(xí)是現(xiàn)代智能技術(shù)中非常重要的一個(gè)方面，主要研究如何從一些觀測(cè)數(shù)據(jù)出發(fā)得出目前尚不能通過(guò)原理分析得到的規(guī)律，利用這些規(guī)律去分析客觀對(duì)象，對(duì)將來(lái)數(shù)據(jù)或無(wú)法觀測(cè)的數(shù)據(jù)進(jìn)展預(yù)測(cè)?，F(xiàn)實(shí)世界中存在大量我們尚無(wú)法準(zhǔn)確認(rèn)識(shí)但卻可以進(jìn)展觀測(cè)的事物，因此這種機(jī)器學(xué)習(xí)在從現(xiàn)代科學(xué)、技術(shù)到社會(huì)、經(jīng)濟(jì)等各領(lǐng)域中都有著非常重要的應(yīng)用。當(dāng)我們把要研究的規(guī)律抽象成分類關(guān)系時(shí)，這種機(jī)器學(xué)習(xí)問(wèn)題就是形式識(shí)別。統(tǒng)計(jì)是我們面對(duì)數(shù)據(jù)而又缺乏理論模型時(shí)最根本的分析手段，傳

2、統(tǒng)統(tǒng)計(jì)學(xué)所研究的是漸進(jìn)理論，即當(dāng)樣本數(shù)目趨向于無(wú)窮大時(shí)的極限特性，統(tǒng)計(jì)學(xué)中關(guān)于估計(jì)的一致性、無(wú)偏性和估計(jì)方差的界等，以及分類錯(cuò)誤率諸多結(jié)論，都具有這種漸近特性。但實(shí)際應(yīng)用中，這種前提條件卻往往得不到滿足，當(dāng)問(wèn)題處在高維空間時(shí)尤其如此，這實(shí)際上是包括形式識(shí)別和神經(jīng)網(wǎng)絡(luò)等在內(nèi)的現(xiàn)有機(jī)器學(xué)習(xí)理論和方法中的一個(gè)根本問(wèn)題。V.Vapnik等人早在20世紀(jì)60年代就開(kāi)場(chǎng)研究有限樣本情況下的機(jī)器學(xué)習(xí)問(wèn)題。由于當(dāng)時(shí)這些研究尚不非常完善，在解決形式識(shí)別問(wèn)題中往往趨于保守，且數(shù)學(xué)上比擬晦澀，90年代以前并沒(méi)有提出可以將其理論付諸實(shí)現(xiàn)的較好的方法。加之當(dāng)時(shí)正處在其他學(xué)習(xí)方法飛速開(kāi)展的時(shí)期，因此這些研究一直沒(méi)有得到充

3、分的重視。直到90年代中期，有限樣本情況下的機(jī)器學(xué)習(xí)理論研究逐漸成熟起來(lái)，形成了一個(gè)較完善的理論體系統(tǒng)計(jì)學(xué)習(xí)理論StatistialLearningThery，簡(jiǎn)稱SLT。同時(shí)，神經(jīng)網(wǎng)絡(luò)等較新興的機(jī)器學(xué)習(xí)方法的研究那么遇到一些重要的困難，比方如何確定網(wǎng)絡(luò)構(gòu)造的問(wèn)題、過(guò)學(xué)習(xí)與欠學(xué)習(xí)問(wèn)題、部分極小點(diǎn)問(wèn)題等等。在這種情況下，試圖從更本質(zhì)上研究機(jī)器學(xué)習(xí)問(wèn)題的統(tǒng)計(jì)學(xué)習(xí)理論逐步得到重視。為理解決有限樣本的機(jī)器學(xué)習(xí)問(wèn)題，在過(guò)去二十多年里，開(kāi)展了很多新的統(tǒng)計(jì)學(xué)方法，其中V.Vapnike等開(kāi)展了專門(mén)研究小樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)的統(tǒng)計(jì)學(xué)習(xí)理論以及構(gòu)造風(fēng)險(xiǎn)最小化原那么StruturalRiskiniizatin，SR

4、。統(tǒng)計(jì)學(xué)習(xí)理論就是研究小樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)的理論，主要內(nèi)容包括四個(gè)方面：1經(jīng)歷風(fēng)險(xiǎn)最小化原那么下統(tǒng)計(jì)學(xué)習(xí)一致性的條件；2在這些條件下關(guān)于統(tǒng)計(jì)學(xué)習(xí)方法推廣性的界的結(jié)論；3在這些界的根底上建立的小樣本歸納推理準(zhǔn)那么；4實(shí)現(xiàn)新的準(zhǔn)那么的實(shí)際方法算法。其中，最有指導(dǎo)性的理論結(jié)果是推廣性的界，與此相關(guān)的一個(gè)核心概念是V維。2V維形式識(shí)別方法中VVapnikhervnenkDiensin維的直觀定義是：對(duì)一個(gè)指示函數(shù)集，假如存在h個(gè)樣本可以被函數(shù)集中的函數(shù)按所有可能的2h種形式分開(kāi)，那么稱函數(shù)集可以把h個(gè)樣本打散；函數(shù)集的V維就是它能打散的最大樣本數(shù)目h。假設(shè)對(duì)任意數(shù)目的樣本都有函數(shù)能將它們打散，那么函數(shù)

5、集的V維是無(wú)窮大。有界實(shí)函數(shù)的V維可以通過(guò)用一定的閾值將它轉(zhuǎn)化成指示函數(shù)來(lái)定義。V維反映了函數(shù)集的學(xué)習(xí)才能，V維越大那么學(xué)習(xí)機(jī)器越復(fù)雜容量越大。遺憾的是，目前尚沒(méi)有通用的關(guān)于任意函數(shù)集V維計(jì)算的理論，只對(duì)一些特殊的函數(shù)集知道其V維。比方在n維實(shí)數(shù)空間中線性分類器和線性實(shí)函數(shù)的V維是n+1，而上一節(jié)例子中的V維那么為無(wú)窮大。對(duì)于一些比擬復(fù)雜的學(xué)習(xí)機(jī)器如神經(jīng)網(wǎng)絡(luò)，其V維除了與函數(shù)集神經(jīng)網(wǎng)構(gòu)造有關(guān)外，還受學(xué)習(xí)算法等的影響，其確定更加困難。對(duì)于給定的學(xué)習(xí)函數(shù)集，如何用理論或?qū)嶒?yàn)的方法計(jì)算其V維是當(dāng)前統(tǒng)計(jì)學(xué)習(xí)理論中有待研究的一個(gè)問(wèn)題。3推廣性的界統(tǒng)計(jì)學(xué)習(xí)理論系統(tǒng)地研究了對(duì)于各種類型的函數(shù)集，經(jīng)歷風(fēng)險(xiǎn)和實(shí)

6、際風(fēng)險(xiǎn)之間的關(guān)系，即推廣性的界。關(guān)于兩類分類問(wèn)題，結(jié)論是：對(duì)指示函數(shù)集中的所有函數(shù)包括使經(jīng)歷風(fēng)險(xiǎn)最小的函數(shù)，經(jīng)歷風(fēng)險(xiǎn)和真實(shí)風(fēng)險(xiǎn)之間以致少1-的概率滿足如下關(guān)系：上式右端第一項(xiàng)反映訓(xùn)練樣本的擬合程度；第二項(xiàng)稱為Vapnikhervnenkis置信范圍又稱V置信范圍，h是函數(shù)集的V維。式1說(shuō)明，在有限訓(xùn)練樣本下，學(xué)習(xí)機(jī)器的V維越高復(fù)雜性越高那么置信范圍越大，導(dǎo)致真實(shí)風(fēng)險(xiǎn)與經(jīng)歷風(fēng)險(xiǎn)之間可能的差異越大。這就是為什么會(huì)出現(xiàn)過(guò)學(xué)習(xí)現(xiàn)象的原因。機(jī)器學(xué)習(xí)過(guò)程不但要使經(jīng)歷風(fēng)險(xiǎn)最小，還要使V維盡量小以縮小置信范圍，才能獲得較小的實(shí)際風(fēng)險(xiǎn)，即對(duì)將來(lái)樣本有較好的推廣性。4構(gòu)造風(fēng)險(xiǎn)最小化SR原那么在傳統(tǒng)方法中，選擇學(xué)習(xí)

7、模型和算法的過(guò)程就是調(diào)整置信范圍的過(guò)程，假如模型比擬合適現(xiàn)有的的訓(xùn)練樣本相當(dāng)于n/h值適當(dāng)，那么可以獲得比擬好的效果。但因?yàn)槿狈碚撝笇?dǎo)，這種選擇只能依賴先驗(yàn)知識(shí)和經(jīng)歷，造成了如神經(jīng)網(wǎng)絡(luò)等方法對(duì)使用者技巧的過(guò)分依賴。當(dāng)n/h較大時(shí)，式1右邊的第二部分就較小，真實(shí)風(fēng)險(xiǎn)就接近經(jīng)歷風(fēng)險(xiǎn)的取值。假如n/h較小，那么一個(gè)小的經(jīng)歷風(fēng)險(xiǎn)值并不能保證小的真實(shí)風(fēng)險(xiǎn)值。在這種情況下，要最小化真實(shí)風(fēng)險(xiǎn)值，就必須對(duì)不等式1右邊的兩項(xiàng)同時(shí)最小化。但是需要注意，不等式1右邊的第一項(xiàng)取決于函數(shù)集中的一個(gè)特定函數(shù)，而第二項(xiàng)取決于整個(gè)函數(shù)集的V維。因此要對(duì)風(fēng)險(xiǎn)的界，即式1的右邊的兩項(xiàng)同時(shí)最小化，我們必須使V維成為一個(gè)可以控制的變量。統(tǒng)計(jì)學(xué)習(xí)理論提出了一種新的策略，即把函數(shù)集構(gòu)造為一個(gè)函數(shù)子集序列，使各個(gè)子集按照V維的大小亦即的大小排列，在每個(gè)子集中尋找最小經(jīng)歷風(fēng)險(xiǎn)，在子集間折衷考慮經(jīng)歷風(fēng)險(xiǎn)和置信范圍，獲得真實(shí)風(fēng)險(xiǎn)的最小，如圖1所示。于是有兩個(gè)本文由論文聯(lián)盟搜集整理思路：一是在每個(gè)子集中求最小經(jīng)歷風(fēng)險(xiǎn)，然后選擇使最小經(jīng)歷風(fēng)險(xiǎn)和置信范圍之和最小的子集。這種方法比擬費(fèi)時(shí)，當(dāng)子