【正文】 則 |H|最多為 3nk，代入式 ，得到 – 因此， k項 DNF的樣本復(fù)雜度為 1/?、 1/?、 n和 k的多項式級 – 但是計算復(fù)雜度不是多項式級，該問題是 NP完全問題（等效于其他已知的不能在多項式時間內(nèi)解決的問題） – 因此，雖然 k項 DNF有多項式級的樣本復(fù)雜度，它對于使用H=C的學(xué)習(xí)器沒有多項式級的計算復(fù)雜度 ? ?)/1ln(3ln1 ?? ?? nkm 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 28 其他概念類別的 PAC可學(xué)習(xí)性（ 3） – 令人吃驚的是，雖然 k項 DNF不是 PAC可學(xué)習(xí)的，但存在一個更大的概念類是 PAC可學(xué)習(xí)的 – 這個更大的概念類是 KCNF，它有每樣例的多項式級時間復(fù)雜度，又有多項式級的樣本復(fù)雜度 – KCNF：任意長度的合取式 T1?...?Tj，其中每個 Ti為最多 k個布爾變量的析取 – 容易證明 KCNF包含了 K項 DNF，因此概念類 k項DNF是使用 H=KCNF的一個有效算法可 PAC學(xué)習(xí)的 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 29 無限假設(shè)空間的樣本復(fù)雜度 ? 式子 |H|刻畫樣本復(fù)雜度有兩個缺點： – 可能導(dǎo)致非常弱的邊界 – 對于無限假設(shè)空間的情形，無法應(yīng)用 ? 本節(jié)考慮 H的復(fù)雜度的另一種度量，稱為 H的VapnikChervonenkis維度（簡稱 VC維或 VC(H)） ? 使用 VC維代替 |H|也可以得到樣本復(fù)雜度的邊界，基于 VC維的樣本復(fù)雜度比 |H|更緊湊，另外還可以刻畫無限假設(shè)空間的樣本復(fù)雜度 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 30 打散一個實例集合 ? VC維衡量假設(shè)空間復(fù)雜度的方法不是用不同假設(shè)的數(shù)量 |H|，而是用 X中能被 H徹底區(qū)分的不同實例的數(shù)量 ? S是一個實例集， H中每個 h導(dǎo)致 S的一個劃分，即 h將 S分割為兩個子集 {x?S|h(x)=1}和 {x?S|h(x)=0} ? 定義：一實例集 S被假設(shè)空間 H打散，當且僅當對 S的每個劃分，存在 H中的某假設(shè)與此劃分一致 ? 如果一實例集合沒有被假設(shè)空間打散，那么必然存在某概念可被定義在實例集之上，但不能由假設(shè)空間表示 ? H的這種打散實例集合的能力是其表示這些實例上定義的目標概念的能力的度量 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 31 VapnikChervonenkis維度 ? 打散一實例集合的能力與假設(shè)空間的歸納偏置緊密相關(guān) ? 無偏的假設(shè)空間能夠打散所有實例組成的集合 X ? 直觀上，被打散的 X的子集越大， H的表示能力越強 ? 定義：定義在實例空間 X上的假設(shè)空間 H的 VapnikChervonenkis維，是可被 H打散的 X的最大有限子集的大小 ? 如果 X的任意有限大的子集可被 H打散，則 VC(H)=? 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 32 VapnikChervonenkis維度（ 2） ? 對于任意有限的 H， VC(H)=log2|H| ? VC維舉例 – 假定實例空間 X為實數(shù)集合，而且 H為實數(shù)軸上的區(qū)間的集合，問 VC(H)是多少？ ? 只要找到能被 H打散的 X的最大子集，首先包含 2個實例的集合能夠被 H打散，其次包含 3個實例的集合不能被 H打散，因此 VC(H)=2 – 實例集合 S對應(yīng) x、 y平面上的點，令 H為此平面內(nèi)所有線性決策面的集合，問 H的 VC維是多少？ ? 能夠找到 3個點組成的集合，被 H打散，但無法找到能夠被H打散的 4個點組成的集合，因此 VC(H)=3 ? 更一般地，在 r維空間中，線性決策面的 VC維為 r+1 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 33 VapnikChervonenkis維度（ 3） – 假定 X上每個實例由恰好 3個布爾文字的合取表示，而且假定 H中每個假設(shè)由至多 3個布爾文字描述，問VC(H)是多少？ ? 找到下面 3個實例的集合 – instance1: 100 – instance2: 010 – instance3: 001 ? 這三個實例的集合可被 H打散，可對如下任意所希望的劃分建立一假設(shè)：如果該劃分要排除 instancei，就將文字 ?li加入到假設(shè)中 ? 此討論很容易擴展到特征數(shù)為 n的情況， n個布爾文字合取的 VC維至少為 n ? 實際就是 n，但證明比較困難，需要說明 n+1個實例的集合不可能被打散 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 34 樣本復(fù)雜度和 VC維 ? 使用 VC維作為 H復(fù)雜度的度量，就有可能推導(dǎo)出該問題的另一種解答，類似于式子 ，即（ Blumer el al. 1989） ? 定理 ：樣本復(fù)雜度的下界（ Ehrenfeucht et al. 1989） – 考慮任意概念類 C，且 VC(C)=2，任意學(xué)習(xí)器 L，以及任意0?1/8， 0?1/100。為增量地處理每個訓(xùn)練樣例， FindS算法要求的運算量根據(jù) n線性增長，并獨立于 1/?、 1/?和 size(c)。布爾文字是任意的布爾變量，或它的否定。 – 任一假設(shè)真實錯誤率大于 ?，且與一個隨機抽取樣例一致的可能性最多為 1?，因此，該假設(shè)與 m個獨立抽取樣例一致的概率最多為 (1?)m – 由于已知有 k個假設(shè)錯誤率大于 ?，那么至少有一個與所有 m個訓(xùn)練樣例都不一致的概率最多為（當 ，則 ） meH ??||mmm eHHk ??? ????? ||)1(||)1(10 ??? ?? e??1 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 19 有限假設(shè)空間的樣本復(fù)雜度（ 5） ? 定理 m、允許的錯誤率?和 H的大小，給出了變型空間不是 ?詳盡的概率的上界 ? 即它對于使用假設(shè)空間 H的任意學(xué)習(xí)器界定了 m個訓(xùn)練樣例未能將所有“壞”的假設(shè)（錯誤率大于 ?的假設(shè)）剔除出去的概率 ? 利用上面的結(jié)論來確定為了減少此“未剔除”概率到一希望程度 ?所需的訓(xùn)練樣例數(shù) – 由 – 解出 m，得到 ?? ?? meH ||? ?)/1ln(||ln1 ?? ?? Hm 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 20 有限假設(shè)空間的樣本復(fù)雜度（ 6） ? 式子 ，該數(shù)目的樣例足以在所期望的值 ?和 ?程度下，使任何一致學(xué)習(xí)器成功地學(xué)習(xí)到 H中的任意目標概念 ? 訓(xùn)練樣例的數(shù)目 m足以保證任意一致假設(shè)是可能（可能性為 1 ?）近似（錯誤率為 ?）正確的 ? m隨著 1/?線性增長，隨著 1/?和假設(shè)空間的規(guī)模對數(shù)增長 ? 上面的界限可能是過高的估計，主要來源于 |H|項，它產(chǎn)生于證明過程中在所有可能假設(shè)上計算那些不可接受的假設(shè)的概率和 ? 在 假設(shè)空間的邊界 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 21 不可知學(xué)習(xí)和不一致假設(shè) ? 如果學(xué)習(xí)器不假定目標概念可在 H中表示，而只簡單地尋找具有最小訓(xùn)練錯誤率的假設(shè)，這樣的學(xué)習(xí)器稱為不可知學(xué)習(xí)器 ? 式 ，在更一般的情形下學(xué)習(xí)器考慮到了有非零訓(xùn)練錯誤率的假設(shè)時，仍能找到一個簡單的邊界 ? 令 S代表學(xué)習(xí)器可觀察到的特定訓(xùn)練樣例集合， errorS(h)表示 h的訓(xùn)練錯誤率，即 S中被 h誤分類的訓(xùn)練樣例所占比例 ? 令 hbest表示 H中有最小訓(xùn)練錯誤率的假設(shè)，問題是：多少訓(xùn)練樣例才足以保證其真實錯誤率 errorD(hbest)不會多于 ?+errorS(hbest)？（上一節(jié)問題是這個問題的特例） 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 22 不可知學(xué)習(xí)和不一致假設(shè)（ 2） ? 前面問題的回答使用類似定理 ，這里有必要引入一般的 Hoeffding邊界 ? Hoeffding邊界刻畫的是某事件的真實概率及其 m個獨立試驗中觀察到的頻率之間的差異 ? Hoeffding邊界表明，當訓(xùn)練錯誤率 errorS(h)在包含 m個隨機抽取樣例的集合 S上測量時，則 ? 上式給出了一個概率邊界，說明任意選擇的假設(shè)訓(xùn)練錯誤率不能代表真實情況，為保證 L尋找到的最佳的假設(shè)的錯誤率有以上的邊界，我們必須考慮這 |H|個假設(shè)中任一個有較大錯誤率的概率 22])()(P r[ ?? mSD ehe r r orhe r r or ????? ?? ?? ? 22||)()(Pr ?? mSD eHhe r r o rhe r r o rHh ?????? 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 23 不可知學(xué)習(xí)和不一致假設(shè)（ 3） ? 將上式左邊概率稱為 ?，問多少個訓(xùn)練樣例 m才足以使 ?維持在一定值內(nèi)，求解得到 ? 式 ，適用于當最佳假設(shè)可能有非零訓(xùn)練錯誤率時，學(xué)習(xí)器仍能選擇到最佳假設(shè) h?H的情形。 ???? )()( , herro rVSh DDH 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 17 有限假設(shè)空間的樣本復(fù)雜度（ 3） ? ?詳盡的變型空間表示與訓(xùn)練樣例一致的所有假設(shè)的真實錯誤率都小于 ? ?