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

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