【正文】 常更關(guān)心所需的訓(xùn)練樣例數(shù)， – 如果 L對每個訓(xùn)練樣例需要某最小處理時間，那么為了使 c是 L可 PAC學(xué)習(xí)的， L必須從多項式數(shù)量的訓(xùn)練樣例中進行學(xué)習(xí) – 實際上，為了顯示某目標概念類別 C是可 PAC學(xué)習(xí)的，一個典型的途徑是證明 C中每個目標概念可以從多項式數(shù)量的訓(xùn)練樣例中學(xué)習(xí)到，且處理每個樣例的時間也是多項式級 ? PAC可學(xué)習(xí)性的一個隱含的條件：對 C中每個目標概念 c，假設(shè)空間 H都包含一個以任意小誤差接近 c的假設(shè) 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 15 有限假設(shè)空間的樣本復(fù)雜度 ? PAC可學(xué)習(xí)性很大程度上由所需的訓(xùn)練樣例數(shù)確定 ? 隨著問題規(guī)模的增長所帶來的所需訓(xùn)練樣例的增長稱為該學(xué)習(xí)問題的樣本復(fù)雜度 ? 我們把樣本復(fù)雜度的討論限定于一致學(xué)習(xí)器（輸出完美擬合訓(xùn)練數(shù)據(jù)的學(xué)習(xí)器） ? 能夠獨立于特定算法，推導(dǎo)出任意一致學(xué)習(xí)器所需訓(xùn)練樣例數(shù)的界限 ? 變型空間：能正確分類訓(xùn)練樣例 D的所有假設(shè)的集合。當 VSH,D中每個假設(shè) h關(guān)于 c和 D錯誤率小于 ?時，變型空間被稱為c和 D是 ?詳盡的。當且僅當 k個假設(shè)中至少有一個恰好與所有 m個獨立隨機抽取樣例一致時，不能使變型空間 ?詳盡化。 ? ?)/1ln(||ln2 1 2 ?? ?? Hm 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 24 布爾文字的合取是 PAC可學(xué)習(xí)的 ? 我們已經(jīng)有了一個訓(xùn)練樣例數(shù)目的邊界，表示樣本數(shù)目為多少時才足以可能近似學(xué)習(xí)到目標概念，現(xiàn)在用它來確定某些特定概念類別的樣本復(fù)雜度和 PAC可學(xué)習(xí)性 ? 考慮目標概念類 C，它由布爾文字的合取表示。問題： C是可 PAC學(xué)習(xí)的嗎？ ? 若假設(shè)空間 H定義為 n個布爾文字的合取，則假設(shè)空間 |H|的大小為 3n，得到關(guān)于 n布爾文字合取學(xué)習(xí)問題的樣本復(fù)雜度 ? ? ? ? 140)( 1)/1l n(3ln1 ????? ?? nm 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 25 布爾文字的合取是 PAC可學(xué)習(xí)的（ 2） ? 定理 ：布爾合取式的 PAC可學(xué)習(xí)性 –布爾文字合取的類 C是用 FindS算法 PAC可學(xué)習(xí)的 ? 證明： –式 n、 1/?和 1/?的多項式級，而且獨立于 size(c)。因此這一概念類別是 FindS算法 PAC可學(xué)習(xí)的。存在一個分布 D以及 C中一個目標概念，當 L觀察到的樣例數(shù)目小于下式時： L將以至少 ?的概率輸出一假設(shè) h，使 errorD(h)? ? ?)/13(l og)(8)/2(l og41 22 ??? HVCm ???????? ???? 32 1)(),/1log (1m a x CVC 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 35 樣本復(fù)雜度和 VC維（ 2） ? 定理 ，若訓(xùn)練樣例的數(shù)目太少，那么沒有學(xué)習(xí)器能夠以 PAC模型學(xué)習(xí)到任意非平凡的 C中每個目標概念 ? 式子 ，而定理 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 36 神經(jīng)網(wǎng)絡(luò)的 VC維 ? 本節(jié)給出一般性的結(jié)論，以計算分層無環(huán)網(wǎng)絡(luò)的 VC維。 Vazirani 1994） –令 G為一分層有向無環(huán)圖，有 n個輸入節(jié)點和s?2個內(nèi)部節(jié)點，每個至少有 r個輸入，令 C為 VC維為 d的 Rr上的概念類，對應(yīng)于可由每個內(nèi)部節(jié)點 s描述的函數(shù)集合，令 CG為 C的 G合成，對應(yīng)于可由 G表示的函數(shù)集合，則VC(CG)=2dslog(es) 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 39 神經(jīng)網(wǎng)絡(luò)的 VC維（ 4） ? 假定要考慮的分層有向無環(huán)網(wǎng)絡(luò)中單個節(jié)點都是感知器，由于單獨的 r輸入感知器 VC維為 r+1，代入定理 ，得到 ? 上面的結(jié)果不能直接應(yīng)用于反向傳播的網(wǎng)絡(luò)，原因有兩個： – 此結(jié)果應(yīng)用于感知器網(wǎng)絡(luò)，而不是 sigmoid單元網(wǎng)絡(luò) – 不能處理反向傳播中的訓(xùn)練過程 )l o g ()1(2)( essrCVC sp e rc e p tro nG ??))/13l og ()l og ()1(16)/2l og (4(1 ??? essrm ??? 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 40 學(xué)習(xí)的出錯界限模型 ? 計算學(xué)習(xí)理論考慮多種不同的問題框架 – 訓(xùn)練樣例的生成方式（被動觀察、主動提出查詢） – 數(shù)據(jù)中的噪聲（有噪聲或無噪聲） – 成功學(xué)習(xí)的定義（必須學(xué)到正確的目標概念還是有一定的可能性和近似性） – 學(xué)習(xí)器所做得假定（實例的分布情況以及是否 C?H） – 評估學(xué)習(xí)器的度量標準（訓(xùn)練樣例數(shù)量、出錯數(shù)量、計算時間） 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 41 學(xué)習(xí)的出錯界限模型（ 2） ? 機器學(xué)習(xí)的出錯界限模型 – 學(xué)習(xí)器的評估標準是它在收斂到正確假設(shè)前總的出錯數(shù) – 學(xué)習(xí)器每接受到一個樣例 x，先預(yù)測目標值 c(x)，然后施教者給出正確的目標值 – 考慮的問題是：在學(xué)習(xí)器學(xué)習(xí)到目標概念前，它的預(yù)測會有多少次出錯 – 下面討論中，只考慮學(xué)習(xí)器確切學(xué)到目標概念前出錯的次數(shù)，確切學(xué)到的含義是 ?x h(x)=c(x) 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 42 FindS算法的出錯界限 ? FindS算法的一個簡單實現(xiàn) – 將 h初始化為最特殊假設(shè) l1??l1?...?ln??ln – 對每個正例 x ? 從 h中移去任何不滿足 x的文字 – 輸出假設(shè) h ? 計算一個邊界，以描述 FindS在確切學(xué)到目標概念 c前全部的出錯次數(shù) – FindS永遠不會將一反例錯誤地劃分為正例，因此只需要計算將正例劃分為反例的出錯次數(shù) – 遇到第一個正例，初始假設(shè)中 2n個項半數(shù)被刪去，對后續(xù)的被當前假設(shè)誤分類的正例，至少有一項從假設(shè)中刪去 – 出錯總數(shù)至多為 n+1 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 43 Halving算法的出錯界限 ? 學(xué)習(xí)器對每個新實例 x做出預(yù)測的方法是：從當前變型空間的所有假設(shè)中取多數(shù)票得來 ? 將變型空間學(xué)習(xí)和用多數(shù)票來進行后續(xù)預(yù)測結(jié)合起來的算法稱為 Halving算法 ? Halving算法只有在當前變型空間的多數(shù)假設(shè)不能正確分類新樣例時出錯，此時變型空間至少可減少到它的一半大小，因此出錯界線是 log2|H| ? Halving算法有可能不出任何差錯就確切學(xué)習(xí)到目標概念，因為即使多數(shù)票是正確的，算法仍將移去那些不正確、少數(shù)票假設(shè) ? Halving算法的一個擴展是允許假設(shè)以不同的權(quán)值進行投票（如貝葉斯最優(yōu)分類器和后面討論的加權(quán)多數(shù)算法） 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 44 最優(yōu)出錯界限 ? 問題：對于任意概念類 C，假定 H=C，最優(yōu)的出錯邊界是什么？ ? 最優(yōu)出錯邊界是指在所有可能的學(xué)習(xí)算法中，最壞情況下出錯邊界中最小的那一個 ? 對任意學(xué)習(xí)算法 A和任意目標概念 c，令 MA(c)代表 A為了確切學(xué)到 c，在所有可能訓(xùn)練樣例序列中出錯的最大值 ? 對于任意非空概念類 C，令 MA(C)=maxc?CMA(c) ? 定義： C為任意非空概念類， C的最優(yōu)出錯界限定義為Opt(C)是所有可能學(xué)習(xí)算法 A中 MA(C)的最小值 )(m in)( 學(xué) 習(xí) CMCO p t AA 算法?? 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 45 最優(yōu)出錯界限（ 2） ? 非形式地說， Opt(C)是 C中最難的那個目標概念使用最不利的訓(xùn)練樣例序列用最好的算法時的出錯次數(shù) ? Littlestone1987證明了 ||l o g)()()( 2 CCMCO p tCVC Ha lv in g ??? 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 46 加權(quán)多數(shù)算法 ? Halving算法的更一般形式稱為加權(quán)多數(shù)算法 ? 加權(quán)多數(shù)算法通過在一組預(yù)測算法中進行加權(quán)投票來作出預(yù)測，并通過改變每個預(yù)測算法的權(quán)來學(xué)習(xí) ? 加權(quán)多數(shù)算法可以處理不一致的訓(xùn)練數(shù)據(jù)，因為它不會消除與樣例不一致的假設(shè)，只是降低其權(quán) ? 要計算加權(quán)多數(shù)算法的出錯數(shù)量邊界，可以用預(yù)測算法組中最好的那個算法的出錯數(shù)量 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 47 加權(quán)多數(shù)算法（ 2） ? 加權(quán)多數(shù)算法一開始將每個預(yù)測算法賦予權(quán)值 1，然后考慮訓(xùn)練樣例，只要一個預(yù)測算法誤分類新訓(xùn)練樣例，它的權(quán)被乘以某個系數(shù) β， 0=β1。如果一算法誤分類一個樣例，那么它的權(quán)值變小 機器學(xué)習(xí) 計算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 48 加權(quán)多數(shù)算法（ 3） ? ai代表算法池 A中第 i個預(yù)測算法， wi代表與 ai相關(guān)聯(lián)的權(quán)值 ? 對所有 i，初始化 wi?1 ? 對每個訓(xùn)練樣例 x, c(x)做： – 初始化 q0和 q1為 0 – 對每個預(yù)測算法 ai ? 如果 ai(x)=0，那么 q0?q0+wi ? 如果 ai(x)=1，那么 q