關(guān)鍵字
PAC總結(jié)理論：同等條件下烫映，模型越復(fù)雜泛化誤差越大抽兆。同一模型在樣本滿足一定條件的情況下辫红，其數(shù)量越大贴妻，模型泛化誤差越小白翻，因此還可以說模型越復(fù)雜越吃樣本滤馍。
1.基礎(chǔ)知識：
計算學(xué)習(xí)理論研究的是關(guān)于通過“計算”來進(jìn)行“學(xué)習(xí)”的理論，其目的是分析學(xué)習(xí)任務(wù)的困難本質(zhì)阁苞，為學(xué)習(xí)算法提供理論保證那槽，并根據(jù)分析結(jié)果知道算法
幾個常用的不等式：
- Jensen不等式：對任意凸函數(shù)f(x),有：
2.PAC學(xué)習(xí)（概率近似正確學(xué)習(xí)）：
PAC學(xué)習(xí)理論的作用：
讓你明白到邀摆，為什么一個假設(shè)（模型或函數(shù)）學(xué)習(xí)了訓(xùn)練樣本后栋盹，能保證這個假設(shè)在訓(xùn)練樣本之外的數(shù)據(jù)上有效。
什么是PAC學(xué)習(xí)理論：
某個訓(xùn)練樣本對正確目標(biāo)的映射榨汤，而稱為‘概念’，用符號c表示蜜宪，即存在一個映射，使得c（x） = y澳窑，這只是某一個結(jié)果，并不是集合栗精。
所有我們希望所有訓(xùn)練目標(biāo)的映射集合為‘概念類’鹿寨，用符號C表示赫悄。
模型經(jīng)過訓(xùn)練后得到的所有結(jié)果映射集合姑隅，稱為‘假設(shè)空間’，用符號H表示鄙陡。
首先PAC學(xué)習(xí)理論對機(jī)器學(xué)習(xí)算法結(jié)果有兩個概念
- 可分的：
訓(xùn)練樣本通過學(xué)習(xí)算法后，得出的假設(shè)空間，c屬于H培漏，我們稱為可分的 - 不可分的：
訓(xùn)練樣本通過學(xué)習(xí)算法后，得出的假設(shè)空間，c不屬于H咒锻，我們稱為不可分的
當(dāng)然在學(xué)習(xí)算法中，我們都希望學(xué)習(xí)算法盡可能有更多的c屬于H中，為什么只是盡可能多恭取，而不是要求精確呢耗跛？因?yàn)樵跈C(jī)器學(xué)習(xí)算法中惠猿，會受到很多因素的制約蜒茄，所以并不會百分百地對應(yīng)到。
當(dāng)選擇學(xué)習(xí)算法時候，我們希望以比較大的把握學(xué)得比較好的模型润讥。要判斷哪些學(xué)習(xí)算法能選用竿痰，這就需要符合PAC可學(xué)習(xí)性
PAC可學(xué)習(xí)性：
首先學(xué)習(xí)算法得出的‘假設(shè)’必須滿足以下的兩個條件（PAC辨識）才算上“近似”正確對應(yīng)目的概念c：
PAC辨識：
近似正確：泛化誤差E(h)足夠小
E(h)越小越好，最好泛化誤差能能于0，但一般是不可能的。那我們就把E(h)限定在一個很小的數(shù)?之內(nèi)夏哭，即只要假設(shè)h滿足E(h)≤?里逆，我們就認(rèn)為h是正確的胁镐。
可能正確
不指望選擇的假設(shè)h百分之百是近似正確的（按上段所述笨农，即E(h)≤?）竭宰，只要很可能是近似正確的就可以锁摔，即我們給定一個值δ孕豹，假設(shè)h滿足P(h近似正確)≥1?δ
滿足以上兩點(diǎn)的學(xué)習(xí)算法，就是能以較大概率學(xué)得目標(biāo)概念c的近似。
PAC可學(xué)習(xí)：
概念：當(dāng)學(xué)習(xí)算法能從假設(shè)空間H中PAC辨識概念類C杖狼，則稱概念類對假設(shè)空間H而言是PAC可學(xué)習(xí)的炼蛤。
PAC學(xué)習(xí)中一個關(guān)鍵因素是假設(shè)空間H的復(fù)雜度，H包含了學(xué)習(xí)算法所有可能輸出的假設(shè)蝶涩。在實(shí)際問題中概念類C往往是不等于H的理朋，因?yàn)槲覀儗Ω拍铑愋跏叮桓挪恢．?dāng)H越大嗽上，其包含任意目標(biāo)概念的可能性越大次舌，但從中找到某個具體目標(biāo)概念的難度也越大。|H|有限時候兽愤，我們稱H為“有限假設(shè)空間”彼念，否則稱為“無限假設(shè)空間”
可分情形:
在可分情形下，如何找到滿足誤參數(shù)的假設(shè)呢浅萧？
訓(xùn)練集D中逐沙，樣例都可以通過目標(biāo)概念c，映射結(jié)果洼畅，而c存在假設(shè)空間H中吩案，那么我們通過保留D中一致的假設(shè)，剔除與D不一致的假設(shè)土思，知道H只剩下一個假設(shè)位置务热，這個假設(shè)就是目標(biāo)概念。前提是訓(xùn)練集D足夠大己儒。
不可分情形：
對比較困難的學(xué)習(xí)問題崎岂，目標(biāo)概念c通常不存在于H中，也就是說闪湾，H中的任意一個假設(shè)都會在訓(xùn)練集上出現(xiàn)或多或少的錯誤冲甘，有Hoeffding不等式知：
通過式12.17可得：
由該公式可知道，說明了對于任意?途样，只要樣本數(shù)量m足夠小江醇，|E(h)?^E(h)|>? 發(fā)生的可能性就非常大，此時我們不能用經(jīng)驗(yàn)誤差近似泛化誤差何暇，但是反之陶夜，當(dāng)樣本數(shù)量m足夠大時，|E(h)?^E(h)|>?發(fā)生的可能性就非常小裆站，此時我們可以用經(jīng)驗(yàn)誤差近似泛化誤差条辟。
為什么在訓(xùn)練樣本上學(xué)習(xí)得到的假設(shè)會在真實(shí)樣本上有效？公式很好的說明了這一問題宏胯。只要樣本數(shù)量m足夠大或者假設(shè)空間的大小|H|足夠小羽嫡，公式就能保證學(xué)到的假設(shè)h′的泛化誤差E(h′)與經(jīng)驗(yàn)誤差^E(h′)足夠接近。h′在訓(xùn)練樣本上的表現(xiàn)與在真實(shí)樣本上一致
令置信區(qū)間等于2|H|exp（-2m?2）肩袍，并經(jīng)過轉(zhuǎn)換杭棵，即可得式12.19
由12.19可知，不可分時氛赐，學(xué)習(xí)算法無法學(xué)得目標(biāo)概念c的?近似魂爪，但是先舷，當(dāng)假設(shè)空間H給定時，其中必存在一個泛化誤差最小的假設(shè)甫窟，所以解決這些不可知學(xué)習(xí)密浑，最好辦法是找到此假設(shè)的?近似蛙婴。
滿足上述公式條件的粗井，我們可稱該假設(shè)空間H為不可知PAC可學(xué)習(xí)的。
