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. [機器學習旨在讓電腦能由資料中累積的經驗來自我進步。我們的兩項姊妹課程將介紹各領域中的機器學習使用者都應該知道的基礎演算法、理論及實務工具。本課程將較為著重數學類的工具，而另一課程將較為著重方法類的工具。]
Interpreting VC Dimension
Loading...
En provenance du cours de Université nationale de Taïwan
機器學習基石上 (Machine Learning Foundations)---Mathematical Foundations
344 notes
Université nationale de Taïwan
344 notes
À partir de la leçon
第七講: The VC Dimension
learning happens if there is finite model complexity (called VC dimension), enough data, and low training error
Rencontrer les enseignants
Hsuan-Tien Lin, 林軒田教授 (Professor)
資訊工程學系 (Computer Science and Information Engineering)
好，那我們現在想要更深入地了解VC dimension的意義是什麼。
要了解這個之前，我們就先把VC Bound重新寫過，這是我們 原來的VC
Bound式子，它說壞事情發生的機會 會很小很小，好所以右邊有一個這個很小很小的項。
如果我們把這個很小很小的項叫做δ的話，我們現在回頭來看說，誒我們能不能
描述好事情發生的時候到底是什麼事情？也就是說，誒這些壞事情發生的機會很小，
那麼另外一個角度就是，好事情發生的機會應該很大。
所以我們實際上可以這樣寫說，with probability比1－δ還要大的機率應該要發生好事。
好，所以好事發生的時候是怎麼樣？誒我們就看看說，所以δ跟ε這些條件我們都要
互相滿足啊，那我們把δ設定成我們這個bound所給我們的這個保證的時候，
我們可以一路代換，從這個δ出發，換成什麼？ 換成說，誒那在我們覺得
這個幸運的等級，這個δ上，到底相對應的ε 是多少？也就是說我可以確保我的Ein跟Eout差多遠。
那這是一個簡單的代換。
我們第一步也許會說，誒好，那我們把這個4啊然後2N這些東西除過來，
除過來以後取一個log，ok，取一個log於是呢，就把兩邊通通都換過來了。
那還有呢這個負號的部分會在log裏面對應到倒過來的這個項。
對應到倒過來的項之後，那我們現在右邊還剩什麼？我們右邊剩下1/8 N
還有一個這個平方，我們可以再把它換到另外一邊。
所以我從這個δ出發， 最後倒到了一個相對應的ε是長這個樣子的。
大家看到說是根號，然後呢裏面是這個 8/N然後乘上log的這個某個式子。
好，有這個式子的意義是什麼？這個式子的意義是我們就可以寫下來說，有很高的機會
Ein跟Eout的差別會被限制在 誒這個根號然後這個咚咚咚，這個很大的項目裏面。
也就是說我們現在描述的是好事情發生，好事情發生就是Ein跟Eout會很靠近。
那這個左邊的這邊Ein跟Eout到底有多靠近這件事情，我們一般就把它叫做 generalization
error，就是說我們到底舉一反三這個部分做得多好。
然後所以VC Bound 告訴我們什麼事情？它說Eout，我們最有興趣知道是Eout，
會被限制在兩個東西的中間，一個是Ein加上這個根號那一項，一個是Ein
減掉根號那一項，在統計上呢，這就很像我們在做所謂的confidence interval，這個信賴的區間,
我的Eout的信賴區間就會是大概是這個樣子。
好，那這樣的話，我們看到說，誒左邊的那個部分我把它標成灰色的，
那是因為左邊這個部分我們通常不太重視，我們不太重視說，誒到底
Eout這個比什麼東西來得高，不過右邊的部分我們通常比較重視，
我們重視說我們的Eout最糟糕最糟糕說到底有多壞，例如說你拿這個g去投資啊，你會想到
說誒放到股市上的時候，到底如果在我所設定的這個幸運指數這個δ上面的話， 到底最壞最壞的時候會有多壞。
所以我們通常比較在意右邊的這個 部分。
那這右邊的部分裏面這個根號 裏面這些東西，我們一般就把它叫做model
complexity，這個model指的實際上是我們的 hypothesis
set，我們可以說我的hypothesis set今天到底有多麼的powerful，有多麼的有力，
有多麼的強，然後但是我在generalization的時候要付出的代價 就是這麼多。
那我們一般用一個符號叫做Ω，大寫的Ω來做代表。
那我可以看到說，誒這個根號這個項裏面有三個事情，一個是N， 就是你到底有多少個點，另外一個是H，它是說你的VC
Dimension是多少， 然後再來是δ，說誒你覺得你有多幸運。
好，所以我們來看看VC告訴我們的事情就是
有很高的機率Eout會比Ein 加上我們剛才這個model complexity 的penalty來得小。
也就是說誒，我們可以把圖，這個learning發生的事情大概畫
成這樣的圖，這個圖裏面有什麼呢？這個圖裏面橫軸是VC Dimension， 縱軸則是error。
好，我們有兩種error，一個是in-sample，也就是Ein的部分。
一個是out-of-sample，也就是Eout的部分。
大家看到說我把這個in-sample 跟out-of-sample畫成這個樣子，也就是說我們看看它隨著VC
Dimension的這個變化。
它隨著VC Dimension變化，裏面就還會有一項進入我們的式子裏面，
就是所謂的model complexity，在我們上面的式子裏面就是這個Ω。
好，所以我們來看兩件事情。
一個是model complexity隨著VC Dimension的變大越來越變大，這是我們知道的。
然後呢Ein呢，好因為VC Dimension變大的時候，你可以shatter的點就變多了，所以
通常Ein會變小，因為這個你資料如果固定在那邊，
那你可以shatter的點變多，可能就有比較多種的排列組合， 那就有機會找到一個更好的。
所以如果你是一個合理的learning algorithm，你應該比較有機會找到更小的Ein。
好所以Ein變小了，model complexity變大了，那麼out-of-sample
error就 常常會像我們上面畫的那樣，是一個這個三股形的這樣的表現。
好，一開始的時候，隨著in-sample error的下降，這個Eout會一直下降，但是到某個地方
因為我們要付出的代價變多了，然後model complexity上升了，所以Eout又會上升，
所以最好的這個Ein會在中間，隨著VC Dimension
上升的時候，Ein會下降，然後但是model complexity會上升，
VC Dimension下降的時候，那反過來說model complexity會下降，可是Ein 會上升。
那最好的VC Dimension在某個中間的地方。
我們未來會常常看到類似這個東西的圖。
就是說，誒不見得我下面 畫的是VC Dimension，但是可能是某個跟它有關的量，然後呢我們未來會
利用這個圖來想辦法設計更好的機器學習的演算法。
那這邊有一個很重要的訊息是這樣，剛開始使用machine learning可能就會想，
誒我就想辦法把Ein做好就好啦，把Ein做好也可能意味著你要用更高的VC Dimension或者更
強大的這個hypothesis set，但是你如果就用更強大的hypothesis
set把Ein做到很低的話，從這個圖 可以看出來這不見得是最好的選擇，OK，
因為你要付出很大的model complexity的代價。
那一個這個正確使用machine learning的人，現在就會想了，
好，所以我並不是只是想辦法把Ein做到最低就好， 而是誒我今天真的要考慮，我在我的hypothesis
set 上面到底付出了多少的penalty，付出了多少的成本。
好，那VC Bound呢其實還有另外一個意思，我們通常叫做
Sample Complexity，樣本的複雜度或實際上就是資料量的複雜度。
好，什麼意思呢？想像你老板開出了一些規格，他說這個規格是這樣，
我希望你的Ein跟Eout差最多0.1，
然後呢我希望壞事情發生的機會最多最多就10%，也就是說我們 90%的時候相信好事情會發生。
然後再來我給你一個learning model， 假設它VC
Dimension是3，例如說2D的perceptron，我們現在知道它的VC Dimension是3，
那麼你老板就問了，你到底要多少的資料才夠？ 你說，哦好，我現在有這個VC
Bound啦，我就把數字代進去，我說誒看看 我今天是100筆資料的時候，我得到的bound，我得到的上限是多少。
代一代你說，哎呀2.82×10^7，怎麼這麼大，一個機率小於等於
2.82×10^7，這跟有寫跟沒有寫一樣，因為機率一定是小於等於1的數字。
你說這一定是資料不夠，不然的話我們用多一點資料好了。
如果今天1000筆資料的時候發生什麼事？1000筆資料的時候，一代進去，哎喲， 結果更糟糕了，變成9.17×10^9。
你說這不太對啊，資料還不夠嗎？你代10000筆資料進去，誒，好一點，稍微好一點，變成
1.19×10^8，也就是後面那一項，這個exponential裏下降的項 開始發揮作用。
如果用100000筆資料呢，哇那就真的變得很小了，1.65×10^(-38)，
所以壞事情發生的機率很小很小很小，所以呢你如果今天有100000筆的資料，然後你的- perceptron
learning algorithm呢做的很好， 你就可以很開心地說，哎呀我真的學到東西了。
如果退回來說，誒那我還有一些這個額度啊， 那我可不可以退回來？算一算，你會發現，在大概29000筆
資料左右呢，你可以達到你的老板的規格的要求。
誒我統統滿足你的規格，理論上我可以保證這些規格的發生，然後我需要大概29000- 筆資料。
好，你如果呢用不同的VC Dimension代進去的話，大概
你會得到說你需要的資料量是10000倍的VC Dimension這麼多。
你說，哎喲，10,000 倍的 VC Dimension 我去哪裡找來這麼多的資料？想像你今天如果今天是一個二維平面，你要做
Perceptrons Learning，你就要找 30,000 個點， 你哪裡找來這麼多資料？好，的確沒錯，實務上
我們根本不需要這麼多資料，就可以得到 還不錯的 learning 表現。
大概多少呢？大概 10 倍的 VC Dimension 的量，就很夠了。
因為你想像一個平面，我如果給你 30 個點，你要選一條線，很夠狠夠了。
你如果給 100 個點，就已經很奢侈了。
好，所以 10 倍的 VC Dimension 這是實務上我們發現夠用的數字。
那 你如果真的去找 VC Bound 的話，它會跟你說，大概要 10,000 倍的 VC Dimension 才夠用。
好，這也就是說，這個 VC Bound ，OK 裡面是非常的寬鬆的。
OK，這個理論告訴我們，10,000 倍的 VC Dimension， 然後實務上是
10 倍的 VC Dimension，這中間的差距就是 VC Bound 到底有多寬鬆。
好，那這個寬鬆的來源是什麼呢？這寬鬆的來源有，例如說我們用了Hoeffding， Hoeffding
確保什麼？確保說我們不需要知道 P，我們也不需要 知道 F。
也就是說，我們對任何的 distribution， 對任何的 target 都可以用這個 Bound 來確保。
也就是說它非常的包山包海，包得非常之廣。
那還有什麼呢？哎，我們並沒有用這個 Hypothesis Set
產生的 dichotomy 的真正的數量，我們用的是成長函數。
成長函數的話，它確保什麼？它確保說，我們這個在做分析的時候，
我們可以使用任何的資料，OK，而不是說我們真正只抓到我們手上那一筆， 也就是說，它讓我們可以從我們
distribution sample 出很多資料，然後真正 去看說哎，到底發生了什麼事情。
但是這邊大家可以想像說，這邊也 建立了說，這邊有一個寬鬆的地方，因為我的成長函數只是我實際上
dichotomy 數量的高估而已。
啊還有，OK，我們用一個多項式來做上限的上 限的上限。
我們不是真的用成長函數，我們用上限的上限的上限，然後這樣可以確保什麼？ 確保說，我們看一個
Hypothesis Set，我們只要看一個數字就好，我們只要看它的 VC Dimension 就好，我不用看說這個 Hypothesis Set 所有的細節。
但是這裡一樣，大家記得成長函數說啊這個，如果今天 是 4
個點的話，然後我們不能夠 shatter，我們最多是有 15 個，但是 perceptrons
實際上有 14 個，那如果我們再用什麼 N 的多少次方的話，這邊只會更寬鬆而已。
好，那還有什麼呢？我們使用了 union bound。
我們雖然已經很盡量地 把那些重疊地方盡量算得很好，但是我們使用這個 union bound 的時候，我們說我們使用在哪裡？我們使用在 最差的狀況。
我們想像我們很害怕，我們的演算法一定可能踩到雷，只要有雷，它就有可能踩到。
實際上你的演算法有沒有那麼容易踩到雷，搞不好沒有。
搞 不好沒有的話，所以我們這邊就還是會有一個寬鬆的地方在。
好，所以看到說，我們在這個 VC Bound 上一路的推導都是很寬鬆的，那這些寬鬆
就進入了說，為什麼我們這個需要的 資料的數量，跟實際上理論告訴我們的，好像差很多。
不過呢，故事是這樣，故事是雖然 VC Bound 非常的寬鬆，但
是很多的研究者嘗試著要讓 VC Bound 更緊一點等等等等。
但是要做到跟 VC Bound 一樣的事情，我說一樣的事情是，在這麼多 面向上，例如說 distribution， 例如說 target
function，例如說演算法 都能夠做到很隨意，很隨、 很廣，包山包海這樣子的話，
很難很難做得比 VC Bound 更好，幾乎沒有做得更好的。
而且呢 對於所有，也就是說我們未來會介紹很多不同的
Hypothesis Set，很多不同的 Learning Models， VC Bound
呢，其實寬鬆的程度是差不多的，也就是說例如說，我如果讓 VC Dimension 來比較不同的
Model 的話，我還是可以這樣做，不管理論實際上怎麼說，但是因為差不多寬鬆，差不多寬鬆意思是說
好，譬如說所有人這個 Bound 都好像比原來放大了 20,000
倍，那沒有什麼大不了的，因為我還是可以 拿這個 Bound 來比大小，然後來利用
VC Bound 來想辦法，說哎實務上的表現可能會是什麼樣子。
好，所以呢，我們這邊介紹 VC Bound，它是一個非常
theoretical 的結果，但是我們未來 會用到的，並不是真正它 theory 的部份。
因為真正用到它 theory 的部份，我們就要拿例如說 10,000 倍的 VC Dimension 的資料下去。
這個在大多數的時候，我們是做不到的。
但是我們會拿什麼？我們會拿說，哎在這個 VC Bound 的背後，
到底它的哲學意義是什麼？它告訴我們一些什麼事情？例如說，我們剛才講 Model Complexity，
它告訴我們說，我們不要一味地追求最強的 Hypothesis Set，OK，這樣的
這個哲學的訊息，是我們未來在設計機器學習演算法上，會使用到的 東西。
好，那我們這邊呢，再給大家一個練習。
我們說，哎，到底 VC Bound 在這邊，你要
怎麼減少壞事情發生的機會？那我們這邊下面實際上有 3 個選項，或者你可以選這個以上皆是，
說，哎你是要減少 VC Dimension，你是要增加你的資料量
增加很多，還是說，哎你要增加你對這個啊 隔得很遠這件事情的寬容度。
好！那大家想一想之後，我希望大家能夠選到正確的答案是 4。
就是說，哎以上皆是。
那也恭喜大家，瞭解了 VC Bound，掌握了機器學習裡面最重要的一個理論工具。
好！總結來說呢，我們今天跟大家介紹了 VC Dimension 是什麼 東西。
那我們說，VC Dimension 是最大的 non-break point。
OK， 也就是說我們給 break point 一個正式的名字， 最大的還不是 break point 的那個點，我們說它是 VC Dimension。
那麼我們說在 Perceptrons 上，它恰好就是 d + 1，就是我的 Perceptrons 裡面到底有多少個維度。
那麼物理意義上，VC Dimension 告訴我們說，哎我們的 這個
Hypothesis Set 到底有多少的自由度，大概就是啊
有多少的自由的這個旋鈕，那麼 啊在
VC Dimension 我們就可以用來什麼？我們可以用來看看我們的 Model，
我們的 Hypothesis Set 到底有多複雜，然後我們能夠用它來決定，我們大概需要多少的 資料才夠。
好，那所以這是 VC Dimension 跟 VC Bound，我們再給大家加強更深的印象。
那下一次呢，我們則是要說，我們現在說的事情都只是說，哎我們 資料從某個
distribution 出來，然後經過某個 target function，所以沒有 noise。
然後呢，而且我們也只能在 Binary Classification 上面做。
那在下一堂課裡面，我們會嘗試著把 VC Dimension 的概念延伸到更多不同的 learning 的問題上面。
那歡迎大家下一次回來，謝謝！ [音樂]
[音樂]
[音樂]
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
