沿著PAC學(xué)習(xí)理論当宴，討論有限假設(shè)空間的樣本復(fù)雜度轰传，并用Hoeffding不等式來(lái)界定概率邊界盗扒。
假設(shè)空間的樣本復(fù)雜度
PAC可學(xué)習(xí)性很大程度上由所需的訓(xùn)練樣本數(shù)量決定。隨著問(wèn)題規(guī)模的增長(zhǎng)所帶來(lái)的所需訓(xùn)練樣本的增長(zhǎng)稱為學(xué)習(xí)問(wèn)題的樣本復(fù)雜度（sample complexity）刨啸。在多數(shù)實(shí)際問(wèn)題中堡赔，最限制學(xué)習(xí)器成功的因素是有限的可用的訓(xùn)練數(shù)據(jù)。
我們通常都喜歡能與訓(xùn)練數(shù)據(jù)擬合程度更高的假設(shè)呜投，當(dāng)一個(gè)學(xué)習(xí)器在可能時(shí)都輸出能完美擬合訓(xùn)練數(shù)據(jù)的假設(shè)時(shí)加匈，我們稱該學(xué)習(xí)器是一致的（consistent）。這就要求訓(xùn)練錯(cuò)誤率是0仑荐。
遺憾的是雕拼，如果假設(shè)空間里不總是能找到一個(gè)零錯(cuò)誤率的假設(shè)，這時(shí)粘招，最多能要求學(xué)習(xí)器輸出的假設(shè)在訓(xùn)練數(shù)據(jù)上有最小的錯(cuò)誤率啥寇。
在更一般的情形下，我們要考慮學(xué)習(xí)器有非零訓(xùn)練錯(cuò)誤率的假設(shè)時(shí)洒扎，仍能找到一個(gè)邊界來(lái)限定學(xué)習(xí)器所需的樣本數(shù)量辑甜。
Hoeffding邊界
描述問(wèn)題
現(xiàn)在，我們來(lái)更準(zhǔn)確的描述我們要解決的問(wèn)題袍冷。
令D代表學(xué)習(xí)器可觀察的特定的訓(xùn)練數(shù)據(jù)集合磷醋，而P代表整個(gè)數(shù)據(jù)集合背后滿足的概率分布。令Ein(h)代表假設(shè)h的訓(xùn)練錯(cuò)誤率（在機(jī)器學(xué)習(xí)基石課程中胡诗，該錯(cuò)誤率被稱為in-sample error）邓线，確切的說(shuō)淌友，Ein(h)是數(shù)據(jù)集D中被h誤分類的訓(xùn)練數(shù)據(jù)所占比例，Ein(h)是定義在訓(xùn)練數(shù)據(jù)集D上的骇陈，而真實(shí)錯(cuò)誤率Eout(h)（out-of-sample error）是定義在整個(gè)概率分布P上的≌鹜ィ現(xiàn)在令g代表H中有最小訓(xùn)練錯(cuò)誤率的假設(shè)。問(wèn)：多少訓(xùn)練數(shù)據(jù)才足以保證真實(shí)錯(cuò)誤率Eout(h)和訓(xùn)練錯(cuò)誤率Ein(h)很接近你雌，并且接近0器联。
Hoeffding不等式
Hoeffding Inequality
Hoeffding刻畫(huà)的是某個(gè)事件的真實(shí)概率及其m個(gè)獨(dú)立重復(fù)試驗(yàn)中觀察到的頻率之間的差異，更準(zhǔn)確的將婿崭，它是應(yīng)用于m個(gè)不同的Bernoulli試驗(yàn)拨拓。
該不等式給出了一個(gè)概率邊界，它說(shuō)明任意選擇的假設(shè)訓(xùn)練錯(cuò)誤率不能代表真實(shí)情況氓栈。
確認(rèn)（verification）流程
我們發(fā)現(xiàn)滿足上面給的邊界不等式的h可不可以說(shuō)它是一個(gè)好的學(xué)習(xí)器呢千元？當(dāng)然不能，上面的不等式只能說(shuō)明h的訓(xùn)練錯(cuò)誤率和真實(shí)錯(cuò)誤率很接近颤绕，但卻不一定是最小的，即h不一定是最佳的假設(shè)祟身。所以奥务，這只是對(duì)一個(gè)假設(shè)做確認(rèn)的過(guò)程。
這里因?yàn)橹挥幸粋€(gè)hypothesis在手上袜硫，所以我們還不能做選擇氯葬，但是我們可以給它一些verifying examples來(lái)讓它做確認(rèn)，看看h的表現(xiàn)如何婉陷，正如上圖流程所示帚称。
有限假設(shè)空間的錯(cuò)誤率的概率邊界
Hoeffding不等式告訴我們什么呢？較好擬合訓(xùn)練數(shù)據(jù)的假設(shè)與該假設(shè)針對(duì)整個(gè)數(shù)據(jù)集合的預(yù)測(cè)秽澳，這兩者的錯(cuò)誤率差別很大的那種情況發(fā)生的概率是很小的闯睹。
那么現(xiàn)在的問(wèn)題是什么呢？如果在多個(gè)假設(shè)中担神，其中一個(gè)假設(shè)針對(duì)訓(xùn)練數(shù)據(jù)的輸出都是正確的楼吃，那要不要選這個(gè)假設(shè)作為算法的輸出的假設(shè)呢？
帶著這個(gè)問(wèn)題妄讯，我們先了解一下什么叫做不好的數(shù)據(jù)孩锡。
Bad Sample and Bad Data
壞的樣本就是訓(xùn)練錯(cuò)誤率Ein=0，而真實(shí)錯(cuò)誤率Eout=1/2的情況亥贸。
壞的數(shù)據(jù)是Ein和Eout差別很大的情況躬窜，通常Ein很小，Eout很大炕置。
而Hoeffding說(shuō)明的是如果把所有的訓(xùn)練數(shù)據(jù)（從輸入空間中荣挨，隨機(jī)選取產(chǎn)生的數(shù)據(jù)的不同組合）窮舉出來(lái)男韧，得到的不好的樣本（Bad Sample）的概率是很小的。
所以壞的樣本就是讓算法的預(yù)測(cè)的準(zhǔn)確率和訓(xùn)練時(shí)的正確率差別很大的情況（Ein和Eout差別很大）垦沉。
上圖說(shuō)明：
對(duì)于一個(gè)假設(shè)hi（每一行）煌抒，Hoeffding保證其不好的情況總體的概率是很小的
對(duì)于含有BAD的每一列來(lái)說(shuō)，只要有BAD厕倍，算法就無(wú)法從所有假設(shè)中自由做選擇
表中D1126這個(gè)數(shù)據(jù)集是好的數(shù)據(jù)
Bound of BAD Data
我們來(lái)算一下壞的數(shù)據(jù)的概率邊界：
這個(gè)式子是有限個(gè)假設(shè)的Hoeffding不等式寡壮。
對(duì)于這個(gè)式子來(lái)說(shuō)，如果訓(xùn)練數(shù)據(jù)的數(shù)量N夠大的話讹弯，那么能保證Ein和Eout差別很小况既。
總結(jié)：如果現(xiàn)有有限個(gè)假設(shè)且訓(xùn)練數(shù)據(jù)量夠多的情況下，那么不管我們?nèi)绾芜x擇訓(xùn)練數(shù)據(jù)组民，訓(xùn)練錯(cuò)誤率和真實(shí)錯(cuò)誤率都會(huì)很接近棒仍；我們?cè)O(shè)計(jì)算法來(lái)找一個(gè)Ein最小的，PAC理論就保證了Eout很小臭胜。這樣機(jī)器學(xué)習(xí)算法是有可能學(xué)到有用的知識(shí)的莫其！
————————————————
原文鏈接：https://blog.csdn.net/jasonding1354/java/article/details/41871733
