# 6 -- Theory of Generalization
上一節課,我們主要探討了當M的數值大小對機器學習的影響。如果M很大,那么就不能保證機器學習有很好的泛化能力,所以問題轉換為驗證M有限,即最好是按照多項式成長。然后通過引入了成長函數和dichotomy以及break point的概念,提出2D perceptrons的成長函數是多項式級別的猜想。這就是本節課將要深入探討和證明的內容。
### **一、Restriction of Break Point**
我們先回顧一下上節課的內容,四種成長函數與break point的關系:

下面引入一個例子,如果k=2,那么當N取不同值的時候,計算其成長函數是多少。很明顯,當N=1時,=2,;當N=2時,由break point為2可知,任意兩點都不能被shattered(shatter的意思是對N個點,能夠分解為種dichotomies);最大值只能是3;當N=3時,簡單繪圖分析可得其,即最多只有4種dichotomies。

所以,我們發現當N>k時,break point限制了值的大小,也就是說影響成長函數的因素主要有兩個:
* 抽樣數據集N
* break point k(這個變量確定了假設的類型)
那么,如果給定N和k,能夠證明其的最大值的上界是多項式的,則根據霍夫丁不等式,就能用代替M,得到機器學習是可行的。所以,證明的上界是poly(N),是我們的目標。

### **二、Bounding Function: Basic Cases**
現在,我們引入一個新的函數:bounding function,B(N,k)。Bound Function指的是當break point為k的時候,成長函數可能的最大值。也就是說B(N,k)是的上界,對應最多有多少種dichotomy。那么,我們新的目標就是證明:
這里值得一提的是,B(N,k)的引入不考慮是1D postive intrervals問題還是2D perceptrons問題,而只關心成長函數的上界是多少,從而簡化了問題的復雜度。

求解B(N,k)的過程十分巧妙:
* 當k=1時,B(N,1)恒為1。
* 當N < k時,根據break point的定義,很容易得到。
* 當N = k時,此時N是第一次出現不能被shatter的值,所以最多只能有個dichotomies,則。

到此,bounding function的表格已經填了一半了,對于最常見的N>k的情況比較復雜,推導過程下一小節再詳細介紹。
### **三、Bounding Function: Inductive Cases**
N > k的情況較為復雜,下面給出推導過程:
以B(4,3)為例,首先想著能否構建B(4,3)與B(3,x)之間的關系。
首先,把B(4,3)所有情況寫下來,共有11組。也就是說再加一種dichotomy,任意三點都能被shattered,11是極限。

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

將Orange去掉x4后去重得到4個不同的vector并成為,相應的purple為。那么,這個是直接轉化。緊接著,由定義,B(4,3)是不能允許任意三點shatter的,所以由和構成的所有三點組合也不能shatter(alpha經過去重),即。

另一方面,由于中x4是成對存在的,且是不能被任意三點shatter的,則能推導出是不能被任意兩點shatter的。這是因為,如果是不能被任意兩點shatter,而x4又是成對存在的,那么x1、x2、x3、x4組成的必然能被三個點shatter。這就違背了條件的設定。這個地方的推導非常巧妙,也解釋了為什么會這樣分組。此處得到的結論是

由此得出B(4,3)與B(3,x)的關系為:

最后,推導出一般公式為:

根據推導公式,下表給出B(N,K)值

根據遞推公式,推導出B(N,K)滿足下列不等式:

上述不等式的右邊是最高階為k-1的N多項式,也就是說成長函數的上界B(N,K)的上界滿足多項式分布poly(N),這就是我們想要得到的結果。
得到了的上界B(N,K)的上界滿足多項式分布poly(N)后,我們回過頭來看看之前介紹的幾種類型它們的與break point的關系:

我們得到的結論是,對于2D perceptrons,break point為k=4,的上界是。推廣一下,也就是說,如果能找到一個模型的break point,且是有限大的,那么就能推斷出其成長函數有界。
### **四、A Pictorial Proof**
我們已經知道了成長函數的上界是poly(N)的,下一步,如果能將代替M,代入到Hoffding不等式中,就能得到的結論:

實際上并不是簡單的替換就可以了,正確的表達式為:

該推導的證明比較復雜,我們可以簡單概括為三個步驟來證明:



這部分內容,我也只能聽個大概內容,對具體的證明過程有興趣的童鞋可以自行研究一下,研究的結果記得告訴一下我哦。
最終,我們通過引入成長函數,得到了一個新的不等式,稱為Vapnik-Chervonenkis(VC) bound:

對于2D perceptrons,它的break point是4,那么成長函數。所以,我們可以說2D perceptrons是可以進行機器學習的,只要找到hypothesis能讓,就能保證。
### **五、總結**
本節課我們主要介紹了只要存在break point,那么其成長函數就滿足poly(N)。推導過程是先引入的上界B(N,k),B(N,k)的上界是N的k-1階多項式,從而得到的上界就是N的k-1階多項式。然后,我們通過簡單的三步證明,將代入了Hoffding不等式中,推導出了Vapnik-Chervonenkis(VC) bound,最終證明了只要break point存在,那么機器學習就是可行的。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程。
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale