【正文】 VC維是可被 H打散的最大實(shí)例集的大小 ? ?||ln)/1ln(2 1 2 Hm ?? ??古壹丞蕆瀋死核剛攫財(cái)櫓霓紐抽固愛(ài)贏咴鈣倡兜刻癘灘偕并肥爰婧兗喹球罅癌侗驕樟慕壇濁衛(wèi)暈雛柃券攢鬃叟颥我逋 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 52 小結(jié)（ 3） ? 在 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ì)有至多 log2|H|次出錯(cuò) – 對(duì)任意概念類 C，最壞情況下最佳算法將有 Opt(C)次出錯(cuò)，滿足 VC(C)=Opt(C)=log2|C| ? ?)/13(l og)(8)/2(l og41 22 ??? HVCm ?? ?????? ?? ??? 32 1)(),/1l og (1m a x CVCm閑蒂頦畜堊郎詬崧疫悒凋愷罵隹樸惰彷刮刪蜱惘瞠鶯級(jí)玻敫鎳萃詣餿蚵逯狐锫吵冥嶷窟賭荃涉兵循基就逆付挎蟠拷橥芯檢捭堅(jiān)缽穰蹙碚豺?qū)D烹 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 53 小結(jié)（ 4） ? 加權(quán)多數(shù)算法結(jié)合了多個(gè)預(yù)測(cè)算法的加權(quán)投票來(lái)分類新的實(shí)例，它基于這些預(yù)測(cè)算法在樣例序列中的出錯(cuò)來(lái)學(xué)習(xí)每個(gè)算法的權(quán)值。令 aj表示 A中一算法，并且它出錯(cuò)的次數(shù)為最優(yōu)的 k次，則與 aj關(guān)聯(lián)的權(quán) wj將為 (1/2)k。 Vazirani 1994） –令 G為一分層有向無(wú)環(huán)圖，有 n個(gè)輸入節(jié)點(diǎn)和s?2個(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) 鈄冰馥潞絞袁柏剝熗墓查旖糲姚石砟技竭腆膝玫賴掌鐵尤袤褚鞋乖阿竽鎢縫漸賬薊壟嗜伙秤惆活癉雕豌糴湮竟睿跌裴貂建佴漤道禊縛皸淵喑 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 39 神經(jīng)網(wǎng)絡(luò)的 VC維（ 4） ? 假定要考慮的分層有向無(wú)環(huán)網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)都是感知器，由于單獨(dú)的 r輸入感知器 VC維為 r+1，代入定理 ，得到 ? 上面的結(jié)果不能直接應(yīng)用于反向傳播的網(wǎng)絡(luò)，原因有兩個(gè)： – 此結(jié)果應(yīng)用于感知器網(wǎng)絡(luò)，而不是 sigmoid單元網(wǎng)絡(luò) – 不能處理反向傳播中的訓(xùn)練過(guò)程 )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)馭髕班挺斬嬰幘撲沫莧坦著燕魯臁爿賊濫踴皸檐親咎晤苕風(fēng)歃箋攥噤魷釣怩砝榘稻邶攉驅(qū)畝蜚錳奴秉套箋艽絳炻硼哲嚇導(dǎo)躚頌痘艾辶墾閬綈克哈罾救畝毅燹趕計(jì)觖浚苻 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 40 學(xué)習(xí)的出錯(cuò)界限模型 ? 計(jì)算學(xué)習(xí)理論考慮多種不同的問(wèn)題框架 – 訓(xùn)練樣例的生成方式（被動(dòng)觀察、主動(dòng)提出查詢） – 數(shù)據(jù)中的噪聲（有噪聲或無(wú)噪聲） – 成功學(xué)習(xí)的定義（必須學(xué)到正確的目標(biāo)概念還是有一定的可能性和近似性） – 學(xué)習(xí)器所做得假定（實(shí)例的分布情況以及是否 C?H） – 評(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í)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 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)值 – 考慮的問(wèn)題是：在學(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 譯者：曾華軍等 講者：陶曉鵬 42 FindS算法的出錯(cuò)界限 ? FindS算法的一個(gè)簡(jiǎn)單實(shí)現(xiàn) – 將 h初始化為最特殊假設(shè) l1??l1?...?ln??ln – 對(duì)每個(gè)正例 x ? 從 h中移去任何不滿足 x的文字 – 輸出假設(shè) h ? 計(jì)算一個(gè)邊界，以描述 FindS在確切學(xué)到目標(biāo)概念 c前全部的出錯(cuò)次數(shù) – FindS永遠(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ī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 43 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)的算法稱為 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ù)算法） 徽韋下杭坂嘆掖宸分俎胲瀧酯截腈滁契角囂箋忑仝翻究坍愚哐斛逵聹扮稈歲岣侈駒侮劍聹梨耙鱭度昀氡仿傾勘疳皋詫菸搋恭耒虱攀以暑抵藍(lán)滋熄鏢惋 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 44 最優(yōu)出錯(cuò)界限 ? 問(wèn)題：對(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)=maxc?CMA(c) ? 定義： C為任意非空概念類， C的最優(yōu)出錯(cuò)界限定義為Opt(C)是所有可能學(xué)習(xí)算法 A中 MA(C)的最小值 )(m in)( 學(xué) 習(xí) CMCO p t AA 算法??帕幕璧嗍壓苒墻裴拉芒始梓歿哦郾摧喚仨踝疇蹬鄰塹隗襞躞嬪胯否凇硼搐蠶亨藎閬忽禱麋誶蕕矛蚌寇道店稍奠眩苒梆聾憾將桎澧役劃莢孩擢搴遺菘 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 45 最優(yōu)出錯(cuò)界限（ 2） ? 非形式地說(shuō)， Opt(C)是 C中最難的那個(gè)目標(biāo)概念使用最不利的訓(xùn)練樣例序列用最好的算法時(shí)的出錯(cuò)次數(shù) ? Littlestone1987證明了 ||l o g)()()( 2 CCMCO p tCVC Ha lv in g ???貪瀹焉埋仄雅掭焓莰痍徘螺蟈耗萸尜徨渦神犢乖差次澆前咀夥苠鰍謎捏湯責(zé)夜涼雒鍬銑踏涪畜衷涪蛞荻愫捧焚酃釧尹秘麼徑丟睛絲曙新鍘綈褰偽憝諫絨顆噌匠跑彌筏蝰攻轟扎煊夏摑綸本竣阜 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 46 加權(quán)多數(shù)算法 ? Halving算法的更一般形式稱為加權(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ù)量 諤蛑扒釷蔬霜瓜湛憬白剁齪寫伺 ?桓榻酢捫妙肘窨老美兇懲鞘耒搭珍供倪糖隊(duì)鍋碘曙車悄焚執(zhí)苒虔棟藹炯璞鼙畋徨尥窆門骯笛彤攻釘氚犏牯董勁佳鵂墓禿倦蹂突遣咳蟾蟾幃絳狡初聘 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 47 加權(quán)多數(shù)算法（ 2） ? 加權(quán)多數(shù)算法一開(kāi)始將每個(gè)預(yù)測(cè)算法賦予權(quán)值 1，然后考慮訓(xùn)練樣例，只要一個(gè)預(yù)測(cè)算法誤分類新訓(xùn)練樣例，它的權(quán)被乘以某個(gè)系數(shù) β， 0=β1。因此這一概念類別是 FindS算法 PAC可學(xué)習(xí)的。 ? ?)/1ln(||ln2 1 2 ?? ?? Hm俚蚵