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. [機器學習旨在讓電腦能由資料中累積的經驗來自我進步。我們的兩項姊妹課程將介紹各領域中的機器學習使用者都應該知道的基礎演算法、理論及實務工具。本課程將較為著重方法類的工具，而另一課程將較為著重數學類的工具。]
Leave-One-Out Cross Validation
Loading...
En provenance du cours de National Taiwan University
機器學習基石下 (Machine Learning Foundations)---Algorithmic Foundations
142 notes
À partir de la leçon
第十五講: Validation
(crossly) reserve validation data to simulate testing procedure for model selection
Rencontrer les enseignants
林軒田教授 (Professor)
資訊工程學系 (Computer Science and Information Engineering)
好，那我們來看看，我們剛才說K又要大又要小，這當然是很難同時滿足的。
那麼現在先考慮一個極端的情形好了，說如果我的K非常非常非常的小
最小是多少？最小是1吧，K=1聽起來
我就可以讓什麼？我就可以讓我的g-跟g非常非常非常的接近。
現在面臨的問題是什麼？如果我要K=1的話，右邊那邊我希望K很大這件事情，也就是我要
我的validation的錯誤跟我的Eout非常接近這件事情就很難滿足了。
所以呢，這是問題所在，我們來看看我們能不能 克服這個問題，怎麼克服呢？我們先讓K=1的時候發生什麼事。
K=1的時候代表我從我的大N筆資料裏面我只留一筆資料出來做validation
那因為只留一筆資料做validation，所以我的validation錯誤，也就是- 我在我的validation錯誤上
面標一個小n，代表我留了第小n筆資料做validation。
然後呢，我把我的g-，在下邊加一個小n代表我 是用減掉小n的所有的資料訓練出的這個g-
那我就只要算什麼？我就只要算g-小n
然後呢在那一筆資料上看看它單一筆上面的這個error是多少，這就是我的valida- tion驗證的錯誤。
所以為了簡化這些符號，我就把這樣一個錯誤叫做小en
寫在這邊，小en這樣的錯誤，所以這是我的validation的錯誤，如果我今天只有- 一筆的驗證
資料的話，我的validation error就是小en 看我把哪一筆資料留著當validation。
那小en到底能不能告訴我們Eout有多好呢？例如只看一個小en當然不行
一個小en,例如說你做二元分類的話，一個小en不是零就是壹，你怎麼知道實際的Eou- t到底是32%
還是27%，還是多少。
不知道，但是如果我有很多個en的話
是不是就有可能可以告訴我說Eout是怎麼樣呢？
也就是說我如果，今天我的en是什麼，我把第n筆資料移掉看看錯誤怎麼樣。
如果今天把第一筆資料移掉，第二筆資料移掉，第三筆資料移掉，一筆一筆的移掉
然後把這些移掉以後，算出來的en把它平均起來 那它應該就可以大概告訴我說Eout是怎麼樣。
所以這個平均的錯誤我們把它叫做loocv,這個字是 loo是leave
one out，什麼意思，留一個起來當驗證資料。
所以leave one out的validation我用留下的那個當驗證資料，但是我做很多不同的
e1,e2,e3，然後呢把它們平均起來，這樣的東西叫做cross validation。
交叉的驗證，交叉什麼意思？我同一筆資料 有的時候當訓練資料，有的時候當測試資料，這是交叉部分。
然後我就把這些小e，剛才算出來這些小e平均起來 然後這個平均起來的值應該可以告訴我說到底我們的Eout
長什麼樣子，Eout什麼東西長什麼樣子？Eout(g)長什麼樣子。
因為現在每一個en是用不同的g-得到的，不是告訴我單一的
g-好或不好，它是告訴我說這個演算法在你的資料上到
底表現的好不好，例如說它最想告訴我們的是左邊這個Eout(g)
也就是說今天，我們希望的事情是今天我做了這樣 的程序，leave one
out cross validation之後，我最後得到衡量跟我Eout真正的g 是接近的。
我們現在看看這個過程到底是什麼意思，我們想像我們有三個點
這三個點，然後呢我如果要跑剛才那個leave one out，一次留一個的過程的話
那我們看到說什麼，我們就說三個點移掉一個點我就剩下兩個點。
兩個點我如果做，意味著這個迴歸分析一定有一條直線就穿過這兩個
點，然後呢我把這一條直線跟第三個點的距離
做比較，嚴格來說是這個距離的平方的話那麼我就得到e1
然後呢，再來，再移開另外一個點，用另外兩個點做一條
直線然後看看它跟第三個點的距離是多少，我得到e2。
然後呢，同樣的事情，移掉另外一個點，用另外兩個點
做一個直線看看距離是多少，距離的平方是多少，我們得到e3。
這樣子我就可以算出來說我用e1、e2、e3去算出来 leave
one out cross validation的錯誤Eloocv到底是多少。
那我也可以做同樣的事情，但是現在不用一直線，我用一個常數
好不好，我用一個常數來代表說我的迴歸分析，不要做一直線我用一常數。
好那我今天如果只有倆個點，最好的常數是什麼，最好的常數是這兩個點的中間值
所以我可以來看看說我現在如果有一個新的模型，新的演算法是只輸出一個常數的hypot- hesis的
好，那我就一樣做一下，拿出兩個點來做訓練。
另外一個點做測試，看看距離的平方是多少。
然後再拿兩個點然後再做測試，看看距離的平方是多少。
再拿兩個點做測試，看看距離的平方是多少，就得到說如果我用 常數的模型的話我的leave
one out cross validation的錯誤到底是多少。
現在我怎麼做模型的選擇，我就看上面的跟下面的哪一個比較小
因為我們有一個平方牽扯在裏面，所以你可以看到這一項的平方 其實很大很大很大的，所以會告訴我們說上面那個
得到的平均錯誤應該比較高，下面這個比較低，所以它能夠幫助我們選到說你既然只有三個點- ，你用常數就好
你不要用那麼複雜的方法，線性的對你來說已經太複雜，用常數可能會 比較穩當的，說這是個比較好的模型。
好，那所以這是我們用leave one out 來做選擇，也就是什麼，我們剛才
在原來整個validation過程裏面，我要用來選擇那個Em
就是每一個model的error到底是多少，我本來是用validation錯誤來決- 定，現在
我可以用loocv leave one out cross validation 錯誤來決定。
決定完以後，你說我選擇37號模型，那你當然可以再用37號模型去做出你的g37
來，你之前做決定的時候你花的力氣是說我把這些leave one out cross
validation算出來 代替我原來說我留五分之一做validation這樣的動作。
那我們現在了解了leave one out cross validation的實務操作，我們來看看它帶給我
們什麼理論上的保證呢，或者我們最在乎的事情是它到底能不能告訴我們
Eout(g)有多好。好，我們說大概 是可以的，大概可以是什麼意思，我們來看看兩件事情。
一件事情是我有一個演算法，我有一個演算法我手上有1000筆資料
我說我把這1000筆資料拿來用這個演算法做leave one out cross validation。
所以用1000筆資料做leave one out cross validation
然後我對 各式各樣不同的1000筆資料來做，取一個平均
所以這是leave one out cross validation在1000筆資料上面的平均值。
這個東西我們等一下要證明跟什麼是一樣的呢？ 跟我如果把我的演算法拿來
然後呢我喂999筆資料給它 n-1筆資料給它，999筆資料給它然後
我算想像我能夠算它的Eout是多少。
我999筆資料喂給我的演算法得到一個g，嚴格來說得到一個g-
對吧，得到一個g-，然後呢g-的Eout的平均值是多少
也就是說這一項就是Eout （g-）的平均值。
所以呢，我們現在來看看說原來這兩項 是可以連接關係的，因為我們的g-跟g怎麼樣，
几乎一模一樣，一個是999筆資料做出來，一個是1000筆做出來，所以這樣 表示leave
one out可以几乎告訴我們g會表現的多好。
我們要怎麼樣證這件事情呢？注意到我們先從定義寫下來 定義裏面leave
one out cross validation就是我把它 對這個各種不同的leave
one out 的 錯誤，也就是說留下一個驗證的錯誤來做一個平均的動作
這樣，平均的動作寫下來之後呢我就可以寫到什麼？我們可以先用一些事情
例如說我可以先用說我今天做這個期望值的動作 期望值的動作是什麼？是線性的
summation也是線性的，所以我可以把期望值跟summation先做一個交換。
交換以後就怎麼樣？好我們來看看en。
en呢對於我的資料來說有兩個部分，第一個部分是對留下來的那個
example，另外一個部份是其他的就是用來做訓練的Dtrain 所以我其實是可以把這個expectation拆成兩個部份
一個ε是Dtrain 另外一個expectation是
今天我留下來的那筆資料。
對不對，好，我其他什麽事情都不動，只是暫時什麽事情都不動，我只是把
我的期望值拆成兩部份，因為我們ID的關係，所以這個期望值等等都可以這樣寫下來
好，那Dtrain的部份呢，我把它用一個比較簡單的寫法用Dn來代表
好，然後呢，當然留下來那個就是xn yn 那我這邊就可以寫什麽，我可以把小en的定義寫下來
小en是什麽，我今天有error 對不對，然後呢我有什麽，我今天有
gn減的xn 然後呢再來我要跟yn來做比較
對吧，gn減好這代表我用999筆做出來的 然後在xn上面，然後呢跟它的yn做比較
好，所以我這樣一路寫下來之後，我們先來看看這裡 這裡是什麽，
我已經有一個給定的gn減，這個紅色的gn減 是指跟我的這個大Dn有關哦，沒有跟其他東西有關
然後呢，我丟一筆一筆一筆一筆的新的測試資料 我現在把它叫做xn
yn，我把它叫x y也沒有差別 也就是說我今天是有一個固定的g然後在各式各樣不同的資料上面平均表現，這是什麽
這個就是Eout的gn減 對不對？gn減固定，你丟一筆一筆一筆各式各樣不同的
測試資料看它表現怎麼樣，這就是Eout的gn減 好然後呢，那這邊就有什麽，對各式
各樣不同的Dn把Eout gn減做平均，這就是什麽，這就是Eout
barred 大N 減1 ，999筆資料上的平均表現
好，所以我如果把這樣寫下來，好現在是一個常數然後再取平均 那當然就還是常數的本身，所以這個證明並沒有很難證
我們需要知道的意思是什麽，知道的意思是說所以leave-one-out cross
validation的期望值 跟Eout的期望值，或是Eout(g-)的期望值是類似的
所以這代表說我們得到了一個幾乎 完全不偏不倚可以告訴我們Eout
g 是多少的一個衡量方式，是leave-one-out的cross validation
好實務上，所以我們來看看了，leave-one-out的 cross
validation能夠幫助我們怎麼樣子 我們回到我們很熟悉的一個問題說，我今天要做這個手寫的辨識
然後呢，做一個問題是，我要辨識說是1還是不是1，然後把它用一些二維的feature來
表示，例如對稱性，還有例如說這個intensity，好就是有多少格子是黑色的這-
樣的事情 好那我們來考慮一些些不同的選擇方式，說什麽呢，說我今天要
拿這個這個兩個維度來做一些多項式的轉換
做多項式轉換以後，我要決定說我要從裏面使用
多少個unit，多少維度的多項式，或我要使用多少個轉換過的feature，然後看看- 它們的這個error是多少
好如果看Ein的話，當然是用越多越好，也就是我用越多我的error就越低，這就是藍- 色的這一條線
然後所以我如果拿Ein去做選擇，我會選到什麽，我會選到最高次
最多次的那個feature，然後我得到的分類的邊界就是這樣子好像有點彎彎曲曲
不太平滑的，但是我如果用看Eout呢，我如果看Eout的話，會看到我們有
我們先前說的，有一點點像在中間的某個值的Eout可能會比較好一些，你用太多的fea- ture
你會overfit等等，因為這是實務的資料，所以不像我們之前畫的一些平均的曲綫，這- 麼的平滑，但是你可以看到說
好的feature 的數量會在中間而不是真正用越多的轉換，越多的數量越好
那你看cross validation，看leave-one-out的cross validation的話呢，它會看起來可以給你的
黑色的這一條曲綫跟紅色的會稍微比較接近一點，所以你如果選一個leave-one- -out cross
validation最小的那個， 你會選到可能是5個feature，可能是7個feature，有一些重複的
當然你有一些選擇的自由度，那你會得到的曲綫是長這個樣子 好，你可以看到說這個曲綫看起來有一點點錯誤等等等等，但是
平滑了多了，避開了overfitting的問題，實物上的表現可以更好
好所以這是我們看到的事情，今天leave-one-out cross validation
會比Ein來的更有用，在選擇上來的更有用 好所以我們這邊呢再給大家一個小小的練習，
說我今天如果有三筆資料，然後呢它們有一些不同的y等等等等的
那我如果今天要算說，我如果是一個演算法這個演算法是
等於是輸出一個constant，OK，輸出一個最好的constant，那它的lea- ve-ont-out
cross validation的錯誤到底是多少 好那大家算一算之後，我希望大家能夠得到正確的答案是
4，好基本上這就是我們剛才畫給大家看的那個圖說，我們用兩個點
算一個平均值，然後在第三個點上測出它的錯誤是多少，然後 循環這個過程，然後最後再把所有的東西平均起來。
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
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.
