洞見|機器為什么可以學習？

文|機器2025

PAC學習模型

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

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

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

1、理解這些問題有助于理解為什么機器可以學習，增強學習具體算法的信心，有助于深入進去;

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

舉例

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

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

可能近似正確（probably approximately correct，PAC）學習模型

問題框架

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

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

學習器在學習目標函數(shù)時考慮可能假設(shè)的集合H。

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

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

錯誤率

為了描述學習器輸出的假設(shè)h對真實目標函數(shù)f的逼近程度，我們要定義兩種錯誤率：

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

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

具體定義如下：

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

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

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

PAC可學習性(PAC Learnability)

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

機器學習的現(xiàn)實情況：

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

2、訓練樣本是隨機選取的，訓練樣本總有一定的誤導性

為此，我們要弱化對學習器的要求：

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

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

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

一個可PAC學習的學習器要滿足兩個條件：

學習器必須以任意高的概率輸出一個錯誤率任意低的假設(shè)

學習過程的時間最多以多項式方式增長

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

Hoeffding不等式

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

PAC可學習性很大程度上由所需的訓練樣本數(shù)量決定。隨著問題規(guī)模的增長所帶來的所需訓練樣本的增長稱為學習問題的樣本復(fù)雜度(sample complexity)。在多數(shù)實際問題中，最限制學習器成功的因素是有限的可用的訓練數(shù)據(jù)。

我們通常都喜歡能與訓練數(shù)據(jù)擬合程度更高的假設(shè)，當一個學習器在可能時都輸出能完美擬合訓練數(shù)據(jù)的假設(shè)時，我們稱該學習器是一致的(consistent)。這就要求訓練錯誤率是0。

遺憾的是，如果假設(shè)空間里不總是能找到一個零錯誤率的假設(shè)，這時，最多能要求學習器輸出的假設(shè)在訓練數(shù)據(jù)上有最小的錯誤率。

在更一般的情形下，我們要考慮學習器有非零訓練錯誤率的假設(shè)時，仍能找到一個邊界來限定學習器所需的樣本數(shù)量。

Hoeffding邊界

描述問題

現(xiàn)在，我們來更準確的描述我們要解決的問題。

令D代表學習器可觀察的特定的訓練數(shù)據(jù)集合，而P代表整個數(shù)據(jù)集合背后滿足的概率分布。令Ein(h)代表假設(shè)h的訓練錯誤率(在機器學習基石課程中，該錯誤率被稱為in-sample error)，確切的說，Ein(h)是數(shù)據(jù)集D中被h誤分類的訓練數(shù)據(jù)所占比例，Ein(h)是定義在訓練數(shù)據(jù)集D上的，而真實錯誤率Eout(h)(out-of-sample error)是定義在整個概率分布P上的。現(xiàn)在令g代表H中有最小訓練錯誤率的假設(shè)。問：多少訓練數(shù)據(jù)才足以保證真實錯誤率Eout(h)和訓練錯誤率Ein(h)很接近，并且接近0。

Hoeffding不等式

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

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

確認（verification）流程

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

這里因為只有一個hypothesis在手上，所以我們還不能做選擇，但是我們可以給它一些verifying examples來讓它做確認，看看h的表現(xiàn)如何，正如上圖流程所示。

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

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

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

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

Bad Sample and Bad Data

壞的樣本就是訓練錯誤率Ein=0，而真實錯誤率Eout=1/2的情況。

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

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

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

上圖說明：

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

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

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

Bound of BAD Data

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

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

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

統(tǒng)計學習流程

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

VC理論

面臨待解決的問題

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

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

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

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

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

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

Dichotomy，一分為二的劃分

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

成長函數(shù)Growth Function

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

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

shatter

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

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

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

Break Point of H

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

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

Bounding Function

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

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

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

VC Bound

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

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

小結(jié)

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

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

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

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

好的運氣，因為之前說明的是一個概率問題，所以要有一點點運氣，惡劣的情況才不會發(fā)生

VC維

定義

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

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

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

VC維和學習的關(guān)系

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

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

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

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

VC維的物理意義

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

VC維、真實錯誤率、訓練錯誤率

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

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

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

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

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

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

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

VC維傳遞的信息

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

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

因為VC維變大時，數(shù)據(jù)中可以shatter的點就變多了，那么假設(shè)空間的容量就變大了，如果是一個合理的學習算法的話，就有機會找到一個更好的假設(shè)，使得Ein更小。

而Eout呢?在一開始的時候，Eout隨著Ein的下降也下降，但是到某個點，因為我們要付出的代價變大了，Eout開始上升，所以最好的Eout是在中間的某個位置。

這里得到一個重要的結(jié)論，VC維越大或者假設(shè)空間能力越強大，雖然可以使得訓練誤差很小，但不見得是最好的選擇，因為要為模型復(fù)雜度付出代價。

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

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

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

我們利用Hoeffding對任何的分布和任何的目標函數(shù)來推測真實的錯誤率

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

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

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

以上有關(guān)VC Bound傳遞的哲學信息可以很好的指導我們進行機器學習算法的實踐。

參考資料

機器學習技法課程，林軒田，臺灣大學

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

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

生成海報

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