計(jì)算學(xué)習(xí)理論

計(jì)算學(xué)習(xí)理論2003.12.181*第1頁(yè)，共54頁(yè)，2023年，2月20日，星期四概述本章從理論上刻畫(huà)了若干類(lèi)型的機(jī)器學(xué)習(xí)問(wèn)題中的困難和若干類(lèi)型的機(jī)器學(xué)習(xí)算法的能力這個(gè)理論要回答的問(wèn)題是：在什么樣的條件下成功的學(xué)習(xí)是可能的？在什么條件下某個(gè)特定的學(xué)習(xí)算法可保證成功運(yùn)行？這里考慮兩種框架：可能近似正確（PAC）確定了若干假設(shè)類(lèi)別，判斷它們能否從多項(xiàng)式數(shù)量的訓(xùn)練樣例中學(xué)習(xí)得到定義了一個(gè)對(duì)假設(shè)空間復(fù)雜度的自然度量，由它可以界定歸納學(xué)習(xí)所需的訓(xùn)練樣例數(shù)目出錯(cuò)界限框架考查了一個(gè)學(xué)習(xí)器在確定正確假設(shè)前可能產(chǎn)生的訓(xùn)練錯(cuò)誤數(shù)量2003.12.182*第2頁(yè)，共54頁(yè)，2023年，2月20日，星期四簡(jiǎn)介機(jī)器學(xué)習(xí)理論的一些問(wèn)題：是否可能獨(dú)立于學(xué)習(xí)算法確定學(xué)習(xí)問(wèn)題中固有的難度？能否知道為保證成功的學(xué)習(xí)有多少訓(xùn)練樣例是必要的或充足的？如果學(xué)習(xí)器被允許向施教者提出查詢(xún)，而不是觀察訓(xùn)練集的隨機(jī)樣本，會(huì)對(duì)所需樣例數(shù)目有怎樣的影響？能否刻畫(huà)出學(xué)習(xí)器在學(xué)到目標(biāo)函數(shù)前會(huì)有多少次出錯(cuò)？能否刻畫(huà)出一類(lèi)學(xué)習(xí)問(wèn)題中固有的計(jì)算復(fù)雜度？2003.12.183*第3頁(yè)，共54頁(yè)，2023年，2月20日，星期四簡(jiǎn)介（2）對(duì)所有這些問(wèn)題的一般回答還未知，但不完整的學(xué)習(xí)計(jì)算理論已經(jīng)開(kāi)始出現(xiàn)本章闡述了該理論中的一些關(guān)鍵結(jié)論，并提供了在特定問(wèn)題下一些問(wèn)題的答案主要討論在只給定目標(biāo)函數(shù)的訓(xùn)練樣例和候選假設(shè)空間的條件下，對(duì)該未知目標(biāo)函數(shù)的歸納學(xué)習(xí)問(wèn)題主要要解決的問(wèn)題是：需要多少訓(xùn)練樣例才足以成功地學(xué)習(xí)到目標(biāo)函數(shù)以及學(xué)習(xí)器在達(dá)到目標(biāo)前會(huì)出多少次錯(cuò)2003.12.184*第4頁(yè)，共54頁(yè)，2023年，2月20日，星期四簡(jiǎn)介（3）如果明確了學(xué)習(xí)問(wèn)題的如下屬性，那么有可能給出前面問(wèn)題的定量的上下界學(xué)習(xí)器所考慮的假設(shè)空間的大小和復(fù)雜度目標(biāo)概念須近似到怎樣的精度學(xué)習(xí)器輸出成功的假設(shè)的可能性訓(xùn)練樣例提供給學(xué)習(xí)器的方式本章不會(huì)著重于單獨(dú)的學(xué)習(xí)算法，而是在較寬廣的學(xué)習(xí)算法類(lèi)別中考慮問(wèn)題：樣本復(fù)雜度：學(xué)習(xí)器要收斂到成功假設(shè)，需要多少訓(xùn)練樣例？計(jì)算復(fù)雜度：學(xué)習(xí)器要收斂到成功假設(shè)，需要多大的計(jì)算量？出錯(cuò)界限：在成功收斂到一個(gè)假設(shè)前，學(xué)習(xí)器對(duì)訓(xùn)練樣例的錯(cuò)誤分類(lèi)有多少次？2003.12.185*第5頁(yè)，共54頁(yè)，2023年，2月20日，星期四簡(jiǎn)介（4）為了解決這些問(wèn)題需要許多特殊的條件設(shè)定，比如“成功”的學(xué)習(xí)器的設(shè)定學(xué)習(xí)器是否輸出等于目標(biāo)概念的假設(shè)只要求輸出的假設(shè)與目標(biāo)概念在多數(shù)時(shí)間內(nèi)意見(jiàn)一致學(xué)習(xí)器通常輸出這樣的假設(shè)學(xué)習(xí)器如何獲得訓(xùn)練樣例由一個(gè)施教者給出由學(xué)習(xí)器自己實(shí)驗(yàn)獲得按照某過(guò)程隨機(jī)生成2003.12.186*第6頁(yè)，共54頁(yè)，2023年，2月20日，星期四簡(jiǎn)介（5）7.2節(jié)介紹可能近似正確（PAC）學(xué)習(xí)框架7.3節(jié)在PAC框架下，分析幾種學(xué)習(xí)算法的樣本復(fù)雜度和計(jì)算復(fù)雜度7.4節(jié)介紹了假設(shè)空間復(fù)雜度的一個(gè)重要度量標(biāo)準(zhǔn)，稱(chēng)為VC維，并且將PAC分析擴(kuò)展到假設(shè)空間無(wú)限的情況7.5節(jié)介紹出錯(cuò)界限模型，并提供了前面章節(jié)中幾個(gè)學(xué)習(xí)算法出錯(cuò)數(shù)量的界限，最后介紹了加權(quán)多數(shù)算法2003.12.187*第7頁(yè)，共54頁(yè)，2023年，2月20日，星期四可能學(xué)習(xí)近似正確假設(shè)可能近似正確學(xué)習(xí)模型（PAC）指定PAC學(xué)習(xí)模型適用的問(wèn)題在此模型下，學(xué)習(xí)不同類(lèi)別的目標(biāo)函數(shù)需要多少訓(xùn)練樣例和多大的計(jì)算量本章的討論將限制在學(xué)習(xí)布爾值概念，且訓(xùn)練數(shù)據(jù)是無(wú)噪聲的（許多結(jié)論可擴(kuò)展到更一般的情形）2003.12.188*第8頁(yè)，共54頁(yè)，2023年，2月20日，星期四問(wèn)題框架X表示所有實(shí)例的集合，C代表學(xué)習(xí)器要學(xué)習(xí)的目標(biāo)概念集合，C中每個(gè)目標(biāo)概念c對(duì)應(yīng)于X的某個(gè)子集或一個(gè)等效的布爾函數(shù)c:X{0,1}假定實(shí)例按照某概率分布D從X中隨機(jī)產(chǎn)生學(xué)習(xí)器L在學(xué)習(xí)目標(biāo)概念時(shí)考慮可能假設(shè)的集合H。在觀察了一系列關(guān)于目標(biāo)概念c的訓(xùn)練樣例后，L必須從H中輸出某假設(shè)h，它是對(duì)c的估計(jì)我們通過(guò)h在從X中抽取的新實(shí)例上的性能來(lái)評(píng)估L是否成功。新實(shí)例與訓(xùn)練數(shù)據(jù)具有相同的概率分布我們要求L足夠一般，以至可以從C中學(xué)到任何目標(biāo)概念而不管訓(xùn)練樣例的分布如何，因此，我們會(huì)對(duì)C中所有可能的目標(biāo)概念和所有可能的實(shí)例分布D進(jìn)行最差情況的分析2003.12.189*第9頁(yè)，共54頁(yè)，2023年，2月20日，星期四假設(shè)的錯(cuò)誤率為了描述學(xué)習(xí)器輸出的假設(shè)h對(duì)真實(shí)目標(biāo)概念的逼近程度，首先要定義假設(shè)h對(duì)應(yīng)于目標(biāo)概念c和實(shí)例分布D的真實(shí)錯(cuò)誤率h的真實(shí)錯(cuò)誤率是應(yīng)用h到將來(lái)按分布D抽取的實(shí)例時(shí)的期望的錯(cuò)誤率定義：假設(shè)h的關(guān)于目標(biāo)概念c和分布D的真實(shí)錯(cuò)誤率為h誤分類(lèi)根據(jù)D隨機(jī)抽取的實(shí)例的概率2003.12.1810*第10頁(yè)，共54頁(yè)，2023年，2月20日，星期四假設(shè)的錯(cuò)誤率（2）圖7-1：h關(guān)于c的錯(cuò)誤率是隨機(jī)選取的實(shí)例落入h和c不一致的區(qū)間的概率真實(shí)錯(cuò)誤率緊密地依賴(lài)于未知的概率分布D如果D是一個(gè)均勻的概率分布，那么圖7-1中假設(shè)的錯(cuò)誤率為h和c不一致的空間在全部實(shí)例空間中的比例如果D恰好把h和c不一致區(qū)間中的實(shí)例賦予了很高的概率，相同的h和c將造成更高的錯(cuò)誤率h關(guān)于c的錯(cuò)誤率不能直接由學(xué)習(xí)器觀察到，L只能觀察到在訓(xùn)練樣例上h的性能訓(xùn)練錯(cuò)誤率：指代訓(xùn)練樣例中被h誤分類(lèi)的樣例所占的比例問(wèn)題：h的觀察到的訓(xùn)練錯(cuò)誤率對(duì)真實(shí)錯(cuò)誤率產(chǎn)生不正確估計(jì)的可能性多大？2003.12.1811*第11頁(yè)，共54頁(yè)，2023年，2月20日，星期四PAC可學(xué)習(xí)性我們的目標(biāo)是刻畫(huà)出這樣的目標(biāo)概念，它們能夠從合理數(shù)量的隨機(jī)抽取訓(xùn)練樣例中通過(guò)合理的計(jì)算量可靠地學(xué)習(xí)對(duì)可學(xué)習(xí)性的表述一種可能的選擇：為了學(xué)習(xí)到使errorD(h)=0的假設(shè)h，所需的訓(xùn)練樣例數(shù)這樣的選擇不可行：首先要求對(duì)X中每個(gè)可能的實(shí)例都提供訓(xùn)練樣例；其次要求訓(xùn)練樣例無(wú)誤導(dǎo)性可能近似學(xué)習(xí)：首先只要求學(xué)習(xí)器輸出錯(cuò)誤率限定在某常數(shù)范圍內(nèi)的假設(shè)，其次要求對(duì)所有的隨機(jī)抽取樣例序列的失敗的概率限定在某常數(shù)范圍內(nèi)只要求學(xué)習(xí)器可能學(xué)習(xí)到一個(gè)近似正確的假設(shè)2003.12.1812*第12頁(yè)，共54頁(yè)，2023年，2月20日，星期四PAC可學(xué)習(xí)性（2）PAC可學(xué)習(xí)性的定義考慮定義在長(zhǎng)度為n的實(shí)例集合X上的一概念類(lèi)別C，學(xué)習(xí)器L使用假設(shè)空間H。當(dāng)對(duì)所有cC，X上的分布D，和滿(mǎn)足0<,<1/2，學(xué)習(xí)器L將以至少1-輸出一假設(shè)hH，使errorD(h)，這時(shí)稱(chēng)C是使用H的L可PAC學(xué)習(xí)的，所使用的時(shí)間為1/，1/，n以及size(c)的多項(xiàng)式函數(shù)上面定義要求學(xué)習(xí)器L滿(mǎn)足兩個(gè)條件L必須以任意高的概率（1-）輸出一個(gè)錯(cuò)誤率任意低（）的假設(shè)學(xué)習(xí)過(guò)程必須是高效的，其時(shí)間最多以多項(xiàng)式方式增長(zhǎng)上面定義的說(shuō)明1/和1/表示了對(duì)輸出假設(shè)要求的強(qiáng)度，n和size(c)表示了實(shí)例空間X和概念類(lèi)別C中固有的復(fù)雜度n為X中實(shí)例的長(zhǎng)度，size(c)為概念c的編碼長(zhǎng)度2003.12.1813*第13頁(yè)，共54頁(yè)，2023年，2月20日，星期四PAC可學(xué)習(xí)性（3）在實(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)概念類(lèi)別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è)2003.12.1814*第14頁(yè)，共54頁(yè)，2023年，2月20日，星期四有限假設(shè)空間的樣本復(fù)雜度PAC可學(xué)習(xí)性很大程度上由所需的訓(xùn)練樣例數(shù)確定隨著問(wèn)題規(guī)模的增長(zhǎng)所帶來(lái)的所需訓(xùn)練樣例的增長(zhǎng)稱(chēng)為該學(xué)習(xí)問(wèn)題的樣本復(fù)雜度我們把樣本復(fù)雜度的討論限定于一致學(xué)習(xí)器（輸出完美擬合訓(xùn)練數(shù)據(jù)的學(xué)習(xí)器）能夠獨(dú)立于特定算法，推導(dǎo)出任意一致學(xué)習(xí)器所需訓(xùn)練樣例數(shù)的界限變型空間：能正確分類(lèi)訓(xùn)練樣例D的所有假設(shè)的集合。2003.12.1815*第15頁(yè)，共54頁(yè)，2023年，2月20日，星期四有限假設(shè)空間的樣本復(fù)雜度（2）變型空間的重要意義是：每個(gè)一致學(xué)習(xí)器都輸出一個(gè)屬于變型空間的假設(shè)因此界定任意一個(gè)一致學(xué)習(xí)器所需的樣例數(shù)量，只需要界定為保證變型中沒(méi)有不可接受假設(shè)所需的樣例數(shù)量定義：考慮一假設(shè)空間H，目標(biāo)概念c，實(shí)例分布D以及c的一組訓(xùn)練樣例S。當(dāng)VSH,D中每個(gè)假設(shè)h關(guān)于c和D錯(cuò)誤率小于時(shí)，變型空間被稱(chēng)為c和D是-詳盡的。2003.12.1816*第16頁(yè)，共54頁(yè)，2023年，2月20日，星期四有限假設(shè)空間的樣本復(fù)雜度（3）-詳盡的變型空間表示與訓(xùn)練樣例一致的所有假設(shè)的真實(shí)錯(cuò)誤率都小于從學(xué)習(xí)器的角度看，所能知道的只是這些假設(shè)能同等地?cái)M合訓(xùn)練數(shù)據(jù)，它們都有零訓(xùn)練錯(cuò)誤率只有知道目標(biāo)概念的觀察者才能確定變型空間是否為-詳盡的但是，即使不知道確切的目標(biāo)概念或訓(xùn)練樣例抽取的分布，一種概率方法可在給定數(shù)目的訓(xùn)練樣例之后界定變型空間為-詳盡的2003.12.1817*第17頁(yè)，共54頁(yè)，2023年，2月20日，星期四有限假設(shè)空間的樣本復(fù)雜度（4）定理7.1（變型空間的-詳盡化）若假設(shè)空間H有限，且D為目標(biāo)概念c的一系列m>=1個(gè)獨(dú)立隨機(jī)抽取的樣例，那么對(duì)于任意0=<<=1，變型空間VSH,D不是-詳盡的概率小于或等于：證明：令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)，則）2003.12.1818*第18頁(yè)，共54頁(yè)，2023年，2月20日，星期四有限假設(shè)空間的樣本復(fù)雜度（5）定理7.1基于訓(xùn)練樣例的數(shù)目m、允許的錯(cuò)誤率和H的大小，給出了變型空間不是-詳盡的概率的上界即它對(duì)于使用假設(shè)空間H的任意學(xué)習(xí)器界定了m個(gè)訓(xùn)練樣例未能將所有“壞”的假設(shè)（錯(cuò)誤率大于的假設(shè)）剔除出去的概率利用上面的結(jié)論來(lái)確定為了減少此“未剔除”概率到一希望程度所需的訓(xùn)練樣例數(shù)由解出m，得到2003.12.1819*第19頁(yè)，共54頁(yè)，2023年，2月20日，星期四有限假設(shè)空間的樣本復(fù)雜度（6）式子7.2提供了訓(xùn)練樣例數(shù)目的一般邊界，該數(shù)目的樣例足以在所期望的值和程度下，使任何一致學(xué)習(xí)器成功地學(xué)習(xí)到H中的任意目標(biāo)概念訓(xùn)練樣例的數(shù)目m足以保證任意一致假設(shè)是可能（可能性為1-）近似（錯(cuò)誤率為）正確的m隨著1/線(xiàn)性增長(zhǎng)，隨著1/和假設(shè)空間的規(guī)模對(duì)數(shù)增長(zhǎng)上面的界限可能是過(guò)高的估計(jì)，主要來(lái)源于|H|項(xiàng)，它產(chǎn)生于證明過(guò)程中在所有可能假設(shè)上計(jì)算那些不可接受的假設(shè)的概率和在7.4節(jié)討論一個(gè)更緊湊的邊界以及能夠覆蓋無(wú)限大的假設(shè)空間的邊界2003.12.1820*第20頁(yè)，共54頁(yè)，2023年，2月20日，星期四不可知學(xué)習(xí)和不一致假設(shè)如果學(xué)習(xí)器不假定目標(biāo)概念可在H中表示，而只簡(jiǎn)單地尋找具有最小訓(xùn)練錯(cuò)誤率的假設(shè)，這樣的學(xué)習(xí)器稱(chēng)為不可知學(xué)習(xí)器式7.2基于的假定是學(xué)習(xí)器輸出一零錯(cuò)誤率假設(shè)，在更一般的情形下學(xué)習(xí)器考慮到了有非零訓(xùn)練錯(cuò)誤率的假設(shè)時(shí)，仍能找到一個(gè)簡(jiǎn)單的邊界令S代表學(xué)習(xí)器可觀察到的特定訓(xùn)練樣例集合，errorS(h)表示h的訓(xùn)練錯(cuò)誤率，即S中被h誤分類(lèi)的訓(xùn)練樣例所占比例令hbest表示H中有最小訓(xùn)練錯(cuò)誤率的假設(shè)，問(wèn)題是：多少訓(xùn)練樣例才足以保證其真實(shí)錯(cuò)誤率errorD(hbest)不會(huì)多于+errorS(hbest)？（上一節(jié)問(wèn)題是這個(gè)問(wèn)題的特例）2003.12.1821*第21頁(yè)，共54頁(yè)，2023年，2月20日，星期四不可知學(xué)習(xí)和不一致假設(shè)（2）前面問(wèn)題的回答使用類(lèi)似定理7.1的證明方法，這里有必要引入一般的Hoeffding邊界Hoeffding邊界刻畫(huà)的是某事件的真實(shí)概率及其m個(gè)獨(dú)立試驗(yàn)中觀察到的頻率之間的差異Hoeffding邊界表明，當(dāng)訓(xùn)練錯(cuò)誤率errorS(h)在包含m個(gè)隨機(jī)抽取樣例的集合S上測(cè)量時(shí)，則上式給出了一個(gè)概率邊界，說(shuō)明任意選擇的假設(shè)訓(xùn)練錯(cuò)誤率不能代表真實(shí)情況，為保證L尋找到的最佳的假設(shè)的錯(cuò)誤率有以上的邊界，我們必須考慮這|H|個(gè)假設(shè)中任一個(gè)有較大錯(cuò)誤率的概率2003.12.1822*第22頁(yè)，共54頁(yè)，2023年，2月20日，星期四不可知學(xué)習(xí)和不一致假設(shè)（3）將上式左邊概率稱(chēng)為，問(wèn)多少個(gè)訓(xùn)練樣例m才足以使維持在一定值內(nèi)，求解得到式7.3是式7.2的一般化情形，適用于當(dāng)最佳假設(shè)可能有非零訓(xùn)練錯(cuò)誤率時(shí)，學(xué)習(xí)器仍能選擇到最佳假設(shè)hH的情形。2003.12.1823*第23頁(yè)，共54頁(yè)，2023年，2月20日，星期四布爾文字的合取是PAC可學(xué)習(xí)的我們已經(jīng)有了一個(gè)訓(xùn)練樣例數(shù)目的邊界，表示樣本數(shù)目為多少時(shí)才足以可能近似學(xué)習(xí)到目標(biāo)概念，現(xiàn)在用它來(lái)確定某些特定概念類(lèi)別的樣本復(fù)雜度和PAC可學(xué)習(xí)性考慮目標(biāo)概念類(lèi)C，它由布爾文字的合取表示。布爾文字是任意的布爾變量，或它的否定。問(wèn)題：C是可PAC學(xué)習(xí)的嗎？若假設(shè)空間H定義為n個(gè)布爾文字的合取，則假設(shè)空間|H|的大小為3n，得到關(guān)于n布爾文字合取學(xué)習(xí)問(wèn)題的樣本復(fù)雜度2003.12.1824*第24頁(yè)，共54頁(yè)，2023年，2月20日，星期四布爾文字的合取是PAC可學(xué)習(xí)的（2）定理7.2：布爾合取式的PAC可學(xué)習(xí)性布爾文字合取的類(lèi)C是用Find-S算法PAC可學(xué)習(xí)的證明：式7.4顯示了該概念類(lèi)的樣本復(fù)雜度是n、1/和1/的多項(xiàng)式級(jí)，而且獨(dú)立于size(c)。為增量地處理每個(gè)訓(xùn)練樣例，F(xiàn)ind-S算法要求的運(yùn)算量根據(jù)n線(xiàn)性增長(zhǎng)，并獨(dú)立于1/、1/和size(c)。因此這一概念類(lèi)別是Find-S算法PAC可學(xué)習(xí)的。2003.12.1825*第25頁(yè)，共54頁(yè)，2023年，2月20日，星期四其他概念類(lèi)別的PAC可學(xué)習(xí)性無(wú)偏學(xué)習(xí)器（無(wú)歸納偏置）考慮一無(wú)偏概念類(lèi)C，它包含與X相關(guān)的所有可教授概念，X中的實(shí)例定義為n個(gè)布爾值特征，則有無(wú)偏的目標(biāo)概念類(lèi)在PAC模型下有指數(shù)級(jí)的樣本復(fù)雜度2003.12.1826*第26頁(yè)，共54頁(yè)，2023年，2月20日，星期四其他概念類(lèi)別的PAC可學(xué)習(xí)性（2）K項(xiàng)DNF和K-CNF概念某概念類(lèi)有多項(xiàng)式級(jí)的樣本復(fù)雜度，但不能夠在多項(xiàng)式時(shí)間內(nèi)被學(xué)習(xí)到概念類(lèi)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í)，該問(wèn)題是NP完全問(wèn)題（等效于其他已知的不能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題）因此，雖然k項(xiàng)DNF有多項(xiàng)式級(jí)的樣本復(fù)雜度，它對(duì)于使用H=C的學(xué)習(xí)器沒(méi)有多項(xiàng)式級(jí)的計(jì)算復(fù)雜度2003.12.1827*第27頁(yè)，共54頁(yè)，2023年，2月20日，星期四其他概念類(lèi)別的PAC可學(xué)習(xí)性（3）令人吃驚的是，雖然k項(xiàng)DNF不是PAC可學(xué)習(xí)的，但存在一個(gè)更大的概念類(lèi)是PAC可學(xué)習(xí)的這個(gè)更大的概念類(lèi)是K-CNF，它有每樣例的多項(xiàng)式級(jí)時(shí)間復(fù)雜度，又有多項(xiàng)式級(jí)的樣本復(fù)雜度K-CNF：任意長(zhǎng)度的合取式T1...Tj，其中每個(gè)Ti為最多k個(gè)布爾變量的析取容易證明K-CNF包含了K項(xiàng)DNF，因此概念類(lèi)k項(xiàng)DNF是使用H=K-CNF的一個(gè)有效算法可PAC學(xué)習(xí)的2003.12.1828*第28頁(yè)，共54頁(yè)，2023年，2月20日，星期四無(wú)限假設(shè)空間的樣本復(fù)雜度式子7.2用|H|刻畫(huà)樣本復(fù)雜度有兩個(gè)缺點(diǎn)：可能導(dǎo)致非常弱的邊界對(duì)于無(wú)限假設(shè)空間的情形，無(wú)法應(yīng)用本節(jié)考慮H的復(fù)雜度的另一種度量，稱(chēng)為H的Vapnik-Chervonenkis維度（簡(jiǎn)稱(chēng)VC維或VC(H)）使用VC維代替|H|也可以得到樣本復(fù)雜度的邊界，基于VC維的樣本復(fù)雜度比|H|更緊湊，另外還可以刻畫(huà)無(wú)限假設(shè)空間的樣本復(fù)雜度2003.12.1829*第29頁(yè)，共54頁(yè)，2023年，2月20日，星期四打散一個(gè)實(shí)例集合VC維衡量假設(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í)例集合沒(méi)有被假設(shè)空間打散，那么必然存在某概念可被定義在實(shí)例集之上，但不能由假設(shè)空間表示H的這種打散實(shí)例集合的能力是其表示這些實(shí)例上定義的目標(biāo)概念的能力的度量2003.12.1830*第30頁(yè)，共54頁(yè)，2023年，2月20日，星期四Vapnik-Chervonenkis維度打散一實(shí)例集合的能力與假設(shè)空間的歸納偏置緊密相關(guān)無(wú)偏的假設(shè)空間能夠打散所有實(shí)例組成的集合X直觀上，被打散的X的子集越大，H的表示能力越強(qiáng)定義：定義在實(shí)例空間X上的假設(shè)空間H的Vapnik-Chervonenkis維，是可被H打散的X的最大有限子集的大小如果X的任意有限大的子集可被H打散，則VC(H)=2003.12.1831*第31頁(yè)，共54頁(yè)，2023年，2月20日，星期四Vapnik-Chervonenkis維度（2）對(duì)于任意有限的H，VC(H)<=log2|H|VC維舉例假定實(shí)例空間X為實(shí)數(shù)集合，而且H為實(shí)數(shù)軸上的區(qū)間的集合，問(wèn)VC(H)是多少？只要找到能被H打散的X的最大子集，首先包含2個(gè)實(shí)例的集合能夠被H打散，其次包含3個(gè)實(shí)例的集合不能被H打散，因此VC(H)=2實(shí)例集合S對(duì)應(yīng)x、y平面上的點(diǎn)，令H為此平面內(nèi)所有線(xiàn)性決策面的集合，問(wèn)H的VC維是多少？能夠找到3個(gè)點(diǎn)組成的集合，被H打散，但無(wú)法找到能夠被H打散的4個(gè)點(diǎn)組成的集合，因此VC(H)=3更一般地，在r維空間中，線(xiàn)性決策面的VC維為r+12003.12.1832*第32頁(yè)，共54頁(yè)，2023年，2月20日，星期四Vapnik-Chervonenkis維度（3）假定X上每個(gè)實(shí)例由恰好3個(gè)布爾文字的合取表示，而且假定H中每個(gè)假設(shè)由至多3個(gè)布爾文字描述，問(wèn)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，但證明比較困難，需要說(shuō)明n+1個(gè)實(shí)例的集合不可能被打散2003.12.1833*第33頁(yè)，共54頁(yè)，2023年，2月20日，星期四樣本復(fù)雜度和VC維使用VC維作為H復(fù)雜度的度量，就有可能推導(dǎo)出該問(wèn)題的另一種解答，類(lèi)似于式子7.2的邊界，即（Blumerelal.1989）定理7.3：樣本復(fù)雜度的下界（Ehrenfeuchtetal.1989）考慮任意概念類(lèi)C，且VC(C)>=2，任意學(xué)習(xí)器L，以及任意0<<1/8，0<<1/100。存在一個(gè)分布D以及C中一個(gè)目標(biāo)概念，當(dāng)L觀察到的樣例數(shù)目小于下式時(shí)：

L將以至少的概率輸出一假設(shè)h，使errorD(h)>2003.12.1834*第34頁(yè)，共54頁(yè)，2023年，2月20日，星期四樣本復(fù)雜度和VC維（2）定理7.3說(shuō)明，若訓(xùn)練樣例的數(shù)目太少，那么沒(méi)有學(xué)習(xí)器能夠以PAC模型學(xué)習(xí)到任意非平凡的C中每個(gè)目標(biāo)概念式子7.7給出了保證充足數(shù)量的上界，而定理7.3給出了下界2003.12.1835*第35頁(yè)，共54頁(yè)，2023年，2月20日，星期四神經(jīng)網(wǎng)絡(luò)的VC維本節(jié)給出一般性的結(jié)論，以計(jì)算分層無(wú)環(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è)分層有向無(wú)環(huán)圖分層有向無(wú)環(huán)圖的特點(diǎn)：節(jié)點(diǎn)可劃分成層，即所有第l層出來(lái)的有向邊進(jìn)入到第l+1層節(jié)點(diǎn)沒(méi)有有向環(huán)，即有向弧形成的回路這樣網(wǎng)絡(luò)的VC維的界定可以基于其圖的結(jié)構(gòu)和構(gòu)造該圖的基本單元的VC維2003.12.1836*第36頁(yè)，共54頁(yè)，2023年，2月20日，星期四神經(jīng)網(wǎng)絡(luò)的VC維（2）定義一些術(shù)語(yǔ)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ù)類(lèi)C定義C的G-合成：網(wǎng)絡(luò)G能實(shí)現(xiàn)的所有函數(shù)的類(lèi)，即網(wǎng)絡(luò)G表示的假設(shè)空間，表示成CG2003.12.1837*第37頁(yè)，共54頁(yè)，2023年，2月20日，星期四神經(jīng)網(wǎng)絡(luò)的VC維（3）定理7.4分層有向無(wú)環(huán)網(wǎng)絡(luò)的VC維（Kearns&Vazirani1994）令G為一分層有向無(wú)環(huán)圖，有n個(gè)輸入節(jié)點(diǎn)和s2個(gè)內(nèi)部節(jié)點(diǎn)，每個(gè)至少有r個(gè)輸入，令C為VC維為d的Rr上的概念類(lèi)，對(duì)應(yīng)于可由每個(gè)內(nèi)部節(jié)點(diǎn)s描述的函數(shù)集合，令CG為C的G合成，對(duì)應(yīng)于可由G表示的函數(shù)集合，則VC(CG)<=2dslog(es)2003.12.1838*第38頁(yè)，共54頁(yè)，2023年，2月20日，星期四神經(jīng)網(wǎng)絡(luò)的VC維（4）假定要考慮的分層有向無(wú)環(huán)網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)都是感知器，由于單獨(dú)的r輸入感知器VC維為r+1，代入定理7.4和式子7.7，得到上面的結(jié)果不能直接應(yīng)用于反向傳播的網(wǎng)絡(luò)，原因有兩個(gè)：此結(jié)果應(yīng)用于感知器網(wǎng)絡(luò)，而不是sigmoid單元網(wǎng)絡(luò)不能處理反向傳播中的訓(xùn)練過(guò)程2003.12.1839*第39頁(yè)，共54頁(yè)，2023年，2月20日，星期四學(xué)習(xí)的出錯(cuò)界限模型計(jì)算學(xué)習(xí)理論考慮多種不同的問(wèn)題框架訓(xùn)練樣例的生成方式（被動(dòng)觀察、主動(dòng)提出查詢(xún)）數(shù)據(jù)中的噪聲（有噪聲或無(wú)噪聲）成功學(xué)習(xí)的定義（必須學(xué)到正確的目標(biāo)概念還是有一定的可能性和近似性）學(xué)習(xí)器所做得假定（實(shí)例的分布情況以及是否CH）評(píng)估學(xué)習(xí)器的度量標(biāo)準(zhǔn)（訓(xùn)練樣例數(shù)量、出錯(cuò)數(shù)量、計(jì)算時(shí)間）2003.12.1840*第40頁(yè)，共54頁(yè)，2023年，2月20日，星期四學(xué)習(xí)的出錯(cuò)界限模型（2）機(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)值考慮的問(wèn)題是：在學(xué)習(xí)器學(xué)習(xí)到目標(biāo)概念前，它的預(yù)測(cè)會(huì)有多少次出錯(cuò)下面討論中，只考慮學(xué)習(xí)器確切學(xué)到目標(biāo)概念前出錯(cuò)的次數(shù)，確切學(xué)到的含義是xh(x)=c(x)2003.12.1841*第41頁(yè)，共54頁(yè)，2023年，2月20日，星期四Find-S算法的出錯(cuò)界限Find-S算法的一個(gè)簡(jiǎn)單實(shí)現(xiàn)將h初始化為最特殊假設(shè)l1l1...lnln對(duì)每個(gè)正例x從h中移去任何不滿(mǎn)足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è)誤分類(lèi)的正例，至少有一項(xiàng)從假設(shè)中刪去出錯(cuò)總數(shù)至多為n+12003.12.1842*第42頁(yè)，共54頁(yè)，2023年，2月20日，星期四Halving算法的出錯(cuò)界限學(xué)習(xí)器對(duì)每個(gè)新實(shí)例x做出預(yù)測(cè)的方法是：從當(dāng)前變型空間的所有假設(shè)中取多數(shù)票得來(lái)將變型空間學(xué)習(xí)和用多數(shù)票來(lái)進(jìn)行后續(xù)預(yù)測(cè)結(jié)合起來(lái)的算法稱(chēng)為Halving算法Halving算法只有在當(dāng)前變型空間的多數(shù)假設(shè)不能正確分類(lèi)新樣例時(shí)出錯(cuò)，此時(shí)變型空間至少可減少到它的一半大小，因此出錯(cuò)界線(xiàn)是log2|H|Halving算法有可能不出任何差錯(cuò)就確切學(xué)習(xí)到目標(biāo)概念，因?yàn)榧词苟鄶?shù)票是正確的，算法仍將移去那些不正確、少數(shù)票假設(shè)Halving算法的一個(gè)擴(kuò)展是允許假設(shè)以不同的權(quán)值進(jìn)行投票（如貝葉斯最優(yōu)分類(lèi)器和后面討論的加權(quán)多數(shù)算法）2003.12.1843*第43頁(yè)，共54頁(yè)，2023年，2月20日，星期四最優(yōu)出錯(cuò)界限問(wèn)題：對(duì)于任意概念類(lèi)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ì)于任意非空概念類(lèi)C，令MA(C)=maxcCMA(c)定義：C為任意非空概念類(lèi)，C的最優(yōu)出錯(cuò)界限定義為Opt(C)是所有可能學(xué)習(xí)算法A中MA(C)的最小值2003.12.1844*第44頁(yè)，共54頁(yè)，2023年，2月20日，星期四最優(yōu)出錯(cuò)界限（2）非形式地說(shuō)，Opt(C)是C中最難的那個(gè)目標(biāo)概念使用最不利的訓(xùn)練樣例序列用最好的算法時(shí)的出錯(cuò)次數(shù)Littlestone1987證明了2003.12.1845*第45頁(yè)，共54頁(yè)，2023年，2月20日，星期四加權(quán)多數(shù)算法Halving算法的更一般形式稱(chēng)為加權(quán)多數(shù)算法加權(quán)多數(shù)算法通過(guò)在一組預(yù)測(cè)算法中進(jìn)行加權(quán)投票來(lái)作出預(yù)測(cè)，并通過(guò)改變每個(gè)預(yù)測(cè)算法的權(quán)來(lái)學(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ù)量2003.12.1846*第46頁(yè)，共54頁(yè)，2023年，2月20日，星期四加權(quán)多數(shù)算法（2）加權(quán)多數(shù)算法一開(kāi)始將每個(gè)預(yù)測(cè)算法賦予權(quán)值1，然后考慮訓(xùn)練樣例，只要一個(gè)預(yù)測(cè)算法誤分類(lèi)新訓(xùn)練樣例，它的權(quán)被乘以某個(gè)系數(shù)β，0<=β<1。如果β=0，則是Halving算法如果β>0，則沒(méi)有一個(gè)預(yù)測(cè)算法會(huì)被完全去掉。如果一算法誤分類(lèi)一個(gè)樣例，那么它的權(quán)值變小2003.12.1847*第47頁(yè)，共54頁(yè)，2023年，2月20日，星期四加權(quán)多數(shù)算法（3）ai代表算法池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βwi2003.12.1848*第48頁(yè)，共54頁(yè)，2023年，2月20日，星期四加權(quán)多數(shù)算法（4）定理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)證明：可通過(guò)比較最佳預(yù)測(cè)算法的最終權(quán)和所有算法的權(quán)之和來(lái)證明。令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被