上一節課，我們主要探讨了當M的數值大小對機器學習的影響。如果M很大，那麼就不能保證機器學習有很好的泛化能力，是以問題轉換為驗證M有限，即最好是按照多項式成長。然後通過引入了成長函數m_H(N)和dichotomy以及break point的概念，提出2D perceptrons的成長函數m_H(N)是多項式級别的猜想。這就是本節課将要深入探讨和證明的内容。
我們先回顧一下上節課的内容，四種成長函數與break point的關系：
下面引入一個例子，如果k=2，那麼當N取不同值的時候，計算其成長函數m_H(N)是多少。很明顯，當N=1時，m_H(N)=2,；當N=2時，由break point為2可知，任意兩點都不能被shattered（shatter的意思是對N個點，能夠分解為2^N種dichotomies）；m_H(N)最大值隻能是3；當N=3時，簡單繪圖分析可得其m_H(N)=4，即最多隻有4種dichotomies。
是以，我們發現當N>k時，break point限制了m_H(N)值的大小，也就是說影響成長函數m_H(N)的因素主要有兩個：
抽樣資料集N
break point k（這個變量确定了假設的類型）
那麼，如果給定N和k，能夠證明其m_H(N)的最大值的上界是多項式的，則根據霍夫丁不等式，就能用m_H(N)代替M，得到機器學習是可行的。是以，證明m_H(N)的上界是poly(N)，是我們的目标。
現在，我們引入一個新的函數：bounding function，B(N,k)。Bound Function指的是當break point為k的時候，成長函數m_H(N)可能的最大值。也就是說B(N,k)是m_H(N)的上界，對應m_H(N)最多有多少種dichotomy。那麼，我們新的目标就是證明： B(N,k)\leq poly(N)
這裡值得一提的是，B(N,k)的引入不考慮是1D postive intrervals問題還是2D perceptrons問題，而隻關心成長函數的上界是多少，進而簡化了問題的複雜度。
求解B(N,k)的過程十分巧妙：
當k=1時，B(N,1)恒為1。
當N < k時，根據break point的定義，很容易得到B(N,k)=2^N。
當N = k時，此時N是第一次出現不能被shatter的值，是以最多隻能有2^N-1個dichotomies，則B(N,k)=2^N-1。
到此，bounding function的表格已經填了一半了，對于最常見的N>k的情況比較複雜，推導過程下一小節再詳細介紹。
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) = 2\alpha + \beta，這個是直接轉化。緊接着，由定義，B(4,3)是不能允許任意三點shatter的，是以由α和β構成的所有三點組合也不能shatter（alpha經過去重），即\alpha + \beta\leq B(3,3)。
另一方面，由于α中x4是成對存在的，且α是不能被任意三點shatter的，則能推導出α是不能被任意兩點shatter的。這是因為，如果α不能被任意兩點shatter，而x4又是成對存在的，那麼x1、x2、x3、x4組成的α必然能被三個點shatter。這就違背了條件的設定。這個地方的推導非常巧妙，也解釋了為什麼會這樣分組。此處得到的結論是\\alpha \leq B(3,2)
由此得出B(4,3)與B(3,x)的關系為：
最後，推導出一般公式為：
根據推導公式，下表給出B(N,K)值
根據遞推公式，推導出B(N,K)滿足下列不等式：
上述不等式的右邊是最高階為k-1的N多項式，也就是說成長函數m_H(N)的上界B(N,K)的上界滿足多項式分布poly(N)，這就是我們想要得到的結果。
得到了m_H(N)的上界B(N,K)的上界滿足多項式分布poly(N)後，我們回過頭來看看之前介紹的幾種類型它們的m_H(N)與break point的關系：
我們得到的結論是，對于2D perceptrons，break point為k=4，m_H(N)的上界是N^{k-1}。推廣一下，也就是說，如果能找到一個模型的break point，且是有限大的，那麼就能推斷出其成長函數m_H(N)有界。
我們已經知道了成長函數的上界是poly(N)的，下一步，如果能将m_H(N)代替M，代入到Hoffding不等式中，就能得到E_{out}\approx E_{in}的結論：
實際上并不是簡單的替換就可以了，正确的表達式為：
該推導的證明比較複雜，我們可以簡單概括為三個步驟來證明：
這部分内容，我也隻能聽個大概内容，對具體的證明過程有興趣的童鞋可以自行研究一下，研究的結果記得告訴一下我哦。
最終，我們通過引入成長函數m_H，得到了一個新的不等式，稱為Vapnik-Chervonenkis(VC) bound：
對于2D perceptrons，它的break point是4，那麼成長函數m_H(N)=O(N^3)。是以，我們可以說2D perceptrons是可以進行機器學習的，隻要找到hypothesis能讓E_{in}\approx0，就能保證E_{in}\approx E_{out}。
本節課我們主要介紹了隻要存在break point，那麼其成長函數m_H(N)就滿足poly(N)。推導過程是先引入m_H(N)的上界B(N,k)，B(N,k)的上界是N的k-1階多項式，進而得到m_H(N)的上界就是N的k-1階多項式。然後，我們通過簡單的三步證明，将m_H(N)代入了Hoffding不等式中，推導出了Vapnik-Chervonenkis(VC) bound，最終證明了隻要break point存在，那麼機器學習就是可行的。
注明：
文章中所有的圖檔均來自中國台灣大學林軒田《機器學習基石》課程。