7-計(jì)算學(xué)習(xí)理論課件

第七章計(jì)算機(jī)學(xué)習(xí)理論第七章計(jì)算機(jī)學(xué)習(xí)理論17.1簡介在研究機(jī)器學(xué)習(xí)的過程中,學(xué)習(xí)器應(yīng)遵循什么樣的規(guī)則?是否能夠獨(dú)立于學(xué)習(xí)算法確定學(xué)習(xí)問題中固有的難度?能否知道為保證成功的學(xué)習(xí)有多少訓(xùn)練樣例是必要的和充足的?如果學(xué)習(xí)器被允許想施教者提出查詢,而不是觀察訓(xùn)練集的隨機(jī)樣本,會(huì)對(duì)所需樣例數(shù)目有怎樣的影響?能否刻畫出學(xué)習(xí)器在學(xué)習(xí)目標(biāo)函數(shù)前回有多少次出錯(cuò)?能否刻畫出一類學(xué)習(xí)問題中固有的計(jì)算復(fù)雜度?7.1簡介在研究機(jī)器學(xué)習(xí)的過程中,學(xué)習(xí)器應(yīng)遵循什么樣的規(guī)則2在這里我們著重討論只給定目標(biāo)函數(shù)的訓(xùn)練樣例和候選假設(shè)空間的條件下,對(duì)該未知的目標(biāo)函數(shù)的歸納學(xué)習(xí)問題.主要要解決的問題如:需要多少訓(xùn)練樣例才足以成功的學(xué)習(xí)到目標(biāo)函數(shù)以及學(xué)習(xí)器在達(dá)到目標(biāo)前會(huì)出多少次錯(cuò).在這里我們著重討論只給定目標(biāo)函數(shù)的訓(xùn)練樣例和候選假設(shè)空間3后面將對(duì)以上的問題提出定量的上下界,這基于學(xué)習(xí)問題的如下屬性:學(xué)習(xí)器所考慮的假設(shè)空間的大小和復(fù)雜度目標(biāo)概念須近似到怎樣的精度學(xué)習(xí)器輸出成功的假設(shè)的可能性訓(xùn)練樣例提供給學(xué)習(xí)器的方式后面將對(duì)以上的問題提出定量的上下界,這基于學(xué)習(xí)問題的如下4我們學(xué)習(xí)本章的目標(biāo)的就是為了回答以下的問題:樣本復(fù)雜度:學(xué)習(xí)器要收斂到成功假設(shè)(以較高的概率),需要多少的訓(xùn)練樣例?計(jì)算復(fù)雜度:學(xué)習(xí)器要收斂到成功假設(shè)(以較高的概率)需要多大計(jì)算量?出錯(cuò)界限:在成功收斂到一個(gè)假設(shè)前,學(xué)習(xí)器對(duì)訓(xùn)練樣例的錯(cuò)誤分類有多少次?我們學(xué)習(xí)本章的目標(biāo)的就是為了回答以下的問題:5注意:為解決這些問題需要許多特殊的條件設(shè)定.如:有許多方法來指定對(duì)于學(xué)習(xí)器什么是”成功的”.一種可能判斷的方法是:學(xué)習(xí)器是否輸出等于目標(biāo)函數(shù)的假設(shè).另一種方法是:只要求輸出的假設(shè)與目標(biāo)函數(shù)在多數(shù)的時(shí)間內(nèi)意見是一致,或是學(xué)習(xí)器通常會(huì)輸出這樣的假設(shè).如:學(xué)習(xí)器是如何獲得訓(xùn)練樣例的?可以指定訓(xùn)練樣例由一個(gè)施教者給出,或由學(xué)習(xí)器自己實(shí)驗(yàn)得到,或按照某過程隨機(jī)的生成而不受學(xué)習(xí)器的控制.對(duì)于以上問題的回答以來我們所考慮的特定框架或?qū)W習(xí)模型注意:為解決這些問題需要許多特殊的條件設(shè)定.67.2可能學(xué)習(xí)近似正確假設(shè)這節(jié)我們學(xué)習(xí)一種特殊的框架---可能學(xué)習(xí)近似正確(probablyapproximatelycorrect,PAC)學(xué)習(xí)模型.首先我們指定PAC學(xué)習(xí)模型適用的問題,然后分析在此模型下學(xué)習(xí)不同類別的目標(biāo)函數(shù)需要多少訓(xùn)練樣例和多大計(jì)算量.前提:這里的討論將限制在學(xué)習(xí)布爾值的概念,且訓(xùn)練數(shù)據(jù)是無噪聲.

7.2可能學(xué)習(xí)近似正確假設(shè)這節(jié)我們學(xué)習(xí)一種特殊的框架77.2.1問題框架另X代表所有實(shí)例的集合,目標(biāo)函數(shù)在其上定義.每個(gè)實(shí)例由屬性來描述.另C代表學(xué)習(xí)器要代表的目標(biāo)概念集合.C中的每個(gè)目標(biāo)概念c對(duì)應(yīng)于X的某個(gè)子集或一個(gè)等效的布爾函數(shù)c:X{0,1}7.2.1問題框架另X代表所有實(shí)例的集合,目標(biāo)函數(shù)在其上定8實(shí)例按照某概率分布D從X中隨機(jī)的產(chǎn)生.一般D,可為任何分布,而且它對(duì)學(xué)習(xí)器是未知的.對(duì)于D,所要求是它的穩(wěn)定性,既該分布不會(huì)隨時(shí)間的變化.訓(xùn)練樣例的生成按照分布D隨機(jī)抽取實(shí)例x,然后x及其目標(biāo)值c(x)被提供給學(xué)習(xí)器.學(xué)習(xí)器L在學(xué)習(xí)目標(biāo)概念時(shí)考慮可能的假設(shè)集合H.(H可為所有屬性的合取表示的假使的集合.)在觀察了一系列目標(biāo)概念c的訓(xùn)練樣例后,L必須從H中輸出某假設(shè)h,他是對(duì)c的估計(jì).我們通過h在從X中抽取的新實(shí)例上性能來評(píng)估L是否成功.抽取過程按照分布D,即與產(chǎn)生訓(xùn)練樣例相同的概率分布.實(shí)例按照某概率分布D從X中隨機(jī)的產(chǎn)生.一般D,可為任何分布,9在此框架下,我們感興趣的是刻畫不同的學(xué)習(xí)器L的性能,這些學(xué)習(xí)器使用不同的假設(shè)空間H,并學(xué)習(xí)不同類別的C中的目標(biāo)概念.由于我們要求L足夠一般,以至可以學(xué)到任何目標(biāo)概念而不管訓(xùn)練樣例的分布如何,所以我們經(jīng)常會(huì)對(duì)C中所有可能的目標(biāo)概念和所有可能的實(shí)例分布進(jìn)行最差的分析.在此框架下,我們感興趣的是刻畫不同的學(xué)習(xí)器L的性能,這些學(xué)習(xí)107.2.2假設(shè)的錯(cuò)誤率定義:假設(shè)h的關(guān)于目標(biāo)概念c和分布D的真實(shí)錯(cuò)誤率為h誤分類根據(jù)D隨機(jī)抽取的實(shí)例的概率.7.2.2假設(shè)的錯(cuò)誤率定義:假設(shè)h的關(guān)于目標(biāo)概念c和分布D11圖7-1顯示了該錯(cuò)誤率的定義.概念c和h被表示為X中標(biāo)為正例的實(shí)例集合.h關(guān)于c的錯(cuò)誤率為隨機(jī)選取的實(shí)例落入和不一致的區(qū)間(即它們的集合差)的概率.注意:錯(cuò)誤率定義在整個(gè)的分布上,而不只是訓(xùn)練樣例上,因?yàn)樗菍?shí)際應(yīng)用此假設(shè)h到后續(xù)實(shí)例上時(shí)會(huì)遇到真實(shí)的錯(cuò)誤率.圖7-1顯示了該錯(cuò)誤率的定義.概念c和h被表示為X中標(biāo)為正例12注意:此錯(cuò)誤率緊密的依賴于未知的概率分布D,例如:如果D是一個(gè)均勻的概率分布,它對(duì)X中的每個(gè)實(shí)例都賦予相同的概率.那么假設(shè)的錯(cuò)誤率為h和c不一致的空間在全部實(shí)例空間中的比例.然而,如果D恰好把h和c不一致的區(qū)間中的實(shí)例賦予了很高的概率,相同的h和c將造成更高的錯(cuò)誤率.極端的情況下,若D對(duì)滿足h(x)=c(x)的所有的實(shí)例賦予零概率,圖中的錯(cuò)誤率將為1,而不論在多少實(shí)例上分類一致.注意:此錯(cuò)誤率緊密的依賴于未知的概率分布D,13最后,注意h關(guān)于c的錯(cuò)誤率不能直接有學(xué)習(xí)器觀察到.L只能觀察到在訓(xùn)練樣例上h的性能,它也只能在此基礎(chǔ)上選擇其假設(shè)輸出.用術(shù)語訓(xùn)練錯(cuò)誤率來指代訓(xùn)練樣例中被誤分類的樣例所占的比例,以區(qū)分真實(shí)錯(cuò)誤率.這里關(guān)于學(xué)習(xí)復(fù)雜度的分析多數(shù)圍繞著這樣的問題:”的觀察到的訓(xùn)練錯(cuò)誤率對(duì)真實(shí)錯(cuò)誤率產(chǎn)生不正確估計(jì)的可能性有多大?”.最后,注意h關(guān)于c的錯(cuò)誤率不能直接有學(xué)習(xí)器觀察到.L只能觀察14PAC可學(xué)習(xí)性我們的目標(biāo)是刻畫出這樣的目標(biāo)概念，它們能夠從合理數(shù)量的隨機(jī)抽取訓(xùn)練樣例中通過合理的計(jì)算量可靠地學(xué)習(xí)對(duì)可學(xué)習(xí)性的表述一種可能的選擇：為了學(xué)習(xí)到使errorD(h)=0的假設(shè)h，所需的訓(xùn)練樣例數(shù)這樣的選擇不可行：首先要求對(duì)X中每個(gè)可能的實(shí)例都提供訓(xùn)練樣例；其次要求訓(xùn)練樣例無誤導(dǎo)性可能近似學(xué)習(xí)：首先只要求學(xué)習(xí)器輸出錯(cuò)誤率限定在某常數(shù)范圍內(nèi)的假設(shè)，其次要求對(duì)所有的隨機(jī)抽取樣例序列的失敗的概率限定在某常數(shù)范圍內(nèi)只要求學(xué)習(xí)器可能學(xué)習(xí)到一個(gè)近似正確的假設(shè)PAC可學(xué)習(xí)性我們的目標(biāo)是刻畫出這樣的目標(biāo)概念，它們能夠從合15PAC可學(xué)習(xí)性的定義考慮定義在長度為n的實(shí)例集合X上的一概念類別C，學(xué)習(xí)器L使用假設(shè)空間H。當(dāng)對(duì)所有cC，X上的分布D，和滿足0<,<1/2，學(xué)習(xí)器L將以至少1-輸出一假設(shè)hH，使errorD(h)，這時(shí)稱C是使用H的L可PAC學(xué)習(xí)的，所使用的時(shí)間為1/，1/，n以及size(c)的多項(xiàng)式函數(shù)上面定義要求學(xué)習(xí)器L滿足兩個(gè)條件L必須以任意高的概率（1-）輸出一個(gè)錯(cuò)誤率任意低（）的假設(shè)學(xué)習(xí)過程必須是高效的，其時(shí)間最多以多項(xiàng)式方式增長上面定義的說明1/和1/表示了對(duì)輸出假設(shè)要求的強(qiáng)度，n和size(c)表示了實(shí)例空間X和概念類別C中固有的復(fù)雜度n為X中實(shí)例的長度，size(c)為概念c的編碼長度PAC可學(xué)習(xí)性的定義16在實(shí)踐中，通常更關(guān)心所需的訓(xùn)練樣例數(shù)，如果L對(duì)每個(gè)訓(xùn)練樣例需要某最小處理時(shí)間，那么為了使c是L可PAC學(xué)習(xí)的，L必須從多項(xiàng)式數(shù)量的訓(xùn)練樣例中進(jìn)行學(xué)習(xí)實(shí)際上，為了顯示某目標(biāo)概念類別C是可PAC學(xué)習(xí)的，一個(gè)典型的途徑是證明C中每個(gè)目標(biāo)概念可以從多項(xiàng)式數(shù)量的訓(xùn)練樣例中學(xué)習(xí)到，且處理每個(gè)樣例的時(shí)間也是多項(xiàng)式級(jí)PAC可學(xué)習(xí)性的一個(gè)隱含的條件：對(duì)C中每個(gè)目標(biāo)概念c，假設(shè)空間H都包含一個(gè)以任意小誤差接近c(diǎn)的假設(shè).在實(shí)踐中，通常更關(guān)心所需的訓(xùn)練樣例數(shù)，17引論:PAC可學(xué)習(xí)性很大程度上由所需的訓(xùn)練樣例數(shù)確定，隨著問題規(guī)模的增長所帶來的所需訓(xùn)練樣例的增長稱為該學(xué)習(xí)問題的樣本復(fù)雜度。我們把樣本復(fù)雜度的討論限定于一致學(xué)習(xí)器（輸出完美擬合訓(xùn)練數(shù)據(jù)的學(xué)習(xí)器）能夠獨(dú)立于特定算法，推導(dǎo)出任意一致學(xué)習(xí)器所需訓(xùn)練樣例數(shù)的界限。這里需要引入以前學(xué)習(xí)過的變型空間的定義：7-3有限假設(shè)空間的樣本復(fù)雜度引論:7-3有限假設(shè)空間的樣本復(fù)雜度18變型空間：能正確分類訓(xùn)練樣例D的所有假 設(shè)的集合。形式化：變型空間的重要意義是：每個(gè)一致學(xué)習(xí)器都輸出一個(gè)屬于變型空間的假設(shè)。而不管X、H、D。因此界定任意一個(gè)一致學(xué)習(xí)器所需的樣例數(shù)量，只需要界定為保證變型中沒有不可接受假設(shè)所需的樣例數(shù)量。為此下面精確的描述了這一條件：變型空間：能正確分類訓(xùn)練樣例D的所有假 設(shè)的集19定義：考慮一假設(shè)空間H，目標(biāo)概念c，實(shí)例分布D以及c的一組訓(xùn)練樣例S。當(dāng)VSH,D中每個(gè)假設(shè)h關(guān)于c和D錯(cuò)誤率小于時(shí)，變型空間被稱為c和D是-詳盡的。形式化：說明：-詳盡的變型空間表示與訓(xùn)練樣例一致的所有假設(shè)的真實(shí)錯(cuò)誤率都小于。從學(xué)習(xí)器的角度看，所能知道的只是這些假設(shè)能同等地?cái)M合訓(xùn)練數(shù)據(jù)，它們都有零訓(xùn)練錯(cuò)誤率。定義：考慮一假設(shè)空間H，目標(biāo)概念c，實(shí)例分布D以及c的一組訓(xùn)20只有知道目標(biāo)概念的觀察者才能確定變型空間是否為-詳盡的。但是，即使不知道確切的目標(biāo)概念或訓(xùn)練樣例抽取的分布，一種概率方法可在給定數(shù)目的訓(xùn)練樣例之后界定變型空間為-詳盡的。定理7.1（變型空間的-詳盡化）若假設(shè)空間H有限，且D為目標(biāo)概念c的一系列m>=1個(gè)獨(dú)立隨機(jī)抽取的樣例，那么對(duì)于任意0=<<=1，變型空間VSH,D不是-詳盡的概率小于或等于：只有知道目標(biāo)概念的觀察者才能確定變型空間是否為-21證明：令h1,...,hk為H中關(guān)于c的真實(shí)錯(cuò)誤率大于的所有假設(shè)。當(dāng)且僅當(dāng)k個(gè)假設(shè)中至少有一個(gè)恰好與所有m個(gè)獨(dú)立隨機(jī)抽取樣例一致時(shí)，不能使變型空間-詳盡化。任一假設(shè)真實(shí)錯(cuò)誤率大于，且與一個(gè)隨機(jī)抽取樣例一致的可能性最多為1-，因此，該假設(shè)與m個(gè)獨(dú)立抽取樣例一致的概率最多為(1-)m由于已知有k個(gè)假設(shè)錯(cuò)誤率大于，那么至少有一個(gè)與所有m個(gè)訓(xùn)練樣例都不一致的概率最多為（當(dāng)，則）因此證畢#證明：令h1,...,hk為H中關(guān)于c的真實(shí)錯(cuò)誤率大于的所22

定理7.1基于訓(xùn)練樣例的數(shù)目m、允許的錯(cuò)誤率和H的大小，給出了變型空間不是-詳盡的概率的上界。換言之它對(duì)于使用假設(shè)空間H的任意學(xué)習(xí)器界定了m個(gè)訓(xùn)練樣例未能將所有“壞”的假設(shè)（錯(cuò)誤率大于的假設(shè)）剔除出去的概率利用上面的結(jié)論來確定為了減少此“未剔除”概率到一希望程度所需的訓(xùn)練樣例數(shù)。由可以得到定理7.1基于訓(xùn)練樣例的數(shù)目m、允許的錯(cuò)誤率和23

式子7.2提供了訓(xùn)練樣例數(shù)目的一般邊界，該數(shù)目的樣例足以在所期望的值和程度下，使任何一致學(xué)習(xí)器成功地學(xué)習(xí)到H中的任意目標(biāo)概念。訓(xùn)練樣例的數(shù)目m足以保證任意一致假設(shè)是可能（可能性為1-）近似（錯(cuò)誤率為）正確的m隨著1/線性增長，隨著1/和假設(shè)空間的規(guī)模對(duì)數(shù)增長上面的界限可能是過高的估計(jì)，主要來源于|H|項(xiàng)，它產(chǎn)生于證明過程中在所有可能假設(shè)上計(jì)算那些不可接受的假設(shè)的概率和。在7.4節(jié)討論一個(gè)更緊湊的邊界以及能夠覆蓋無限大的假設(shè)空間的邊界。式子7.2提供了訓(xùn)練樣例數(shù)目的一般邊界，該數(shù)目24

如果學(xué)習(xí)器不假定目標(biāo)概念可在H中表示，而只簡單地尋找具有最小訓(xùn)練錯(cuò)誤率的假設(shè)，這樣的學(xué)習(xí)器稱為不可知學(xué)習(xí)器式7.2基于的假定是學(xué)習(xí)器輸出一零錯(cuò)誤率假設(shè)，在更一般的情形下學(xué)習(xí)器考慮到了有非零訓(xùn)練錯(cuò)誤率的假設(shè)時(shí)，仍能找到一個(gè)簡單的邊界。7-3不可知學(xué)習(xí)和不一致假設(shè)如果學(xué)習(xí)器不假定目標(biāo)概念可在H中表示，而只簡單地尋25

令S代表學(xué)習(xí)器可觀察到的特定訓(xùn)練樣例集合，errorS(h)表示h的訓(xùn)練錯(cuò)誤率，即S中被h誤分類的訓(xùn)練樣例所占比例令hbest表示H中有最小訓(xùn)練錯(cuò)誤率的假設(shè)，問題是：多少訓(xùn)練樣例才足以保證其真實(shí)錯(cuò)誤率errorD(hbest)不會(huì)多+errorS(hbest)

（上一節(jié)問題是這個(gè)問題的特例）？前面問題的回答使用類似定理7.1的證明方法，這里有必要引入一般的Hoeffding邊界。令S代表學(xué)習(xí)器可觀察到的特定訓(xùn)練樣例集合，erro26Hoeffding邊界表明，當(dāng)訓(xùn)練錯(cuò)誤率errorS(h)在包含m個(gè)隨機(jī)抽取樣例的集合S上測(cè)量時(shí)，則：上式給出了一個(gè)概率邊界，說明任意選擇的假設(shè)訓(xùn)練錯(cuò)誤率不能代表真實(shí)情況，為保證L尋找到的最佳的假設(shè)的錯(cuò)誤率有以上的邊界，我們必須考慮這|H|個(gè)假設(shè)中任一個(gè)有較大錯(cuò)誤率的概率：Hoeffding邊界表明，當(dāng)訓(xùn)練錯(cuò)誤率errorS(h)在27將上式左邊概率稱為，問多少個(gè)訓(xùn)練樣例m才足以使維持在一定值內(nèi)，求解得到：式7.3是式7.2的一般化情形，適用于當(dāng)最佳假設(shè)可能有非零訓(xùn)練錯(cuò)誤率時(shí)，學(xué)習(xí)器仍能選擇到最佳假設(shè)hH的情形。將上式左邊概率稱為，問多少個(gè)訓(xùn)練樣例m才足以使維持在一定28

我們已經(jīng)有了一個(gè)訓(xùn)練樣例數(shù)目的邊界，表示樣本數(shù)目為多少時(shí)才足以可能近似學(xué)習(xí)到目標(biāo)概念，現(xiàn)在用它來確定某些特定概念類別的樣本復(fù)雜度和PAC可學(xué)習(xí)性?？紤]目標(biāo)概念類C，它由布爾文字的合取表示。布爾文字是任意的布爾變量，或它的否定。問題：C是可PAC學(xué)習(xí)的嗎？若假設(shè)空間H定義為n個(gè)布爾文字的合取，則假設(shè)空間|H|的大小為3n，得到關(guān)于n布爾文字合取學(xué)習(xí)問題的樣本復(fù)雜性。7.3.1布爾文字的合取是PAC可學(xué)習(xí)的我們已經(jīng)有了一個(gè)訓(xùn)練樣例數(shù)目的邊界，表示樣本數(shù)29定理7.2：布爾合取式的PAC可學(xué)習(xí)性布爾文字合取的類C是用Find-S算法PAC可學(xué)習(xí)的證明：上式顯示了該概念類的樣本復(fù)雜度是n、1/和1/的多項(xiàng)式級(jí)，而且獨(dú)立于size(c)。為增量地處理每個(gè)訓(xùn)練樣例，F(xiàn)ind-S算法要求的運(yùn)算量根據(jù)n線性增長，并獨(dú)立于1/、1/和size(c)。因此這一概念類別是Find-S算法PAC可學(xué)習(xí)的。定理7.2：布爾合取式的PAC可學(xué)習(xí)性301無偏學(xué)習(xí)器（無歸納偏置）考慮一無偏概念類C，它包含與X相關(guān)的所有可教授概念，X中的實(shí)例定義為n個(gè)布爾值特征，則有無偏的目標(biāo)概念類在PAC模型下有指數(shù)級(jí)的樣本復(fù)雜度。7.3.2其它概念類別的PAC可學(xué)習(xí)性1無偏學(xué)習(xí)器（無歸納偏置）7.3.2其它概念類別的P312K項(xiàng)DNF和K-CNF概念某概念類有多項(xiàng)式級(jí)的樣本復(fù)雜度，但不能夠在多項(xiàng)式時(shí)間內(nèi)被學(xué)習(xí)到。概念類C為k項(xiàng)析取范式（k項(xiàng)DNF）的形式k項(xiàng)DNF：T1...Tk，其中每一個(gè)Ti為n個(gè)布爾屬性和它們的否定的合取。假定H=C，則|H|最多為3nk，代入式7.2，得到因此，k項(xiàng)DNF的樣本復(fù)雜度為1/、1/、n和k的多項(xiàng)式級(jí)但是計(jì)算復(fù)雜度不是多項(xiàng)式級(jí)，該問題是NP完全問題（等效于其他已知的不能在多項(xiàng)式時(shí)間內(nèi)解決的問題）2K項(xiàng)DNF和K-CNF概念32

因此，雖然k項(xiàng)DNF有多項(xiàng)式級(jí)的樣本復(fù)雜度，它對(duì)于使用H=C的學(xué)習(xí)器沒有多項(xiàng)式級(jí)的計(jì)算復(fù)雜度。令人吃驚的是，雖然k項(xiàng)DNF不是PAC可學(xué)習(xí)的，但存在一個(gè)更大的概念類是PAC可學(xué)習(xí)的這個(gè)更大的概念類是K-CNF，它有每樣例的多項(xiàng)式級(jí)時(shí)間復(fù)雜度，又有多項(xiàng)式級(jí)的樣本復(fù)雜度。K-CNF：任意長度的合取式T1...Tj，其中每個(gè)Ti為最多k個(gè)布爾變量的析取。容易證明K-CNF包含了K項(xiàng)DNF，因此概念類k項(xiàng)DNF是使用H=K-CNF的一個(gè)有效算法可PAC學(xué)習(xí)的。因此，雖然k項(xiàng)DNF有多項(xiàng)式級(jí)的樣本復(fù)雜度，33式子7.2用|H|刻畫樣本復(fù)雜度有兩個(gè)缺點(diǎn)：1可能導(dǎo)致非常弱的邊界2對(duì)于無限假設(shè)空間的情形，無法應(yīng)用本節(jié)考慮H的復(fù)雜度的另一種度量，稱為H的Vapnik-Chervonenkis維度（簡稱VC維或VC(H)）使用VC維代替|H|也可以得到樣本復(fù)雜度的邊界，基于VC維的樣本復(fù)雜度比|H|更緊湊，另外還可以刻畫無限假設(shè)空間的樣本復(fù)雜度.7-4無限假設(shè)空間的樣本復(fù)雜度式子7.2用|H|刻畫樣本復(fù)雜度有兩個(gè)缺點(diǎn)：7-4無限假設(shè)34VC維衡量假設(shè)空間復(fù)雜度的方法不是用不同假設(shè)的數(shù)量|H|，而是用X中能被H徹底區(qū)分的不同實(shí)例的數(shù)量.S是一個(gè)實(shí)例集，H中每個(gè)h導(dǎo)致S的一個(gè)劃分，即h將S分割為兩個(gè)子集{xS|h(x)=1}和{xS|h(x)=0}.定義：一實(shí)例集S被假設(shè)空間H打散，當(dāng)且僅當(dāng)對(duì)S的每個(gè)劃分，存在H中的某假設(shè)與此劃分一致如果一實(shí)例集合沒有被假設(shè)空間打散，那么必然存在某概念可被定義在實(shí)例集之上，但不能由假設(shè)空間表示.H的這種打散實(shí)例集合的能力是其表示這些實(shí)例上定義的目標(biāo)概念的能力的度量.7.4.1打散一個(gè)實(shí)例集合7.4.1打散一個(gè)實(shí)例集合35定義：定義在實(shí)例空間X上的假設(shè)空間H的Vapnik-Chervonenkis維，是可被H打散的X的最大有限子集的大小.如果X的任意有限大的子集可被H打散則VC(H)=.對(duì)于任意有限的H，VC(H)<=log2|H|。假定VC(H)=d;那么|H|需要2^d個(gè)實(shí)例。所以2^d<=|H|.

7.4.2Vapnik-Chervonenkis維度定義：定義在實(shí)例空間X上的假設(shè)空間H的Vapnik-Cher36下面看三個(gè)例子：例1：假定實(shí)例空間X為實(shí)數(shù)集合，而且H為實(shí)數(shù)軸上的區(qū)間的集合，問VC(H)是多少？只要找到能被H打散的X的最大子集，首先包含2個(gè)實(shí)例的集合能夠被H打散，其次包含3個(gè)實(shí)例的集合不能被H打散，因此VC(H)=2.注解：下面看三個(gè)例子：37例2：實(shí)例集合S對(duì)應(yīng)x、y平面上的點(diǎn)，令H為此平面內(nèi)所有線性決策面的集合，問H的VC維是多少？能夠找到3個(gè)點(diǎn)組成的集合，被H打散，但無法找到能夠被H打散的4個(gè)點(diǎn)組成的集合，因此VC(H)=3更一般地，在r維空間中，線性決策面的VC維為r+1注解：例2：實(shí)例集合S對(duì)應(yīng)x、y平面上的點(diǎn)，令H為此平面內(nèi)所有線38例3：假定X上每個(gè)實(shí)例由恰好3個(gè)布爾文字的合取表示，而且假定H中每個(gè)假設(shè)由至多3個(gè)布爾文字描述，問VC(H)是多少？找到下面3個(gè)實(shí)例的集合instance1:100instance2:010instance3:001這三個(gè)實(shí)例的集合可被H打散，可對(duì)如下任意所希望的劃分建立一假設(shè)：如果該劃分要排除instancei，就將文字li加入到假設(shè)中此討論很容易擴(kuò)展到特征數(shù)為n的情況，n個(gè)布爾文字合取的VC維至少為n實(shí)際就是n，但證明比較困難，需要說明n+1個(gè)實(shí)例的集合不可能被打散。例3：假定X上每個(gè)實(shí)例由恰好3個(gè)布爾文字的合取表示，而且假定39

使用VC維作為H復(fù)雜度的度量，就有可能推導(dǎo)出該問題的另一種解答，類似于式子7.2的邊界，即（Blumerelal.1989）定理7.3：樣本復(fù)雜度的下界考慮任意概念類C，且VC(C)>=2，任意學(xué)習(xí)器L，以及任意0<<1/8，0<<1/100。存在一個(gè)分布D以及C中一個(gè)目標(biāo)概念，當(dāng)L觀察到的樣例數(shù)目小于下式時(shí)：7.4.3樣本復(fù)雜度和VC維使用VC維作為H復(fù)雜度的度量，就有可能推導(dǎo)出該問題40L將以至少的概率輸出一假設(shè)h，使errorD(h)>。說明：若訓(xùn)練樣例的數(shù)目太少，那么沒有學(xué)習(xí)器能夠以PAC模型學(xué)習(xí)到任意非平凡的C中每個(gè)目標(biāo)概念。式子7.7給出了保證充足數(shù)量的上界，而定理7.3給出了下界。7-計(jì)算學(xué)習(xí)理論課件41本節(jié)給出一般性的結(jié)論，以計(jì)算分層無環(huán)網(wǎng)絡(luò)的VC維。這個(gè)VC維可用于界定訓(xùn)練樣例的數(shù)量，該數(shù)達(dá)到多大才足以按照希望的和值近似可能正確地學(xué)習(xí)一個(gè)前饋網(wǎng)絡(luò)考慮一個(gè)由單元組成的網(wǎng)絡(luò)G，它形成一個(gè)分層有向無環(huán)圖。分層有向無環(huán)圖的特點(diǎn)：1節(jié)點(diǎn)可劃分成層，即所有第l層出來的有向邊進(jìn)入到第l+1層節(jié)點(diǎn)2沒有有向環(huán)，即有向弧形成的回路7.4.4神經(jīng)網(wǎng)絡(luò)的VC維本節(jié)給出一般性的結(jié)論，以計(jì)算分層無環(huán)網(wǎng)絡(luò)的VC維。這個(gè)VC維42這樣網(wǎng)絡(luò)的VC維的界定可以基于其圖的結(jié)構(gòu)和構(gòu)造該圖的基本單元的VC維。定義一些術(shù)語G表示神經(jīng)網(wǎng)絡(luò)n是G的輸入數(shù)目G只有1個(gè)輸出節(jié)點(diǎn)G的每個(gè)內(nèi)部單元Ni最多有r個(gè)輸入，并實(shí)現(xiàn)一布爾函數(shù)ci:Rr{0,1}，形成函數(shù)類C定義C的G-合成：網(wǎng)絡(luò)G能實(shí)現(xiàn)的所有函數(shù)的類，即網(wǎng)絡(luò)G表示的假設(shè)空間，表示成CG。這樣網(wǎng)絡(luò)的VC維的界定可以基于其圖的結(jié)構(gòu)和構(gòu)造該圖43定理7.4分層有向無環(huán)網(wǎng)絡(luò)的VC維：

令G為一分層有向無環(huán)圖，有n個(gè)輸入節(jié)點(diǎn)和s2個(gè)內(nèi)部節(jié)點(diǎn)，每個(gè)至少有r個(gè)輸入，令C為VC維為d的Rr上的概念類，對(duì)應(yīng)于可由每個(gè)內(nèi)部節(jié)點(diǎn)s描述的函數(shù)集合，令CG為C的G合成，對(duì)應(yīng)于可由G表示的函數(shù)集合，則VC(CG)<=2dslog(es)。假定要考慮的分層有向無環(huán)網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)都是感知器，由于單獨(dú)的r輸入感知器VC維為r+1，代入定理7.4和式子7.7，得到定理7.4分層有向無環(huán)網(wǎng)絡(luò)的VC維：44上面的結(jié)果不能直接應(yīng)用于反向傳播的網(wǎng)絡(luò)，原因有兩個(gè)：1此結(jié)果應(yīng)用于感知器網(wǎng)絡(luò)，而不是sigmoid單元網(wǎng)絡(luò)。2不能處理反向傳播中的訓(xùn)練過程。總結(jié)。上面的結(jié)果不能直接應(yīng)用于反向傳播的網(wǎng)絡(luò)，原因有兩個(gè)：457.5學(xué)習(xí)的出錯(cuò)界限模型計(jì)算學(xué)習(xí)理論考慮多種不同的問題框架訓(xùn)練樣例的生成方式（被動(dòng)觀察、主動(dòng)提出查詢）數(shù)據(jù)中的噪聲（有噪聲或無噪聲）成功學(xué)習(xí)的定義（必須學(xué)到正確的目標(biāo)概念還是有一定的可能性和近似性）學(xué)習(xí)器所做得假定（實(shí)例的分布情況以及是否CH）評(píng)估學(xué)習(xí)器的度量標(biāo)準(zhǔn)（訓(xùn)練樣例數(shù)量、出錯(cuò)數(shù)量、計(jì)算時(shí)間）7.5學(xué)習(xí)的出錯(cuò)界限模型計(jì)算學(xué)習(xí)理論考慮多種不同的問題框架46機(jī)器學(xué)習(xí)的出錯(cuò)界限模型學(xué)習(xí)器的評(píng)估標(biāo)準(zhǔn)是它在收斂到正確假設(shè)前總的出錯(cuò)數(shù)學(xué)習(xí)器每接受到一個(gè)樣例x，先預(yù)測(cè)目標(biāo)值c(x)，然后施教者給出正確的目標(biāo)值考慮的問題是：在學(xué)習(xí)器學(xué)習(xí)到目標(biāo)概念前，它的預(yù)測(cè)會(huì)有多少次出錯(cuò)下面討論中，只考慮學(xué)習(xí)器確切學(xué)到目標(biāo)概念前出錯(cuò)的次數(shù)，確切學(xué)到的含義是xh(x)=c(x)機(jī)器學(xué)習(xí)的出錯(cuò)界限模型477.5.1Find-S算法的出錯(cuò)界限Find-S算法的一個(gè)簡單實(shí)現(xiàn)將h初始化為最特殊假設(shè)l1l1...lnln對(duì)每個(gè)正例x從h中移去任何不滿足x的文字輸出假設(shè)h計(jì)算一個(gè)邊界，以描述Find-S在確切學(xué)到目標(biāo)概念c前全部的出錯(cuò)次數(shù)Find-S永遠(yuǎn)不會(huì)將一反例錯(cuò)誤地劃分為正例，因此只需要計(jì)算將正例劃分為反例的出錯(cuò)次數(shù)遇到第一個(gè)正例，初始假設(shè)中2n個(gè)項(xiàng)半數(shù)被刪去，對(duì)后續(xù)的被當(dāng)前假設(shè)誤分類的正例，至少有一項(xiàng)從假設(shè)中刪去出錯(cuò)總數(shù)至多為n+17.5.1Find-S算法的出錯(cuò)界限Find-S算法的一個(gè)487.5.2Halving算法的出錯(cuò)界限學(xué)習(xí)器對(duì)每個(gè)新實(shí)例x做出預(yù)測(cè)的方法是：從當(dāng)前變型空間的所有假設(shè)中取多數(shù)票得來將變型空間學(xué)習(xí)和用多數(shù)票來進(jìn)行后續(xù)預(yù)測(cè)結(jié)合起來的算法稱為Halving算法Halving算法只有在當(dāng)前變型空間的多數(shù)假設(shè)不能正確分類新樣例時(shí)出錯(cuò)，此時(shí)變型空間至少可減少到它的一半大小，因此出錯(cuò)界線是log2|H|Halving算法有可能不出任何差錯(cuò)就確切學(xué)習(xí)到目標(biāo)概念，因?yàn)榧词苟鄶?shù)票是正確的，算法仍將移去那些不正確、少數(shù)票假設(shè)Halving算法的一個(gè)擴(kuò)展是允許假設(shè)以不同的權(quán)值進(jìn)行投票（如貝葉斯最優(yōu)分類器和后面討論的加權(quán)多數(shù)算法）7.5.2Halving算法的出錯(cuò)界限學(xué)習(xí)器對(duì)每個(gè)新實(shí)例x497.5.3最優(yōu)出錯(cuò)界限問題：對(duì)于任意概念類C，假定H=C，最優(yōu)的出錯(cuò)邊界是什么？最優(yōu)出錯(cuò)邊界是指在所有可能的學(xué)習(xí)算法中，最壞情況下出錯(cuò)邊界中最小的那一個(gè)對(duì)任意學(xué)習(xí)算法A和任意目標(biāo)概念c，令MA(c)代表A為了確切學(xué)到c，在所有可能訓(xùn)練樣例序列中出錯(cuò)的最大值對(duì)于任意非空概念類C，令MA(C)=maxcCMA(c)定義：C為任意非空概念類，C的最優(yōu)出錯(cuò)界限定義為Opt(C)是所有可能學(xué)習(xí)算法A中MA(C)的最小值7.5.3最優(yōu)出錯(cuò)界限問題：對(duì)于任意概念類C，假定H=C，50非形式地說，Opt(C)是C中最難的那個(gè)目標(biāo)概念使用最不利的訓(xùn)練樣例序列用最好的算法時(shí)的出錯(cuò)次數(shù)Littlestone1987證明了非形式地說，Opt(C)是C中最難的那個(gè)目標(biāo)概念使用最不利的517.5.4加權(quán)多數(shù)算法Halving算法的更一般形式稱為加權(quán)多數(shù)算法加權(quán)多數(shù)算法通過在一組預(yù)測(cè)算法中進(jìn)行加權(quán)投票來作出預(yù)測(cè)，并通過改變每個(gè)預(yù)測(cè)算法的權(quán)來學(xué)習(xí)加權(quán)多數(shù)算法可以處理不一致的訓(xùn)練數(shù)據(jù)，因?yàn)樗粫?huì)消除與樣例不一致的假設(shè)，只是降低其權(quán)要計(jì)算加權(quán)多數(shù)算法的出錯(cuò)數(shù)量邊界，可以用預(yù)測(cè)算法組中最好的那個(gè)算法的出錯(cuò)數(shù)量7.5.4加權(quán)多數(shù)算法Halving算法的更一般形式稱為加52加權(quán)多數(shù)算法一開始將每個(gè)預(yù)測(cè)算法賦予權(quán)值1，然后考慮訓(xùn)練樣例，只要一個(gè)預(yù)測(cè)算法誤分類新訓(xùn)練樣例，它的權(quán)被乘以某個(gè)系數(shù)β，0<=β<1。如果β=0，則是Halving算法如果β>0，則沒有一個(gè)預(yù)測(cè)算法會(huì)被完全去掉。如果一算法誤分類一個(gè)樣例，那么它的權(quán)值變小加權(quán)多數(shù)算法一開始將每個(gè)預(yù)測(cè)算法賦予權(quán)值1，然后考慮訓(xùn)練樣例53ai代表算法池A中第i個(gè)預(yù)測(cè)算法，wi代表與ai相關(guān)聯(lián)的權(quán)值對(duì)所有i，初始化wi1對(duì)每個(gè)訓(xùn)練樣例<x,c(x)>做：初始化q0和q1為0對(duì)每個(gè)預(yù)測(cè)算法ai如果ai(x)=0，那么q0q0+wi如果ai(x)=1，那么q1q1+wi如果q1>q0，那么預(yù)測(cè)c(x)=1如果q0>q1，那么預(yù)測(cè)c(x)=0如果q0=q1，那么對(duì)c(x)隨機(jī)預(yù)測(cè)為0或1對(duì)每個(gè)預(yù)測(cè)算法ai如果ai(x)c(x)，那么wiβwiai代表算法池A中第i個(gè)預(yù)測(cè)算法，wi代表與ai相關(guān)聯(lián)的權(quán)值54定理7.5：加權(quán)多數(shù)算法的相對(duì)誤差界限令D為任意的訓(xùn)練樣例序列，令A(yù)為任意n個(gè)預(yù)測(cè)算法集合，令k為A中任意算法對(duì)樣例序列D的出錯(cuò)次數(shù)的最小值。那么使用β=1/2的加權(quán)多數(shù)算法在D上出錯(cuò)次數(shù)最多為：2.4(k+log2n)證明：可通過比較最佳預(yù)測(cè)算法的最終權(quán)和所有算法的權(quán)之和來證明。令aj表示A中一算法，并且它出錯(cuò)的次數(shù)為最優(yōu)的k次，則與aj關(guān)聯(lián)的權(quán)wj將為(1/2)k。A中所有n個(gè)算法的權(quán)的和，W的初始值為n，對(duì)加權(quán)多數(shù)算法的每次出錯(cuò)，W被減小為最多，其原因是加權(quán)投票占少數(shù)的算法最少擁有整個(gè)權(quán)W的一半值，而這一部分將被乘以因子1/2。令M代表加權(quán)多數(shù)算法對(duì)訓(xùn)練序列D的總出錯(cuò)次數(shù)，那么最終的總權(quán)W最多為n(3/4)M由，得意義：加權(quán)多數(shù)算法的出錯(cuò)數(shù)量不會(huì)大于算法池中最佳算法出錯(cuò)數(shù)量，加上一個(gè)隨著算法池大小對(duì)數(shù)增長的項(xiàng)，再乘以一常數(shù)因子定理7.5：加權(quán)多數(shù)算法的相對(duì)誤差界限55小結(jié)可能近似正確模型（PAC）針對(duì)的算法從某概念類C中學(xué)習(xí)目標(biāo)概念，使用按一個(gè)未知但固定的概念分布中隨機(jī)抽取的訓(xùn)練樣例，它要求學(xué)習(xí)器可能學(xué)習(xí)到一近似正確的假設(shè)，而計(jì)算量和訓(xùn)練樣例數(shù)都只隨著1/、1/、實(shí)例長度和目標(biāo)概念長度的多項(xiàng)式級(jí)增長在PAC學(xué)習(xí)模型的框架下，任何使用有限假設(shè)空間H的一致學(xué)習(xí)器，將以1-的概率輸出一個(gè)誤差在內(nèi)的假設(shè)，所需的訓(xùn)練樣例數(shù)m滿足小結(jié)可能近似正確模型（PAC）針對(duì)的算法從某概念類C中學(xué)習(xí)目56不可知學(xué)習(xí)考慮更一般的問題：學(xué)習(xí)器不假定目標(biāo)概念所在的類別，學(xué)習(xí)器從訓(xùn)練數(shù)據(jù)中輸出H中有最小誤差率的假設(shè)。學(xué)習(xí)保證以概率1-從H中最可能的假設(shè)中輸出錯(cuò)誤率小于的假設(shè)，需要的隨機(jī)抽取的訓(xùn)練樣例數(shù)目m滿足學(xué)習(xí)器考慮的假設(shè)空間的復(fù)雜度對(duì)所需樣例的數(shù)目影響很大，而衡量假設(shè)空間復(fù)雜度的一個(gè)有用的度量是VC維。VC維是可被H打散的最大實(shí)例集的大小不可知學(xué)習(xí)考慮更一般的問題：學(xué)習(xí)器不假定目標(biāo)概念所在的類別，57在PAC模型下以VC(H)表示的足以導(dǎo)致成功學(xué)習(xí)的訓(xùn)練樣例數(shù)目的上界和下界分別是：另一種學(xué)習(xí)模式稱為出錯(cuò)界限模式，用于分析學(xué)習(xí)器在確切學(xué)習(xí)到目標(biāo)概念之前會(huì)產(chǎn)生的誤分類次數(shù)Halving算法在學(xué)習(xí)到H中的任意目標(biāo)概念前會(huì)有至多l(xiāng)og2|H|次出錯(cuò)對(duì)任意概念類C，最壞情況下最佳算法將有Opt(C)次出錯(cuò)，滿足VC(C)<=Opt(C)<=log2|C|在PAC模型下以VC(H)表示的足以導(dǎo)致成功學(xué)習(xí)的訓(xùn)練樣例數(shù)58加權(quán)多數(shù)算法結(jié)合了多個(gè)預(yù)測(cè)算法的加權(quán)投票來分類新的實(shí)例，它基于這些預(yù)測(cè)算法在樣例序列中的出錯(cuò)來學(xué)習(xí)每個(gè)算法的權(quán)值。加權(quán)多數(shù)算法產(chǎn)生的錯(cuò)誤界限可用算法池中最佳預(yù)測(cè)算法的出錯(cuò)數(shù)來計(jì)算加權(quán)多數(shù)算法結(jié)合了多個(gè)預(yù)測(cè)算法的加權(quán)投票來分類新的實(shí)例，它基59補(bǔ)充讀物計(jì)算學(xué)習(xí)理論中許多早期的工作針對(duì)的問題是：學(xué)習(xí)器能否在極限時(shí)確定目標(biāo)概念Gold1967給出了極限模型下的確定算法Angluin1992給出了一個(gè)好的綜述Vapnik1982詳細(xì)考察了一致收斂Valiant1984給出了PAC學(xué)習(xí)模型Haussler1988討論了-詳盡變型空間Blueretal.1989給出了PAC模型下的一組有用的結(jié)論Kearns&Vazirani1994提供了計(jì)算學(xué)習(xí)理論中許多結(jié)論的優(yōu)秀的闡述會(huì)議：計(jì)算學(xué)習(xí)理論年會(huì)COLT雜志：機(jī)器學(xué)習(xí)的特殊欄目補(bǔ)充讀物計(jì)算學(xué)習(xí)理論中許多早期的工作針對(duì)的問題是：學(xué)習(xí)器能否60第七章計(jì)算機(jī)學(xué)習(xí)理論第七章計(jì)算機(jī)學(xué)習(xí)理論617.1簡介在研究機(jī)器學(xué)習(xí)的過程中,學(xué)習(xí)器應(yīng)遵循什么樣的規(guī)則?是否能夠獨(dú)立于學(xué)習(xí)算法確定學(xué)習(xí)問題中固有的難度?能否知道為保證成功的學(xué)習(xí)有多少訓(xùn)練樣例是必要的和充足的?如果學(xué)習(xí)器被允許想施教者提出查詢,而不是觀察訓(xùn)練集的隨機(jī)樣本,會(huì)對(duì)所需樣例數(shù)目有怎樣的影響?能否刻畫出學(xué)習(xí)器在學(xué)習(xí)目標(biāo)函數(shù)前回有多少次出錯(cuò)?能否刻畫出一類學(xué)習(xí)問題中固有的計(jì)算復(fù)雜度?7.1簡介在研究機(jī)器學(xué)習(xí)的過程中,學(xué)習(xí)器應(yīng)遵循什么樣的規(guī)則62在這里我們著重討論只給定目標(biāo)函數(shù)的訓(xùn)練樣例和候選假設(shè)空間的條件下,對(duì)該未知的目標(biāo)函數(shù)的歸納學(xué)習(xí)問題.主要要解決的問題如:需要多少訓(xùn)練樣例才足以成功的學(xué)習(xí)到目標(biāo)函數(shù)以及學(xué)習(xí)器在達(dá)到目標(biāo)前會(huì)出多少次錯(cuò).在這里我們著重討論只給定目標(biāo)函數(shù)的訓(xùn)練樣例和候選假設(shè)空間63后面將對(duì)以上的問題提出定量的上下界,這基于學(xué)習(xí)問題的如下屬性:學(xué)習(xí)器所考慮的假設(shè)空間的大小和復(fù)雜度目標(biāo)概念須近似到怎樣的精度學(xué)習(xí)器輸出成功的假設(shè)的可能性訓(xùn)練樣例提供給學(xué)習(xí)器的方式后面將對(duì)以上的問題提出定量的上下界,這基于學(xué)習(xí)問題的如下64我們學(xué)習(xí)本章的目標(biāo)的就是為了回答以下的問題:樣本復(fù)雜度:學(xué)習(xí)器要收斂到成功假設(shè)(以較高的概率),需要多少的訓(xùn)練樣例?計(jì)算復(fù)雜度:學(xué)習(xí)器要收斂到成功假設(shè)(以較高的概率)需要多大計(jì)算量?出錯(cuò)界限:在成功收斂到一個(gè)假設(shè)前,學(xué)習(xí)器對(duì)訓(xùn)練樣例的錯(cuò)誤分類有多少次?我們學(xué)習(xí)本章的目標(biāo)的就是為了回答以下的問題:65注意:為解決這些問題需要許多特殊的條件設(shè)定.如:有許多方法來指定對(duì)于學(xué)習(xí)器什么是”成功的”.一種可能判斷的方法是:學(xué)習(xí)器是否輸出等于目標(biāo)函數(shù)的假設(shè).另一種方法是:只要求輸出的假設(shè)與目標(biāo)函數(shù)在多數(shù)的時(shí)間內(nèi)意見是一致,或是學(xué)習(xí)器通常會(huì)輸出這樣的假設(shè).如:學(xué)習(xí)器是如何獲得訓(xùn)練樣例的?可以指定訓(xùn)練樣例由一個(gè)施教者給出,或由學(xué)習(xí)器自己實(shí)驗(yàn)得到,或按照某過程隨機(jī)的生成而不受學(xué)習(xí)器的控制.對(duì)于以上問題的回答以來我們所考慮的特定框架或?qū)W習(xí)模型注意:為解決這些問題需要許多特殊的條件設(shè)定.667.2可能學(xué)習(xí)近似正確假設(shè)這節(jié)我們學(xué)習(xí)一種特殊的框架---可能學(xué)習(xí)近似正確(probablyapproximatelycorrect,PAC)學(xué)習(xí)模型.首先我們指定PAC學(xué)習(xí)模型適用的問題,然后分析在此模型下學(xué)習(xí)不同類別的目標(biāo)函數(shù)需要多少訓(xùn)練樣例和多大計(jì)算量.前提:這里的討論將限制在學(xué)習(xí)布爾值的概念,且訓(xùn)練數(shù)據(jù)是無噪聲.

7.2可能學(xué)習(xí)近似正確假設(shè)這節(jié)我們學(xué)習(xí)一種特殊的框架677.2.1問題框架另X代表所有實(shí)例的集合,目標(biāo)函數(shù)在其上定義.每個(gè)實(shí)例由屬性來描述.另C代表學(xué)習(xí)器要代表的目標(biāo)概念集合.C中的每個(gè)目標(biāo)概念c對(duì)應(yīng)于X的某個(gè)子集或一個(gè)等效的布爾函數(shù)c:X{0,1}7.2.1問題框架另X代表所有實(shí)例的集合,目標(biāo)函數(shù)在其上定68實(shí)例按照某概率分布D從X中隨機(jī)的產(chǎn)生.一般D,可為任何分布,而且它對(duì)學(xué)習(xí)器是未知的.對(duì)于D,所要求是它的穩(wěn)定性,既該分布不會(huì)隨時(shí)間的變化.訓(xùn)練樣例的生成按照分布D隨機(jī)抽取實(shí)例x,然后x及其目標(biāo)值c(x)被提供給學(xué)習(xí)器.學(xué)習(xí)器L在學(xué)習(xí)目標(biāo)概念時(shí)考慮可能的假設(shè)集合H.(H可為所有屬性的合取表示的假使的集合.)在觀察了一系列目標(biāo)概念c的訓(xùn)練樣例后,L必須從H中輸出某假設(shè)h,他是對(duì)c的估計(jì).我們通過h在從X中抽取的新實(shí)例上性能來評(píng)估L是否成功.抽取過程按照分布D,即與產(chǎn)生訓(xùn)練樣例相同的概率分布.實(shí)例按照某概率分布D從X中隨機(jī)的產(chǎn)生.一般D,可為任何分布,69在此框架下,我們感興趣的是刻畫不同的學(xué)習(xí)器L的性能,這些學(xué)習(xí)器使用不同的假設(shè)空間H,并學(xué)習(xí)不同類別的C中的目標(biāo)概念.由于我們要求L足夠一般,以至可以學(xué)到任何目標(biāo)概念而不管訓(xùn)練樣例的分布如何,所以我們經(jīng)常會(huì)對(duì)C中所有可能的目標(biāo)概念和所有可能的實(shí)例分布進(jìn)行最差的分析.在此框架下,我們感興趣的是刻畫不同的學(xué)習(xí)器L的性能,這些學(xué)習(xí)707.2.2假設(shè)的錯(cuò)誤率定義:假設(shè)h的關(guān)于目標(biāo)概念c和分布D的真實(shí)錯(cuò)誤率為h誤分類根據(jù)D隨機(jī)抽取的實(shí)例的概率.7.2.2假設(shè)的錯(cuò)誤率定義:假設(shè)h的關(guān)于目標(biāo)概念c和分布D71圖7-1顯示了該錯(cuò)誤率的定義.概念c和h被表示為X中標(biāo)為正例的實(shí)例集合.h關(guān)于c的錯(cuò)誤率為隨機(jī)選取的實(shí)例落入和不一致的區(qū)間(即它們的集合差)的概率.注意:錯(cuò)誤率定義在整個(gè)的分布上,而不只是訓(xùn)練樣例上,因?yàn)樗菍?shí)際應(yīng)用此假設(shè)h到后續(xù)實(shí)例上時(shí)會(huì)遇到真實(shí)的錯(cuò)誤率.圖7-1顯示了該錯(cuò)誤率的定義.概念c和h被表示為X中標(biāo)為正例72注意:此錯(cuò)誤率緊密的依賴于未知的概率分布D,例如:如果D是一個(gè)均勻的概率分布,它對(duì)X中的每個(gè)實(shí)例都賦予相同的概率.那么假設(shè)的錯(cuò)誤率為h和c不一致的空間在全部實(shí)例空間中的比例.然而,如果D恰好把h和c不一致的區(qū)間中的實(shí)例賦予了很高的概率,相同的h和c將造成更高的錯(cuò)誤率.極端的情況下,若D對(duì)滿足h(x)=c(x)的所有的實(shí)例賦予零概率,圖中的錯(cuò)誤率將為1,而不論在多少實(shí)例上分類一致.注意:此錯(cuò)誤率緊密的依賴于未知的概率分布D,73最后,注意h關(guān)于c的錯(cuò)誤率不能直接有學(xué)習(xí)器觀察到.L只能觀察到在訓(xùn)練樣例上h的性能,它也只能在此基礎(chǔ)上選擇其假設(shè)輸出.用術(shù)語訓(xùn)練錯(cuò)誤率來指代訓(xùn)練樣例中被誤分類的樣例所占的比例,以區(qū)分真實(shí)錯(cuò)誤率.這里關(guān)于學(xué)習(xí)復(fù)雜度的分析多數(shù)圍繞著這樣的問題:”的觀察到的訓(xùn)練錯(cuò)誤率對(duì)真實(shí)錯(cuò)誤率產(chǎn)生不正確估計(jì)的可能性有多大?”.最后,注意h關(guān)于c的錯(cuò)誤率不能直接有學(xué)習(xí)器觀察到.L只能觀察74PAC可學(xué)習(xí)性我們的目標(biāo)是刻畫出這樣的目標(biāo)概念，它們能夠從合理數(shù)量的隨機(jī)抽取訓(xùn)練樣例中通過合理的計(jì)算量可靠地學(xué)習(xí)對(duì)可學(xué)習(xí)性的表述一種可能的選擇：為了學(xué)習(xí)到使errorD(h)=0的假設(shè)h，所需的訓(xùn)練樣例數(shù)這樣的選擇不可行：首先要求對(duì)X中每個(gè)可能的實(shí)例都提供訓(xùn)練樣例；其次要求訓(xùn)練樣例無誤導(dǎo)性可能近似學(xué)習(xí)：首先只要求學(xué)習(xí)器輸出錯(cuò)誤率限定在某常數(shù)范圍內(nèi)的假設(shè)，其次要求對(duì)所有的隨機(jī)抽取樣例序列的失敗的概率限定在某常數(shù)范圍內(nèi)只要求學(xué)習(xí)器可能學(xué)習(xí)到一個(gè)近似正確的假設(shè)PAC可學(xué)習(xí)性我們的目標(biāo)是刻畫出這樣的目標(biāo)概念，它們能夠從合75PAC可學(xué)習(xí)性的定義考慮定義在長度為n的實(shí)例集合X上的一概念類別C，學(xué)習(xí)器L使用假設(shè)空間H。當(dāng)對(duì)所有cC，X上的分布D，和滿足0<,<1/2，學(xué)習(xí)器L將以至少1-輸出一假設(shè)hH，使errorD(h)，這時(shí)稱C是使用H的L可PAC學(xué)習(xí)的，所使用的時(shí)間為1/，1/，n以及size(c)的多項(xiàng)式函數(shù)上面定義要求學(xué)習(xí)器L滿足兩個(gè)條件L必須以任意高的概率（1-）輸出一個(gè)錯(cuò)誤率任意低（）的假設(shè)學(xué)習(xí)過程必須是高效的，其時(shí)間最多以多項(xiàng)式方式增長上面定義的說明1/和1/表示了對(duì)輸出假設(shè)要求的強(qiáng)度，n和size(c)表示了實(shí)例空間X和概念類別C中固有的復(fù)雜度n為X中實(shí)例的長度，size(c)為概念c的編碼長度PAC可學(xué)習(xí)性的定義76在實(shí)踐中，通常更關(guān)心所需的訓(xùn)練樣例數(shù)，如果L對(duì)每個(gè)訓(xùn)練樣例需要某最小處理時(shí)間，那么為了使c是L可PAC學(xué)習(xí)的，L必須從多項(xiàng)式數(shù)量的訓(xùn)練樣例中進(jìn)行學(xué)習(xí)實(shí)際上，為了顯示某目標(biāo)概念類別C是可PAC學(xué)習(xí)的，一個(gè)典型的途徑是證明C中每個(gè)目標(biāo)概念可以從多項(xiàng)式數(shù)量的訓(xùn)練樣例中學(xué)習(xí)到，且處理每個(gè)樣例的時(shí)間也是多項(xiàng)式級(jí)PAC可學(xué)習(xí)性的一個(gè)隱含的條件：對(duì)C中每個(gè)目標(biāo)概念c，假設(shè)空間H都包含一個(gè)以任意小誤差接近c(diǎn)的假設(shè).在實(shí)踐中，通常更關(guān)心所需的訓(xùn)練樣例數(shù)，77引論:PAC可學(xué)習(xí)性很大程度上由所需的訓(xùn)練樣例數(shù)確定，隨著問題規(guī)模的增長所帶來的所需訓(xùn)練樣例的增長稱為該學(xué)習(xí)問題的樣本復(fù)雜度。我們把樣本復(fù)雜度的討論限定于一致學(xué)習(xí)器（輸出完美擬合訓(xùn)練數(shù)據(jù)的學(xué)習(xí)器）能夠獨(dú)立于特定算法，推導(dǎo)出任意一致學(xué)習(xí)器所需訓(xùn)練樣例數(shù)的界限。這里需要引入以前學(xué)習(xí)過的變型空間的定義：7-3有限假設(shè)空間的樣本復(fù)雜度引論:7-3有限假設(shè)空間的樣本復(fù)雜度78變型空間：能正確分類訓(xùn)練樣例D的所有假 設(shè)的集合。形式化：變型空間的重要意義是：每個(gè)一致學(xué)習(xí)器都輸出一個(gè)屬于變型空間的假設(shè)。而不管X、H、D。因此界定任意一個(gè)一致學(xué)習(xí)器所需的樣例數(shù)量，只需要界定為保證變型中沒有不可接受假設(shè)所需的樣例數(shù)量。為此下面精確的描述了這一條件：變型空間：能正確分類訓(xùn)練樣例D的所有假 設(shè)的集79定義：考慮一假設(shè)空間H，目標(biāo)概念c，實(shí)例分布D以及c的一組訓(xùn)練樣例S。當(dāng)VSH,D中每個(gè)假設(shè)h關(guān)于c和D錯(cuò)誤率小于時(shí)，變型空間被稱為c和D是-詳盡的。形式化：說明：-詳盡的變型空間表示與訓(xùn)練樣例一致的所有假設(shè)的真實(shí)錯(cuò)誤率都小于。從學(xué)習(xí)器的角度看，所能知道的只是這些假設(shè)能同等地?cái)M合訓(xùn)練數(shù)據(jù)，它們都有零訓(xùn)練錯(cuò)誤率。定義：考慮一假設(shè)空間H，目標(biāo)概念c，實(shí)例分布D以及c的一組訓(xùn)80只有知道目標(biāo)概念的觀察者才能確定變型空間是否為-詳盡的。但是，即使不知道確切的目標(biāo)概念或訓(xùn)練樣例抽取的分布，一種概率方法可在給定數(shù)目的訓(xùn)練樣例之后界定變型空間為-詳盡的。定理7.1（變型空間的-詳盡化）若假設(shè)空間H有限，且D為目標(biāo)概念c的一系列m>=1個(gè)獨(dú)立隨機(jī)抽取的樣例，那么對(duì)于任意0=<<=1，變型空間VSH,D不是-詳盡的概率小于或等于：只有知道目標(biāo)概念的觀察者才能確定變型空間是否為-81證明：令h1,...,hk為H中關(guān)于c的真實(shí)錯(cuò)誤率大于的所有假設(shè)。當(dāng)且僅當(dāng)k個(gè)假設(shè)中至少有一個(gè)恰好與所有m個(gè)獨(dú)立隨機(jī)抽取樣例一致時(shí)，不能使變型空間-詳盡化。任一假設(shè)真實(shí)錯(cuò)誤率大于，且與一個(gè)隨機(jī)抽取樣例一致的可能性最多為1-，因此，該假設(shè)與m個(gè)獨(dú)立抽取樣例一致的概率最多為(1-)m由于已知有k個(gè)假設(shè)錯(cuò)誤率大于，那么至少有一個(gè)與所有m個(gè)訓(xùn)練樣例都不一致的概率最多為（當(dāng)，則）因此證畢#證明：令h1,...,hk為H中關(guān)于c的真實(shí)錯(cuò)誤率大于的所82

定理7.1基于訓(xùn)練樣例的數(shù)目m、允許的錯(cuò)誤率和H的大小，給出了變型空間不是-詳盡的概率的上界。換言之它對(duì)于使用假設(shè)空間H的任意學(xué)習(xí)器界定了m個(gè)訓(xùn)練樣例未能將所有“壞”的假設(shè)（錯(cuò)誤率大于的假設(shè)）剔除出去的概率利用上面的結(jié)論來確定為了減少此“未剔除”概率到一希望程度所需的訓(xùn)練樣例數(shù)。由可以得到定理7.1基于訓(xùn)練樣例的數(shù)目m、允許的錯(cuò)誤率和83

式子7.2提供了訓(xùn)練樣例數(shù)目的一般邊界，該數(shù)目的樣例足以在所期望的值和程度下，使任何一致學(xué)習(xí)器成功地學(xué)習(xí)到H中的任意目標(biāo)概念。訓(xùn)練樣例的數(shù)目m足以保證任意一致假設(shè)是可能（可能性為1-）近似（錯(cuò)誤率為）正確的m隨著1/線性增長，隨著1/和假設(shè)空間的規(guī)模對(duì)數(shù)增長上面的界限可能是過高的估計(jì)，主要來源于|H|項(xiàng)，它產(chǎn)生于證明過程中在所有可能假設(shè)上計(jì)算那些不可接受的假設(shè)的概率和。在7.4節(jié)討論一個(gè)更緊湊的邊界以及能夠覆蓋無限大的假設(shè)空間的邊界。式子7.2提供了訓(xùn)練樣例數(shù)目的一般邊界，該數(shù)目84

如果學(xué)習(xí)器不假定目標(biāo)概念可在H中表示，而只簡單地尋找具有最小訓(xùn)練錯(cuò)誤率的假設(shè)，這樣的學(xué)習(xí)器稱為不可知學(xué)習(xí)器式7.2基于的假定是學(xué)習(xí)器輸出一零錯(cuò)誤率假設(shè)，在更一般的情形下學(xué)習(xí)器考慮到了有非零訓(xùn)練錯(cuò)誤率的假設(shè)時(shí)，仍能找到一個(gè)簡單的邊界。7-3不可知學(xué)習(xí)和不一致假設(shè)如果學(xué)習(xí)器不假定目標(biāo)概念可在H中表示，而只簡單地尋85

令S代表學(xué)習(xí)器可觀察到的特定訓(xùn)練樣例集合，errorS(h)表示h的訓(xùn)練錯(cuò)誤率，即S中被h誤分類的訓(xùn)練樣例所占比例令hbest表示H中有最小訓(xùn)練錯(cuò)誤率的假設(shè)，問題是：多少訓(xùn)練樣例才足以保證其真實(shí)錯(cuò)誤率errorD(hbest)不會(huì)多+errorS(hbest)

（上一節(jié)問題是這個(gè)問題的特例）？前面問題的回答使用類似定理7.1的證明方法，這里有必要引入一般的Hoeffding邊界。令S代表學(xué)習(xí)器可觀察到的特定訓(xùn)練樣例集合，erro86Hoeffding邊界表明，當(dāng)訓(xùn)練錯(cuò)誤率errorS(h)在包含m個(gè)隨機(jī)抽取樣例的集合S上測(cè)量時(shí)，則：上式給出了一個(gè)概率邊界，說明任意選擇的假設(shè)訓(xùn)練錯(cuò)誤率不能代表真實(shí)情況，為保證L尋找到的最佳的假設(shè)的錯(cuò)誤率有以上的邊界，我們必須考慮這|H|個(gè)假設(shè)中任一個(gè)有較大錯(cuò)誤率的概率：Hoeffding邊界表明，當(dāng)訓(xùn)練錯(cuò)誤率errorS(h)在87將上式左邊概率稱為，問多少個(gè)訓(xùn)練樣例m才足以使維持在一定值內(nèi)，求解得到：式7.3是式7.2的一般化情形，適用于當(dāng)最佳假設(shè)可能有非零訓(xùn)練錯(cuò)誤率時(shí)，學(xué)習(xí)器仍能選擇到最佳假設(shè)hH的情形。將上式左邊概率稱為，問多少個(gè)訓(xùn)練樣例m才足以使維持在一定88

我們已經(jīng)有了一個(gè)訓(xùn)練樣例數(shù)目的邊界，表示樣本數(shù)目為多少時(shí)才足以可能近似學(xué)習(xí)到目標(biāo)概念，現(xiàn)在用它來確定某些特定概念類別的樣本復(fù)雜度和PAC可學(xué)習(xí)性?？紤]目標(biāo)概念類C，它由布爾文字的合取表示。布爾文字是任意的布爾變量，或它的否定。問題：C是可PAC學(xué)習(xí)的嗎？若假設(shè)空間H定義為n個(gè)布爾文字的合取，則假設(shè)空間|H|的大小為3n，得到關(guān)于n布爾文字合取學(xué)習(xí)問題的樣本復(fù)雜性。7.3.1布爾文字的合取是PAC可學(xué)習(xí)的我們已經(jīng)有了一個(gè)訓(xùn)練樣例數(shù)目的邊界，表示樣本數(shù)89定理7.2：布爾合取式的PAC可學(xué)習(xí)性布爾文字合取的類C是用Find-S算法PAC可學(xué)習(xí)的證明：上式顯示了該概念類的樣本復(fù)雜度是n、1/和1/的多項(xiàng)式級(jí)，而且獨(dú)立于size(c)。為增量地處理每個(gè)訓(xùn)練樣例，F(xiàn)ind-S算法要求的運(yùn)算量根據(jù)n線性增長，并獨(dú)立于1/、1/和size(c)。因此這一概念類別是Find-S算法PAC可學(xué)習(xí)的。定理7.2：布爾合取式的PAC可學(xué)習(xí)性901無偏學(xué)習(xí)器（無歸納偏置）考慮一無偏概念類C，它包含與X相關(guān)的所有可教授概念，X中的實(shí)例定義為n個(gè)布爾值特征，則有無偏的目標(biāo)概念類在PAC模型下有指數(shù)級(jí)的樣本復(fù)雜度。7.3.2其它概念類別的PAC可學(xué)習(xí)性1無偏學(xué)習(xí)器（無歸納偏置）7.3.2其它概念類別的P912K項(xiàng)DNF和K-CNF概念某概念類有多項(xiàng)式級(jí)的樣本復(fù)雜度，但不能夠在多項(xiàng)式時(shí)間內(nèi)被學(xué)習(xí)到。概念類C為k項(xiàng)析取范式（k項(xiàng)DNF）的形式k項(xiàng)DNF：T1...Tk，其中每一個(gè)Ti為n個(gè)布爾屬性和它們的否定的合取。假定H=C，則|H|最多為3nk，代入式7.2，得到因此，k項(xiàng)DNF的樣本復(fù)雜度為1/、1/、n和k的多項(xiàng)式級(jí)但是計(jì)算復(fù)雜度不是多項(xiàng)式級(jí)，該問題是NP完全問題（等效于其他已知的不能在多項(xiàng)式時(shí)間內(nèi)解決的問題）2K項(xiàng)DNF和K-CNF概念92

因此，雖然k項(xiàng)DNF有多項(xiàng)式級(jí)的樣本復(fù)雜度，它對(duì)于使用H=C的學(xué)習(xí)器沒有多項(xiàng)式級(jí)的計(jì)算復(fù)雜度。令人吃驚的是，雖然k項(xiàng)DNF不是PAC可學(xué)習(xí)的，但存在一個(gè)更大的概念類是PAC可學(xué)習(xí)的這個(gè)更大的概念類是K-CNF，它有每樣例的多項(xiàng)式級(jí)時(shí)間復(fù)雜度，又有多項(xiàng)式級(jí)的樣本復(fù)雜度。K-CNF：任意長度的合取式T1...Tj，其中每個(gè)Ti為最多k個(gè)布爾變量的析取。容易證明K-CNF包含了K項(xiàng)DNF，因此概念類k項(xiàng)DNF是使用H=K-CNF的一個(gè)有效算法可PAC學(xué)習(xí)的。因此，雖然k項(xiàng)DNF有多項(xiàng)式級(jí)的樣本復(fù)雜度，93式子7.2用|H|刻畫樣本復(fù)雜度有兩個(gè)缺點(diǎn)：1可能導(dǎo)致非常弱的邊界2對(duì)于無限假設(shè)空間的情形，無法應(yīng)用本節(jié)考慮H的復(fù)雜度的另一種度量，稱為H的Vapnik-Chervonenkis維度（簡稱VC維或VC(H)）使用VC維代替|H|也可以得到樣本復(fù)雜度的邊界，基于VC維的樣本復(fù)雜度比|H|更緊湊，另外還可以刻畫無限假設(shè)空間的樣本復(fù)雜度.7-4無限假設(shè)空間的樣本復(fù)雜度式子7.2用|H|刻畫樣本復(fù)雜度有兩個(gè)缺點(diǎn)：7-4無限假設(shè)94VC維衡量假設(shè)空間復(fù)雜度的方法不是用不同假設(shè)的數(shù)量|H|，而是用X中能被H徹底區(qū)分的不同實(shí)例的數(shù)量.S是一個(gè)實(shí)例集，H中每個(gè)h導(dǎo)致S的一個(gè)劃分，即h將S分割為兩個(gè)子集{xS|h(x)=1}和{xS|h(x)=0}.定義：一實(shí)例集S被假設(shè)空間H打散，當(dāng)且僅當(dāng)對(duì)S的每個(gè)劃分，存在H中的某假設(shè)與此劃分一致如果一實(shí)例集合沒有被假設(shè)空間打散，那么必然存在某概念可被定義在實(shí)例集之上，但不能由假設(shè)空間表示.H的這種打散實(shí)例集合的能力是其表示這些實(shí)例上定義的目標(biāo)概念的能力的度量.7.4.1打散一個(gè)實(shí)例集合7.4.1打散一個(gè)實(shí)例集合95定義：定義在實(shí)例空間X上的假設(shè)空間H的Vapnik-Chervonenkis維，是可被H打散的X的最大有限子集的大小.如果X的任意有限大的子集可被H打散則VC(H)=.對(duì)于任意有限的H，VC(H)<=log2|H|。假定VC(H)=d;那么|H|需要2^d個(gè)實(shí)例。所以2^d<=|H|.

7.4.2Vapnik-Chervonenkis維度定義：定義在實(shí)例空間X上的假設(shè)空間H的Vapnik-Cher96下面看三個(gè)例子：例1：假定實(shí)例空間X為實(shí)數(shù)集合，而且H為實(shí)數(shù)軸上的區(qū)間的集合，問VC(H)是多少？只要找到能被H打散的X的最大子集，首先包含2個(gè)實(shí)例的集合能夠被H打散，其次包含3個(gè)實(shí)例的集合不能被H打散，因此VC(H)=2.注解：下面看三個(gè)例子：97例2：實(shí)例集合S對(duì)應(yīng)x、y平面上的點(diǎn)，令H為此平面內(nèi)所有線性決策面的集合，問H的VC維是多少？能夠找到3個(gè)點(diǎn)組成的集合，被H打散，但無法找到能夠被H打散的4個(gè)點(diǎn)組成的集合，因此VC(H)=3更一般地，在r維空間中，線性決策面的VC維為r+1注解：例2：實(shí)例集合S對(duì)應(yīng)x、y平面上的點(diǎn)，令H為此平面內(nèi)所有線98例3：假定X上每個(gè)實(shí)例由恰好3個(gè)布爾文字的合取表示，而且假定H中每個(gè)假設(shè)由至多3個(gè)布爾文字描述，問VC(H)是多少？找到下面3個(gè)實(shí)例的集合instance1:100instance2:010instance3:001這三個(gè)實(shí)例的集合可被H打散，可對(duì)如下任意所希望的劃分建立一假設(shè)：如果該劃分要排除instancei，就將文字li加入到假設(shè)中此討論很容易擴(kuò)展到特征數(shù)為n的情況，n個(gè)布爾文字合取的VC維至少為n實(shí)際就是n，但證明比較困難，需要說明n+1個(gè)實(shí)例的集合不可能被打散。例3：假定X上每個(gè)實(shí)例由恰好3個(gè)布爾文字的合取表示，而且假定99

使用VC維作為H復(fù)雜度的度量，就有可能推導(dǎo)出該問題的另一種解答，類似于式子7.2的邊界，即（Blumerelal.1989）定理7.3：樣本復(fù)雜度的下界考慮任意概念類C，且VC(C)>=2，任意學(xué)習(xí)器L，以及任意0<<1/8，0<<1/100。存在一個(gè)分布D以及C中一個(gè)目標(biāo)概念，當(dāng)L觀察到的樣例數(shù)目小于下式時(shí)：7.4.3樣本復(fù)雜度和VC維使用VC維作為H復(fù)雜度的度量，就有可能推導(dǎo)出該問題100L將以至少的概率輸出一假設(shè)h，使errorD(h)>。說明：若訓(xùn)練樣例的數(shù)目太少，那么沒有學(xué)習(xí)器能夠以PAC模型學(xué)習(xí)到任意非平凡的C中每個(gè)目標(biāo)概念。式子7.7給出了保證充足數(shù)量的上界，而定理7.3給出了下界。7-計(jì)算學(xué)習(xí)理論課件101本節(jié)給出一般性的結(jié)論，以計(jì)算分層無環(huán)網(wǎng)絡(luò)的VC維。這個(gè)VC維可用于界定訓(xùn)練樣例的數(shù)量，該數(shù)達(dá)到多大才足以按照希望的和值近似可能正確地學(xué)習(xí)一個(gè)前饋網(wǎng)絡(luò)考慮一個(gè)由單元組成的網(wǎng)絡(luò)G，它形成一個(gè)分層有向無環(huán)圖。分層有向無環(huán)圖的特點(diǎn)：1節(jié)點(diǎn)可劃分成層，即所有第l層出來的有向邊進(jìn)入到第l+1層節(jié)點(diǎn)2沒有有向環(huán)，即有向弧形成的回路7.4.4神經(jīng)網(wǎng)絡(luò)的VC維本節(jié)給出一般性的結(jié)論，以計(jì)算分層無環(huán)網(wǎng)絡(luò)的VC維。這個(gè)VC維102這樣網(wǎng)絡(luò)的VC維的界定可以基于其圖的結(jié)構(gòu)和構(gòu)造該圖的基本單元的VC維。定義一些術(shù)語G表示神經(jīng)網(wǎng)絡(luò)n是G的輸入數(shù)目G只有1個(gè)輸出節(jié)點(diǎn)G的每個(gè)內(nèi)部單元Ni最多有r個(gè)輸入，并實(shí)現(xiàn)一布爾函數(shù)ci:Rr{0,1}，形成函數(shù)類C定義C的G-合成：網(wǎng)絡(luò)G能實(shí)現(xiàn)的所有函數(shù)的類，即網(wǎng)絡(luò)G表示的假設(shè)空間，表示成CG。這樣網(wǎng)絡(luò)的VC維的界定可以基于其圖的結(jié)構(gòu)和構(gòu)造該圖103定理7.4分層有向無環(huán)網(wǎng)絡(luò)的VC維：

令G為一分層有向無環(huán)圖，有n個(gè)輸入節(jié)點(diǎn)和s2個(gè)內(nèi)部節(jié)點(diǎn)，每個(gè)至少有r個(gè)輸入，令C為VC維為d的Rr上的概念類，對(duì)應(yīng)于可由每個(gè)內(nèi)部節(jié)點(diǎn)s描述的函數(shù)集合，令CG為C的G合成，對(duì)應(yīng)于可由G表示的函數(shù)集合，則VC(CG)<=2dslog(es)。假定要考慮的分層有向無環(huán)網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)都是感知器，由于單獨(dú)的r輸入感知器VC維為r+1，代入定理7.4和式子7.7，得到定理7.4分層有向無環(huán)網(wǎng)絡(luò)的VC維：104上面的結(jié)果不能直接應(yīng)用于反向傳播的網(wǎng)絡(luò)，原因有兩個(gè)：1此結(jié)果應(yīng)用于感知器網(wǎng)絡(luò)，而不是sigmoid單元網(wǎng)絡(luò)。2不能處理反向傳播中的訓(xùn)練過程?？偨Y(jié)。上面的結(jié)果不能直接應(yīng)用于反向傳播的網(wǎng)絡(luò)，原因有兩個(gè)：1057.5學(xué)習(xí)的出錯(cuò)界限模型計(jì)算學(xué)習(xí)理論考慮多種不同的問題框架訓(xùn)練樣例的生成方式（被動(dòng)觀察、主動(dòng)提出查詢）數(shù)據(jù)中的噪聲（有噪聲或無噪聲）成功學(xué)習(xí)的定義（必須學(xué)到正確的目標(biāo)概念還是有一定的可能性和近似性）學(xué)習(xí)器所做得假定（實(shí)例的分布情況以及是否CH）評(píng)估學(xué)習(xí)器的度量標(biāo)準(zhǔn)（訓(xùn)練樣例數(shù)量、出錯(cuò)數(shù)量、計(jì)算時(shí)間）7.5學(xué)習(xí)的出錯(cuò)界限模型計(jì)算學(xué)習(xí)理論考慮多種不同的問題框架106機(jī)器學(xué)習(xí)的出錯(cuò)界限模型學(xué)習(xí)器的評(píng)估標(biāo)準(zhǔn)是它在收斂到正確假設(shè)前總的出錯(cuò)數(shù)學(xué)習(xí)器每接受到一個(gè)樣例x，先預(yù)測(cè)目標(biāo)值c(x)，然后施教者給出正確的目標(biāo)值考慮的問題是：在學(xué)習(xí)器學(xué)習(xí)到目標(biāo)概念前，它的預(yù)測(cè)會(huì)有多少次出錯(cuò)下面討論中，只考慮學(xué)習(xí)器確切學(xué)到目標(biāo)概念前出錯(cuò)的次數(shù)，確切學(xué)到的含義是xh(x)=c(x)機(jī)器學(xué)習(xí)的出錯(cuò)界限模型1077.5.1Find-S算法的出錯(cuò)界限Find-S算法的一個(gè)簡單實(shí)現(xiàn)將h初始化為最特殊假設(shè)l1l1...lnln對(duì)每個(gè)正例x從h中移去任何不滿足x的文字輸出假設(shè)h計(jì)算一個(gè)邊界，以描述Find-S在確切學(xué)到目標(biāo)概念c前全部的出錯(cuò)次數(shù)Find-S永遠(yuǎn)不會(huì)將一反例錯(cuò)誤地劃分為正例，因此只需要計(jì)算將正例劃分為反例的出錯(cuò)次數(shù)遇到第一個(gè)正例，初始假設(shè)中2n個(gè)項(xiàng)半數(shù)被刪去，對(duì)后續(xù)的被當(dāng)前假設(shè)誤分類的正例，至少有一項(xiàng)從假設(shè)中刪去出錯(cuò)總數(shù)至多為n+17.5.1Find-S算法的出錯(cuò)界限Find-S算法的一個(gè)1087.5.2Halving算法的出錯(cuò)界限學(xué)習(xí)器對(duì)每個(gè)新實(shí)例x做出預(yù)測(cè)的方法是：從當(dāng)前變型空間的所有假設(shè)中取多數(shù)票得來將變型空間學(xué)習(xí)和用多數(shù)票來進(jìn)行后續(xù)預(yù)測(cè)結(jié)合起來的算法稱為Halving算法Halving算法只有在當(dāng)前變型空間的多數(shù)假設(shè)不能正確分類新樣例時(shí)出錯(cuò)，此時(shí)變型空間至少可減少到它的一半大小，因此出錯(cuò)界線是log2|H|Halving算法有可能不出任何差錯(cuò)就確切學(xué)習(xí)到目標(biāo)概念，因?yàn)榧词苟鄶?shù)票是正確的，算法仍將移去那些不正確、少數(shù)票假設(shè)Halving算法的一個(gè)擴(kuò)展是允許假設(shè)以不同的權(quán)值進(jìn)行投票（如貝葉斯最優(yōu)分類器和后面討論的加權(quán)多數(shù)算法）7.5.2Halving算法