文|機(jī)器2025

PAC學(xué)習(xí)模型

11月21日訊，自從下定決心認(rèn)真學(xué)習(xí)機(jī)器學(xué)習(xí)理論開始，接觸到很多基本問題，但其實(shí)都不是很理解，比如損失函數(shù)、風(fēng)險(xiǎn)函數(shù)、經(jīng)驗(yàn)結(jié)構(gòu)最小化、結(jié)構(gòu)風(fēng)險(xiǎn)最小化、學(xué)習(xí)方法的泛化能力、VC維等，這些概念在學(xué)習(xí)中都純屬空泛的概念存在，我都不理解這些概念存在的意義。

為什么會(huì)存在這樣的問題呢?我自己想了一下，有幾個(gè)原因：首先，很多相關(guān)的書籍在講授這些概念的時(shí)候，很少說這些為什么會(huì)有這樣的概念問題，為解決什么問題引入的這些概念;然后，還有一些書，在簡單表述了這些概念之后就立馬挨個(gè)介紹算法了，遇到這樣的書也會(huì)忽視這些基礎(chǔ)問題的存在;最后，當(dāng)初學(xué)者在遇到這些概念的時(shí)候，看到很多公式和抽象的表達(dá)方式，很容易產(chǎn)生挫敗感，進(jìn)而忽視了這些基礎(chǔ)。

但是，我覺得這些問題還是很重要的。為什么這么說呢?原因如下：

1、理解這些問題有助于理解為什么機(jī)器可以學(xué)習(xí)，增強(qiáng)學(xué)習(xí)具體算法的信心，有助于深入進(jìn)去;

2、理解這些基本問題并掌握基本的分析方法有助于分析具體學(xué)習(xí)算法的泛化能力;

舉例

如圖所示，輸入為x，是一個(gè)三維數(shù)據(jù)，且元素都為布爾值，如果以D來做訓(xùn)練數(shù)據(jù)，那么要預(yù)測未知的情況，那請(qǐng)問當(dāng)x為101,110,111的時(shí)候，預(yù)測輸出y是什么呢?

我們看到圖表中，會(huì)有8中不同的假設(shè)(hypothesis)，所以我們無論預(yù)測是哪種輸出，都有可能讓我們的預(yù)測是完全錯(cuò)誤的。這是不是就說明這種條件下，學(xué)習(xí)器是不可學(xué)習(xí)的呢?現(xiàn)在我們就從這個(gè)角度出發(fā)，看看如何訓(xùn)練我們的學(xué)習(xí)器，才能讓學(xué)習(xí)器真正學(xué)到有用的知識(shí)，進(jìn)而來產(chǎn)生有效的預(yù)測。

可能近似正確（probably approximately correct，PAC）學(xué)習(xí)模型

問題框架

這里我會(huì)簡要描述一下我們要處理的具體問題。

假定數(shù)據(jù)按照某概率分布P從X中隨機(jī)產(chǎn)生，一般，D可為任意分布，并且它對(duì)學(xué)習(xí)型算法是未知的。對(duì)于P，所要求的是它的穩(wěn)定性，即該分布不會(huì)隨時(shí)間變化(不然我們就沒有學(xué)習(xí)的意義了)。訓(xùn)練數(shù)據(jù)的由P分布隨機(jī)抽取而產(chǎn)生x，然后x及其目標(biāo)值(可以理解為y，標(biāo)簽)被提供給學(xué)習(xí)器

學(xué)習(xí)器在學(xué)習(xí)目標(biāo)函數(shù)時(shí)考慮可能假設(shè)的集合H。

在觀察了一系列訓(xùn)練數(shù)據(jù)后，學(xué)習(xí)器需要從假設(shè)集合H中得到最終的假設(shè)g，這是對(duì)未知的符合D分布的理想模型f的估計(jì)。

最后，我們通過精心挑選出來的假設(shè)g對(duì)X中新的數(shù)據(jù)的性能來評(píng)估訓(xùn)練器。

錯(cuò)誤率

為了描述學(xué)習(xí)器輸出的假設(shè)h對(duì)真實(shí)目標(biāo)函數(shù)f的逼近程度，我們要定義兩種錯(cuò)誤率：

1、真實(shí)錯(cuò)誤率(true error)，也可以說是out-of-sample error,即樣本之外，對(duì)于從任意分布中抽取的所有數(shù)據(jù)而言。

h的真實(shí)錯(cuò)誤率是應(yīng)用h到未來按分布P抽取的數(shù)據(jù)時(shí)的期望錯(cuò)誤率

具體定義如下：

2、樣本錯(cuò)誤率(sample error)，也可以說是in-sample error，即針對(duì)所訓(xùn)練的樣本數(shù)據(jù)的。

因?yàn)閔關(guān)于f的錯(cuò)誤率不能直接由學(xué)習(xí)器觀察到。學(xué)習(xí)器只能觀察到在訓(xùn)練數(shù)據(jù)上h的性能如何，所以訓(xùn)練器也只能在此性能基礎(chǔ)上選擇其假設(shè)輸出。我們用訓(xùn)練錯(cuò)誤率(training error)來指代訓(xùn)練樣本中被h誤分類的數(shù)據(jù)所占的比例，以區(qū)分真實(shí)錯(cuò)誤率。

那么，數(shù)據(jù)集合S的樣本錯(cuò)誤率為數(shù)據(jù)集合S中被h誤分類的數(shù)據(jù)所占的比例。訓(xùn)練錯(cuò)誤率就是當(dāng)S為訓(xùn)練數(shù)據(jù)集合時(shí)的樣本錯(cuò)誤率。

PAC可學(xué)習(xí)性(PAC Learnability)

我們訓(xùn)練學(xué)習(xí)器的目標(biāo)是，能夠從合理數(shù)量的訓(xùn)練數(shù)據(jù)中通過合理的計(jì)算量可靠的學(xué)習(xí)到知識(shí)。

機(jī)器學(xué)習(xí)的現(xiàn)實(shí)情況：

1、除非對(duì)每個(gè)可能的數(shù)據(jù)進(jìn)行訓(xùn)練，否則總會(huì)存在多個(gè)假設(shè)使得真實(shí)錯(cuò)誤率不為0，即學(xué)習(xí)器無法保證和目標(biāo)函數(shù)完全一致

2、訓(xùn)練樣本是隨機(jī)選取的，訓(xùn)練樣本總有一定的誤導(dǎo)性

為此，我們要弱化對(duì)學(xué)習(xí)器的要求：

1、我們不要求學(xué)習(xí)器輸出零錯(cuò)誤率的假設(shè)，只要求錯(cuò)誤率被限制在某常數(shù)ε范圍內(nèi)，ε可為任意小。

2、不要求學(xué)習(xí)器對(duì)所有任意抽取的數(shù)據(jù)都能成功預(yù)測，只要求其失敗的概率被限定在某個(gè)常數(shù)μ的范圍內(nèi)，μ可取任意小。

簡而言之，我們只要求學(xué)習(xí)器可能學(xué)習(xí)到一個(gè)近似正確的假設(shè)，故得到了“可能近似正確學(xué)習(xí)”或PAC學(xué)習(xí)。

一個(gè)可PAC學(xué)習(xí)的學(xué)習(xí)器要滿足兩個(gè)條件：

學(xué)習(xí)器必須以任意高的概率輸出一個(gè)錯(cuò)誤率任意低的假設(shè)

學(xué)習(xí)過程的時(shí)間最多以多項(xiàng)式方式增長

對(duì)于PAC學(xué)習(xí)來說，訓(xùn)練樣本的數(shù)量和學(xué)習(xí)所需的計(jì)算資源是密切相關(guān)的。如果學(xué)習(xí)器對(duì)每個(gè)訓(xùn)練樣本需要某最小處理時(shí)間，那么為了使目標(biāo)函數(shù)f是可PAC學(xué)習(xí)的，學(xué)習(xí)器必須在多項(xiàng)式數(shù)量的訓(xùn)練樣本中進(jìn)行學(xué)習(xí)。實(shí)際上，為了顯示某輸出空間的類別C是可PAC學(xué)習(xí)的，一個(gè)典型的途徑是證明中每個(gè)C可以從多項(xiàng)式數(shù)量的訓(xùn)練樣本中學(xué)習(xí)到，而后證明每個(gè)樣本處理時(shí)間也限制于多項(xiàng)式級(jí)。

Hoeffding不等式

假設(shè)空間的樣本復(fù)雜度

PAC可學(xué)習(xí)性很大程度上由所需的訓(xùn)練樣本數(shù)量決定。隨著問題規(guī)模的增長所帶來的所需訓(xùn)練樣本的增長稱為學(xué)習(xí)問題的樣本復(fù)雜度(sample complexity)。在多數(shù)實(shí)際問題中，最限制學(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è)邊界來限定學(xué)習(xí)器所需的樣本數(shù)量。

Hoeffding邊界

描述問題

現(xiàn)在，我們來更準(zhǔ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)，確切的說，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上的?，F(xiàn)在令g代表H中有最小訓(xùn)練錯(cuò)誤率的假設(shè)。問：多少訓(xùn)練數(shù)據(jù)才足以保證真實(shí)錯(cuò)誤率Eout(h)和訓(xùn)練錯(cuò)誤率Ein(h)很接近，并且接近0。

Hoeffding不等式

Hoeffding刻畫的是某個(gè)事件的真實(shí)概率及其m個(gè)獨(dú)立重復(fù)試驗(yàn)中觀察到的頻率之間的差異，更準(zhǔn)確的將，它是應(yīng)用于m個(gè)不同的Bernoulli試驗(yàn)。

該不等式給出了一個(gè)概率邊界，它說明任意選擇的假設(shè)訓(xùn)練錯(cuò)誤率不能代表真實(shí)情況。

確認(rèn)（verification）流程

我們發(fā)現(xiàn)滿足上面給的邊界不等式的h可不可以說它是一個(gè)好的學(xué)習(xí)器呢?當(dāng)然不能，上面的不等式只能說明h的訓(xùn)練錯(cuò)誤率和真實(shí)錯(cuò)誤率很接近，但卻不一定是最小的，即h不一定是最佳的假設(shè)。所以，這只是對(duì)一個(gè)假設(shè)做確認(rèn)的過程。

這里因?yàn)橹挥幸粋€(gè)hypothesis在手上，所以我們還不能做選擇，但是我們可以給它一些verifying examples來讓它做確認(rèn)，看看h的表現(xiàn)如何，正如上圖流程所示。

有限假設(shè)空間的錯(cuò)誤率的概率邊界

Hoeffding不等式告訴我們什么呢?較好擬合訓(xùn)練數(shù)據(jù)的假設(shè)與該假設(shè)針對(duì)整個(gè)數(shù)據(jù)集合的預(yù)測，這兩者的錯(cuò)誤率差別很大的那種情況發(fā)生的概率是很小的。

那么現(xiàn)在的問題是什么呢?如果在多個(gè)假設(shè)中，其中一個(gè)假設(shè)針對(duì)訓(xùn)練數(shù)據(jù)的輸出都是正確的，那要不要選這個(gè)假設(shè)作為算法的輸出的假設(shè)呢?

帶著這個(gè)問題，我們先了解一下什么叫做不好的數(shù)據(jù)。

Bad Sample and Bad Data

壞的樣本就是訓(xùn)練錯(cuò)誤率Ein=0，而真實(shí)錯(cuò)誤率Eout=1/2的情況。

壞的數(shù)據(jù)是Ein和Eout差別很大的情況，通常Ein很小，Eout很大。

而Hoeffding說明的是如果把所有的訓(xùn)練數(shù)據(jù)(從輸入空間中，隨機(jī)選取產(chǎn)生的數(shù)據(jù)的不同組合)窮舉出來，得到的不好的樣本(Bad Sample)的概率是很小的。

所以壞的樣本就是讓算法的預(yù)測的準(zhǔn)確率和訓(xùn)練時(shí)的正確率差別很大的情況(Ein和Eout差別很大)。

上圖說明：

對(duì)于一個(gè)假設(shè)hi(每一行)，Hoeffding保證其不好的情況總體的概率是很小的

對(duì)于含有BAD的每一列來說，只要有BAD，算法就無法從所有假設(shè)中自由做選擇

表中D1126這個(gè)數(shù)據(jù)集是好的數(shù)據(jù)

Bound of BAD Data

我們來算一下壞的數(shù)據(jù)的概率邊界：

這個(gè)式子是有限個(gè)假設(shè)的Hoeffding不等式。

對(duì)于這個(gè)式子來說，如果訓(xùn)練數(shù)據(jù)的數(shù)量N夠大的話，那么能保證Ein和Eout差別很小。

統(tǒng)計(jì)學(xué)習(xí)流程

上面的流程總結(jié)了我們這篇文章討論的問題，那就是如果現(xiàn)有有限個(gè)假設(shè)且訓(xùn)練數(shù)據(jù)量夠多的情況下，那么不管我們?nèi)绾芜x擇訓(xùn)練數(shù)據(jù)，訓(xùn)練錯(cuò)誤率和真實(shí)錯(cuò)誤率都會(huì)很接近;我們設(shè)計(jì)算法來找一個(gè)Ein最小的，PAC理論就保證了Eout很小。這樣機(jī)器學(xué)習(xí)算法是有可能學(xué)到有用的知識(shí)的!

VC理論

面臨待解決的問題

我們證明了PAC學(xué)習(xí)的樣本復(fù)雜度隨假設(shè)空間對(duì)數(shù)增長，但是以假設(shè)空間的個(gè)數(shù)|H|來刻畫樣本復(fù)制度存在缺點(diǎn)：

對(duì)于|H|很大的情形，會(huì)使一個(gè)很弱的邊界，即出現(xiàn)錯(cuò)誤的概率很大

對(duì)于無限假設(shè)空間的情形無法應(yīng)用

所以，我們要考慮H的復(fù)雜度的另一種度量方式，稱為H的Vapnik-Chervonenkis維度(簡稱VC維)，我們用VC(H)代替|H|得到樣本復(fù)雜度的邊界。

打散(shatter)一個(gè)數(shù)據(jù)集合

VC維衡量假設(shè)空間復(fù)雜度的方法不是用不同假設(shè)的數(shù)量|H|，而是用給定X中能被H徹底區(qū)分的不同實(shí)例的數(shù)量(舉個(gè)例子，比如2D空間有兩個(gè)數(shù)據(jù)，如果是用感知機(jī)模型的話，可以將這兩個(gè)數(shù)據(jù)分成兩個(gè)正例、兩個(gè)負(fù)例、一正一負(fù)或一負(fù)一正，我們知道在這種情況下，感知機(jī)的假設(shè)空間是無窮的，但是實(shí)際上導(dǎo)致最終分類的只有4中不同結(jié)果)。

Dichotomy，一分為二的劃分

想象我們現(xiàn)在有一個(gè)假設(shè)集合，這個(gè)假設(shè)集合將N個(gè)點(diǎn)的數(shù)據(jù)分成正例和負(fù)例的不同組合(用圈和叉來表示)，于是我們就將假設(shè)將數(shù)據(jù)分成不同正負(fù)例的組合稱為Dichotomy。Hypotheses和Dichotomies的區(qū)別如下圖所示，Dichotomies最多有2的N次方種可能。于是，我們就打算用Dichotomies的有效數(shù)量來取代有限假設(shè)空間的Hoeffding不等式中的M。

成長函數(shù)Growth Function

由于這里我們定義的Dichotomy是依賴具體的N個(gè)輸入數(shù)據(jù)的，為了移除這里的影響，我們現(xiàn)定義成長函數(shù)mH(N)，用它來表示對(duì)于不同的數(shù)據(jù)集的Dichotomy的最大值。

以2D的Perceptron舉例來說，針對(duì)不一樣的輸入點(diǎn)的個(gè)數(shù)N，可能有不同的有效分離平面，不一定是2的N次方種。

shatter

一數(shù)據(jù)集D被假設(shè)空間H打散(shatter)，當(dāng)且僅當(dāng)對(duì)D的每個(gè)劃分，存在H中的某假設(shè)與此劃分一致(即當(dāng)D的每種可能劃分可由H中的某個(gè)假設(shè)來表達(dá)時(shí)，稱H打散D)。

注意：如果一個(gè)數(shù)據(jù)集合沒有被假設(shè)空間打散，那么必然存在某種劃分可被定義在數(shù)據(jù)集中，但不能由假設(shè)空間表示。

H的這種打散數(shù)據(jù)集合的能力是其在這些數(shù)據(jù)上定義目標(biāo)函數(shù)的表示能力的度量?？梢哉f被打散的X的子集越大，H的表示能力越強(qiáng)。

Break Point of H

基于上面的介紹我們可以回頭看看Hoeffding不等式，我們想要用成長函數(shù)mH(N)來代替假設(shè)空間的數(shù)量|H|，而如果mH(N)和e的負(fù)冪次相乘，那么得到一個(gè)很小的數(shù)，這就對(duì)出錯(cuò)的概率作了一個(gè)限制;而如果mH(N)是一個(gè)冪指數(shù)的話，就無法限制錯(cuò)誤率。

下面，我們定義一個(gè)新的概念——Break Point。如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)k是，假設(shè)空間H無法打散這個(gè)數(shù)據(jù)集，那么就說k是H的Break Point。比如，2D的Perceptron的情形，當(dāng)N=4時(shí)，數(shù)據(jù)集應(yīng)該可以有16種類別情形，而實(shí)際上，假設(shè)空間的有效個(gè)數(shù)只是14，那么4就是這個(gè)H的Break Point。

Bounding Function

上限函數(shù)Bounding Function B(N,k)是Break Point為k時(shí)，成長函數(shù)mH(N)的最大值，利用上限函數(shù)可以不去管假設(shè)空間里的具體細(xì)節(jié)，這樣，只要上限函數(shù)是多項(xiàng)式的形式的話，就可以解決問題。

這里我們經(jīng)過計(jì)算歸納，得到了上限函數(shù)的列表和規(guī)律：

經(jīng)過一番努力，我們可以得到成長函數(shù)mH(N)<=上限函數(shù)B(N,k) <=多項(xiàng)式函數(shù)poly(N)，只要成長函數(shù)有Break Point存在，那么該成長函數(shù)就是一個(gè)多項(xiàng)式。

VC Bound

這里給出VC bound的結(jié)論

這個(gè)結(jié)論通俗來講就是，數(shù)據(jù)夠多的時(shí)候，機(jī)器學(xué)習(xí)算法真的可以學(xué)到有用的知識(shí)。

小結(jié)

上面我們可以知道,要學(xué)到有用的東西需要下面幾個(gè)條件：

好的假設(shè)空間，即mH(N)存在Break Point

好的數(shù)據(jù)，即數(shù)據(jù)足夠多，使得訓(xùn)練誤差和真實(shí)誤差很接近

好的算法，即算法可以選出一個(gè)訓(xùn)練誤差很小的假設(shè)

好的運(yùn)氣，因?yàn)橹罢f明的是一個(gè)概率問題，所以要有一點(diǎn)點(diǎn)運(yùn)氣，惡劣的情況才不會(huì)發(fā)生

VC維

定義

定義在輸入空間X上的假設(shè)空間H的VC維，是可被H打散的X的最大有限子集的大小(數(shù)據(jù)量的大小)。如果X的任意有限大的子集可被H打散，則VC(H)為無窮大。

結(jié)合上面的介紹，我們知道VC維和Break Point的關(guān)系是：VC維=‘minimum k’- 1。通俗一點(diǎn)，比VC維大就是Break Point。

終于，我們可以得出結(jié)論，VC維是有限的假設(shè)就是好的假設(shè)。

VC維和學(xué)習(xí)的關(guān)系

VC維和具體的學(xué)習(xí)算法A沒有關(guān)系

VC維和輸入數(shù)據(jù)的概率分布P沒有關(guān)系

VC維和目標(biāo)函數(shù)f沒有關(guān)系

VC維與模型復(fù)雜度、樣本復(fù)雜度

VC維的物理意義

如果我們將假設(shè)集合的數(shù)量|H|比作假設(shè)集合的自由度，那么VC維就是假設(shè)集合在做二元分類的有效的自由度，即這個(gè)假設(shè)空間能夠產(chǎn)生多少Dichotomies的能力(VC維說的是，到什么時(shí)候，假設(shè)集合還能shatter，還能產(chǎn)生最多的Dichotomies)。

VC維、真實(shí)錯(cuò)誤率、訓(xùn)練錯(cuò)誤率

在上一節(jié)中，我們討論要做到好的預(yù)測要滿足兩個(gè)條件，第一是訓(xùn)練誤差要接近真實(shí)誤差，即Ein(g)約等于Eout(g);第二是訓(xùn)練誤差要盡量接近0，即Ein(g)約等于0。

現(xiàn)在，我們用VC維這個(gè)工具來描述。

如果VC維很小，那么發(fā)生預(yù)測偏差很大的壞事情的可能性也就很小，那這有利于Ein(g)接近Eout(g);但是，這是我們的假設(shè)空間的表達(dá)能力受到了限制，這樣Ein(g)可能就沒有辦法做到很小。

如果VC維很大，那么假設(shè)空間的表達(dá)能力很強(qiáng)，我們很有可能選到一個(gè)Ein(g)很小的假設(shè)，但是Ein(g)和Eout(g)之差很大的壞事情發(fā)生的情況發(fā)生的可能性就變得很大，這樣Ein(g)和Eout(g)根本不接近，我們就無法確定選擇的假設(shè)在測試數(shù)據(jù)的時(shí)候表現(xiàn)的很好。

這時(shí)，VC維變成了我們一個(gè)重要的選擇，我們可以用VC維提供的信息來選擇更好的模型和假設(shè)空間。

模型復(fù)雜度（Model Complexity）

我們可以根據(jù)VC Bound公式，設(shè)發(fā)生壞事情的概率是δ，將其恒等變換可以得到訓(xùn)練誤差和測試誤差的差別ε。所以反過來講，好事情(訓(xùn)練誤差和測試誤差的差別小于ε)發(fā)生時(shí)，Eout(g)被限制在一個(gè)范圍內(nèi)。這里根號(hào)內(nèi)的式子定義為Ω(N,Η,δ)，稱作模型復(fù)雜度,這個(gè)參數(shù)描述的意義是，我們的假設(shè)空間H有多么的強(qiáng)，使得我們的算法在泛化能力上需要付出多少代價(jià)。通俗的來講，假設(shè)空間的容量越大，VC維越大，那么模型就越難學(xué)習(xí)。

VC維傳遞的信息

如下圖所示，我們可以看出隨VC維變化，Ein、Eout、模型復(fù)雜度都是如何變化的。

這里一個(gè)很直接的信息就是模型復(fù)雜度隨著VC維的變大不斷變大，呈正相關(guān)趨勢。

因?yàn)閂C維變大時(shí)，數(shù)據(jù)中可以shatter的點(diǎn)就變多了，那么假設(shè)空間的容量就變大了，如果是一個(gè)合理的學(xué)習(xí)算法的話，就有機(jī)會(huì)找到一個(gè)更好的假設(shè)，使得Ein更小。

而Eout呢?在一開始的時(shí)候，Eout隨著Ein的下降也下降，但是到某個(gè)點(diǎn)，因?yàn)槲覀円冻龅拇鷥r(jià)變大了，Eout開始上升，所以最好的Eout是在中間的某個(gè)位置。

這里得到一個(gè)重要的結(jié)論，VC維越大或者假設(shè)空間能力越強(qiáng)大，雖然可以使得訓(xùn)練誤差很小，但不見得是最好的選擇，因?yàn)橐獮槟Ｐ蛷?fù)雜度付出代價(jià)。

樣本復(fù)雜度（Sample Complexity）

根據(jù)理論而言，樣本復(fù)雜度大約是VC維的10000倍，而實(shí)際應(yīng)用中，只需要VC維的10倍的量就夠了。

我們這里介紹的VC Bound的條件是非常寬松的，這使得在樣本復(fù)雜度的估計(jì)上可以和理論值相差很大，原因如下：

我們利用Hoeffding對(duì)任何的分布和任何的目標(biāo)函數(shù)來推測真實(shí)的錯(cuò)誤率

我們利用成長函數(shù)mH(N)來代替假設(shè)集合的數(shù)量，確?？梢允褂萌魏螖?shù)據(jù)

用VC維表示的多項(xiàng)式來代替成長函數(shù)，使得我們只通過VC維就可以了解某個(gè)假設(shè)空間的性質(zhì)

使用union bound來避免最差的狀況

以上有關(guān)VC Bound傳遞的哲學(xué)信息可以很好的指導(dǎo)我們進(jìn)行機(jī)器學(xué)習(xí)算法的實(shí)踐。

參考資料

機(jī)器學(xué)習(xí)技法課程，林軒田，臺(tái)灣大學(xué)

轉(zhuǎn)載請(qǐng)注明作者Jason Ding及其出處

GitCafe博客主頁(http://jasonding1354.gitcafe.io/)

生成海報(bào)

免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請(qǐng)進(jìn)一步核實(shí)，并對(duì)任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對(duì)有關(guān)資料所引致的錯(cuò)誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個(gè)人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識(shí)產(chǎn)權(quán)或存在不實(shí)內(nèi)容時(shí)，應(yīng)及時(shí)向本網(wǎng)站提出書面權(quán)利通知或不實(shí)情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后，將會(huì)依法盡快聯(lián)系相關(guān)文章源頭核實(shí)，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。