好，那我們來看看，我剛介紹了Linear Regression的這個演算法， 大部分的同學, 學到這裡腦袋裡都會浮現一個疑問，說 這真的是機器學習嗎？老師你騙我吧？你不是介紹我機器學習一個演算法吧？ 怎麼會有一個演算法好像有一種一步登天的感覺？ 它一下子就算出結果，這種我們一般叫做 analytic solution,也就是分析出來的結果。 它一下子就算出結果了，instantaneous, 一下子就算出來了。 好像沒有感覺它在學習呀，或者是說好像，好像這是一個非常聰明的 演算、 非常聰明的電腦，它一下子就告訴你答案，你沒有看到它學習的過程， 好像很不心安，有時候我們也把這個叫做一個closed-form 的 solution 也就是我有一個公式可以寫出來說，到底它的解是什麼樣子？ 你說這真的是機器學習嗎？好那或者說, 我們根本沒有觀察到我們說以前說機器學習的定義 的時候我們說，咦好像應該要隨著我們所看到的資料然後要有所進 步等等，我們現在也沒有看到它進步啊，Ein也沒有進步，Eout也沒有進步，而且都 沒有給我們w, 然後就好像很帥氣的說，哎呀好這個 w 就是最佳解了，結束了，你不用，你不用再煩我了。 好，Linear Regression 這個演算法，到底能不能算的是一個機械學習的演算法？ 好，那我們跟大家講的事情是這樣。 從某些角度來看, 我們可以把它算的上是機械學習的演算法，什麼意思呢？它有好的Ein。 好，我們說了我們這個整個解，我們很輕易地就解到最好的那個Ein。 它有好的Ein，所以相對於，好例如說你亂猜一個w你的確得到了一個好的Ein。 你能夠保證它有好的Eout，如果你相信我們對VC的這些分析，然後你對VC的這些哲學- 性的想法 的話，你說我們就只有d+1個變數而已，所以只要我的資料量夠多 我能夠保證說，誒我用這些資料所觀察出來了它既然有好的Ein， 它就會延伸到好的Eout，好所以, 如果你相信VC的那些解釋的話，我們可以說它有好的Ein也有好的Eout。 然後更重要另外一件事情是什麼？哎你說這個演算法看起來一步登天。 啊一步登天是你看起來的，實際上你如果了解, 例如說pseudo-inverse 或者是好你要算那個inverse是怎樣算出來的話？ 你可能會發現什麼？可能會發現說實際上你如果把你在算那個inverse的過程，好把它- 當成一些 中間暫時的步驟的話，這些步驟裡面好像 你的Ein或你的Eout的確是在跟隨這些步驟進步。 只是因為這些演算法實在是包的太好，所以你把它統統包包起來你還是覺得它好像一步登天，- 但是你例如 說，如果 iii系的同學可能就知道，你要怎麼算一個舉證和反舉證，好你說我這個所謂的高斯的 這個巧取法，好用這個高斯的方法的話，那麼我用這個方法 實際上它也是一個套一個for迴圈在那邊跑，也是一個一步一步的方法 所以你不能說，人家沒有一步一步就像沒有學到東西，實際上人家只是偷偷地一步一步學, 沒有讓你知道而已。 好那麼，總結來說是什麼，總結來說 實際上如果我們能夠說，這個方法的Eout是好的， 我們，我們從這個之前的理論分析，我們一再強調，我們其實最終的目標就是說Eout- 是好的。 所以不管它學習的過程是什麼，今天呢它是 回家躲在棉被裡偷偷學，還是它真的一步一步看書給你看，還是怎麼麼樣子，只要它最後的表- 現，最後 Eout裡面考試的表現是好的話我們就說，誒實際上這中間已經發生了學習這件事情。 好，所以接下來我們就來探討，剛才只是講說，VC可以可能幫助我們解釋說這個Eout- 會很小。 那我們先來看看另外一種解釋Eout為什麼可能會很小？好 我們先來看看另外一種怎麼保證Eout是好的方式，實際上我們會先從Ein出發， 然後呢，但是同樣的推導可以類似的用在推導Eout為甚麼是好的。 好我們要怎麼做呢？我們說我們要做的事情是看Ein的平均， 好，這跟VC做的事情不一樣，VC做的事情是看個別的Ein，我們先來看Ein的平均。 那因為Linear Regression的一些特性，因為它有這個analytical solution有能夠輕易地寫下這些舉證的解 所以就有人對這個Ein的平均還有我們之後寫對Eout的平均，做了一些分析，然後用- 這些分析 來justify說linear regression應該能夠work得很好。 好那說Ein的平均是什麼意思？我們說對什麼東西平均呢？對於我現在有資料，大家 記得我們資料就像從罐子里抓一把起來，我現在抓一把起來資料一號，再抓另一把起來 資料二號，我對於所有不同的資料，好這樣抓一把起來這個動作 做它的Ein的平均，這是我們現在有興趣算的事情。 好用力地算一算以後，之後會得到什麼呢？我們會得到說，誒這個Ein的平均大概長這- 個樣子。 好有兩個部分，第一個部分我們叫做noise level，noise level意思是說， 到底我的資料裡面有多少個雜訊，大家記得我們上次講到雜訊的時候說， 雜訊可以看成說，誒我們今天有一個distribution 來描述，這個distribution 上面有我們做得到的事情，就是這個最好的target function 跟我們做不到的事情, 這些, 一定會做錯的部分，好這是我們的雜訊。 然後呢雜訊的， 雜訊就可以想成我們一定做不到的部分，但是比雜訊稍微 小一點點，小多少呢？小d+1除以N那麼多。 好，這是我們等一下要證明的事情，大家記得d+1是什麼？d+1是我們的自由度，我們有- 多少個不同的w， 然後呢，N是什麼？N是我們的資料的量，所以你的資料量越多，那麼這個 呃差別就越小。 好你說，這一件事情要怎麼證明呢？我們要用到linear regression的一些性質， 那我們不會給大家完整的證明，但是我們會把證明裡面的一些大的概念跟大家講，也希望幫助- 大家更了解 linear regression 這個方法。 好怎麼做呢？我們先把我們的Ein 寫下來，好我拿到一個ϴz]我Ein到底長什麼樣子？我的Ein我們剛才說是y 減掉ŷ，ŷ是我們預測出來那個東西的平方，好這是Ein的這個定義。 好ŷ後面已經知道了，在上面給大家練習裡面我們已經知道ŷ長什麼樣子，所以我們是可以把- 它帶進去的， 好帶進去以後，好所以我就一樣我就得到一些，一堆的舉證啦，我還是用我原來的y 然後呢但是我ŷ部分，ŷ要兩個東西來表達，一個是我原來的y， 再來是我前面要乘上這個所謂X跟X的這個 dagger, dagger 我們這個dagger是pseudo-inverse就是這個虛擬的 這個反舉證的部分。 好那乘上這個之後我們怎麼樣呢？我們就可以說， 啊，所以我這整個裡面跟兩件事情有關，一個是我的Y是什麼？ 另外一個是什麼？另外一個則是identity，identity是，我今天就把Y，我- 的Y複製一份，還 有那個X乘上這個X的虛假的反舉證這個東西，好我把，如果把它提出來的話， 所以我就看到說，我最後是裡面有兩項，一個是identity減掉那兩個X相乘的東西， 然後另外一項則是我的Y的部分，這個有點像把輸入跟輸出的部分 分開，在這個error的式子裡面做表達。 好那我們會把X乘上X†就是乘上 X的這個pseudo-inverse這個東西，我們把它叫做hat。 為什麼把它叫做hat? 好我們把它取個名字叫h, 叫hat matrix。 這是統計學裡面的人說，好為什麼叫這個，因為很簡單啊，我們有個Y 然後呢如果這個Y乘上這個hat matrix以後，它頭上就長出一個帽子來了，那麼就變成了Y-hat， 好所以，我們很簡單意思大家很容易記，我們把這個舉證就叫做hat matrix，Ok帽子 舉證，這是統計裡面的人取出來的名字。 好這個 hat 舉證做什麼事情呢？我們用這張圖來跟大家解釋。 這張圖裡面講什麼呢？這張圖裡面講說， 哎,我今天如果在一個N維的空間里， 我看到是什麼事情, 好什麼叫N維的空間，首先我的Y是在一個N維的空間里的向量， 對吧，有Y1、 Y2、 一直到YN，Y是在一個N維空間裡的向量， 好我在一個N維空間裡的向量，然後呢我現在在想 我要做預測我的Y-hat，我的Y-hat在哪裡？我的Y-hat是拿X那個舉證 乘上我的w, Ok，我最後是乘上這個linear regression得到的 w但是，在還沒有做linear regression之前，我可能會乘上任何w。 這些任何的w做的事情是什麼？就是把X這個舉證它的每一個column， 拿來做線形組合，它每一個column也是一個N維的向量，拿來做線形 組合，w這個向量做的事情就是，把那些每一個column的向量做線形組合。 做線形組合以後，大家學過線形代數就知道，所以它會對應到什麼？對應到我這邊畫粉紅色的- 這一塊， 說誒, 我把X用一個column做這個，展開做這個span的動作， 然後呢, 我的Y-hat會落在這個span 的裡面。 好，所以幾何上來說，我們就了解了三件事情，一件是我的Y原來是一個N維的向量， 再來我的X，我拿iii column來我可以展開成在這個N維度裡面一個小的空間， 然後我的y-hat，會在這個空間裡面。 好那我們linear regression要做 說什麼大家記不記得，我們希望y 跟ŷ 的差別越小越好。 什麼叫越小越好，我今天如果展開一個線性空間，然後我外面有一個項量， 越小越好代表我要做的事情是什麼?我要投影到這個線性空間裏面，或 者說我投上去，所以我的y-ŷ 這些我們知道餘數或餘數相連餘數的項量的部分 就要垂直于我的這個粉紅色的空間，這是從這個圖像大家 也看的很清楚，我如果要 y-ŷ 越小越好的話那麼我做的 最好的事情就是我做一個垂直的投影下去，然後那樣，那一段就是我會得到最小的值。 好，所以h這個舉證做的是什麼事情，h做的是投影啊，對不對? 投影是一個線性 變化，h把它乘在y的前面，就變成ŷ，ok 所以 h 做的事情就是把任何一個項量 投影到x所展開的那個空間裏面。 那另外來說，i 減h做的是什麼事情，i 減h就變成它也是一個線性變化，h做了一個投影，然 後 i 把它減掉，所以等於我們是在求所謂的餘數的部分，求到y 減 ŷ 那個餘數的部分，所以任何一個項量我們要求對於某一個空間，對於這個x的空間 的餘數在哪裡，這個剩下的項量在哪裡的話，我們接著用i 減h這個項量，這個轉換來 求這一件事情。 那只是幫大家複習說你線性代數裏面概念告訴你的一些事情。 好那我們大體上來提一下，這些事情大概需要數學上驗證，不過呢如果我們 去衡量說 i減h 這個項量它的trace，trace就是對角線上所有值加起來是多少的話， 大家如果用力的去算一算，會發現它加起來的值是n，n就是 ok 我們有多少資料減掉d+1,d+1 就是我們有多少的w這個變數。 好, 在證明這個之前我只是想跟大家講說這個的物理意義喔，大家私底下可以去把這個證明寫下來- ，這個物理意義是什麼? 物理意義就是我們原來有一個有n個自由度的項量所以在這個n緯的空間裏面轉來轉去 現在我們要把它投影到一個d+1維的空間，因為x由d+1個項量展開，最多最多就是- d+1維 投影到一個d+1維的空間，然後取餘數，所以我餘數剩下的自由度 最多最多就只有n減掉d+1這麼多。 概念上是這樣，當然大家要做詳細的數學證理，就是我希望大家有這樣一個概念，我們就可以- 幫助大家 瞭解我們接下來要揮一揮手跟大家講的說那個Ein的平均 到底是怎麼一回事。 好，這個平均是怎麼一回事。 我們來想一件事情，如果我們今天有一個理想，最理想的那個target的function 最理想的target function當然會落在哪裡，會落在我們這個x所展開的地方。 好, 落在x所展開的地方的話，所以我可以把我看到的 y想成從這個理想的target function出發，從這個 最理想的一堆預測出發，加上某一群的 noise,對吧，好,我在這個平面上加上某個noise,這是我實際上看到的y,這是- 我們從上一次 說今天在有雜訊狀況下我們怎麼做學習的時候，我們描述說我們從一個target function出發，加上一個noise 我們就會得到我們真正看到的label，所以我們真正看到的label可以被 描述成我們的目標函數加上noise，這是我們看到的label。 好，圖裏畫這件事情。 好, 這個noise是發生什麼事呢，注意到我們算Ein 的時候算的是什麼 跟上一張圖一樣，我們算Ein的時候算的是y-ŷ在哪裡，y-ŷ是什麼 垂直于這個平面的,的,的,的那個g，那個我們永遠做不到的那個g。 那所以另外一個看這個事情的角度是什麼？我如果把noise 同樣地做對這個平面的這個餘數的這個轉換，大家記得做餘數的轉換用什麼，用i-h。 我同樣做這個轉換的話我也會得到綠色的這條虛線。 也就是說我今天要求的Ein 其實就是把i-h 這個線性的變換用在我們剛才講的那些雜訊上面，我就可以得到綠色的那一條線。 那事實上寫下來就是我的Ein,Ein是綠色那條線長度的平方再除以n 那實際上是把i-h這個線性變化的 舉證用在我剛才講的那個雜訊向量上。 事實上就這樣，上面那個圖告訴我們的就是這一件事情。 那有了這件事情以後我們就可以概略地解釋那個Ein的平均是怎麼來的。 什麼意思呢？ 大家記不記得我們說我們的i-h有多少的自由度，有多少的這個trace，或者有多少- 的能量。 它的能量最多最多就是N-(d+1)這麼多，所以我們把這個 noise做個投影，然後有N-(d+1）這個能量全部再除上N， noise因為是亂亂的，是我們沒有辦法掌控的, 所以noise 的, 這是noise的能量。 這是我們做投影的時候發生的事情，這樣的式子列下來，然後我們對 noise做平均的話，我們就可以得到Ein的平均 是noise level，所以這是對所有的各種亂亂的noise做平均的結 果，然後乘上前面的那些東西怎麼來的，前面的那些東西就是我的N-(d+1)，然後 跟N做平均，所以這個式子是從這裡跑出來的。 好Ein可以這樣算，你如果認真的去算的話Eout也可以 類似的算，只是比較複雜一點，你會得到一個很有趣的事情，Eout 的平均也是一樣noise，也是一樣乘上1，不過現在不是 減掉後面那個數字而是加上後面那個數字。 哲學上的意義是什麼，Ein是你看到的東西, 所以就算你有noise 你看到的那一條線會往noise那邊偏一點點，會讓你的Ein好看一點點。 好那個減掉d+1除以n，那個是讓你的Ein好看一點點 那為什麼Eout是加，因為你要看新的資料，新的資料，你往左邊偏，結果新的資料的雜訊 是在右邊的話，那麼一來一往，你就可能有這個兩倍的這個差均，所以如果你要看Eout- 的話，它 會比最好的那個還要再往另外一邊再偏一點點。 好,所以，從這個Ein跟Eout式子我們就可以畫出一個圖，這個圖 通常我們叫做learning curve，它描述的是什麼，它描述的是我們有多少的資料量。 跟我們平均可以得到的Eout跟Ein的關係，當然從VC bound 我們也要畫一個類似的圖，只是VC bound裏面就不是平均，我們這邊畫的是平均的圖。 所以如果我們看平均的Eout的話，它會從很大的地方，因為它是加上去的，OK，然後你- 資料少的時候 它會加一個很大的項上去，你資料越多越多越多的時候，n變的很大，d+1是一個固定的數- ，所以最後 會變到哪裡，變到我們叫做Σ平方也就是你的noise的地方。 那Ein呢，Ein則是從下面慢慢地長上去然後最多長到這個Σ的平方。 好，至少這個分析告訴我們這件事，當然我們可以詳細的去推導這個分析，只是我覺得細節數學 不是很重要，我希望大家腦袋裏是一些有這個事情的幾何意義還有物理意義，物理意義說什麼? 我今天只有n個點，所以我的線會往我的n個點偏一點點，這個偏一點點讓我的Ein 小一點點。 但是如果我今天是Eout的話，我是看例如說像另外的n個點，另外的n個點的話 可能我的Eout實際上會比我做到的還要大一點點，因為我的線已經偏走了，我 線已經偏走的話，那你Eout出來那個東西就會再遠一點點。 好，那所以所謂的generalization error就是Ein跟Eout到底差多少，平均來說 就大概是兩倍的d+1除以n。 好，那這跟VC給我們的保證不太一樣，VC說最壞最壞的情形怎麼樣， 這跟我們說是平均的情形怎麼樣，不過呢兩個保證是類似的，OK注意到, 大家記得話，在 我今天有d+1個自由度的時候，VC demension大概也是d+1,然後呢，那這個除以n，隨著n變小這件事情 跟VC所講的事情是差不多的，好所以我們看到說 哎, linear regression我們剛才花了大半天講說linear regression到底是不是learning啊？ 從這些結果，你相信VC的結果或你相信我們推導這個平均 Eout的結果的話,你應該有理由相信當你的n夠大的時候 我們已經想辦法做得盡可能好，什麼叫做盡可能好，就跟noise的這個level 做的是差不多的，所以在這樣狀況下，如果你noise不是太多的話，那麼學習真的已經 發生了。 好，那我們剛才講这個hat magic 這個帽子的这个举证 这帽子的举证其实有很多很有趣的幸事，那大家可以做數學上的推導，不過我們這邊不是要求- 大家一定要做數學上的推導， 我們要大家說哎, 用你對線性代數的一些直覺上的想法來 想一想說, 這四個選項到底哪一個不是對的。 好那大家想一想之後我希望大家能夠選到正確 的答案說哎,今天，這個第四個選項不是對的，一二三其實都是對的。 一二三說什麼，好第一個它是對稱的，對稱的就比較容易答, 大家從它的式子，大概就可以看得出來它是一個對稱的舉證。 二三呢，你實際上要證明，但是我不希望大家去證明，二三說什麼? 第二個選項說, 哎你如果今天是h的平方等於h，這代表什麼? 你做了兩次投影，你會投到同樣的地方。 哎, 這當然啊, 你做一次投影 已經在那空間裏，已經在那個空間裏，你再做一次投影不會有任何好處。 那第三個選項是類似的說你做兩次轉換, 取餘數的那個轉換, 你會得到同樣的東西，這也是類似的，你已經取 了一次餘數，你取到那個東西已經跟你的那個空間垂直了，你取第二次餘數的話你還是會得到- 一模一樣的向量。 這些是，這些式子，這些線性代數的式子的物理意義。
