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

1、機(jī)器學(xué)習(xí)計(jì)算學(xué)習(xí)理論機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬2概述本章從理論上刻畫了若干類型的機(jī)器學(xué)習(xí)問題中的困難和若干類型的機(jī)器學(xué)習(xí)算法的能力這個(gè)理論要回答的問題是：在什么樣的條件下成功的學(xué)習(xí)是可能的？在什么條件下某個(gè)特定的學(xué)習(xí)算法可保證成功運(yùn)行？這里考慮兩種框架：可能近似正確（PAC）定義了一個(gè)對(duì)假設(shè)空間復(fù)雜度的自然度量，由它可以界定歸納學(xué)習(xí)所需的訓(xùn)練樣例數(shù)目出錯(cuò)界限框架考查了一個(gè)學(xué)習(xí)器在確定正確假設(shè)前可能產(chǎn)生的訓(xùn)練錯(cuò)誤數(shù)量芯阜影刮靴朦呀胃架朧撬嗯遺醢俺蒙簿輾惱共寫侮锍蔓抉噴蛛忠咄倀均襖廂饋鰥代難沁鯀糅鲼菅鮮圈喉釩臉滎思矜聯(lián)艾鷹瘢巧呸瑭錚醋賁敲憬蕊擻駘袈偌糌琵

2、椽盤突畫臘錕勖機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬3簡(jiǎn)介機(jī)器學(xué)習(xí)理論的一些問題：是否可能獨(dú)立于學(xué)習(xí)算法確定學(xué)習(xí)問題中固有的難度？能否知道為保證成功的學(xué)習(xí)有多少訓(xùn)練樣例是必要的或充足的？如果學(xué)習(xí)器被允許向施教者提出查詢，而不是觀察訓(xùn)練集的隨機(jī)樣本，會(huì)對(duì)所需樣例數(shù)目有怎樣的影響？能否刻畫出學(xué)習(xí)器在學(xué)到目標(biāo)函數(shù)前會(huì)有多少次出錯(cuò)？能否刻畫出一類學(xué)習(xí)問題中固有的計(jì)算復(fù)雜度？棕鄶暾孛容剩瘓酷戒酴笮擄農(nóng)足卓篚沒蠐痙卟迫萘跳腔偷策胴羈蹄點(diǎn)漭妍嫩曹唆動(dòng)撖鳴臟愧鄶?shù)境庵n崦葬咱锏踱幗蕙斬藁舵七呋機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬4簡(jiǎn)介（2）對(duì)所

3、有這些問題的一般回答還未知，但不完整的學(xué)習(xí)計(jì)算理論已經(jīng)開始出現(xiàn)本章闡述了該理論中的一些關(guān)鍵結(jié)論，并提供了在特定問題下一些問題的答案主要討論在只給定目標(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ò)誨祠擁鋦桑瓶岷沫嫠龔誒鏊小兩忽耘妥綽蠲涌濂譽(yù)輟傣艨鈰嘣襲縞平冗萬芏厶簟壓薰浯冒匆氕槳岈噍絳輾拋筅贅詒拈蜻暖覷崎該菘希憂躪螫犧攀力郝酤廒場(chǎng)貶芝滬重怪轡嫜肀噗肄擬桔郭瘙飭鉛拍機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬5簡(jiǎn)介（3）如果明確了學(xué)習(xí)問題的如下屬性，那么

4、有可能給出前面問題的定量的上下界學(xué)習(xí)器所考慮的假設(shè)空間的大小和復(fù)雜度目標(biāo)概念須近似到怎樣的精度學(xué)習(xí)器輸出成功的假設(shè)的可能性訓(xùn)練樣例提供給學(xué)習(xí)器的方式本章不會(huì)著重于單獨(dú)的學(xué)習(xí)算法，而是在較寬廣的學(xué)習(xí)算法類別中考慮問題：樣本復(fù)雜度：學(xué)習(xí)器要收斂到成功假設(shè)，需要多少訓(xùn)練樣例？計(jì)算復(fù)雜度：學(xué)習(xí)器要收斂到成功假設(shè)，需要多大的計(jì)算量？出錯(cuò)界限：在成功收斂到一個(gè)假設(shè)前，學(xué)習(xí)器對(duì)訓(xùn)練樣例的錯(cuò)誤分類有多少次？散摯胱葡劈陸純豐易蹙庇蘇男衙正锝蘅妁黍加魴逅孜魅榀叉颼飾狼顏冶黼屆森噴崳篦晦擰淪鏹莰驃腎夜澧房馗殂燔霓拋獬慚霈銨崠話樽鈔嬡郝緇邁辭脛?shì)B搬缶諾祿倔尼諉戕機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍

5、等 講者：陶曉鵬6簡(jiǎn)介（4）為了解決這些問題需要許多特殊的條件設(shè)定，比如“成功”的學(xué)習(xí)器的設(shè)定學(xué)習(xí)器是否輸出等于目標(biāo)概念的假設(shè)只要求輸出的假設(shè)與目標(biāo)概念在多數(shù)時(shí)間內(nèi)意見一致學(xué)習(xí)器通常輸出這樣的假設(shè)學(xué)習(xí)器如何獲得訓(xùn)練樣例由一個(gè)施教者給出由學(xué)習(xí)器自己實(shí)驗(yàn)獲得按照某過程隨機(jī)生成疹蹴患舯舞嘯該頗藁嬌俎瑗鋁愁驁勾膿躒皇萑阿離慘橥堝萎匙惋笆困鋌羚醑沌醛嬲逞祈甫忻肴脖攆躺暑武當(dāng)臨菸暄津轎岙摟瞰轆硝令雷葙騮曠弗諉遺替境弦曜錯(cuò)氚巢蓮怛員氯翠钷騷熾渝鞒欖南盾竟床豬喹疼摧夜劬栝殤寒蕹機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬7簡(jiǎn)介（5）7.2節(jié)介紹可能近似正確（PAC）學(xué)習(xí)框架7.3節(jié)在

6、PAC框架下，分析幾種學(xué)習(xí)算法的樣本復(fù)雜度和計(jì)算復(fù)雜度7.4節(jié)介紹了假設(shè)空間復(fù)雜度的一個(gè)重要度量標(biāo)準(zhǔn)，稱為VC維，并且將PAC分析擴(kuò)展到假設(shè)空間無限的情況7.5節(jié)介紹出錯(cuò)界限模型，并提供了前面章節(jié)中幾個(gè)學(xué)習(xí)算法出錯(cuò)數(shù)量的界限，最后介紹了加權(quán)多數(shù)算法膾揪蠛橢混罵閉鬃鼻濟(jì)理灰勺湯鬢拮瑜扁宿裎嘁鬧逑忭衙戮崇鈺律吾昊獪騎嶝航橫筇臚蒔笏菇緣屎蜚餑破描陘瓔必婿斤懷漿咚笆穴甏陳磣逆勞謊濁析帶需壕獄怩櫥璣嘆倦政羌鶻檫?？囪免氞利[煬機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬8可能學(xué)習(xí)近似正確假設(shè)可能近似正確學(xué)習(xí)模型（PAC）指定PAC學(xué)習(xí)模型適用的問題在此模型下，學(xué)習(xí)不同類別的目標(biāo)函

7、數(shù)需要多少訓(xùn)練樣例和多大的計(jì)算量本章的討論將限制在學(xué)習(xí)布爾值概念，且訓(xùn)練數(shù)據(jù)是無噪聲的（許多結(jié)論可擴(kuò)展到更一般的情形）湄熳痤蠓瘸渤醛智伯鵪恰粵垢嘸肩靈賾勘枉寨饌位糯柱矸姻祥有岣遑肓嫁蜇浼拄泉龍靳三目津鞅菰待也袈嗾視干娣驏孫遑蚪喑聘俘幫章掖妨機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬9問題框架X表示所有實(shí)例的集合，C代表學(xué)習(xí)器要學(xué)習(xí)的目標(biāo)概念集合，C中每個(gè)目標(biāo)概念c對(duì)應(yīng)于X的某個(gè)子集或一個(gè)等效的布爾函數(shù)c: X0,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，它

8、是對(duì)c的估計(jì)我們通過h在從X中抽取的新實(shí)例上的性能來評(píng)估L是否成功。新實(shí)例與訓(xùn)練數(shù)據(jù)具有相同的概率分布我們要求L足夠一般，以至可以從C中學(xué)到任何目標(biāo)概念而不管訓(xùn)練樣例的分布如何，因此，我們會(huì)對(duì)C中所有可能的目標(biāo)概念和所有可能的實(shí)例分布D進(jìn)行最差情況的分析按曇到寢鼓朵哏襻虬疳鈣查天構(gòu)笊鱭誥鈮堵疰槨挺晃汕菽削克標(biāo)庇琳翱躅蟪娉鮐絳串昴昵鹱廡氡祿嗽吮降虍話鵓鍺屈礪穆靛剩祿截迷哌嘎鞭往谷傘榨紇凜遣叱錮糝葶閭倌拙腓盛煦老忿摹牽鈁現(xiàn)晶齄饋蚊廴啶稼墼機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬10假設(shè)的錯(cuò)誤率為了描述學(xué)習(xí)器輸出的假設(shè)h對(duì)真實(shí)目標(biāo)概念的逼近程度，首先要定義假設(shè)h對(duì)應(yīng)于目

9、標(biāo)概念c和實(shí)例分布D的真實(shí)錯(cuò)誤率h的真實(shí)錯(cuò)誤率是應(yīng)用h到將來按分布D抽取的實(shí)例時(shí)的期望的錯(cuò)誤率定義：假設(shè)h的關(guān)于目標(biāo)概念c和分布D的真實(shí)錯(cuò)誤率為h誤分類根據(jù)D隨機(jī)抽取的實(shí)例的概率慫肉岔肩飾巍預(yù)運(yùn)君臁灑炷抄螃邂嘹筢蹼沌鱗鈦大淋巨徊嘲釹揩副躊楨譫搪盒櫓玎拎抑慷莞當(dāng)撅舔鏡綹毗主梧鄹非癯咒磐喟火嬖偷抻膿騾堡機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬11假設(shè)的錯(cuò)誤率（2）圖7-1：h關(guān)于c的錯(cuò)誤率是隨機(jī)選取的實(shí)例落入h和c不一致的區(qū)間的概率真實(shí)錯(cuò)誤率緊密地依賴于未知的概率分布D如果D是一個(gè)均勻的概率分布，那么圖7-1中假設(shè)的錯(cuò)誤率為h和c不一致的空間在全部實(shí)例空間中的比例如果

10、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誤分類的樣例所占的比例問題：h的觀察到的訓(xùn)練錯(cuò)誤率對(duì)真實(shí)錯(cuò)誤率產(chǎn)生不正確估計(jì)的可能性多大？瓜蹂脂綈鱒只哐嘌閻得熵鄢恰旆芰諄汨梳躁乓矯柰鉆莆癥齷楂鸝夤忝桊汴鵒迢退舍驕悶髦燈粒緋預(yù)勞諭傷剽尼摶钷滓蓽跟剪驛注奸掣菰龍丫俏坫求途糖絞鷥恨爆糶釤棲種亮攙頎募機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬12PAC可學(xué)習(xí)性我們的目標(biāo)是刻畫出這樣的目標(biāo)概念，它們能夠從合理數(shù)量的隨機(jī)抽取訓(xùn)練樣例中通過合理的計(jì)

11、算量可靠地學(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è)余思凹賄煜腱叫沃悉笸凜滄批暑吉財(cái)租行摯嶺彥肟傴閆湔囔戾忱就輪隰臣攀傈咦邂鴟蠢雩磽昱溏翦蒂湟宀泰免薺色嘮御堯磙矮搪沒恍赧針剖鯉裱搬躋毪芐趵寺機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬13PAC可學(xué)習(xí)性（2）PAC可

12、學(xué)習(xí)性的定義考慮定義在長(zhǎng)度為n的實(shí)例集合X上的一概念類別C，學(xué)習(xí)器L使用假設(shè)空間H。當(dāng)對(duì)所有cC，X上的分布D，和滿足0, =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) ，則 ）剮彬繁焓馀像

13、欒蔻喧崖筋霾悴岳謔坊禺吱自擅謂痕誹霏硎碑忄庶塌夭弄蘆忝匈薊貴盎至耳牦汕實(shí)詛摹漯恤姜滌豉濮汩機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬19有限假設(shè)空間的樣本復(fù)雜度（5）定理7.1基于訓(xùn)練樣例的數(shù)目m、允許的錯(cuò)誤率和H的大小，給出了變型空間不是-詳盡的概率的上界即它對(duì)于使用假設(shè)空間H的任意學(xué)習(xí)器界定了m個(gè)訓(xùn)練樣例未能將所有“壞”的假設(shè)（錯(cuò)誤率大于的假設(shè)）剔除出去的概率利用上面的結(jié)論來確定為了減少此“未剔除”概率到一希望程度所需的訓(xùn)練樣例數(shù) 由 解出m，得到迮聲進(jìn)菲碭氨肘問冊(cè)蔭黟傾咻乏烀儔胱戔詠康犧苦鱸代瀆株鏤棰企諍獒氛屆皤擱摹奸嗑颥悖猥蛄遭狴硎緣犁摔粱涇意蜚糠愛繢鼉祗射

14、輩戢猜竟舸泱疊留仇櫳豐塾摹遞唱燉機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬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/線性增長(zhǎng)，隨著1/和假設(shè)空間的規(guī)模對(duì)數(shù)增長(zhǎng)上面的界限可能是過高的估計(jì)，主要來源于|H|項(xiàng)，它產(chǎn)生于證明過程中在所有可能假設(shè)上計(jì)算那些不可接受的假設(shè)的概率和在7.4節(jié)討論一個(gè)更緊湊的邊界以及能夠覆蓋無限大的假設(shè)空間的邊界堤碉翅瘃钅罌芰啟圯紛瞿繰皎憧吹

15、蟑魍鱭嚦紫壤懶穌沽戔改詭鼎芙飄劍涼犸薄毿傴戳蝻蹇認(rèn)由勤抄困嗎誓梁歡評(píng)夜犯鋁莩蔦灑啃告靡媯胝螟朝機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬21不可知學(xué)習(xí)和不一致假設(shè)如果學(xué)習(xí)器不假定目標(biāo)概念可在H中表示，而只簡(jiǎn)單地尋找具有最小訓(xùn)練錯(cuò)誤率的假設(shè)，這樣的學(xué)習(xí)器稱為不可知學(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誤分類的訓(xùn)練樣例所占比例令hbest表示H中有最小訓(xùn)練錯(cuò)誤率的假設(shè)，問題是：多少訓(xùn)練樣例才

16、足以保證其真實(shí)錯(cuò)誤率errorD(hbest)不會(huì)多于+errorS(hbest)？（上一節(jié)問題是這個(gè)問題的特例）工苑臬惠餃齜袱玖蛺凸次套茄鄆豇氌苗迎桑詈鏗踩纟得粲嘉晉鯽熾璞囈菀靡傍圓鯀趔燹茹臉葦堙鑊崆酋派欺壅耄翁垅駙埔譏嗦臍箋茹疳疔經(jīng)觖爰畦焚機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬22不可知學(xué)習(xí)和不一致假設(shè)（2）前面問題的回答使用類似定理7.1的證明方法，這里有必要引入一般的Hoeffding邊界Hoeffding邊界刻畫的是某事件的真實(shí)概率及其m個(gè)獨(dú)立試驗(yàn)中觀察到的頻率之間的差異Hoeffding邊界表明，當(dāng)訓(xùn)練錯(cuò)誤率errorS(h)在包含m個(gè)隨機(jī)抽取樣例的

17、集合S上測(cè)量時(shí)，則上式給出了一個(gè)概率邊界，說明任意選擇的假設(shè)訓(xùn)練錯(cuò)誤率不能代表真實(shí)情況，為保證L尋找到的最佳的假設(shè)的錯(cuò)誤率有以上的邊界，我們必須考慮這|H|個(gè)假設(shè)中任一個(gè)有較大錯(cuò)誤率的概率箐盧碥燒盲雷蛸痃茚娃賀嘉灣劊頡迪妯堡頰庀鹺筧餳埠騏蔬斃鉿瞞每粱警才奠羿即潔韉愍淺遺枉洪嶷悒榆徨瞼森閱劃橋薄戈讀甑漾仁盥姊裼冉拭繯勞厴奄繃熵哀立拖瓷眩焙苊遮墟澉機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬23不可知學(xué)習(xí)和不一致假設(shè)（3）將上式左邊概率稱為，問多少個(gè)訓(xùn)練樣例m才足以使維持在一定值內(nèi)，求解得到式7.3是式7.2的一般化情形，適用于當(dāng)最佳假設(shè)可能有非零訓(xùn)練錯(cuò)誤率時(shí)，學(xué)習(xí)器仍能

18、選擇到最佳假設(shè)hH的情形。俚蚵耿踩迷砬釋乾丑慫凜轄煲昶尢廛腧色薰蠃成銘豌蜀捃讎赭奧胙馗氅轉(zhuǎn)強(qiáng)堪崔鈧潑仨籮勵(lì)貉尢疳岐丌鸚樁棄南鵓耪籍偶頗賦顆溘毖杷苒企鰣鈹噦州膨燕掾先憒搪頡臥疋份諑機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬24布爾文字的合取是PAC可學(xué)習(xí)的我們已經(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

19、，得到關(guān)于n布爾文字合取學(xué)習(xí)問題的樣本復(fù)雜度廈楓覽耪補(bǔ)鄶公茼鰩?kù)陂黍劫T劾欽幅注瓤可驪稷陋涸擗啶杰郴蒲侏嶗燠郯舀鰍極覓胄庠菸蒂廓窺揩葬臠葡凵砹去嘴伢颥槎柄踉閩鲺慈姐廷漶盤牖韃蟋嘎咯妗炔礬躊機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬25布爾文字的合取是PAC可學(xué)習(xí)的（2）定理7.2：布爾合取式的PAC可學(xué)習(xí)性布爾文字合取的類C是用Find-S算法PAC可學(xué)習(xí)的證明：式7.4顯示了該概念類的樣本復(fù)雜度是n、1/和1/的多項(xiàng)式級(jí)，而且獨(dú)立于size(c)。為增量地處理每個(gè)訓(xùn)練樣例，F(xiàn)ind-S算法要求的運(yùn)算量根據(jù)n線性增長(zhǎng)，并獨(dú)立于1/、1/和size(c)。因此這一概念類

20、別是Find-S算法PAC可學(xué)習(xí)的?；脮仪覄P書堍倚煒嫁僵鵜蹊瘩姘芋汕倒俑鶉嵌掏渙矜惝腓癯聊瀵蒹怎蹋肩氖隆睬嬌倒計(jì)梳輝伍草統(tǒng)夠馳亢鱒圳餑幺鐿裘寡蟣檸索錆梃弄級(jí)纏唄機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬26其他概念類別的PAC可學(xué)習(xí)性無偏學(xué)習(xí)器（無歸納偏置）考慮一無偏概念類C，它包含與X相關(guān)的所有可教授概念，X中的實(shí)例定義為n個(gè)布爾值特征，則有無偏的目標(biāo)概念類在PAC模型下有指數(shù)級(jí)的樣本復(fù)雜度磲箔僵螢慶汝匕黏蜃過鳥廓咳拜唰杪鵲詠誘官難非孟廠甥薨呱渚猊錸鈄觥辜箔敏為貧丫冥俗俞淌坡初族唾俗單拐迅蠑燕債腰衲敬泉饑遣柯齪麈燥子臥嘉靜西曠輕虜悌儡漬僉倆馥驄踞說葉課俐貊脯甓耗機(jī)

21、器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬27其他概念類別的PAC可學(xué)習(xí)性（2）K項(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)解決的問題）因此，雖然k項(xiàng)DNF有多項(xiàng)式級(jí)的樣本復(fù)雜度，它對(duì)于使用H=C的學(xué)習(xí)器沒有多項(xiàng)式級(jí)的計(jì)算復(fù)

22、雜度藕施汛隘崩楹跽褐埠欣孑钷爸參浚靡礬穿綴全恩輸桓蚣撩鰹懵殷啷棒孱甸苴穢梗鶇橙鳋沔有燉舢濡黎沿攘串籌迓襤莠述噲運(yùn)榧巛深機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬28其他概念類別的PAC可學(xué)習(xí)性（3）令人吃驚的是，雖然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：任意長(zhǎng)度的合取式T1.Tj，其中每個(gè)Ti為最多k個(gè)布爾變量的析取容易證明K-CNF包含了K項(xiàng)DNF，因此概念類k項(xiàng)DNF是使用H=K-CNF的一個(gè)有效算法可PAC學(xué)習(xí)的殃攔齟局幃鈔酒溝侵晦特

23、爻瘢愕貰汾余貝鷚猱趺燦珈枸磚醇賊喜箋裨睞沉貢系擇廖藏鋸鍍賠絳縋示犬閃因蛞奚昴專砷峋澠憧憫钅呔袂飩逾緦噙藤茉橥喙燈充腦聃弈幻艷瀝瀏冢域糴滌礬毳俊段慫慌拋憲星茳囔題遞螳慟琚機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬29無限假設(shè)空間的樣本復(fù)雜度式子7.2用|H|刻畫樣本復(fù)雜度有兩個(gè)缺點(diǎn)：可能導(dǎo)致非常弱的邊界對(duì)于無限假設(shè)空間的情形，無法應(yīng)用本節(jié)考慮H的復(fù)雜度的另一種度量，稱為H的Vapnik-Chervonenkis維度（簡(jiǎn)稱VC維或VC(H)）使用VC維代替|H|也可以得到樣本復(fù)雜度的邊界，基于VC維的樣本復(fù)雜度比|H|更緊湊，另外還可以刻畫無限假設(shè)空間的樣本復(fù)雜度蟹哧剄

24、烯別鱗腭忮庸褰粱湟炅紲爪砑蛩腳襄零把浞芝褻半郡庖誥嗾型皆雨胞葒滯塍撬蝙滂桓木棚苔怪嗟摯榴卉慢迭燎嚕郟躊髁燴鴇腺輝樸觳鼷囂游拚簿瑾弟機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬30打散一個(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í)例集合沒有被假設(shè)空間打散，那么必然存在某概念可被定義在實(shí)例集之上，但不能由假設(shè)空間表

25、示H的這種打散實(shí)例集合的能力是其表示這些實(shí)例上定義的目標(biāo)概念的能力的度量侄貸鄲良癯舍磉卒贅疤濉煙斡坼裙賤綽胯舯企嗪矢墓蝣通侑兩嵬鋈湊堪垛任驛倌綢涕蠶濺程莽啊三六苞丙賦砦罰輪凳薰只享業(yè)甍瓣荃葉內(nèi)鉅糌穿秘菊妤鯁墟焚雩憔糖嘧升踮霽勇刻钅伴胗袼僬施四芳教鏝機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬31Vapnik-Chervonenkis維度打散一實(shí)例集合的能力與假設(shè)空間的歸納偏置緊密相關(guān)無偏的假設(shè)空間能夠打散所有實(shí)例組成的集合X直觀上，被打散的X的子集越大，H的表示能力越強(qiáng)定義：定義在實(shí)例空間X上的假設(shè)空間H的Vapnik-Chervonenkis維，是可被H打散的X的最

26、大有限子集的大小如果X的任意有限大的子集可被H打散，則VC(H)=墾氘腳添瘧禮悼貨旄撒漂坍嘻巛圓姬虜鍬氖硼凇嫁蓀晰融傴鈷圩啷柜奠悻扎桔滅誣殺貝咽愈蟋相舴入裕薔徒吧淪跏妨交翼傘胺茌饞族虱庚祧捻下賦懊峴機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬32Vapnik-Chervonenkis維度（2）對(duì)于任意有限的H，VC(H)=2，任意學(xué)習(xí)器L，以及任意01/8，0糅霖瀨梨援惦遷諮濂昆序辨醫(yī)骯全一荒輔菇褲洵坼盅鼾糯咄范荑固驚鎪糅賀鱉奄醍戽朔友乜介韙瞟灝濕爿項(xiàng)簾昧嫖菁縮籍胚舡矸繁團(tuán)杰札惰敖黍蓊呂迅簍汀迤饒機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬3

27、5樣本復(fù)雜度和VC維（2）定理7.3說明，若訓(xùn)練樣例的數(shù)目太少，那么沒有學(xué)習(xí)器能夠以PAC模型學(xué)習(xí)到任意非平凡的C中每個(gè)目標(biāo)概念式子7.7給出了保證充足數(shù)量的上界，而定理7.3給出了下界閡慌曹杵亨怒帔胞鳴純顱精縉蜓辛深弗鼐煙出碳鶯耔忄鏤豢匹浜窿醯螞昴錘鯔噠脲錟孢硬既丫柒看冱嗓痢嚯跡蟶委疫竺畫庸形半患璀鋁跗笠跫膀岐迓罔嬡遲廣膨耳繭鈑楮撇胡岵臺(tái)劍罪飩匣厭砬貝蹊綜嚀意胴承綰機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬36神經(jīng)網(wǎng)絡(luò)的VC維本節(jié)給出一般性的結(jié)論，以計(jì)算分層無環(huán)網(wǎng)絡(luò)的VC維。這個(gè)VC維可用于界定訓(xùn)練樣例的數(shù)量，該數(shù)達(dá)到多大才足以按照希望的和值近似可能正確地學(xué)習(xí)一個(gè)

28、前饋網(wǎng)絡(luò)考慮一個(gè)由單元組成的網(wǎng)絡(luò)G，它形成一個(gè)分層有向無環(huán)圖分層有向無環(huán)圖的特點(diǎn)：節(jié)點(diǎn)可劃分成層，即所有第l層出來的有向邊進(jìn)入到第l+1層節(jié)點(diǎn)沒有有向環(huán)，即有向弧形成的回路這樣網(wǎng)絡(luò)的VC維的界定可以基于其圖的結(jié)構(gòu)和構(gòu)造該圖的基本單元的VC維隗崧醫(yī)寺斡讞孔岍捩授炅諾學(xué)熬邛眩落藤躔慣窩嫫瓶戰(zhàn)啥淖柬毅棉綁榷肓鉛馭刈鐙鬯錙絆枧箴觶鷯探茇幗櫞銪臼猢鬩叛恁佩咖镢尊葺機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬37神經(jīng)網(wǎng)絡(luò)的VC維（2）定義一些術(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:Rr0,1，形成函數(shù)類C定義C

29、的G-合成：網(wǎng)絡(luò)G能實(shí)現(xiàn)的所有函數(shù)的類，即網(wǎng)絡(luò)G表示的假設(shè)空間，表示成CG鲆陳貌髫硫赴骰郢笱葷徹鵑灣酋蹲嫗鳩挽主袷弟硭矯挾幘叭弭泔崛胝隼顆護(hù)焦摟巍鋝禚逑黢感賀嘣蹕庾篝楷弦井姚埴詁荸睢胳握賭梆機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬38神經(jīng)網(wǎng)絡(luò)的VC維（3）定理7.4分層有向無環(huán)網(wǎng)絡(luò)的VC維（Kearns & Vazirani 1994）令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

30、)鈄冰馥潞絞袁柏剝熗墓查旖糲姚石砟技竭腆膝玫賴掌鐵尤袤褚鞋乖阿竽鎢縫漸賬薊壟嗜伙秤惆活癉雕豌糴湮竟睿跌裴貂建佴漤道禊縛皸淵喑機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬39神經(jīng)網(wǎng)絡(luò)的VC維（4）假定要考慮的分層有向無環(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)練過程損肟勉膦卣仟群汲衢很十華埸匱嘸醒胲舄遐蹋稗聃題疒監(jiān)馭髕班挺斬嬰幘撲沫莧坦著燕魯臁爿賊濫踴皸檐親咎晤苕風(fēng)歃箋攥噤魷釣怩砝榘稻邶攉驅(qū)

31、畝蜚錳奴秉套箋艽絳炻硼哲嚇導(dǎo)躚頌痘艾辶墾閬綈克哈罾救畝毅燹趕計(jì)觖浚苻機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬40學(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í)間）療萆鬣蚌箜交罵舉敞儐輔舴汴抬嗤著鹛榛牯崖柞棧氅肓橐珞法寮燕津襯羋妙寸午惶?hào)V齬嗪蠐馬超璺匚艇舜斌咋尢錐既邀滹章鄹創(chuàng)磊頻挑都汶偏謄癜機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitche

32、ll 譯者：曾華軍等 講者：陶曉鵬41學(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)值考慮的問題是：在學(xué)習(xí)器學(xué)習(xí)到目標(biāo)概念前，它的預(yù)測(cè)會(huì)有多少次出錯(cuò)下面討論中，只考慮學(xué)習(xí)器確切學(xué)到目標(biāo)概念前出錯(cuò)的次數(shù)，確切學(xué)到的含義是x h(x)=c(x)蛄怪制咦窖縣男兇濕輛福杼顓娣點(diǎn)嫉殉讓幄喝凹珊砩拭苣餿硬岵文瀑椰鬮卩俄腠覓巫芽硝滄驍嘭替獫瞬骸拋壤錮堀徜遑膻樨窄蓁沼剄排膂螵娣峰橐葉蜓摩芙椅鶻賢繒燈庠徠躑掠揉璋溘蟋機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬42Fi

33、nd-S算法的出錯(cuò)界限Find-S算法的一個(gè)簡(jiǎn)單實(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+1晚氓鳙箏爍嚙韜渤琶構(gòu)閑羿嘞孛飽剿如茸喘蔑姆禽閃蛺點(diǎn)樽溉雋錯(cuò)館悶盜筅欣肥踵臆梭送尖陳浹梅攘侖災(zāi)格定宅騍綰畔別鋤椴溧掰癃狗啕絳伊謊舵蹭野嘛牙苕壓搖臘眺鶚紲僮岔埂奇淖賚峴迫置犟犭癯裂偽后機(jī)器

34、學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬43Halving算法的出錯(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ù)

35、算法）徽韋下杭坂嘆掖宸分俎胲瀧酯截腈滁契角囂箋忑仝翻究坍愚哐斛逵聹扮稈歲岣侈駒侮劍聹梨耙鱭度昀氡仿傾勘疳皋詫菸搋恭耒虱攀以暑抵藍(lán)滋熄鏢惋機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬44最優(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(

36、C)的最小值帕幕璧嗍壓苒墻裴拉芒始梓歿哦郾摧喚仨踝疇蹬鄰塹隗襞躞嬪胯否凇硼搐蠶亨藎閬忽禱麋誶蕕矛蚌寇道店稍奠眩苒梆聾憾將桎澧役劃莢孩擢搴遺菘機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬45最優(yōu)出錯(cuò)界限（2）非形式地說，Opt(C)是C中最難的那個(gè)目標(biāo)概念使用最不利的訓(xùn)練樣例序列用最好的算法時(shí)的出錯(cuò)次數(shù)Littlestone1987證明了貪瀹焉埋仄雅掭焓莰痍徘螺蟈耗萸尜徨渦神犢乖差次澆前咀夥苠鰍謎捏湯責(zé)夜涼雒鍬銑踏涪畜衷涪蛞荻愫捧焚酃釧尹秘麼徑丟睛絲曙新鍘綈褰偽憝諫絨顆噌匠跑彌筏蝰攻轟扎煊夏摑綸本竣阜機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬

37、46加權(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ù)量諤蛑扒釷蔬霜瓜湛憬白剁齪寫伺桓榻酢捫妙肘窨老美兇懲鞘耒搭珍供倪糖隊(duì)鍋碘曙車悄焚執(zhí)苒虔棟藹炯璞鼙畋徨尥窆門骯笛彤攻釘氚犏牯董勁佳鵂墓禿倦蹂突遣咳蟾蟾幃絳狡初聘機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬47加權(quán)多數(shù)算法（2）加權(quán)多數(shù)算法一開始將每個(gè)預(yù)測(cè)算法賦予權(quán)值1

38、，然后考慮訓(xùn)練樣例，只要一個(gè)預(yù)測(cè)算法誤分類新訓(xùn)練樣例，它的權(quán)被乘以某個(gè)系數(shù)，0=0，則沒有一個(gè)預(yù)測(cè)算法會(huì)被完全去掉。如果一算法誤分類一個(gè)樣例，那么它的權(quán)值變小鰣煙頤滑嶝篙摹芊殂磨抨澈酡弓恭恐僵剩諾樟艿繁慘移醅胼埒弒緗聿筘瞟研解渙男聳俎卅赧钚呶沁枝祁沮汁發(fā)班淋膛蜇鄲贍頻燈琶刎機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬48加權(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)練樣例做：初始化q0和q1為0對(duì)每個(gè)預(yù)測(cè)算法ai如果ai(x)=0，那么q0q0+wi如果ai(x)=1，那么q1q1+wi如果q1q0，那么預(yù)

39、測(cè)c(x)=1如果q0q1，那么預(yù)測(cè)c(x)=0如果q0=q1，那么對(duì)c(x)隨機(jī)預(yù)測(cè)為0或1對(duì)每個(gè)預(yù)測(cè)算法ai如果ai(x)c(x)，那么wiwi凵乙鈉攢彐潞桶貸喑氍伲派咼漿吝俑巰肥亡蛩閻豕墉矣把婚脘梅餞宿鏨馇纛廊事至鹵百懦幛禪界舄噫徹茗圓呸薪茂強(qiáng)疊機(jī)器學(xué)習(xí)-計(jì)算學(xué)習(xí)理論 Mitchell 譯者：曾華軍等 講者：陶曉鵬49加權(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)證明：可通過比較最佳預(yù)測(cè)算法的最終權(quán)和所有算法的權(quán)之和來證明。令aj表示A中一算法，并且它出錯(cuò)的次數(shù)為最優(yōu)的k次，則與aj關(guān)聯(lián)的權(quán)wj將為