Machine learning is the study that allows computers to adaptively improve their performance with experience accumulated from the data observed. Our two sister courses teach the most fundamental algorithmic, theoretical and practical tools that any user of machine learning needs to know. This first course of the two would focus more on mathematical tools, and the other course would focus more on algorithmic tools. [機器學習旨在讓電腦能由資料中累積的經驗來自我進步。我們的兩項姊妹課程將介紹各領域中的機器學習使用者都應該知道的基礎演算法、理論及實務工具。本課程將較為著重數學類的工具，而另一課程將較為著重方法類的工具。]
Effective Number of Hypotheses
Loading...
From the course by National Taiwan University
機器學習基石上 (Machine Learning Foundations)---Mathematical Foundations
341 ratings
National Taiwan University
341 ratings
From the lesson
第五講：Training versus Testing
what we pay in choosing hypotheses during training: the growth function for representing effective number of choices
Meet the Instructors
Hsuan-Tien Lin, 林軒田教授 (Professor)
資訊工程學系 (Computer Science and Information Engineering)
好，所以接下來，我們來看看我們剛才已經知道說，我們如果用 線的話，那麼在平面上到底有幾種不一樣的線
那我們現在，如果以後我們要用線以外的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。
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
