0:00
好,所以接下來,我們來看看我們剛才已經知道說,我們如果用 線的話,那麼在平面上到底有幾種不一樣的線
那我們現在,如果以後我們要用線以外的hypothesis set 例如說,我們可能是hyperplane,可能是高維度的
可能是曲線等等的,我們要怎麼樣來說到底有幾種hypotheses這件事呢 好,我們就來看看說,我們就想象我們現在有一個hypothesis
set,這個hypothesis set 把我們的X的輸入空間變成圈跟叉兩種
情形,那我們說,我們這個幾種是怎麼來的,我們從若干個點,我們先想像說如果我們有N- 個點的話
X1,X2一直到XN,這N個點看過去到底產生了
幾種可能性,幾種什麼可能性,幾種圈圈叉叉的這些組合
那我們把這些組合叫做一個dichotomy,dichotomy這個字的意思是二分的- 意思,所以它把我們手上的點
分成兩堆,圈圈的一堆,叉叉的一堆,那我們想看的事情是一個hypothesis OK,一個hypothesis
set到底可以做出多少種不一樣的dichotomy來 好,所以呢,我們就用這樣的符號,我們說我們把大大的hypothesis
set用在這N個點上 用在這N個點上以後,誒就會產生,好例如說,我如果用了某一條線,它可能全部的都預-
測是圈圈 如果用的某一條線可能前三個是圈圈後面是叉叉,那這就是產生出來的dichotomy,-
我們把這些dichotomy放在一個 集合裡面,這個集合我們還是用H,但是在這個H的後面加上X1,X2......一-
直到XN 好來代表說,我們現在看的事情是個dichotomy,而不是原來的hypothesis
set 好,所以比較一下dichotomy和hypothesis set有什麼不一樣,其實
兩個非常的像,hypothesis set,OK例如說,可能是
平面上所有的直線,那它可以每個hypothesis對 我們的輸入空間X裡面所有的點取值
那dicotomy呢,則是只對N個特定的點來做取值的動作,例如說,我今天
如果有四個的話,我會得到一個長度是四的vector,裡面是圈圈或者是叉叉,這是di- chotomy
那大小上來說呢,hypothesis set,例如說如果我們全部是線的話,可能有無限多條
那dichotomy呢,dichotomy代表是有幾種不一樣的這個 組合,所以這幾種,最多最多是多少,最多最多就是
2的N次方那麼多種,因為我有N個點,每個點最多有兩種可能性 所以最多是2的N次方那麼多種。
好,那我們接下來會用dichotomy 或嚴格的來說是dichotomy的大小,OK我們有幾、
幾dichotomy set的大小,我們有幾個不一樣的dichotomy 來想辦法說,誒我們能不能用這個把我們原來Hoeffding裡面
那個讓我們覺得很困擾的大M,可能是無限大的那個大M,把它換掉 好,那在我們用這個dichotomy
set的大小 來衡量來取代這個大M的之前,有一個小小的麻煩是這樣
大家會看到說,我們的dichotomy set其實取決於 我們先選好的X1,X2一直到XN
那這樣先選好這件事情呢,對我們未來的理論分析會有一點點小的 麻煩,所以我們想要移除掉這個對X的依賴
那我們怎麼做呢,我們就說,好吧,我們既然是要算有幾種,我們就算最多有幾種好了,也- 就是什麼
好,我們一樣選一把X,X1,X2一直到XN 算算它dichotomy set的大小是多少,再選另外一把,算算它dichotomy
set的大小是多少 好,所以我有各式各樣不同的X的可能性,然後我選說最大的dichotomy
set的大小 這個當作我衡量的依據,那我們把這個數字取一個名字叫做mH,OK,小m然後
H,小m的意思是我們將來要用來取代大M,它是一個比大M 可能會小的數字,大M是多少,大M搞不好是無限大
那小m是一個可能比較小的數字,然後H代表它和我們的hypothesis set有關,它是hypothesis
set的一個性質 那這其實是一個函數,什麼東西的函數,N的函數,N是什麼,N是我們的輸入我們的點的個數
所以,例如說我們之前在直線的情形的時候,如果今天是一個點的話,誒我們說有兩種可能d- ichotomy
兩個點有四種可能,三個點我們說有時候誒有六種,有時候有八種,有時候搞不好更少,那最- 多最多多少,最多八種
那四個點,我們上次是說誒最多最多就是14種,OK所以呢,我們之前在percep- tron
2D的perceptron的時候,列出來這個實際上就是,我們之前把它叫做effec- tive
number of line,有效的線的數量,現在呢其實就是這個mH,我們把這個mH取一個
名字,叫做growth function,OK成長函數,什麼東西的成長函數,是跟我們的hypothesis
set有關的 那跟我們之前講effective的時候,那講的事情一樣,這個函數的輸出一定是有限的
對不對?因為最多最多就是2的N次方那麼多
種而已,好,那所以大家就會想啦,好,所以我們之前直線的狀況,我們在一些特定的例子 算了這個growth
function這個成長函數的值,那到底 我們in general,我們能不能真的把這整個函數寫出來呢
好,在perceptron的例子,這是比較困難的,那我們先給大家看一些 更簡單的hypothesis
set,然後看我們可不可以寫出這些東西來 好,什麼意思呢,我們先來看一個簡單的hypothesis
set 這個hypothesis set是這個我們叫做positive
ray 我們現在講,好,我們想要用的輸入是什麼,我們想要用的輸入就是一維的實數
好也就是說,不是像我們之前二維空間,或三維或更高維,我們就一維的實數,也就是我的所-
有的輸入 X1,X2一直到XN都是數線上,好在數線上的話,我還可以稍微
給一個小小的限制,只是為了好看而已,我們把X1排在最左邊,XN排在最右邊
然後我的hypothesis長什麼樣子呢,我的hypothesis說我取某一個
threshold,某一個門檻值,比這個門檻值大的話,我的hypothesis set,我的hypothesis就說是正1
比這門檻值來的小的話,我們hypothesis就說負1 所以任何一個不同的門檻值就決定了一個不一樣的hypothesis
那我的hypothesis set就是所有這樣長相的函數 它靠一個門檻值來決定,然後這個門檻值的右邊比它大的地方是正1
左邊比它小的地方是負1,那這樣的東西我們就叫做 positive
ray,那整個hypothesis set就是要做positive ray的hypothesis set 就是正向的,好像光束一樣,往正向射的
這個光束,好,那其實,有些同學可能看到,我們這個式子sign(x-a)會想到,誒這- 個長的跟
perceptron有一點點像,好,沒有錯,實際上這是就是
1D的perceptron,只是少了一半,少了哪一半,少了往
這個負的那個方向,往比較小的那個方向,指的那種是perceptron 1D的perceptron
的一半,某種角度來說是這樣 好,那我們就問了,如果用這個hypothesis
set 的話可以切出多少種
不一樣的dichotomy,我給你N個點,你可以最多最多切出多少種不一樣的dich- otomy
當然你可以想像N個點,呃比較general的狀況,實際上是N個點都不一樣
如果一樣 dichotomy只會更少,誒所以如果是N個點都不一樣的狀況,你可以切出幾種
我們看一看上面這個示意圖以後,我相信同學應該可以看得出來說 啊,最多最多就N+1這麼多種
這N+1怎麼來的,誒我這N個點,某種角度來說,把數線切成N+1個區塊
我如果把threshold取在任何一個區塊裡面,我都會產生一種不同的dicho- tomy
好,例如說,我現在如果有四個點的話,我所有可能的dichotomy其實就是這五種,- 這五種怎麼樣
好,第一種是,我把那個threshold放在最左邊,好所有人的左邊,所以我就切出一種
放在X1跟X2中間,我就切出第二種;放在X2跟X3中間,我就切出第三種
好,所以我總共就是五種情形,所以在這個情形裡面,我可以很輕易地 寫出成長函數的長相,就是N+1
好,注意到一件事,N+1是遠小於2N的 如果今天N夠大的時候,我們之前說我們要用這個dichotomy
set 的大小,或growth function這個成長函數來取代大M,我們這邊發現,如果我們拿
這樣的東西來取代大M,當N很大的時候是有好處的,因為最終最終那個Exponenti- al負的那一項
會變得很小很小,然後會把這一項,呃很小很小的這個N+1這一項壓掉
好,那我們來看另外一個情形 另外一個情形是什麼,我們現在想象hypothesis一樣是對
這個一維的輸入,但是呢,它不是往一個方向是正1,另外一個方向是負1
它說,我要在某一個interval,OK某一個範圍之內表示正1,然後外面的
是負1,好所以這樣的,所有這樣的hypotheses組成的hypotheses set我們叫做 positive
interval,interval裡面是positive,範圍裡面是正的,然後範圍- 以外是負的 好,這種hypothesis
set,好,我們就要問大家啦,請問如果是這個 hypothesis set 的話,那麼你的Growth
Function,你的成長函數會長什麼樣子? 好,大家看一看以後可能會知道,誒這個成長函數我可以怎麼樣算?
我可以算說,好一樣剛才有N加1個區塊,我如果把我的
這個範圍的兩個端點,取在這個兩個,選兩個區塊。
然後把端點選在這兩個區塊裡面的話,我就可以做出一個不一樣的Interval。
好,所以這是N加1取2好的這些情形。
然後呢還要加上一個什麼情形?還要加上我把這是這個兩個Interval,
兩個端點如果取在同一個, 同一個這個區域裡面,取在同一個區域,就那個區域裡面
是正1,其他東西是負1,所以在我的N個點上就會都回傳什麼? 都回傳負1,或都回傳叉叉。
好,所以還有一種情形是全部都是叉叉的情形,這是我把兩個端點
都放在同一個區塊,如果我把兩個端點放在不同的區塊的話,我就會得在N加1取2之間情形
裡面,所以我們把它寫開來就變成了二分之一N平方加上二分之一N加上1,好這樣的
式子,這是我的這個成長函數的長相,那或者如果 今天是4個點的話,我實際上可以列出這所有的情形,就是這個樣子,
那 基本上做的事情就是,好除了最後一個是全部都是叉叉的情形,其它的情形
都對應到我把端點放在,兩個端點各放在一個,一個區塊的中間。
好,一樣這是一個多項式,這個 多項式最終最終會怎麼樣?會比2的N次方來的小。
好,所以這是,對我們來說這是好消息,如果我們真的能夠把這個成長函數套到
我們之前的那個Hoeffding的那個式子裡面的話,把大N取代掉的話,誒比2的N次- 方來的小是個好消息。
好,還有什麼?我們舉第三個例子說,我們怎麼樣算這個成長函數。
這第三個例子說,誒那我們如果今天回到平面的這個 輸入空間的話,
那平面的輸入空間我們說,我們訂一個這個hypothesis,每一個hypoth- esis
對應到什麼?對應到一個Convex Set,一個這個凸的,凸的幾何。
在這個凸的幾何裡面的是正的,OK是圈圈, 我們說來用藍色來代表,在這個凸的幾何以外的是
叉叉用粉紅色來代表,所以嗯像在左邊的這一個,左邊的這一個就是一個Convex的hy- pothesis,
那右邊這個就不是,因為這個這個範圍並不是一個Convex,並不是凸的。
好,如果 我們把所有這樣的hypothesis集合起來變成一個
hypothesis set的話,我們現在要問的問題是,這樣的hypothesis set
它的成長函數會長什麼樣子? 好,所以我們來看看會長什麼樣子呢?那
我們說我們成長函數要應付各式各樣不同的可能,我現在要給 一個很極端的可能是這樣,我把我所有的輸入
排在一個圓圈圈的邊上面,排一個圓圈圈的邊上面就怎麼樣呢?
我就發現說,不管我要做出什麼樣的
這個dichotomy,啊我先想我要做出dichotomy,例如說我這要做出dic- hotomy是這裡有個,這裡有個正的。
然後這裡有個正的,這裡有個正的,這裡有個正的,這裡有個正的,然後其它是負的,OK所以
那些正的就是我的圈圈,然後其它是我的叉叉,我要做出我的這個dichotomy的話,- 我可以做什麼事情呢?
我就說,啊那我就弄一個多邊形, OK這個多邊形呢就剛好把這些,呃這個
我想要變成正的點連起來,然後把這個多邊形稍微往外闊一點點,
那這樣的話,在這個多邊形裡面而且這實際上大家可以看到這是一個凸多邊形,在這個凸多邊形
裡面的,我就可以順利地這個預測它是正的,外面的就是負的,所以我可不可以產生這種di- chotomy?
可以,所以我要猜是哪個dichotomy的時候,我就畫一個多邊形
好了,如果是我要產生dichotomy有三個正的我就畫一個三角形,有四個正的我就畫- 一個這個四方形。
好,那這樣的話不管我要做出是什麼dichotomy,我都可以很輕易地用
凸多邊形做出來,我既然能用凸多邊形做出來,也就是我就能夠用凸幾何做出來。
然後所以從這裡來看的話,這樣的hypothesis set,
每一種dichotomy都可以做出來,每一種dichotomy都可以做出來代表
它的這個成長函數是2的N次方,OK我給你N個點,你可以吧2的N次方那麼多種dich- otomy
統統做出來,那我們說這N個點我們把它取一個特別的名字叫做
shattered,shattered這個詞是打碎意思,說啊這個N個點 被這個hypothesis
set KO了,KO就是擊倒了,說誒這,這所有的情形統統都 可以做得出來。
好,所以 shattered的意思我們再,再講一次OK,如果我們找到OK,N個點
N個點,可能是特別的N個點,這特別的N個點上呢?我們 可以shattered,我們可以把它擊倒,把2的N次方從dichotomy統統都做-
出來的話, 我們就說成長函數按照我們的定義,成長函數是2的N次方。
好,所以我們這邊講的這個成長函數的這個定義,那這邊給大家
做個練習說,誒大家看看說如果我今天考慮的不是只有positive rays, 而是positive跟negative的rays。
就是我剛才講的one dimensional perceptron的另外一個方向。
那麼這樣的話它的呃,這個成長函數到底是多少?
好大家如果看的話,那就會發現說,誒如果是中間的那些區塊N減一個
區塊的話,你把threshold放在那邊可以產生兩種不同的dichotomy,一個- 往正的方向,一個往負的方向。
那麼還有另外兩種是全正跟全負的選擇。
好,所以總共是2乘以N加1再加上2,所以總共是2N種,我們的參考答案是3。