好,那所以我們現在 想要開始填這個表剩下的部分,那麼剩下的部分顯然是
更為困難一點,所以例如說,我們現在想象,我們要填B(4, 3)這個值 好了,OK,那B(4,
3)這個值我們可能可以從哪裡填起呢? 那我們其中一個想法是說B(4,
3)這個值搞不好跟 前一排的那個B(3,
?)的這些是有關係的,為什麼? 因為(4,3)的意思是什麼?四個點,OK,然後這個任何三個點不能shatter
那我往3那邊走的意思是什麼?是少一個點,OK,也就是說我把我的四個 點遮掉一個點,或者是我本來是三個點加上一個點,就變成四個點
好所以,也許這兩個之間會有關係,那這就是我們接下來要做的事情,我們想辦法要把B(4, 3)這一格
跟(3, ?)那邊建立一些聯繫。
好 那這是不太容易做,所以呢我們為了具體給大家看,我就做了一件事情,我說
哎呀,我是資訊系出身的,不然我來寫個小小的程式好了,我的小小程式會什麼?它 會搜尋所有種,各種不同的dichotomy,我要B(4,
3),所以這是 我有這個長度是4的vector,總共有16種,這些不同的vector,然後呢
我從這16種vector裡面去選各種不同的dichotomy set,然後看看有沒有違反
條件,什麼條件?任何三個不能夠shatter 好,所以我就去做了一番搜尋的動作,然後搜尋什麼?搜尋最大的
dichotomy set,因為我們這是我們在這個B這個函數,這上限函數裡面要算的事情
好所以我算了算后發現,哎呀,好可以長這個樣子 說,這11個dichotomy就是我的B(4,
3)的解 好,這是我寫一隻程式去算,大家先不要問我怎麼算出來的
反正我就寫一隻程式,程式跑2的16次方對它來說沒什麼,咚咚咚咚就算出來了
好,算出來以後,我們就可以,寫出來我們又多進了一格在我們原來表裡面說什麼? 說,B(4,
3)是11,首先可以填這一格 11是什麼?我們等下,再來再寫看看
好,那我們怎麼把11這個值跟前面那一排的那些
值建立連接,搞不好大家看看4跟7,大家想說4加7是11啊,可是這畢竟不是
只是小孩這個玩益智遊戲,我們如果要說11是4加7的話,我們好歹也要舉出一些理由來
好,要做這一件事情呢我們就做什麼?我們把剛才那一個 B(4,
3)的這個解,OK,我們把這個稱之為一個解 我們把這個解做一個整理,整理成什麼樣子呢?
好,大家看到我這邊用兩種顏色,一種是橘色的 一種是紫色的。
好,橘色的這些解 OK,我把這些解,這個左邊那些解做了一些排列組合
橘色的這些解有什麼特性呢?橘色的這些解都是放閃光的
這在台灣這邊我們通常講放閃光叫做成雙成對,什麼東西成雙成對? 我們如果看,OK,它例如說好,我這邊有
1跟5這兩個dichotomy,1跟5這兩個dichotomy呢,它的x1、 x2、
x3都是一模一樣的 但是x4呢成雙成對,什麼成雙成對?一個是圈圈,一個是叉叉
同樣的呢,2跟8這也是成雙成對,OK,前三個一樣的,後面一個是圈圈,一個是叉叉
好,所以我有四個成雙成對的,OK,這些四對放閃光的情侶在這邊
然後呢,還有三個什麼呢?還有三個形單影隻的 形單影隻什麼意思?好,它在,例如說6號這個,它有x1、
x2、 x3、 x4 有沒有1到3跟它相同,然後4不同的那個人?沒有,好所以6號我們說
他是孤孤單單一個人,7號我們說他是孤孤單單一個人,9號我們說他是孤孤單單一個人 好,所以我們把B(4,
3)的解分成兩個部分,成雙成對的部分,根據什麼成雙成對? 根據x4來看成雙成對的部分,還有這個
形單影隻的部分,我們用橘色跟紫色來做代表 分成這兩個部分有什麼好處呢?好,首先我們就說
好,B(4, 3)的數量是11啊,11就可以用這兩個部分加起來
好,前面橘色的部分,我們說橘色有幾個?我們說有2α個 那個2是成雙成對的意思,所以α是4,然後成雙成對,所以總共有8個
然後呢,紫色的部分,我們說它有β個,在這個例子裡面就是3個
那怎麼樣呢?如果我們把x4遮掉 只看x1、
x2、 x3的話 我們現在看看說,所以我們這樣有幾個dichotomy?我們有α
加上β那麼多個,因為那些成雙成對的都被算成1個了,OK,這個
沒有算兩個人,算成一個,那β它本來就形單影隻,所以β也是算
一個,所以我們總共這裡有α加β這麼多個dichotomy
這些dichotomy在什麼東西上面?在x1到x3上面 好,那我就要問大家了,我們之前說什麼?我們說B(4,
3)說的事情是任何的三個點 不能shatter,那任何的三個點包不包括x1到x3的三個點?包括
所以任何的三個點不能shatter,我這邊的dichotomy x1、
x2、 x3上面也不能shatter 不能shatter代表什麼?代表我今天
α加β,也就是說我現在產生出來的這個dichotomy的數量一定要比什麼東西小?
我有三個點,任何三個點不能shatter的,最多最多多少?最多最多B(3, 3)
好,所以我α加β是其中一種,可能比較小,不知道,有沒有真的
誰可以小於我們不知道,但是我們知道反正一定是小於 等於,絕對不會是大於等於。
好,所以這是一個例子,我們說什麼?我們把x4遮掉,遮掉以後
那些成雙成對的統統只算一個,那些形單影隻的本來就算一個,那這些數量加起來 要小於等於B(3,
3),也就是說我們第一次把B(4, 3)跟B(3,
3)往前一個地 做了一個連接,好,那我們再來看 如果我們今天把x4遮掉
不過同時我們把紫色的丟掉,或者我們只看橘色的部分,這樣是發生了什麼事呢?
橘色部分是什麼?大家記不記得,橘色部分是x4裡面已經成雙成對的
那這樣,如果我能夠在x1到x3 裡面找出兩個點,找出兩個人說,我把你們KO掉
那這兩個點跟x4配合起來就會發生什麼事?
就會發生這兩個點加x4三個點被KO掉,三個點被KO掉就是什麼?
發生了shatter,不對啊,你說我們之前說 這個條件就是三個點不能shatter,對啊,三個點不能shatter,所以在這裡
我們在x1到x3裡面,兩個點也不能shatter
對不對?如果兩個點shatter,x1到x3兩個點shatter,加上x4三個點s- hatter,我們就死定了
好,所以x1到x3,如果我只看橘色的部分,x4還是遮起來只看橘色的部分的話
任何兩個點是不能shatter的,所以橘色的部分的數量,橘色是多少?α,α要比 B(3,
2)還來得小。
三個點,任兩個點不能 shatter。
好所以整理起來,我們 說B(4, 3),我們剛才是什麼?B(4,
3)先列出來,它是兩個α加上β 我們說α加β這個要比某個東西小。
β,對不起,α 要比某個東西小,所以這樣推論起來,B(4,
3)要比兩個東西加起來小,哪兩個? B(3, 3)跟B(3, 2)。
好,如果 你用一樣的證明的話,你應該可以很容易地知道什麼?知道
我今天就把4換成N,3換成k一切的證明有沒有變?沒有變
這個好,做出一組解,唯一的差別可能就是,我不是真的叫
電腦跑出一組解,我是腦袋裡想象一組解,腦袋想象的這一組解一定要滿足什麼性質?
一定要滿足說,它有α部分有β部分,α加β要小於等於什麼?α要小於等於什麼?那所- 以加起來 會發生什麼事情。
好,也就是說我現在開始可以填
這個表了,開始可以填這個表了,但是,OK,不是真的填那個表那格是多少,而是 我可以填,這個表的上限是多少。
什麼叫上限是多少?好,我們剛才例如說,好,這一格
這一格是5,OK,然後5並不是它真正的值,至少我現在並不知道它是不是真正的值
但是我們知道我可以從這一個值跟這一個值,兩個值,1跟4兩個 值加起來,來說它的上限是多少。
又或者,好,我現在知道這個值是11,我現在知道這個值是15 我就可以知道,在(5, 4)的這一格的上限是26
好,所以我就可以一路填下來,這一路上限往下,那當然從兩個上限也可以繼續估計下一個上限 是多少。
好,所以我就可以把這個表一路填下來,只是在上面加上這個小於等於的符號而已
好,也就是說,我們做一些事情,我們說
我们從成長函數到上限函數,到上限的上限,我們現在會做的事情實際上是
上限的上限,也就是說我們一路往上限上去 好,有了這些以後,我們實際上可以證明一件有趣的事情
就是,我們的上限函數會被一個上限的上限,好這個上限的上限長這個樣子
它是summation,然後i從零跑到k-1,記得k是什麼
k是我們的那個Break point,露出一線曙光的地方,然後N取i這個組合的函數
好,我們在講這個東西可能可以怎麼證之前,我們先看看這是不是對我們來說是好消息
是因為,這個裡面的最高項是多少 這個裡面最高的那一項就是,N的k-1次方
如果給你一個成長函數,k已經確定了,例如說給你2D的perceptron,K是4,- 所以那它的這個
上限的上限最多最多長什麼樣子,就是N的三次方,這對我們來說是好消息
你說這東西怎麼證呢,這東西的證明方式實際上 就是你可以用,我們剛才已經給你那個表了,那個表有邊界傾斜
然後呢,我們剛才已經給你什麼,我們已經給你一個遞迴式,這個遞迴式可以讓你用數學歸納- 法做推論說
如果我小的情形成立,往大的那邊推的話這些情形也會成立,這是一個很簡單的數學歸納法
所以我們在這裡,並不詳細和大家講。
不過好消息,我們現在終於可以說什麼 成長函數會被上限函數bound住,上限函數會被上限的上限bound住
上限的上限會被什麼bound住,會被某個多項式bound住,這個多項式跟你的b- reak
point,跟你的 一線曙光的那個點有關,所以你只要你原來成長函數有那個一線曙光那個點,那你就不要怕,-
你最後最後一定 會是個多項式,好,這邊順道和大家提一下,這裡我們說起
小於等於說上限函數,然後有個上限的上限,這裡呢實際上最後我們
如果你認真去證的話,可以證明它是等於的,只是用到的證明技巧跟我們這邊講的不太一樣,- 如果你是對數學有興趣的人
歡迎你去試試看,挑戰一下,去證明一下實際上 這邊是等號並不只是小於等於而已,就是說你要證明另外一個方向
你要證明大於等於那個方向,好,所以我們來看看,我們有了這個
上限的上限,那有些什麼例子呢,我們說,好,我們檢查一下,我們之前說過positive ray
我們知道它的成長函數長什麼樣子,我們知道它的一線曙光的點在哪裡,在2那邊
所以,如果我們在橘色這裡,把這個上限函數列出來的話,上限函數是N+1
成長函數有沒有比N+1,有沒有比上限函數小,一個是N+1,一個是N+1,兩個實際-
是一樣大 所以這個小於等於是成立的,如果呢,今天是這個
positive interval,就可以說我們也有它的成長函數,我们说它的成長函數是這個N的平方的-
這個式子 那我們說,它的一線曙光的那個點在3,如果我們把上限的上限列出來的話,上限的上限長-
這個樣子 兩個成長函數我們比較一下,其實兩個一樣大,其實兩個是一樣大,所以這個不等式也是
成立的,那對我們最重要的不是這些,這些的成長函數我們都列了出來,所以對我們來說不是- 太重要,對我們重要的是哪一個
我們目前還寫不出成長函數的那個2D的perceptron,我們不知道
但是我們知道,它第一個一線曙光點在哪裡,在4,所以 我們寫的出來,它的上限的上限最多是多少
ok,但是我們目前實際上還不是完全清楚,它的成長函數是多少
好,也就是說,只要你的mH
多複雜沒有關係,但是只要你找得到一個一線曙光的點
那用我们這裡講的東西,你就可以去做上限的上限,然後說整個成長函數最多最多
就會長的跟多項式是一樣快 好,所以呢我們這邊再給大家一個簡單的練習
說,如果我們現在想的事情是1D的perceptron,大家記得是positive跟- negative的ray
那我們上次已經算過了,它的成長函數是2N 那也就是說,那如果你看看說它的break
point在哪裡的話,你可以 看看說下面哪件事情的性質是不對的
好我們希望大家看看以後呢,能夠發現說,不對的那個性質呢
是3號的性質,也就是說實際上它的成長函數跟我們剛才那個上限的上限
並沒有相等,它是真的是小於的關係 並沒有這個等號的這個發生