1、2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,1,機器學習,第7章 計算學習理論,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,2,概述,本章從理論上刻畫了若干類型的機器學習問題中的困難和若干類型的機器學習算法的能力 這個理論要回答的問題是： 在什么樣的條件下成功的學習是可能的？ 在什么條件下某個特定的學習算法可保證成功運行？ 這里考慮兩種框架： 可能近似正確（PAC） 確定了若干假設類別，判斷它們能否從多項式數量的訓練樣例中學習得到 定義了一個對假設空間復雜度的自然度量，由它可以界定歸

2、納學習所需的訓練樣例數目 出錯界限框架 考查了一個學習器在確定正確假設前可能產生的訓練錯誤數量,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,3,簡介,機器學習理論的一些問題： 是否可能獨立于學習算法確定學習問題中固有的難度？ 能否知道為保證成功的學習有多少訓練樣例是必要的或充足的？ 如果學習器被允許向施教者提出查詢，而不是觀察訓練集的隨機樣本，會對所需樣例數目有怎樣的影響？ 能否刻畫出學習器在學到目標函數前會有多少次出錯？ 能否刻畫出一類學習問題中固有的計算復雜度？,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯

3、者：曾華軍等 講者：陶曉鵬,4,簡介（2）,對所有這些問題的一般回答還未知，但不完整的學習計算理論已經開始出現 本章闡述了該理論中的一些關鍵結論，并提供了在特定問題下一些問題的答案 主要討論在只給定目標函數的訓練樣例和候選假設空間的條件下，對該未知目標函數的歸納學習問題 主要要解決的問題是：需要多少訓練樣例才足以成功地學習到目標函數以及學習器在達到目標前會出多少次錯,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,5,簡介（3）,如果明確了學習問題的如下屬性，那么有可能給出前面問題的定量的上下界 學習器所考慮的假設空間的大小和復雜度 目標概念

4、須近似到怎樣的精度 學習器輸出成功的假設的可能性 訓練樣例提供給學習器的方式 本章不會著重于單獨的學習算法，而是在較寬廣的學習算法類別中考慮問題： 樣本復雜度：學習器要收斂到成功假設，需要多少訓練樣例？ 計算復雜度：學習器要收斂到成功假設，需要多大的計算量？ 出錯界限：在成功收斂到一個假設前，學習器對訓練樣例的錯誤分類有多少次？,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,6,簡介（4）,為了解決這些問題需要許多特殊的條件設定，比如 “成功”的學習器的設定 學習器是否輸出等于目標概念的假設 只要求輸出的假設與目標概念在多數時間內意見一致

5、學習器通常輸出這樣的假設 學習器如何獲得訓練樣例 由一個施教者給出 由學習器自己實驗獲得 按照某過程隨機生成,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,7,簡介（5）,7.2節(jié)介紹可能近似正確（PAC）學習框架 7.3節(jié)在PAC框架下，分析幾種學習算法的樣本復雜度和計算復雜度 7.4節(jié)介紹了假設空間復雜度的一個重要度量標準，稱為VC維，并且將PAC分析擴展到假設空間無限的情況 7.5節(jié)介紹出錯界限模型，并提供了前面章節(jié)中幾個學習算法出錯數量的界限，最后介紹了加權多數算法,2003.12.18,機器學習-計算學習理論 作者：Mitchel

6、l 譯者：曾華軍等 講者：陶曉鵬,8,可能學習近似正確假設,可能近似正確學習模型（PAC） 指定PAC學習模型適用的問題 在此模型下，學習不同類別的目標函數需要多少訓練樣例和多大的計算量 本章的討論將限制在學習布爾值概念，且訓練數據是無噪聲的（許多結論可擴展到更一般的情形）,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,9,問題框架,X表示所有實例的集合，C代表學習器要學習的目標概念集合，C中每個目標概念c對應于X的某個子集或一個等效的布爾函數c: X0,1 假定實例按照某概率分布D從X中隨機產生 學習器L在學習目標概念時考慮可能假設的集合

7、H。在觀察了一系列關于目標概念c的訓練樣例后，L必須從H中輸出某假設h，它是對c的估計 我們通過h在從X中抽取的新實例上的性能來評估L是否成功。新實例與訓練數據具有相同的概率分布 我們要求L足夠一般，以至可以從C中學到任何目標概念而不管訓練樣例的分布如何，因此，我們會對C中所有可能的目標概念和所有可能的實例分布D進行最差情況的分析,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,10,假設的錯誤率,為了描述學習器輸出的假設h對真實目標概念的逼近程度，首先要定義假設h對應于目標概念c和實例分布D的真實錯誤率 h的真實錯誤率是應用h到將來按分布D

8、抽取的實例時的期望的錯誤率 定義：假設h的關于目標概念c和分布D的真實錯誤率為h誤分類根據D隨機抽取的實例的概率,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,11,假設的錯誤率（2）,圖7-1：h關于c的錯誤率是隨機選取的實例落入h和c不一致的區(qū)間的概率 真實錯誤率緊密地依賴于未知的概率分布D 如果D是一個均勻的概率分布，那么圖7-1中假設的錯誤率為h和c不一致的空間在全部實例空間中的比例 如果D恰好把h和c不一致區(qū)間中的實例賦予了很高的概率，相同的h和c將造成更高的錯誤率 h關于c的錯誤率不能直接由學習器觀察到，L只能觀察到在訓練樣例上

9、h的性能 訓練錯誤率：指代訓練樣例中被h誤分類的樣例所占的比例 問題：h的觀察到的訓練錯誤率對真實錯誤率產生不正確估計的可能性多大？,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,12,PAC可學習性,我們的目標是刻畫出這樣的目標概念，它們能夠從合理數量的隨機抽取訓練樣例中通過合理的計算量可靠地學習 對可學習性的表述 一種可能的選擇：為了學習到使errorD(h)=0的假設h，所需的訓練樣例數 這樣的選擇不可行：首先要求對X中每個可能的實例都提供訓練樣例；其次要求訓練樣例無誤導性 可能近似學習：首先只要求學習器輸出錯誤率限定在某常數范圍內的

10、假設，其次要求對所有的隨機抽取樣例序列的失敗的概率限定在某常數范圍內 只要求學習器可能學習到一個近似正確的假設,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,13,PAC可學習性（2）,PAC可學習性的定義 考慮定義在長度為n的實例集合X上的一概念類別C，學習器L使用假設空間H。當對所有cC，X上的分布D，和滿足0, 1/2，學習器L將以至少1-輸出一假設hH，使errorD(h)，這時稱C是使用H的L可PAC學習的，所使用的時間為1/，1/，n以及size(c)的多項式函數 上面定義要求學習器L滿足兩個條件 L必須以任意高的概率（1- ）

11、輸出一個錯誤率任意低（）的假設 學習過程必須是高效的，其時間最多以多項式方式增長 上面定義的說明 1/和1/表示了對輸出假設要求的強度，n和size(c)表示了實例空間X和概念類別C中固有的復雜度 n為X中實例的長度，size(c)為概念c的編碼長度,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,14,PAC可學習性（3）,在實踐中，通常更關心所需的訓練樣例數， 如果L對每個訓練樣例需要某最小處理時間，那么為了使c是L可PAC學習的，L必須從多項式數量的訓練樣例中進行學習 實際上，為了顯示某目標概念類別C是可PAC學習的，一個典型的途徑是證

12、明C中每個目標概念可以從多項式數量的訓練樣例中學習到，且處理每個樣例的時間也是多項式級 PAC可學習性的一個隱含的條件：對C中每個目標概念c，假設空間H都包含一個以任意小誤差接近c的假設,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,15,有限假設空間的樣本復雜度,PAC可學習性很大程度上由所需的訓練樣例數確定 隨著問題規(guī)模的增長所帶來的所需訓練樣例的增長稱為該學習問題的樣本復雜度 我們把樣本復雜度的討論限定于一致學習器（輸出完美擬合訓練數據的學習器） 能夠獨立于特定算法，推導出任意一致學習器所需訓練樣例數的界限 變型空間：能正確分類訓練樣

13、例D的所有假設的集合。,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,16,有限假設空間的樣本復雜度（2）,變型空間的重要意義是：每個一致學習器都輸出一個屬于變型空間的假設 因此界定任意一個一致學習器所需的樣例數量，只需要界定為保證變型中沒有不可接受假設所需的樣例數量 定義：考慮一假設空間H，目標概念c，實例分布D以及c的一組訓練樣例S。當VSH,D中每個假設h關于c和D錯誤率小于時，變型空間被稱為c和D是-詳盡的。,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,17,有限假設空間的樣本

14、復雜度（3）,-詳盡的變型空間表示與訓練樣例一致的所有假設的真實錯誤率都小于 從學習器的角度看，所能知道的只是這些假設能同等地擬合訓練數據，它們都有零訓練錯誤率 只有知道目標概念的觀察者才能確定變型空間是否為-詳盡的 但是，即使不知道確切的目標概念或訓練樣例抽取的分布，一種概率方法可在給定數目的訓練樣例之后界定變型空間為-詳盡的,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,18,有限假設空間的樣本復雜度（4）,定理7.1（變型空間的-詳盡化） 若假設空間H有限，且D為目標概念c的一系列m=1個獨立隨機抽取的樣例，那么對于任意0=1，變型空

15、間VSH,D不是-詳盡的概率小于或等于： 證明： 令h1,.,hk為H中關于c的真實錯誤率大于的所有假設。當且僅當k個假設中至少有一個恰好與所有m個獨立隨機抽取樣例一致時，不能使變型空間-詳盡化。 任一假設真實錯誤率大于，且與一個隨機抽取樣例一致的可能性最多為1-，因此，該假設與m個獨立抽取樣例一致的概率最多為(1-)m 由于已知有k個假設錯誤率大于，那么至少有一個與所有m個訓練樣例都不一致的概率最多為（當 ，則 ）,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,19,有限假設空間的樣本復雜度（5）,定理7.1基于訓練樣例的數目m、允許的錯

16、誤率和H的大小，給出了變型空間不是-詳盡的概率的上界 即它對于使用假設空間H的任意學習器界定了m個訓練樣例未能將所有“壞”的假設（錯誤率大于的假設）剔除出去的概率 利用上面的結論來確定為了減少此“未剔除”概率到一希望程度所需的訓練樣例數 由 解出m，得到,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,20,有限假設空間的樣本復雜度（6）,式子7.2提供了訓練樣例數目的一般邊界，該數目的樣例足以在所期望的值和程度下，使任何一致學習器成功地學習到H中的任意目標概念 訓練樣例的數目m足以保證任意一致假設是可能（可能性為1- ）近似（錯誤率為）正確

17、的 m隨著1/線性增長，隨著1/和假設空間的規(guī)模對數增長 上面的界限可能是過高的估計，主要來源于|H|項，它產生于證明過程中在所有可能假設上計算那些不可接受的假設的概率和 在7.4節(jié)討論一個更緊湊的邊界以及能夠覆蓋無限大的假設空間的邊界,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,21,不可知學習和不一致假設,如果學習器不假定目標概念可在H中表示，而只簡單地尋找具有最小訓練錯誤率的假設，這樣的學習器稱為不可知學習器 式7.2基于的假定是學習器輸出一零錯誤率假設，在更一般的情形下學習器考慮到了有非零訓練錯誤率的假設時，仍能找到一個簡單的邊界

18、 令S代表學習器可觀察到的特定訓練樣例集合，errorS(h)表示h的訓練錯誤率，即S中被h誤分類的訓練樣例所占比例 令hbest表示H中有最小訓練錯誤率的假設，問題是：多少訓練樣例才足以保證其真實錯誤率errorD(hbest)不會多于+errorS(hbest)？（上一節(jié)問題是這個問題的特例）,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,22,不可知學習和不一致假設（2）,前面問題的回答使用類似定理7.1的證明方法，這里有必要引入一般的Hoeffding邊界 Hoeffding邊界刻畫的是某事件的真實概率及其m個獨立試驗中觀察到的頻率

19、之間的差異 Hoeffding邊界表明，當訓練錯誤率errorS(h)在包含m個隨機抽取樣例的集合S上測量時，則 上式給出了一個概率邊界，說明任意選擇的假設訓練錯誤率不能代表真實情況，為保證L尋找到的最佳的假設的錯誤率有以上的邊界，我們必須考慮這|H|個假設中任一個有較大錯誤率的概率,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,23,不可知學習和不一致假設（3）,將上式左邊概率稱為，問多少個訓練樣例m才足以使維持在一定值內，求解得到 式7.3是式7.2的一般化情形，適用于當最佳假設可能有非零訓練錯誤率時，學習器仍能選擇到最佳假設hH的情形

20、。,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,24,布爾文字的合取是PAC可學習的,我們已經有了一個訓練樣例數目的邊界，表示樣本數目為多少時才足以可能近似學習到目標概念，現在用它來確定某些特定概念類別的樣本復雜度和PAC可學習性 考慮目標概念類C，它由布爾文字的合取表示。布爾文字是任意的布爾變量，或它的否定。問題：C是可PAC學習的嗎？ 若假設空間H定義為n個布爾文字的合取，則假設空間|H|的大小為3n，得到關于n布爾文字合取學習問題的樣本復雜度,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者

21、：陶曉鵬,25,布爾文字的合取是PAC可學習的（2）,定理7.2：布爾合取式的PAC可學習性 布爾文字合取的類C是用Find-S算法PAC可學習的 證明： 式7.4顯示了該概念類的樣本復雜度是n、1/和1/的多項式級，而且獨立于size(c)。為增量地處理每個訓練樣例，Find-S算法要求的運算量根據n線性增長，并獨立于1/、1/和size(c)。因此這一概念類別是Find-S算法PAC可學習的。,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,26,其他概念類別的PAC可學習性,無偏學習器（無歸納偏置） 考慮一無偏概念類C，它包含與X相關的

22、所有可教授概念，X中的實例定義為n個布爾值特征，則有 無偏的目標概念類在PAC模型下有指數級的樣本復雜度,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,27,其他概念類別的PAC可學習性（2）,K項DNF和K-CNF概念 某概念類有多項式級的樣本復雜度，但不能夠在多項式時間內被學習到 概念類C為k項析取范式（k項DNF）的形式 k項DNF：T1.Tk，其中每一個Ti為n個布爾屬性和它們的否定的合取 假定H=C，則|H|最多為3nk，代入式7.2，得到 因此，k項DNF的樣本復雜度為1/、1/、n和k的多項式級 但是計算復雜度不是多項式級，該

23、問題是NP完全問題（等效于其他已知的不能在多項式時間內解決的問題） 因此，雖然k項DNF有多項式級的樣本復雜度，它對于使用H=C的學習器沒有多項式級的計算復雜度,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,28,其他概念類別的PAC可學習性（3）,令人吃驚的是，雖然k項DNF不是PAC可學習的，但存在一個更大的概念類是PAC可學習的 這個更大的概念類是K-CNF，它有每樣例的多項式級時間復雜度，又有多項式級的樣本復雜度 K-CNF：任意長度的合取式T1.Tj，其中每個Ti為最多k個布爾變量的析取 容易證明K-CNF包含了K項DNF，因此概

24、念類k項DNF是使用H=K-CNF的一個有效算法可PAC學習的,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,29,無限假設空間的樣本復雜度,式子7.2用|H|刻畫樣本復雜度有兩個缺點： 可能導致非常弱的邊界 對于無限假設空間的情形，無法應用 本節(jié)考慮H的復雜度的另一種度量，稱為H的Vapnik-Chervonenkis維度（簡稱VC維或VC(H)） 使用VC維代替|H|也可以得到樣本復雜度的邊界，基于VC維的樣本復雜度比|H|更緊湊，另外還可以刻畫無限假設空間的樣本復雜度,2003.12.18,機器學習-計算學習理論 作者：Mitchel

25、l 譯者：曾華軍等 講者：陶曉鵬,30,打散一個實例集合,VC維衡量假設空間復雜度的方法不是用不同假設的數量|H|，而是用X中能被H徹底區(qū)分的不同實例的數量 S是一個實例集，H中每個h導致S的一個劃分，即h將S分割為兩個子集xS|h(x)=1和xS|h(x)=0 定義：一實例集S被假設空間H打散，當且僅當對S的每個劃分，存在H中的某假設與此劃分一致 如果一實例集合沒有被假設空間打散，那么必然存在某概念可被定義在實例集之上，但不能由假設空間表示 H的這種打散實例集合的能力是其表示這些實例上定義的目標概念的能力的度量,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華

26、軍等 講者：陶曉鵬,31,Vapnik-Chervonenkis維度,打散一實例集合的能力與假設空間的歸納偏置緊密相關 無偏的假設空間能夠打散所有實例組成的集合X 直觀上，被打散的X的子集越大，H的表示能力越強 定義：定義在實例空間X上的假設空間H的Vapnik-Chervonenkis維，是可被H打散的X的最大有限子集的大小 如果X的任意有限大的子集可被H打散，則VC(H)=,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,32,Vapnik-Chervonenkis維度（2）,對于任意有限的H，VC(H)=log2|H| VC維舉例 假定

27、實例空間X為實數集合，而且H為實數軸上的區(qū)間的集合，問VC(H)是多少？ 只要找到能被H打散的X的最大子集，首先包含2個實例的集合能夠被H打散，其次包含3個實例的集合不能被H打散，因此VC(H)=2 實例集合S對應x、y平面上的點，令H為此平面內所有線性決策面的集合，問H的VC維是多少？ 能夠找到3個點組成的集合，被H打散，但無法找到能夠被H打散的4個點組成的集合，因此VC(H)=3 更一般地，在r維空間中，線性決策面的VC維為r+1,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,33,Vapnik-Chervonenkis維度（3）,假定

28、X上每個實例由恰好3個布爾文字的合取表示，而且假定H中每個假設由至多3個布爾文字描述，問VC(H)是多少？ 找到下面3個實例的集合 instance1: 100 instance2: 010 instance3: 001 這三個實例的集合可被H打散，可對如下任意所希望的劃分建立一假設：如果該劃分要排除instancei，就將文字li加入到假設中 此討論很容易擴展到特征數為n的情況，n個布爾文字合取的VC維至少為n 實際就是n，但證明比較困難，需要說明n+1個實例的集合不可能被打散,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,34,樣本復雜

29、度和VC維,使用VC維作為H復雜度的度量，就有可能推導出該問題的另一種解答，類似于式子7.2的邊界，即（Blumer el al. 1989） 定理7.3：樣本復雜度的下界（Ehrenfeucht et al. 1989） 考慮任意概念類C，且VC(C)=2，任意學習器L，以及任意0,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,35,樣本復雜度和VC維（2）,定理7.3說明，若訓練樣例的數目太少，那么沒有學習器能夠以PAC模型學習到任意非平凡的C中每個目標概念 式子7.7給出了保證充足數量的上界，而定理7.3給出了下界,2003.12.1

30、8,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,36,神經網絡的VC維,本節(jié)給出一般性的結論，以計算分層無環(huán)網絡的VC維。這個VC維可用于界定訓練樣例的數量，該數達到多大才足以按照希望的和值近似可能正確地學習一個前饋網絡 考慮一個由單元組成的網絡G，它形成一個分層有向無環(huán)圖 分層有向無環(huán)圖的特點： 節(jié)點可劃分成層，即所有第l層出來的有向邊進入到第l+1層節(jié)點 沒有有向環(huán)，即有向弧形成的回路 這樣網絡的VC維的界定可以基于其圖的結構和構造該圖的基本單元的VC維,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,3

31、7,神經網絡的VC維（2）,定義一些術語 G表示神經網絡 n是G的輸入數目 G只有1個輸出節(jié)點 G的每個內部單元Ni最多有r個輸入，并實現一布爾函數ci:Rr0,1，形成函數類C 定義C的G-合成：網絡G能實現的所有函數的類，即網絡G表示的假設空間，表示成CG,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,38,神經網絡的VC維（3）,定理7.4分層有向無環(huán)網絡的VC維（Kearns & Vazirani 1994） 令G為一分層有向無環(huán)圖，有n個輸入節(jié)點和s2個內部節(jié)點，每個至少有r個輸入，令C為VC維為d的Rr上的概念類，對應于可由每個

32、內部節(jié)點s描述的函數集合，令CG為C的G合成，對應于可由G表示的函數集合，則VC(CG)=2dslog(es),2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,39,神經網絡的VC維（4）,假定要考慮的分層有向無環(huán)網絡中單個節(jié)點都是感知器，由于單獨的r輸入感知器VC維為r+1，代入定理7.4和式子7.7，得到 上面的結果不能直接應用于反向傳播的網絡，原因有兩個： 此結果應用于感知器網絡，而不是sigmoid單元網絡 不能處理反向傳播中的訓練過程,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬

33、,40,學習的出錯界限模型,計算學習理論考慮多種不同的問題框架 訓練樣例的生成方式（被動觀察、主動提出查詢） 數據中的噪聲（有噪聲或無噪聲） 成功學習的定義（必須學到正確的目標概念還是有一定的可能性和近似性） 學習器所做得假定（實例的分布情況以及是否CH） 評估學習器的度量標準（訓練樣例數量、出錯數量、計算時間）,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,41,學習的出錯界限模型（2）,機器學習的出錯界限模型 學習器的評估標準是它在收斂到正確假設前總的出錯數 學習器每接受到一個樣例x，先預測目標值c(x)，然后施教者給出正確的目標值 考

34、慮的問題是：在學習器學習到目標概念前，它的預測會有多少次出錯 下面討論中，只考慮學習器確切學到目標概念前出錯的次數，確切學到的含義是x h(x)=c(x),2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,42,Find-S算法的出錯界限,Find-S算法的一個簡單實現 將h初始化為最特殊假設l1l1.lnln 對每個正例x 從h中移去任何不滿足x的文字 輸出假設h 計算一個邊界，以描述Find-S在確切學到目標概念c前全部的出錯次數 Find-S永遠不會將一反例錯誤地劃分為正例，因此只需要計算將正例劃分為反例的出錯次數 遇到第一個正例，初始假

35、設中2n個項半數被刪去，對后續(xù)的被當前假設誤分類的正例，至少有一項從假設中刪去 出錯總數至多為n+1,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,43,Halving算法的出錯界限,學習器對每個新實例x做出預測的方法是：從當前變型空間的所有假設中取多數票得來 將變型空間學習和用多數票來進行后續(xù)預測結合起來的算法稱為Halving算法 Halving算法只有在當前變型空間的多數假設不能正確分類新樣例時出錯，此時變型空間至少可減少到它的一半大小，因此出錯界線是log2|H| Halving算法有可能不出任何差錯就確切學習到目標概念，因為即使多

36、數票是正確的，算法仍將移去那些不正確、少數票假設 Halving算法的一個擴展是允許假設以不同的權值進行投票（如貝葉斯最優(yōu)分類器和后面討論的加權多數算法）,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,44,最優(yōu)出錯界限,問題：對于任意概念類C，假定H=C，最優(yōu)的出錯邊界是什么？ 最優(yōu)出錯邊界是指在所有可能的學習算法中，最壞情況下出錯邊界中最小的那一個 對任意學習算法A和任意目標概念c，令MA(c)代表A為了確切學到c，在所有可能訓練樣例序列中出錯的最大值 對于任意非空概念類C，令MA(C)=maxcCMA(c) 定義：C為任意非空概念類，

37、C的最優(yōu)出錯界限定義為Opt(C)是所有可能學習算法A中MA(C)的最小值,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,45,最優(yōu)出錯界限（2）,非形式地說，Opt(C)是C中最難的那個目標概念使用最不利的訓練樣例序列用最好的算法時的出錯次數 Littlestone1987證明了,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,46,加權多數算法,Halving算法的更一般形式稱為加權多數算法 加權多數算法通過在一組預測算法中進行加權投票來作出預測，并通過改變每個預測算法的權來學習 加權

38、多數算法可以處理不一致的訓練數據，因為它不會消除與樣例不一致的假設，只是降低其權 要計算加權多數算法的出錯數量邊界，可以用預測算法組中最好的那個算法的出錯數量,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,47,加權多數算法（2）,加權多數算法一開始將每個預測算法賦予權值1，然后考慮訓練樣例，只要一個預測算法誤分類新訓練樣例，它的權被乘以某個系數，00，則沒有一個預測算法會被完全去掉。如果一算法誤分類一個樣例，那么它的權值變小,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,48,加權多數

39、算法（3）,ai代表算法池A中第i個預測算法，wi代表與ai相關聯(lián)的權值 對所有i，初始化wi1 對每個訓練樣例做： 初始化q0和q1為0 對每個預測算法ai 如果ai(x)=0，那么q0q0+wi 如果ai(x)=1，那么q1q1+wi 如果q1q0，那么預測c(x)=1 如果q0q1，那么預測c(x)=0 如果q0=q1，那么對c(x)隨機預測為0或1 對每個預測算法ai 如果ai(x)c(x)，那么wiwi,2003.12.18,機器學習-計算學習理論 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,49,加權多數算法（4）,定理7.5：加權多數算法的相對誤差界限 令D為任意的訓練樣例序列，令A為任意n個預測算法集合，令k為A中任意算法對樣例序列D的出錯次數的最小值。那么使用=1/2的加權多數算法在D上出錯次數最多為：2.4(k+log2n) 證明： 可通過比較最佳預測算法的最終權和所有算法的權之和來證明。令aj表示A中一算法，并且它出錯的次數為最優(yōu)的k次，則與aj關聯(lián)的權wj將為(1/2)k。A中所有n個算法的權的和 ，W的初始值為n，對加權多數算