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. [機器學習旨在讓電腦能由資料中累積的經驗來自我進步。我們的兩項姊妹課程將介紹各領域中的機器學習使用者都應該知道的基礎演算法、理論及實務工具。本課程將較為著重數學類的工具，而另一課程將較為著重方法類的工具。]
Definition of VC Dimension
Loading...
来自 国立台湾大学 的课程
機器學習基石上 (Machine Learning Foundations)---Mathematical Foundations
342 评分
从本节课中
第七講: The VC Dimension
learning happens if there is finite model complexity (called VC dimension), enough data, and low training error
与讲师见面
Hsuan-Tien Lin, 林軒田教授 (Professor)
資訊工程學系 (Computer Science and Information Engineering)
[音樂] [音樂]
[音樂] [音樂]
好，大家好，大家好，歡迎回到今天的機器學習基石的課程 今天我們要跟大家講的課題叫做The
VC dimension，大家可能猜到了 VC跟我們上個星期講的這個VC
bound是有一點點關係的 那什麼叫VC dimension，這個我們待會兒會為大家
定義。我們先複習一下我們上一次上過的什麼，我們上一次上過的是Theory of
Generalization，什麼是Generalization 一般有人翻譯成一般化，可是更貼切的翻譯是
舉一反三，舉什麼，舉例子，像我們訓練的時候在舉例子 然後反三也就是說我們測試的時候會跟我們訓練的時候的表現是類似
那我們上個禮拜跨出了很重要的一步，我們說我們可以
確保我們的Ein，也就是我們訓練時候的表現，跟我們的Eout
我們測試時候的表現是類似的，什麼時候可以這樣確保呢？我們只要
我們的成長函數在某個地方露出了一線曙光，然後再來
如果我們的資料量夠多的時候，我們就可以確保Ein跟Eout是接近的
那從這裡出發呢，我們就要開始看看這個一線曙光的意義
是什麼？實際上這就會引到我們待會兒對這個VC dimension，這個VC的這個維度
等一下我們會講為什麼我們叫它一個維度的定義 好，我們來看看我們上一次上了什麼東西，我們上一次說如果我們的成長函數在
某個k的地方露出了一線曙光的話，那這個成長函數會被某個上限
函數所bound住，這個上限函數又會被某個多項式 所bound住，這個多項式的次方是k-1次方
所以呢我們可以把這個上限函數的這個表格列出來
我們也可以把什麼列出來呢？我們也可以把所謂N的k-1次方列出來
好，我們來比較，左邊是我們這個上限函數的表格，右邊是N的k-1次方
如果我們認真的去看的話，我們會發現說當N夠大，而且k也夠大，其實夠大也沒有
很大，N大概要比2大，k大概要比3大的時候，我們發現N的k-1次方
已經要比我們的上限函數來得大，也就是說比我們的成長函數來得大
這樣的話所以我們就可以去寫說，那麼我們 可以簡單的把我們的成長函數去寫說，它會被
N的k-1次方所bound住，這樣子的話我們以後就不用說在寫成長函數
的時候，就還是寫的b啊或者那個很複雜的summation式子在那邊，我們可以用簡單的
N的k-1次方來代替，來想像說，這個我們的成長函數最多最多
長什麼樣子。好，我們上次還跟大家提到這個VC bound，我們說這個VC
bound呢我們 上一次證明的事情，是說如果在我的hypothesis
set裏面有任何一個hypothesis 發生壞事情，這件事的機率很小很小，有多小，它是4倍
乘上我們的成長函數，成長函數在2N的地方，然後有後面的一個exponential的項
那這件事情的意義是什麼？這件事情的意義實際上是既然
我們保證了說大部分的時候都不會有壞事情
發生，所以不管我們的演算法做了任何的選擇 我們都可以說你演算法做的選擇被我們的VC
bound所 支配，那這個時候呢所以演算法做選擇，選出了一個g，我們就可以
說這個g的Ein跟Eout離得很遠的機率要來得很小
那如果配合我們在上一頁講到的事情，我們可以把成長函數
代換成這個上限的上限的上限，我們說這個N的k-1次方的話
那麼我們的式子就可以簡單的寫成這個樣子，那這個上限的上限的上限 會需要N夠大還有k夠大，不過呢在我們原來證VC
bound的時候，本來我們就假設N夠大 記得我們那個1/2，那是N夠大的時候跑出來的，然後所以N夠大對我們來說不是問題
那k要大於等於3是我們新進來的一點小小的
條件，那如果今天k比3小的時候，那只是我們不能用N 的k-1次方這個bound，實際上我們可以拿其他bound出來用
好，所以這個時候我們就做到什麼樣事情呢？我們說
幾個條件讓我們learning可能做得到，首先前兩個條件 是我們要有一個好的hypothesis
set，什麼叫好的hypothesis set？ 它的成長函數要在某個地方露出一線曙光
再來我們要有一個好的data，好的data的意思實際上就是夠大 的data，夠大的data才能確保壞事情發生的機率很低很低
那這個時候我們就說我們已經達到了舉一反三，我們的 未來測試的表現跟我們現在訓練的表現會是類似的
那這個時候如果再配合一個好的演算法，這個好的演算法做什麼事呢？
好的演算法選出一個g，這個g的Ein來得很小的話，那我們就說
看起來是學到東西，至少我們的理論保證告訴我們這樣的事情
好，不過這是比較這個ideal的故事是這個樣子，實際上呢
在我們理論裏面，我們說，我們不能保證絕對做到這件事情
所以這實際上是機率上我們做到的事情，所以呢除了好的hypothesis set
除了好的資料，好的演算法之外，我們還需要一點點好的運氣
然後這樣子的話，我們就能夠做到，大概能夠做到這個學習 好，那VC
dimension是什麼呢？我們 開始講說我們今天主要的課題環繞在VC
dimension上，VC維度 那這個VC維度實際上是我們試圖給我們之前一直圍繞著講的這個break
point 一個正式的名稱，不過我們實際上這個正式的名稱還不
是給break point，不是給這個露出一線曙光的點，我們是給最大的
non-break point，記得break point是在某個地方露出一線曙光，所以呢
在break point之前，例如說break point是k的話，k-1那個點
那個點就是最大的non-break point，那這是我們把它定義為叫做我們的VC
dimension 好，所以你可以看到它是一個hypothesis
set 的性質，這個性質說在VC dimension上面
這個hypothesis set可以shatter掉某N個點，不一定所有的N個點，但是是某N個點
不過如果超過這個VC dimension的話，就開始出現不能夠shatter，也就是說我們的break
point的情形 好，那麼這個是dVC，okay，我們的
VC dimension我們一般用這個dVC這個符號來代表，實際上你可以把它寫成
minimum的break point然後再減掉1，如果minimum的break point存在的話
那如果minimum的break point不存在的話，我們一般說VC dimension就是無限大
好，那如果今天說我的資料量小於或等於VC dimension的話
那麼這表示什麼？這表示我的資料有可能 會被這個hypothesis
set shatter，不是一定，因為我說 我的資料量小於等於VC
dimension的時候，我們只是說存在某個資料會被 hypothesis set
來shatter，我們不知道我們手上的資料到底是 不是，而如果我們今天N的數量比hypothesis
set來得大的時候，我們就非常 可以確定什麼？它一定不能被shatter，每個那個大小的數量都不能夠被shatter
實際上在這個情形裏面，我們之前使用的符號不是N，而是k，也就是我們的break point
比VC dimension大就是break point，比VC dimension小或一樣的時候，就不是break
point 這是我們的這個VC dimension。那所以如果這樣的話，我們就可以把我們剛才的
這個符號稍微換過來說，當N夠大，這個VC dimension 也夠大的時候，我們可以說我們的成長函數比什麼來得小？
比N的VC dimension次方來得小，也就是原來那個k-1就變成VC
dimension 所以呢，我們再來回顧一下我們之前看過的幾個例子
我們說如果今天是positive rays的話，它的成長函數是N+1
然後它的VC dimension是多少，它的VC dimension是1，因為我給一個點的時候，所有的
排列組合都產生出來，我們可以shatter掉這個點，那如果兩個點的話就不行了 如果今天是positive
interval的話，那我們可以寫出它的成長函數，重要的是它的VC dimension
是2，我們給它兩個點的時候可以shatter，兩個點以上三個點的時候就一定不能sh- atter
那如果是convex set呢，我們之前說到說不管我們給它幾個點，只要
這些點恰恰好是排在一個圓上的話，我們一定可以用convex set來
shatter，所以我們說它的VC dimension是無限大 那如果今天是2D的perceptron呢，我們給它幾個點可以shatter
我們給它三個點可以shatter，給它四個點就不能shatter，所以我們知道- 它的VC
dimension是3 那我們也可以知道它的成長函數會被N的3次方所bound住
我們今天N夠大的時候。好，然後所以我們新引入一個概念 我們之前說什麼是好的hypothesis
set，露出一線曙光的hypothesis set 現在相對應的什麼是好的hypothesis
set，VC dimension 是finite的hypothesis set就是好的hypothesis set
好，那我們來看看說，今天如果是 一個好的hypothesis
set，它的VC dimension是finite的時候，到底有什麼好事？ 好事就是你的Ein跟你的Eout會是接近，而且這件事情還
不但接近，它跟什麼東西沒有關係？它跟你演算法怎麼選擇這個g沒有關係
所以我們心裏想說好的演算法應該要選一個Ein低一點的，但是如果你今天有一個很糟糕- 的演算法
它就選一個Ein很高的，我們還是會確保什麼，還是確保它的Eout跟Ein是接近的 只是這樣的話對我們沒有太大的好處而已
它還跟什麼沒有關係？它跟你的資料是由什麼樣的distribution產生沒有關係
我們說這件事情我們可以不知道，我們沒有在，我們建立模型的時候把這件事情 含進去。它跟你的target我們這個目標長什麼樣子也沒有關係
所以這樣的話，我們就可以維持target是在不知道的狀況下，做到這個學習的動作。- 我們整個
機器學習的流程，大家記得，從一開始，最一開始的流程 然後到上一次我們把它加上了probability的distribution
我們總算整個完成說，我們可以做到
這個在最壞最壞的狀況下，我們還是能夠確保Ein跟Eout是接近的
好，那我們這邊給大家一個小小的練習，確保大家有跟上我們對VC dimension的這個定義
如果我們今天手上有N筆的資料，這N筆的資料沒有辦法被某個hypothesis set
所shatter的話，那從這一句話的資訊，我們到底可以 怎麼樣推斷說這個hypothesis set的VC
dimension長什麼樣子 它是比N大，還是比N小，還是跟N一樣，還是說其實我們不知道
好，大家想一想之後我希望大家能夠選到正確的答案
是4，這個4答案說我們不知道，為什麼我們不知道，我們只有看到
N筆資料沒有辦法被shatter，但是如果有另外N筆可以被shatter，那麼VC dimension
可能就要比N來得大，那如果其他的任何的N筆統統都不能被shatter，那麼VC dimension
就要比N來得小，所以這兩種都有可能發生，你只看 一個，說一個不能shatter的資料，那這不算
說到底我們能夠說VC dimension是什麼樣子，那只是定義上這個能夠跟不能夠
然後存在一個還是對所有都不一樣，這些不一樣的地方，希望在進入下一段的課程之前
大家能夠好好想一想，然後把這件事情搞清楚
