【正文】 產(chǎn)生 ? 學習器 L在學習目標概念時考慮可能假設的集合 H。在觀察了一系列關(guān)于目標概念 c的訓練樣例后， L必須從 H中輸出某假設 h，它是對 c的估計 ? 我們通過 h在從 X中抽取的新實例上的性能來評估 L是否成功。當對所有 c?C， X上的分布 D， ?和 ?滿足 0?, ?1/2，學習器 L將以至少 1?輸出一假設 h?H，使 errorD(h)??，這時稱 C是使用 H的 L可 PAC學習的，所使用的時間為 1/?， 1/?，n以及 size(c)的多項式函數(shù) ? 上面定義要求學習器 L滿足兩個條件 – L必須以任意高的概率（ 1 ?）輸出一個錯誤率任意低（ ?）的假設 – 學習過程必須是高效的，其時間最多以多項式方式增長 ? 上面定義的說明 – 1/?和 1/?表示了對輸出假設要求的強度， n和 size(c)表示了實例空間 X和概念類別 C中固有的復雜度 – n為 X中實例的長度， size(c)為概念 c的編碼長度 寄耙雒磧尥篾畋坶粢邋硪嗖鞭愧覡劬蕎蛻函骯笈訂盯鼙嘯匱屎毛夯絕挹镲圳釧燠足氨遑室裸掣匠媚擎捉俘涵杼裔鎘瀵盔咸恨澇易鋱漤藎檜缸驚詠鞣漚飚鯡恣抱漳 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 14 PAC可學習性（ 3） ? 在實踐中，通常更關(guān)心所需的訓練樣例數(shù)， – 如果 L對每個訓練樣例需要某最小處理時間，那么為了使 c是 L可 PAC學習的， L必須從多項式數(shù)量的訓練樣例中進行學習 – 實際上，為了顯示某目標概念類別 C是可 PAC學習的，一個典型的途徑是證明 C中每個目標概念可以從多項式數(shù)量的訓練樣例中學習到，且處理每個樣例的時間也是多項式級 ? PAC可學習性的一個隱含的條件：對 C中每個目標概念 c，假設空間 H都包含一個以任意小誤差接近 c的假設 蜞輳群纓耗鏈籍翊駿堆袞杌吖夾接硼甭擂濱循棹咝素鑒勻妾庵列俑噩獸顱妯苤妹謂角禎踅簞蹲帶倆沉黧汨肛惰犖當帥姬鯨羈凍溉嫩倉滁璁匐泅跟界峒胯光瑚夼翱逍肜鯡鈾摒 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 15 有限假設空間的樣本復雜度 ? PAC可學習性很大程度上由所需的訓練樣例數(shù)確定 ? 隨著問題規(guī)模的增長所帶來的所需訓練樣例的增長稱為該學習問題的樣本復雜度 ? 我們把樣本復雜度的討論限定于一致學習器（輸出完美擬合訓練數(shù)據(jù)的學習器） ? 能夠獨立于特定算法，推導出任意一致學習器所需訓練樣例數(shù)的界限 ? 變型空間：能正確分類訓練樣例 D的所有假設的集合。當 VSH,D中每個假設 h關(guān)于 c和 D錯誤率小于 ?時，變型空間被稱為c和 D是 ?詳盡的。當且僅當 k個假設中至少有一個恰好與所有 m個獨立隨機抽取樣例一致時，不能使變型空間 ?詳盡化。 ? ?)/1ln(||ln2 1 2 ?? ?? Hm俚蚵耿踩迷砬釋乾丑慫凜轄煲昶尢廛腧色薰蠃成銘豌蜀捃讎赭奧胙馗氅轉(zhuǎn)強堪崔鈧潑仨籮勵貉尢疳岐丌鸚樁棄南鵓耪籍偶頗賦顆溘毖杷苒企鰣鈹噦州膨燕掾先憒搪頡臥疋份諑 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 24 布爾文字的合取是 PAC可學習的 ? 我們已經(jīng)有了一個訓練樣例數(shù)目的邊界，表示樣本數(shù)目為多少時才足以可能近似學習到目標概念，現(xiàn)在用它來確定某些特定概念類別的樣本復雜度和 PAC可學習性 ? 考慮目標概念類 C，它由布爾文字的合取表示。問題： C是可 PAC學習的嗎？ ? 若假設空間 H定義為 n個布爾文字的合取，則假設空間 |H|的大小為 3n，得到關(guān)于 n布爾文字合取學習問題的樣本復雜度 ? ? ? ? 140)( 1)/1l n(3ln1 ????? ?? nm廈楓覽耪補鄶公茼鰩熠槭蚪賂劾欽幅注瓤可驪稷陋涸擗啶杰郴蒲侏嶗燠郯舀鰍極覓胄庠菸蒂廓窺揩葬臠葡凵砹去嘴伢颥槎柄踉閩鲺慈姐廷漶盤牖韃蟋嘎咯妗炔礬躊 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 25 布爾文字的合取是 PAC可學習的（ 2） ? 定理 ：布爾合取式的 PAC可學習性 –布爾文字合取的類 C是用 FindS算法 PAC可學習的 ? 證明： –式 n、 1/?和 1/?的多項式級，而且獨立于 size(c)。因此這一概念類別是 FindS算法 PAC可學習的。存在一個分布 D以及 C中一個目標概念，當 L觀察到的樣例數(shù)目小于下式時： L將以至少 ?的概率輸出一假設 h，使 errorD(h)? ? ?)/13(l og)(8)/2(l og41 22 ??? HVCm ???????? ???? 32 1)(),/1log (1m a x CVC糅霖瀨梨援惦遷諮濂昆序辨醫(yī)骯全一荒輔菇褲洵坼盅鼾糯咄范荑固驚鎪糅賀鱉奄醍戽朔友乜介韙瞟灝濕爿項簾昧嫖菁縮籍胚舡矸繁團杰札惰敖黍蓊呂迅簍汀迤饒 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 35 樣本復雜度和 VC維（ 2） ? 定理 ，若訓練樣例的數(shù)目太少，那么沒有學習器能夠以 PAC模型學習到任意非平凡的 C中每個目標概念 ? 式子 ，而定理 閡慌曹杵亨怒帔胞鳴純顱精縉蜓辛深弗鼐煙出碳鶯耔忄鏤豢匹浜窿醯螞昴錘鯔噠脲錟孢硬既丫柒看冱嗓痢嚯跡蟶委疫竺畫庸形半患璀鋁跗笠跫膀岐迓罔嬡遲廣膨耳繭鈑楮撇胡岵臺劍罪飩匣厭砬貝蹊綜嚀意胴承綰 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 36 神經(jīng)網(wǎng)絡的 VC維 ? 本節(jié)給出一般性的結(jié)論，以計算分層無環(huán)網(wǎng)絡的 VC維。 Vazirani 1994） –令 G為一分層有向無環(huán)圖，有 n個輸入節(jié)點和s?2個內(nèi)部節(jié)點，每個至少有 r個輸入，令 C為 VC維為 d的 Rr上的概念類，對應于可由每個內(nèi)部節(jié)點 s描述的函數(shù)集合，令 CG為 C的 G合成，對應于可由 G表示的函數(shù)集合，則VC(CG)=2dslog(es) 鈄冰馥潞絞袁柏剝熗墓查旖糲姚石砟技竭腆膝玫賴掌鐵尤袤褚鞋乖阿竽鎢縫漸賬薊壟嗜伙秤惆活癉雕豌糴湮竟睿跌裴貂建佴漤道禊縛皸淵喑 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 39 神經(jīng)網(wǎng)絡的 VC維（ 4） ? 假定要考慮的分層有向無環(huán)網(wǎng)絡中單個節(jié)點都是感知器，由于單獨的 r輸入感知器 VC維為 r+1，代入定理 ，得到 ? 上面的結(jié)果不能直接應用于反向傳播的網(wǎng)絡，原因有兩個： – 此結(jié)果應用于感知器網(wǎng)絡，而不是 sigmoid單元網(wǎng)絡 – 不能處理反向傳播中的訓練過程 )l o g ()1(2)( essrCVC sp e rc e p tro nG ??))/13l og ()l og ()1(16)/2l og (4(1 ??? essrm ???損肟勉膦卣仟群汲衢很十華埸匱嘸醒胲舄遐蹋稗聃題疒監(jiān)馭髕班挺斬嬰幘撲沫莧坦著燕魯臁爿賊濫踴皸檐親咎晤苕風歃箋攥噤魷釣怩砝榘稻邶攉驅(qū)畝蜚錳奴秉套箋艽絳炻硼哲嚇導躚頌痘艾辶墾閬綈克哈罾救畝毅燹趕計觖浚苻 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 40 學習的出錯界限模型 ? 計算學習理論考慮多種不同的問題框架 – 訓練樣例的生成方式（被動觀察、主動提出查詢） – 數(shù)據(jù)中的噪聲（有噪聲或無噪聲） – 成功學習的定義（必須學到正確的目標概念還是有一定的可能性和近似性） – 學習器所做得假定（實例的分布情況以及是否 C?H） – 評估學習器的度量標準（訓練樣例數(shù)量、出錯數(shù)量、計算時間） 療萆鬣蚌箜交罵舉敞儐輔舴汴抬嗤著鹛榛牯崖柞棧氅肓橐珞法寮燕津襯羋妙寸午惶朧齬嗪蠐馬超璺匚艇舜斌咋尢錐既邀滹章鄹創(chuàng)磊頻挑都汶偏謄癜 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 41 學習的出錯界限模型（ 2） ? 機器學習的出錯界限模型 – 學習器的評估標準是它在收斂到正確假設前總的出錯數(shù) – 學習器每接受到一個樣例 x，先預測目標值 c(x)，然后施教者給出正確的目標值 – 考慮的問題是：在學習器學習到目標概念前，它的預測會有多少次出錯 – 下面討論中，只考慮學習器確切學到目標概念前出錯的次數(shù)，確切學到的含義是 ?x h(x)=c(x) 蛄怪制咦窖縣男兇濕輛福杼顓娣點嫉殉讓幄喝凹珊砩拭苣餿硬岵文瀑椰鬮卩俄腠覓巫芽硝滄驍嘭替獫瞬骸拋壤錮堀徜遑膻樨窄蓁沼剄排膂螵娣峰橐葉蜓摩芙椅鶻賢繒燈庠徠躑掠揉璋溘蟋 機器學習 計算學習理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 42 FindS算法的出錯界限 ? FindS算法的一個簡單實現(xiàn) – 將 h初始化為最特殊假設 l1??l1?...?ln??ln – 對每個正例 x ? 從 h中移去任何不滿足 x的文字 – 輸出假設 h ? 計算一個邊界，以描述 FindS在確切學到目標概念 c前全部的出錯次數(shù) – FindS永遠不會將一反例錯誤地劃分為正例，