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 second course of the two would focus more on algorithmic tools, and the other course would focus more on mathematical tools. [機器學習旨在讓電腦能由資料中累積的經驗來自我進步。我們的兩項姊妹課程將介紹各領域中的機器學習使用者都應該知道的基礎演算法、理論及實務工具。本課程將較為著重方法類的工具，而另一課程將較為著重數學類的工具。]
Regularized Hypothesis Set
Loading...
Из курса от партнера National Taiwan University
機器學習基石下 (Machine Learning Foundations)---Algorithmic Foundations
142 оценки
National Taiwan University
142 оценки
Из урока
第十四講: Regularization
minimize augmented error, where the added regularizer effectively limits model complexity
Познакомьтесь с преподавателями
林軒田教授 (Professor)
資訊工程學系 (Computer Science and Information Engineering)
[音樂] [音樂]
[音樂] [音樂]
好，大家好，大家好，歡迎回到今天的機器學習基石課程
我們今天要跟大家講的課題是Regularization，一般有人把它翻成規則化或者
是規律化，那詳細的內涵我們會在這節課裏面跟大家講清楚 那麼先來看看我們上一次上了些什麼，我們上一次說到說
在machine learning裏面最大的危險之一就是overfitting
Overfitting什麼時候會發生呢，當我們有太多的power，然後呢我們的- 資料裏面
量又不夠多，然後又有stochastic或者是deterministic noise的時候
那overfitting就很有可能會發生，那我們今天要講的regularizati- on可以看成是對付overfitting的一個方法
那我們會先講到說它的數學式子的推導是怎麼樣，然後把它延伸到各種不同的regular- ize的方法上面
好，那我們來看看，我們上一次講到overfitting，我們畫的這個圖是典型的ov- erfitting的情形
我們的資料量沒有很多，然後呢但是我們用了 一個例如說四次多項式，更高次方多項式去fit它，然後
這時候我們把Ein做的很低，這條紅色的線統統穿過我們的資料，但是 Eout，也就是紅色的線跟藍色的線距離卻非常的大
那我們今天要做的就是要從這樣不好的狀況變成
左邊這樣的狀況，左邊這個我們叫做regularized fit，這個規則化
規則化的fit，那我們等一下會說到規則到底是怎麼樣子，大家注意到在這個圖裏面的特點- 是什麼，這個圖裏面特點
是這個紅線比起右邊那邊要平滑的多 那平滑以後也就比較貼近我們想要的
藍色的這個目標函數。那我們這樣是怎麼做到的呢？大家如果還有印象的話，實際上我們在上- 一次上課
就show過這兩個圖，右邊這個是一個四次多項式或者是高次多項式 做出來的，左邊是一個比較低次的多項式做出來的
所以我們需要做的事情就是這樣，我們需要做的事情就是從高次多項式的hypothesis set 好像走回去到低次多項式的hypothesis
set，okay，也就是說大家如果還記得的話，我們說 例如說我們如果今天是用多項式的時候，hypothesis
set之間是有一個一層一層的關係 好，低次方的會被包在高次方的裏面
那如果說我們今天用很大的hypothesis set，高次方的hypothesis
set會有問題的話，我們是 不是，稍微勸說自己從這個很大的圈圈裏面走回來走到一個比較小的圈圈裏面
這樣子就不會有overfitting的發生，這是我們主要的idea
那這個regularize規則化這個名字呢是來自於早期在做所謂的 function
approximation，也就是說我們要想辦法逼近某個函數，像我們迴歸分析也是一-
個逼近某個函數的方式 然後呢，approximation的時候大家發現說很多的問題是所謂的ill-pos-
ed，ill-posed的意思 實際上是有很多的函數都滿足我們想要的solution，但是我們不知道要選擇哪一個
於是呢我們就必須要限縮一下，不然的話解太多會造成 一些問題。那我們今天做regression，同樣某種角度也是一個解太多問題
我們就只有有限多個點，要穿過這些點的函數非常非常的多，那我們要從，怎麼從裏面
限縮自己去選擇出一個比較好的函數，這是regularization要做的事情
好，所以我們現在問題是這樣啊，怎麼樣從高次 那我們這裡用10次做例子，怎麼樣從10次多項式走回到
兩次的多項式去，怎麼從高次方走到低次方去 好，要做到這件事情呢，我們就來看看我們還是用我們蠻熟悉的
這個多項式的轉換還有linear regression來做例子
那在這邊呢，我們本來在我們本來的notation裏面呢轉換然後再做linear regression
linear regression的這個weight，我們用這個w上面加上一個小蚯蚓來表示
用這個代表說我們在那個彎彎曲曲的z的那個空間裏面，但是呢
在這堂課裏面，為了簡單起見，為了不要讓大家看一堆的小蚯蚓在那邊飛來飛去
所以我們一律用w來代，就是不加上小蚯蚓的w來代表
說我們在轉換之後在那個z空間裏面找到的這個weight 好，那我們來看看，所以如果我們用這樣表示
的話，我今天是十次多項式hypothesis長什麼樣子 它就有11個weight，w0、w1、w2一路到
w10，好，有11個weight，它裏面的每一個hypothesis，我的hypo- thesis set 裏面的每一個hypothesis都長這個樣子
那今天如果是二次多項式呢，大家想那很簡單，二次多項式就是只有三個系數而已
w0、w1、w2，好所以我列在這邊，這對大家來說應該是簡單的式子
那所以我們從這裡看出什麼事情來 我們看出來事情就是所有的二次多项式
實際上就只是十次多項式加上一些限制，什麼限制？在我們這裡就是
三次的weight，四次的weight，五次的weight，一路到十次的weigh- t，w3、w4一路到w10統統
都要是0，對不對，統統都是0就相當於用什麼把它遮起來，所以我就只有一個二次多項式
這兩個hypothesis的關係是什麼，H2為什麼 包含在H10裏面，因為H2就是H10
加上了我後面列紅色的這個條件，這個條件是 w3、w4、一路到w10統統都要是0
好，所以什麼叫從10號走回去2號，什麼叫從十次多项式 走回去二次多項式，實際上就是代表我想要在
我的learning問題上面加上所謂的constraint，加上一些條件，那我這邊
的條件是一個很特殊的條件，3號、4號、5號一路到10號的weight統統都要是0 也就是說什麼，如果我們今天從
我們要解的問題，我們最佳化裏面要解什麼？我們要minimize Ein 如果要找一個最好的十次多項式來minimize
Ein，這個沒有問題，大家現在已經很熟悉了 我的十次多項式就是有11個系數，然後呢我來minimize
Ein想辦法 找出最好的這11個w的組合，來讓我的Ein整個來說最小
那如果我今天我要找出一個最好的二次多項式，我要怎麼做呢？我可以把我的 hypothesis
set想成說，我跟那個十次的一樣，我都考慮11維的w的向量 然後但是我在hypothesis
set裏面加上那個條件說 後面那些維度我強制你一定要是0，你不可以是其他數字
轉化成最佳化的問題，轉換成如果我要在這個 hypothesis
set裏面去minimize Ein的話，我會去做什麼？ 我可以寫下來事情是，我一樣minimize
Ein，但是我下面要加上一條 constraint，這個constraint就是w3、w4、w5，一路到w10
統統都要是0。好，所以這跟左邊是對照的，左邊是我不加任何條件限制，反正 我就是11維的向量，任何11維的向量，只要你能夠把Ein
minimize都是好的向量 後面那個呢，右面那個呢，我們說我不是任何11維的向量都是好的
向量，如果你今天這11維的向量沒有滿足我的條件，我連看都不看，我連收都不收
我要在所有符合我的條件的向量裏面，找一個最好的向量
好，也就是說我今天想要找一個好的二次多項式
相當於我是找一個好的十次多項式，但是加上條件
我要從十次走回二次這件事情就是我在解Ein的問題上面加上條件
你說老師啊，幹嘛你弄得這麼麻煩啊，為什麼你不直接，既然你要解二次多項式
你就用三個系數就好，要解十次多項式，你就用11個系數，要解幾次多項式，你就用多少個- 系數就好
你幹嘛要好像繞了一大圈說，把二次多項式 表示成十次多項式，再說我要把你們統統設成0，這樣不是很麻煩嗎？
好，我們之所以跨出這一步的目的是希望 能夠拓展我們的視野，讓我們在推導後面的問題的時候
會變得容易一些，什麼意思呢？我們就來看，所以這是我們二次多項式，解
二次多項式的問題，我們說我們還是在一個11度的空間裏面，但是加上了一些條件
如果我現在把這個條件稍微放鬆一點怎麼樣
我這邊條件實際上說什麼，我這邊條件就是說今天把 w3、w4、一直到w10這八個人一定要是0
特定的這八個，這八個w一定要是0哦 那如果我今天不要說特定的八個w一定要是0
我說只要有八個w是0就好 所以你要3號到10號是0，沒意見，1號到8號是0，沒意見
1、3、5、7什麼什麼任何8個人是0，沒有意見，9個人是0，沒意見，10個人是0，- 沒有意見 我把我的條件放松一點點好不好？
也就是說，我今天不，不追求說，我一定要特定的8個人是0，特定二次多項式。
我是任意的8個人是0，於是我可能是很多次的多項式。
不是很多次的多項式裏面，因爲只有少少的系數，所以你可以想成我的Hypothesis- ，看起來
會跟二次多項式有類似的簡單。OK，因爲，也有很多的項都是0，你只能用少數的項，
來組成你的多項式。那你的多項式看起來應該會比較簡單一些。
變成[iii]問題要怎麽樣，所以一樣，我們前面的部分都一樣，Minmax Ein
現在只是條件寫的方式不一樣。我們的條件怎麽樣寫，我們的條件寫下來的方式是說，
哎，好，那我們接下來看，算一算，不等于0的人到底有多少個。
對不對，好，所以我這邊有一個[iii]的Operation ，這個[iii]Operation 是說，不等于0的人到底有多少個。不等于0
的到底有多少個之後，我可以做什麽？我可以說，哎，那，我我既然這個等于0的至少要8個， 那不等于0的最多最多就是3個。
好，所以，我要用，OK，最多最多3個系數，來描述 我的Hypothesis
Set，其他的系數，通通都是設成0，也就是說，有點像，我根本就 不考慮它。好，這個Hypothesis
Set，OK，今天我們叫做H2的Pron， 只是爲了跟我剛才那個H2二次多項式的，稍微做一點點連接。
我們如果把這個Hypothesis Set，跟我們剛才所知道的H2跟H10來作比較，
會發生什麽事呢？好，我們看到，這個Hypothesis Set比H2要寬松一些。
爲什麽？好，因爲任何一個滿足H2條件的，他說3號到10號，他說那要是0。
也滿足H2 Pron條件，也就是說，任何一個左邊的Hypothesis在右邊，哎，是個滿足條件-
的好學生。
但是呢，它又沒有H10那麽包山包海，H10說所有任何
的系數都可以，現在沒有，我們還是加上了條件，說你一定至少至少要有8個W是0。
好，所以這有點像是H2跟H10之間，冒出來的一個中間選項，OK，我們會比
H2更Flexible一點，然後但是，不會像H10 那麽的Powerful，也就是說，也許不會那麽容易的Overfit。
好，所以呢，這個時候，好，我們就想，哎，那我們可不可以解這個Optimizatio-
n問題？ 解出來一個好的W，然後這個W未來可以用，例如說，這個W會有什麽特性？
它因爲有很多個是0，只有3個不是0，所以未來，拿這個W去做預測的時候。哎，很快，
因爲我只要算，例如說，3項的值，然後加起來，我就輸出去。我不用算10個值，再加起來- ，再輸出去。
這種的W，我們叫做一個Sparse Hypothesis，OK，也就是說，它有很多0，
OK，然後只有少數的不是0。那這樣的Hypothesis，我們叫做Sparse。
好，所以這個Hypothesis Set看起來很誘人。不過呢，壞消息是這樣，
大家看看我們右邊的這個Optimization的問題，這個Optimization- 的問題裏面，我們
下的Constraint是說，最多最多有3個不是0。這Constraint裏面- 有什麽？
有一個這個，我們所熟悉的[iii]的Operation，這個是用來什麽？算一算你到- 底是0，還是不是0。
好，那大家現在跟Machine Learning，已經開始有點混熟了，有點經驗了，你應該可以
感覺到，當我們看到這個[iii]Operation的時候，我們什麽時候第一次看到？- 在Perceptron那邊第一次看到。
看到這個的時候，就會想到因爲它是一個Discrete 函數等等的，所以它的最佳化可能是困難的。
好，怎麽樣困難，我們可以跟大家說，這個問題，要怎麽樣找出
一個好的Sparse的W，也被證明是NP-hard問題。
好，所以這個問題，不是那麽容易見，OK，雖然說，哎，我們看起來不錯，我們不是真正的- 要做一個二次多項式，我們稍微放寬一點。
OK，然後看起來賺到一些好處，是說，例如說，我未來跟二次多項式 一樣，我只要算3項，我就可以輸出答案，哎，看起來有點好處。
但是，我們不是很容易解這個問題。
那不容易解這個問題怎麽辦？我們能不能 來解一些我們可能比較會解的問題？
好，所以左邊是那個我們不太會，或至少不太會用有效的方法解決的問題。
我先列一個新的問題是這樣，如果我今天做的事情是，好，我還是Minmax Ein，
不過呢，我把我的條件換掉。
我剛才左邊的條件是什麽？我左邊的條件是，算一算，有多少不是0的人，
有任何一個不是0的W，我就把它算成1，然後呢我說，這些數字加加起來，
要小于等于3。我現在做一個類似的條件是這樣，
我算一算，OK，對我的所有的W算一算。不過呢，爲了要避開
這個，剛才這個Discrete的部分，我說我算一算的時候，我算W的
大小，我不要算說它到底是不是0。好，反正呢，是0的或很接近0的，就會很小，然後呢，
不是0的，就會很大。好，所以呢，我算一算，我算的時候，我是加W的平方。
也就是說，我這邊看每一個W，然後我算它的平方，加加加加加起來，好，那我剛才說，我算- 一算，最多，
要3個人不是0。我現在說，這個加加起來，我假設給它一個我心裏的上限，這個上限是一個
哎，已經設定好的數字，好，我把它叫做C，好，例如說，我可能說，我的上限 叫做13，或我的上限叫做15，或者我的上限叫11.7，
好，這樣的上限。所以我可以想象這是一個類似 的最佳化的問題。或者對應的Hypothesis
Set會長什麽樣子， 會長這個樣子。我說，我考慮所有的W。不過呢，
我希望，這些W裏面，所有的它的Wq的平方加起來，
都要小于等于C。也就是說，我的W的長度的平方要小于等于C。
我把這樣的Hypothesis Set叫做H(C)，OK，代表這個C就代表說，哎，它跟
C有關，我設定一個C的數字，我就會跑出來說，我的H(C)長什麽樣子。
好，那我們來看看。H(C)跟H2 Pron有什麽關系呢？ 它們兩個應該是有一些Overlap的。
Overlap的意思是，哎，如果我今天有一個滿足H pron條件的，
它真的很Sparse ，它真的只有少數的W，這個，
不是0的話，哎，那麽它的平方加起來，應該也 不太大。所以這個Hypothesis很有可能會包含在H(C)裏面。
好，我今天是一個在H(C)裏面也有一些Hypothesis是，哎，很少很少的
W，不是0，然後只有，有很多的W是0，所以這樣的Hypothesis， 也會包含在H2
Pron裏面，所以，這兩個Hypothesis Set是有Overlap的。
不過呢，大家當然可以想象，不是一定是這樣，舉例來說，我今天一個在H(C)裏面的
Hypothesis可能它的每個W都很小很小很小，但是不是0，對，那這樣的Hypo- thesis
就不會在H2 Pron裏面。好，不過H(C)是有個好處的。跟我們剛才說
這個，H2，H3，H4，啊，這樣一路到H10，有一個，這個重疊的這個關系。
那麽，這個H(C)之間呢，也有重疊關系，而且呢，這個重疊關系是因爲，C這個數字，
那C這個數字是個實數，所以我們等于是有無限多種的Hypothesis
Set互相的重疊， 按照C的數字，從小排到大。OK，那這個C很小的時候，Hypothesis
Set很小，就被包在最裏面，C很大的時候， Hypothesis Set很大就在比較外面。如果我今天C是無限大呢，
就好像，我根本就沒有條件一樣，根本就沒有條件， 那就是我原來，最大最大那個Hypothesis Set，也就是H10的部分。
好，所以，我們把這樣的Hypothesis，H(C)這樣的Hypothesis Set，叫做一個Regularized
Hypothesis Set，OK，規則化，規則化實際上就是，加上條件的Hypothesis Set。
加上這個條件的Hypothesis Set，如果我們能夠順利的解決，右邊的那個最佳化問題，
找出一個這個好的W話，我把這個W叫做W的REG。
就是在我們的規則，或在我們的條件下，找出來的Hypothesis。
好，那我們來看看，我們剛才定義了這個H(C)，那我這邊想要問大家
說，如果我今天考慮的是H1的話，也就是我的C的條件是1。
那請問，下面的哪一個Hypothesis不會在這個Hypothesis Set裏面。
好，那大家想一想之後，我希望大家得到，正確的答案
是3。那因爲呢，你如果去把3這個向量的這個長度的平方算一算的話，
你會發現，這個向量長度的平方是Q+1，那這Q+1是比1來得大的。
所以，它不會在我們的Hypothesis Set裏面。
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
