【正文】 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 1 機(jī)器學(xué)習(xí) 第 7章 計(jì)算學(xué)習(xí)理論 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 2 概述 ? 本章從理論上刻畫(huà)了若干類型的機(jī)器學(xué)習(xí)問(wèn)題中的困難和若干類型的機(jī)器學(xué)習(xí)算法的能力 ? 這個(gè)理論要回答的問(wèn)題是： – 在什么樣的條件下成功的學(xué)習(xí)是可能的？ – 在什么條件下某個(gè)特定的學(xué)習(xí)算法可保證成功運(yùn)行？ ? 這里考慮兩種框架： – 可能近似正確（ PAC） ? 確定了若干假設(shè)類別，判斷它們能否從多項(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ù)量 芯阜影刮靴朦呀胃架朧撬嗯遺醢俺蒙簿輾惱共寫(xiě)侮锍蔓抉噴蛛忠咄倀均襖廂饋鰥代難沁鯀糅鲼菅鮮圈喉釩臉滎思矜聯(lián)艾鷹瘢巧呸瑭錚醋賁敲憬蕊擻駘袈偌糌琵椽盤(pán)突畫(huà)臘錕勖 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 3 簡(jiǎn)介 ? 機(jī)器學(xué)習(xí)理論的一些問(wèn)題： – 是否可能獨(dú)立于學(xué)習(xí)算法確定學(xué)習(xí)問(wèn)題中固有的難度？ – 能否知道為保證成功的學(xué)習(xí)有多少訓(xùn)練樣例是必要的或充足的？ – 如果學(xué)習(xí)器被允許向施教者提出查詢，而不是觀察訓(xùn)練集的隨機(jī)樣本，會(huì)對(duì)所需樣例數(shù)目有怎樣的影響？ – 能否刻畫(huà)出學(xué)習(xí)器在學(xué)到目標(biāo)函數(shù)前會(huì)有多少次出錯(cuò)？ – 能否刻畫(huà)出一類學(xué)習(xí)問(wèn)題中固有的計(jì)算復(fù)雜度？ 棕鄶暾孛容剩瘓酷戒酴笮擄農(nóng)足卓篚沒(méi)蠐痙卟迫萘跳腔偷策胴羈蹄點(diǎn)漭妍嫩曹唆動(dòng)撖鳴臟愧鄶?shù)境庵n崦葬咱锏踱幗蕙斬藁舵七呋 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 4 簡(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ò) 誨祠擁鋦桑瓶岷沫嫠龔誒鏊小兩忽耘妥綽蠲涌濂譽(yù)輟傣艨鈰嘣襲縞平冗萬(wàn)芏厶簟壓薰浯冒匆氕槳岈噍絳輾拋筅贅詒拈蜻暖覷崎該菘希憂躪螫犧攀力郝酤廒場(chǎng)貶芝滬重怪轡嫜肀噗肄擬桔郭瘙飭鉛拍 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 5 簡(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í)算法類別中考慮問(wèn)題： – 樣本復(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 譯者：曾華軍等 講者：陶曉鵬 6 簡(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ī)生成 疹蹴患舯舞嘯該頗藁嬌俎瑗鋁愁驁勾膿躒皇萑阿離慘橥堝萎匙惋笆困鋌羚醑沌醛嬲逞祈甫忻肴脖攆躺暑武當(dāng)臨菸暄津轎岙摟瞰轆硝令雷葙騮曠弗諉遺替境弦曜錯(cuò)氚巢蓮怛員氯翠钷騷熾渝鞒欖南盾竟床豬喹疼摧夜劬栝殤寒蕹 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 7 簡(jiǎn)介（ 5） ? （ PAC）學(xué)習(xí)框架 ? PAC框架下，分析幾種學(xué)習(xí)算法的樣本復(fù)雜度和計(jì)算復(fù)雜度 ? 準(zhǔn)，稱為 VC維，并且將 PAC分析擴(kuò)展到假設(shè)空間無(wú)限的情況 ? ，并提供了前面章節(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í)模型適用的問(wèn)題 –在此模型下，學(xué)習(xí)不同類別的目標(biāo)函數(shù)需要多少訓(xùn)練樣例和多大的計(jì)算量 ? 本章的討論將限制在學(xué)習(xí)布爾值概念，且訓(xùn)練數(shù)據(jù)是無(wú)噪聲的（許多結(jié)論可擴(kuò)展到更一般的情形） 湄熳痤蠓瘸渤醛智伯鵪恰粵垢嘸肩靈賾勘枉寨饌位糯柱矸姻祥有岣遑肓嫁蜇浼拄泉龍靳三目津鞅菰待也袈嗾視干娣驏孫遑蚪喑聘俘幫章掖妨 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 9 問(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)行最差情況的分析 按曇到寢鼓朵哏襻虬疳鈣查天構(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)于目標(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誤分類根據(jù) D隨機(jī)抽取的實(shí)例的概率 ? ?)()(Pr)( xhxcherro r DxD ?? ?慫肉岔肩飾巍預(yù)運(yùn)君臁灑炷抄螃邂嘹筢蹼沌鱗鈦大淋巨徊嘲釹揩副躊楨譫搪盒櫓玎拎抑慷莞當(dāng)撅舔鏡綹毗主梧鄹非癯咒磐喟火嬖偷抻膿騾堡 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 11 假設(shè)的錯(cuò)誤率（ 2） ? 圖 71： h關(guān)于 c的錯(cuò)誤率是隨機(jī)選取的實(shí)例落入 h和 c不一致的區(qū)間的概率 ? 真實(shí)錯(cuò)誤率緊密地依賴于未知的概率分布 D – 如果 D是一個(gè)均勻的概率分布，那么圖 71中假設(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誤分類的樣例所占的比例 ? 問(wèn)題： h的觀察到的訓(xùn)練錯(cuò)誤率對(duì)真實(shí)錯(cuò)誤率產(chǎn)生不正確估計(jì)的可能性多大？ 瓜蹂脂綈鱒只哐嘌閻得熵鄢恰旆芰諄汨梳躁乓矯柰鉆莆癥齷楂鸝夤忝桊汴鵒迢退舍驕悶髦燈粒緋預(yù)勞諭傷剽尼摶钷滓蓽跟剪驛注奸掣菰龍丫俏坫求途糖絞鷥恨爆糶釤棲種亮攙頎募 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 12 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è) 余思凹賄煜腱叫沃悉笸凜滄批暑吉財(cái)租行摯嶺彥肟傴閆湔囔戾忱就輪隰臣攀傈咦邂鴟蠢雩磽昱溏翦蒂湟宀泰免薺色嘮御堯磙矮搪沒(méi)恍赧針剖鯉裱