前面講到M如果會變成無限大，就無法滿足能夠學習的理論，所以我們希望能透過成長函式mH(N)來取代M，這一講主要在推論mH(N)是不是真的成長的比較慢，且能夠夠取代掉M
複習一下成長函數的定義是指Hyperthesis集合在N個點上最多能夠產生多少個Dichotomies(即O或是X兩分的排列組合)。上一講提到了四種成長函數，且每一種都可能有出現break point現象，就是指當輸入點數大於某個臨界值後，會產生沒有辦法滿足的Dicotomies組合。
假設今天有一個Hyperthesis在N為1時mH(N)為2種，N為2時mH(N)最多只有3種(3 < 2^2)，那麼我們要找在3點輸入時，而且最小的break point K為2(即任2點不能有shatter)，究竟mH(N)為多少呢？可以發現加上第5種組合，無論前面4種用什麼組合，在第5種任2點都會shatter，所以最多只會有4種可能
到這邊可以發現當N越大時，break point K會對最大可能的mH(N)產生限制(因為K為break point，K+1開始都會shatter)，使得當N越大時，N和mH(N)之間的差距會越來越大。所以如果可以證明mH(N)是一個多項式，就可以在原本的Hoeffiding不等式中，把可能無限大的M取代成有限制且為多項式的mH(N)，使得學習是有可能的。
再來先別管成長函式了，我們透過bounding function來表示在break point為K的情況下，mH(N)的最大可能性，就是在K個點不能出現shatter。這樣我們就可以不用管問題是屬於positive intervals或是1D perceptrons要用不同的方法分析，我們可以統一使用B(N, 3)來表代所有不同的問題。
N和K建立的bounding function可以用表格來呈現，基本上可以分成4種。第一種是如果K為1，即B(N, 1)代表1個點不能出現shatter，那麼只會有1種情況；第二種是右上斜角部份，今天如果K大於N，那麼K等於沒有限制，所以最多會有2^N種情況；第三種是在斜角上，當N和k的值一樣時，因為不能是2^N種，所以減1最多會有2^N-1種。
那麼最重要的斜角下方部份該怎麼填了，假設要填的值是B(4, 3)，我們猜測他可能和前一排的B(3, ?)有關係。這裡可以看到所有的組合總共是11種，看起來B(4, 3)好像是B(3, 3)和B(3, 2)相加，但是該怎麼去證明說是有關係的呢？
把B(4, 3)的11種解可以分成α和β兩種類型，橘色的類型為X1-X3相同，但是X4會不一樣(即2α)，紫色的類型為皆不相同(即β)。B(4, 3)指其中3個點不能shatter，那X1-X3也是其中的3個點，所以也不能shatter，意思就是說如果今天不看X4的話，因為X1-X3不能shatter，所以α加β會小於等於B(3, 3)。
再繼續往下只看α部份的話，如果X1-X3其中有2個點shatter了，那麼再加上X4的話就會造成3點shatter，這也是B(4, 3)不允許的，所以X1-X3其中2個點也不能shatter。於是α會小於等於B(3, 2)
再來就可以把中間證明的過程連結在一起了，B(4, 3) ≤ B(3, 3) + B(3, 2)，又可以轉變成B(N, K) ≤ B(N-1, K) + B(N-1, K-1)，這樣就可以把斜角下方都值都可以填上一個上限值。我們最早從會有無限多組解的大M開始，再到其實大M是有限的，透過成長函數可找到dichotomy數量mH(N)，再推展到上限函式B(K, N)來統一計算N和K的上限值(不用依不同的情況計算mH(N))，最後證明到這裡的值其實就是上限的上限值(很繞口)。
所以推展到這邊可以得到的重點是，mH(N)會被上限函式bounded住，然後這個上限函式又會被上限的上限bounded住，而且這個上限的上限是一個多項式；因此只要確保有出現break point，就可以說mH(N)是個多項式。
再來回到原本的帶有union bound的Hoeffding不等式，我們經過上面的推導後，是不是可以把這個成長函式mH(N)丟進Hoeffding裡面，就可以了呢？再來會開始推導成投影片中的新的式子，是一個長的差不多的式子，他可以證明在N夠大的情況下，就可以根據Hoeffding不等式來說學習是可以達成的。
第一步遇到的問題是Eout會是無限多的值，所以會先把Eout取代成有限的Ein’，這裡的概念是如果Ein和Eout差距很大時(即壞事發生時)，那麼有很大的機會(>1/2)，Ein和Ein’也隔的很遠。
接著第一步的結果，因為多了Ein’所以會多了N個樣本，所以成長函式裡面的N會變成2N。第二步會把Union Bounded中發生各種壞事的情況，找到共同發生的部份，所以把前面說到有限組合的mH(N)代進式子中。
再來因為我們是有限多個值了，所以想像概念就像是現在瓶子裡面有2N個樣本，今天抽出N個樣本，我們就可以把這N個樣本和原本的2N個樣本作比較。這就像是用了一個比較小的瓶子和比較小的誤差，使用了抽後不放回的Hoeffding，他其實還是Hoeffding。
證明到這邊，可以簡單的證明出apnik-Chervonenkis (VC) bound了! 所以在break point為4的2D perceptrons中，如果N夠大的情況下，是真的可以透過PLA達到學習效果的。
總結來說，這一課證明了只要存在break point，就會對未來的成長函數加上很大的限制，因為有了break poin也才能證明mH(N)會被一個多項式的上限函式bounded住，並且mH(N)可以取代Hoeffding原本是無限多的大M