紅色石頭的個(gè)人網(wǎng)站：redstonewill.com

上一節(jié)課，我們主要探討了當(dāng)M的數(shù)值大小對機(jī)器學(xué)習(xí)的影響。如果M很大，那么就不能保證機(jī)器學(xué)習(xí)有很好的泛化能力，所以問題轉(zhuǎn)換為驗(yàn)證M有限，即最好是按照多項(xiàng)式成長。然后通過引入了成長函數(shù)mH(N)mH(N)和dichotomy以及break point的概念，提出2D perceptrons的成長函數(shù)mH(N)mH(N)是多項(xiàng)式級別的猜想。這就是本節(jié)課將要深入探討和證明的內(nèi)容。

一、Restriction of Break Point

我們先回顧一下上節(jié)課的內(nèi)容，四種成長函數(shù)與break point的關(guān)系：

下面引入一個(gè)例子，如果k=2，那么當(dāng)N取不同值的時(shí)候，計(jì)算其成長函數(shù)mH(N)mH(N)是多少。很明顯，當(dāng)N=1時(shí)，mH(N)mH(N)=2,；當(dāng)N=2時(shí)，由break point為2可知，任意兩點(diǎn)都不能被shattered（shatter的意思是對N個(gè)點(diǎn)，能夠分解為2N2N種dichotomies）；mH(N)mH(N)最大值只能是3；當(dāng)N=3時(shí)，簡單繪圖分析可得其mH(N)=4mH(N)=4，即最多只有4種dichotomies。

所以，我們發(fā)現(xiàn)當(dāng)N>k時(shí)，break point限制了mH(N)mH(N)值的大小，也就是說影響成長函數(shù)mH(N)mH(N)的因素主要有兩個(gè)：

• 抽樣數(shù)據(jù)集N

• break point k（這個(gè)變量確定了假設(shè)的類型）

那么，如果給定N和k，能夠證明其mH(N)mH(N)的最大值的上界是多項(xiàng)式的，則根據(jù)霍夫丁不等式，就能用mH(N)mH(N)代替M，得到機(jī)器學(xué)習(xí)是可行的。所以，證明mH(N)mH(N)的上界是poly(N)，是我們的目標(biāo)。

二、Bounding Function: Basic Cases

現(xiàn)在，我們引入一個(gè)新的函數(shù)：bounding function，B(N,k)。Bound Function指的是當(dāng)break point為k的時(shí)候，成長函數(shù)mH(N)mH(N)可能的最大值。也就是說B(N,k)是mH(N)mH(N)的上界，對應(yīng)mH(N)mH(N)最多有多少種dichotomy。那么，我們新的目標(biāo)就是證明：

B(N,k)≤poly(N)B(N,k)≤poly(N)

這里值得一提的是，B(N,k)的引入不考慮是1D postive intrervals問題還是2D perceptrons問題，而只關(guān)心成長函數(shù)的上界是多少，從而簡化了問題的復(fù)雜度。

求解B(N,k)的過程十分巧妙：

• 當(dāng)k=1時(shí)，B(N,1)恒為1。

• 當(dāng)N < k時(shí)，根據(jù)break point的定義，很容易得到B(N,k)=2NB(N,k)=2N。

• 當(dāng)N = k時(shí)，此時(shí)N是第一次出現(xiàn)不能被shatter的值，所以最多只能有2N?12N?1個(gè)dichotomies，則B(N,k)=2N?1B(N,k)=2N?1。

到此，bounding function的表格已經(jīng)填了一半了，對于最常見的N>k的情況比較復(fù)雜，推導(dǎo)過程下一小節(jié)再詳細(xì)介紹。

三、Bounding Function: Inductive Cases

N > k的情況較為復(fù)雜，下面給出推導(dǎo)過程：

以B(4,3)為例，首先想著能否構(gòu)建B(4,3)與B(3,x)之間的關(guān)系。

首先，把B(4,3)所有情況寫下來，共有11組。也就是說再加一種dichotomy，任意三點(diǎn)都能被shattered，11是極限。

對這11種dichotomy分組，目前分成兩組，分別是orange和purple，orange的特點(diǎn)是，x1,x2和x3是一致的，x4不同并成對，例如1和5，2和8等，purple則是單一的，x1,x2,x3都不同，如6,7,9三組。

將Orange去掉x4后去重得到4個(gè)不同的vector并成為αα，相應(yīng)的purple為ββ。那么B(4,3)=2α+βB(4,3)=2α+β，這個(gè)是直接轉(zhuǎn)化。緊接著，由定義，B(4,3)是不能允許任意三點(diǎn)shatter的，所以由αα和ββ構(gòu)成的所有三點(diǎn)組合也不能shatter（alpha經(jīng)過去重），即α+β≤B(3,3)α+β≤B(3,3)。

另一方面，由于αα中x4是成對存在的，且αα是不能被任意三點(diǎn)shatter的，則能推導(dǎo)出αα是不能被任意兩點(diǎn)shatter的。這是因?yàn)?#xff0c;如果αα是不能被任意兩點(diǎn)shatter，而x4又是成對存在的，那么x1、x2、x3、x4組成的αα必然能被三個(gè)點(diǎn)shatter。這就違背了條件的設(shè)定。這個(gè)地方的推導(dǎo)非常巧妙，也解釋了為什么會這樣分組。此處得到的結(jié)論是α≤B(3,2)α≤B(3,2)

由此得出B(4,3)與B(3,x)的關(guān)系為：

最后，推導(dǎo)出一般公式為：

根據(jù)推導(dǎo)公式，下表給出B(N,K)值

根據(jù)遞推公式，推導(dǎo)出B(N,K)滿足下列不等式：

上述不等式的右邊是最高階為k-1的N多項(xiàng)式，也就是說成長函數(shù)mH(N)mH(N)的上界B(N,K)的上界滿足多項(xiàng)式分布poly(N)，這就是我們想要得到的結(jié)果。

得到了mH(N)mH(N)的上界B(N,K)的上界滿足多項(xiàng)式分布poly(N)后，我們回過頭來看看之前介紹的幾種類型它們的mH(N)mH(N)與break point的關(guān)系：

我們得到的結(jié)論是，對于2D perceptrons，break point為k=4，mH(N)mH(N)的上界是Nk?1Nk?1。推廣一下，也就是說，如果能找到一個(gè)模型的break point，且是有限大的，那么就能推斷出其成長函數(shù)mH(N)mH(N)有界。

四、A Pictorial Proof

我們已經(jīng)知道了成長函數(shù)的上界是poly(N)的，下一步，如果能將mH(N)mH(N)代替M，代入到Hoffding不等式中，就能得到Eout≈EinEout≈Ein的結(jié)論：

實(shí)際上并不是簡單的替換就可以了，正確的表達(dá)式為：

該推導(dǎo)的證明比較復(fù)雜，我們可以簡單概括為三個(gè)步驟來證明：

這部分內(nèi)容，我也只能聽個(gè)大概內(nèi)容，對具體的證明過程有興趣的童鞋可以自行研究一下，研究的結(jié)果記得告訴一下我哦。

最終，我們通過引入成長函數(shù)mHmH，得到了一個(gè)新的不等式，稱為Vapnik-Chervonenkis(VC) bound：

對于2D perceptrons，它的break point是4，那么成長函數(shù)mH(N)=O(N3)mH(N)=O(N3)。所以，我們可以說2D perceptrons是可以進(jìn)行機(jī)器學(xué)習(xí)的，只要找到hypothesis能讓Ein≈0Ein≈0，就能保證Ein≈EoutEin≈Eout。

五、總結(jié)

本節(jié)課我們主要介紹了只要存在break point，那么其成長函數(shù)mH(N)mH(N)就滿足poly(N)。推導(dǎo)過程是先引入mH(N)mH(N)的上界B(N,k)，B(N,k)的上界是N的k-1階多項(xiàng)式，從而得到mH(N)mH(N)的上界就是N的k-1階多項(xiàng)式。然后，我們通過簡單的三步證明，將mH(N)mH(N)代入了Hoffding不等式中，推導(dǎo)出了Vapnik-Chervonenkis(VC) bound，最終證明了只要break point存在，那么機(jī)器學(xué)習(xí)就是可行的。

注明：

文章中所有的圖片均來自臺灣大學(xué)林軒田《機(jī)器學(xué)習(xí)基石》課程。

關(guān)注公眾號并輸入關(guān)鍵字“jspdf”獲得該筆記的pdf文件哦～

更多AI資源請關(guān)注公眾號：紅色石頭的機(jī)器學(xué)習(xí)之路（ID：redstonewill）

總結(jié)

以上是生活随笔為你收集整理的台湾大学林轩田机器学习基石课程学习笔记6 -- Theory of Generalization的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。