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. [機器學習旨在讓電腦能由資料中累積的經驗來自我進步。我們的兩項姊妹課程將介紹各領域中的機器學習使用者都應該知道的基礎演算法、理論及實務工具。本課程將較為著重方法類的工具，而另一課程將較為著重數學類的工具。]
Price of Nonlinear Transform
Loading...
Из курса от партнера National Taiwan University
機器學習基石下 (Machine Learning Foundations)---Algorithmic Foundations
142 оценки
National Taiwan University
142 оценки
Из урока
第十二講: Nonlinear Transformation
nonlinear model via nonlinear feature transform+linear model with price of model complexity
Познакомьтесь с преподавателями
林軒田教授 (Professor)
資訊工程學系 (Computer Science and Information Engineering)
你有這麼多個項的意思是什麼呢，所以如果我 今天要做很general一般的所謂的Q次
的多項式轉換，剛才是二次現在我們變成Q次，Q次的話 我就要列出來什麼，好，就我列出來的是這是到一次的部分
然後呢還要有二次的部分，所有的二次式 好，所有的三次式一路列出來，一路列到所有的Q次式，
這是所謂Q次的多項式轉換，我們需要的所有的式子，那怎麼樣呢
這裡面有多少個dimension呢，好，我們一般要算它這個Z有多長的時候 我們用1
加上d~來做代表，這個1特別把它獨立出來是因為，也
就有點像，我們之前在線性的模型裡面，那個d加1一樣，那個1代表的是常數的那個
然後其他非常數的有幾個dimension，我們把它叫做
d~，ok一樣加一個小蚯蚓代表我們是在Z空間裡面發生的事情，
這麼多個dimension到底有多少你呢，大家可以想象說 我需要什麼，我需要算的就是有多少種不同的方法
來組成Q，這個次方是Q或者小於等於Q那麼多的項
那這對應到，大家可能高中的時候學過，就是所謂的重複組合
我有d種不同的東西，我要取Q個出來，或者取小於等於Q個出來
請問有多少種取法，如果我允許這d種不同的東西我可以重複取的話，有多少種不同的取法
那大家可以去翻一翻高中的排列組合的書，那它會告訴你說
你的取法總共就是Q加d取Q這麼多
Okay，用二項式，Q加d取Q這二項式這麼多，或者Q加d取d這麼多
好，列出這樣的式子，是要告訴大家說如果我們把d看成一個常數，因為這是你資料裡面已經有
我們已經給定的話，那麼你使用什麼Q的這個 成長是什麼呢，大概就是這個Q的d次方
那也就是說，你就是付出Q的d次方，這麼多項
Q的d次方這麼多項代表什麼，代表今天就要花這麼多的力氣
在計算，計算什麼，你把X這個 送到Z要計算，就是說X是二維的，好Z那邊是六維的
好所以你要花一個六的力氣去做計算，你今天要算W 好算W不管你今天是pocket也好，linear
regression也好，logistic regression也好 好，你要算W至少至少你要花d~加1的力氣
去做更新吧，對不對POA，每次更新你就要花d~加1 的力氣
那這個linear regression 搞不好更慘，因為那個矩陣，那個矩陣是
d~加1乘上d~加1，然後你要做反矩陣的動作 好所以，計算上，你要花增加的力氣，
還有什麼要花增加的力氣，儲存上也要花增加的力氣，你只要把那個W 那個W~存起來，然後做對未來的預測
這個是要花力氣的，計算上儲存上，你都要花額外的力氣，在你的演算法裡面 所以使用這個變換並不是for
free 並不是這個沒有代價的，你的代價 之一就是你在計算上跟儲存上，要花額外的力氣
那如果你的Q很大的話，這一件事情是很困難的，因為你要你要儲存一個很長的向量，一萬維- ，兩萬維的向量
那可能是，你要更新這個向量，或者從最佳化的角度來說，你在那個
空間裡面要找到好的W~當做你的解，這些可能都是很困難的
好，那還有另外一個代價是這樣
我們剛才講了它有多少項，它有d~加1的那麼多項，這個大概是Q的d次方那麼多項
這同時也代表什麼，代表我就要有這麼多個
W，那我們之前說到這麼多的W大體上就代表這麼多
個自由度，也就是我的VCdimension大概就是d~加 1這麼多
不過啊，這下慘了，你原來linear model過得很好，只有d加1
那樣的自由度 你現在有d~加1那麼大的自由度，然後這個自由度，隨著這個Q是一路很快的長上去
這樣問題就出來啦，那怎麼辦呢 by
the way實際上我們可以證明的事情是，這個我們這個新增加的
自由度，最多最多是d~加1，我們沒有說，這個下限是，我上限是d~加1
為什麼，因為任何一個在Z空間裡面 的d加2個點，我們知道在Z空間裡面d~
加2個點是沒有任何一條直線沒有任何一個perceptron可以shatter的
對不對，這是之前已經證過的事情，Z空間裡面d加2個點，無論如何都不能被shatter
那這代表什麼，這代表我們回到X空間裡面 X空間裡面的d加2個點，也不能夠被
任何我們要用的Q次的曲線來shatter，如果那邊可以，我就找出一組係數，在Z空間- 裡面也可以shatter
那看起來是不對的，所以Z空間裡面不能shatter代表 我回到X空間，我也不能用Q次的曲線來做shatter
我這樣就對我們的VC dimension產生了一個限制，那在這邊呢，另外一個方向的部分
比較難證明，我們這邊不特別跟大家提，我們希望大家只記得是上限的部分，我們可能最多最多 要付出d~加2那樣的代價
好，這是所謂的model complexity的代價，也就是說我的Q變大的時候，我的VC
dimension也變大 那這一件事情有什麼壞處呢，我先問問
大家啦，我這邊列了兩張圖，同一個資料，兩種不同的分類方式
左邊那張圖說我用一條線來做分類，右邊那張圖 說我用一個四次曲線來做分類
右邊那張圖Ein是0，圈圈跟叉叉都分得很開，左邊那一張圖用一條線然後但是有幾個
圈圈有幾個叉叉，看起來是被擺在錯誤的那邊請問大家你要選哪一個
好，大部分的人看看之後可能會說，我們選左邊那個吧，左邊那個
視覺上來說，好像是比較符合我們對這個資料的特性的認知
右邊那個雖然Ein是0，但是可能太過頭了 對不對，可能這個有一些看起來顯然不太
合群的點，居然也被我們分隊，這樣的使用方式太過頭了 也就是說這是什麼呢，在回到我們之前講過的
說今天我們使用不同的hypothesis set 的時候 我們會冒出不同的問題來，它們對這個
我們在learning裡面，兩個核心的問題，Ein跟Eout接不接近 還有Ein夠不夠小，兩個問題的這個trade-off是不一樣的
我今天如果這個d~ 或者哪個是我用的Q這個變換是大的時候
大的時候怎麼樣，大的時候我就可以讓Ein還蠻小的，我開心因為它還蠻小的
但是另外一部分來說，我Ein跟Eout可能就會隔很遠，所以這是我沒有辦法滿足的-
好的地方 那另外呢，如果我今天d~是小的時候
那我就可以讓Ein跟Eout靠的很近，這裡很開心，可是另外一方面來說，Ein可能- 就會很大
所以一樣，我們再三的強調這是在machine learning裡面，最重要的一個trade-off
所以大家可能又會問啦，我們要怎麼選擇 適當的變換，我們要怎麼選擇到底我要用哪個φ呢
好，所以這是一個問題啦，那大家想不然這樣好了，我們剛才是怎麼選擇
要用φ1，φ1也就是我完全不做任何的轉換，或者我用所謂的一次轉換
然後還是我要選φ4，我說我是用眼睛來決定，那
就是說，我實務上我可不可以就用眼睛來決定我要用什麼轉換就好了
好，我先問大家，如果我今天給你的資料是在一個十度空間裡面
你真的有辦法用眼睛來決定嗎 好，至少我不行，我不知道大家可不可以，如果這個你幾何想像能力很厲害搞不好可以
但是我真的沒辦法，高維度的空間，我們大部分的時候用的資料都是高維度的資料 這個你要用視覺來決定，這個不太容易
然後即便在低維度的空間裡面，我們要跟大家講的是你用眼睛決定可能會有
一些潛在的問題，什麼意思呢，好例如說我們現在低維度的空間，想象我們覺得要用二次的曲線
二次曲線，我們之前說需要，如果我今天要用最一般的二次曲線
的話，我需要六種不同的變換方式放在同一個Z裡面，
好，你說用的這個，你找到了一個hypothesis
你用眼睛看一看，發現這個hypothesis它不用這麼複雜，它不用六個維度
說那我們可不可以用三個維度就好 也就是說我剛才原來要用這個VC
dimension等於6，也就是我要付出7 6的代價，現在呢，我付出VC
dimension等於3的代價就好 3的代價就是，你眼睛看一看，你剛才已經做過6了，然後你眼睛看一看說不用了不用了，我-
只需要3就好了 我是不是付出3的代價就好了，你說，啊，是這樣嗎？
那有一個更聰明的這個同學就說啦，哎，不然我們幹嘛要只付出3的代價？
我們付出2的代價好了。什麼意思？哎，反正我今天x1跟x2我如果要正圓的話
我只要算它們這個跟原點的距離的平方就好了。我們2的代價就好了。我第一維度的變換- 是常數。
第二維度的變換我不用一定死守著這個，嗯，一般的polynomial。
我說我有一個特別的polynomial，x1加x2的平方好不好？ 哦，乍看之下你好像從原來要－6的
model complication代價降到2個model complication代價。
說這樣可以嗎？大家心裡已經開始有個問號了。
那我要說，哎，好啦，我是老師，我來做最聰明的事情好了。
最聰明的事情就是，我直接使用一個z是長這個樣子。
我的z是把這個0.6，好然後跟這個x1的平方, x2的平方做相減，取了sign
當作我的變換。對吧？我的變換不一定要是多項式，我的變換也不一定要是平方函數啊。
我的變換可以加上sign，可以加上什麼？可以加上任何我覺得有道理的事情啊。
乾脆我做這樣的變換，我變到什麼？我的z變到1維空間。連那個加上的常數項都不用了。
哎，這樣我是不是只要付出VC dimension是1的代價？
聽起來太棒了吧！可是 你想一想，在我們剛才這個過程裡面，實際上是你做了什麼？
你聰明的小腦袋經過了一些運算，實際上經過了你聰明的小腦袋的學習過程
把適合的特徵變換用出來了，用在這一個資料上面。
這一個，這跟我們原來VC的推論裡面說，哎，我今天從某個distribution, 然後可能會產生很多種資料
然後我們要去算說，哎，到底我們什麼時候，有多少時候會運氣 好，產生說可以讓我們做學習的資料，什麼時候會運氣不好
產程說，哎，有時候會踩到地雷的資料。對不對？以前我們VC的分析是這樣。現在，你用你- 的小腦袋
做出了一個適合這個資料的 這個，嗯，transform的方式。這代表什麼？
你要付出的代價已經在你的小腦袋裡了。這已經不是 你說我幫機器省了力氣，對呀，這是你的human learning.
不是machine learning。也就是說你看過，你看過你的腦袋已經處理了。
你的腦袋做了human learning之後，再交給機器的東西，已經受到
你的腦袋裡的主觀的選擇的影響。
我們之前說，機器學習的那個這些代價從哪裡來？這些model complication
代價來自於我們要讓我們的演算法可以好好地做選擇。
你現在說，我做轉化我不用讓我演算法做選擇，我做選擇就好。
你做選擇好啊。可是你的腦袋做選擇，付出的這個代價要被算在
裡面啊，不然的話，哎，機器就賺到，也就是說你會太高估你的機器學習可以做到的事情 實際上，都是你聰明的腦袋做到的事情。
然後怎麼樣呢？你聰明的腦袋做到的事情，你如果沒有把它代價算進去的話，你就會太樂觀。
比如說，你做出來的結果，你說，哎，我這樣做e in很低啊，然後呢我用的VC dimension很小。
不不不不，不是這麼回事。因為你看起來用的VC dimension很小，只是因為你沒有把你腦袋裡的VC
dimension算進去而已。
然後你夠聰明的話，我相信你腦袋裡的VC dimension應該是還蠻大的。
對不對？因為你可以做到很多不同的分類的工作等等等等，所以
okay如果你沒有算進去你就會過份樂觀地估計你的機器學習的結果。
要跟大家說的重要的事情是
你要確保我們在VC這邊的推導等等等等都是正確的話，你要非常得小心。
你要非常得小心，不要讓你的視覺化或任何你聰明的決策進入這個
機器學習裡面。因為一旦這些視覺化的東西進來之後，一旦你偷看了資料再做決定之後
你這些決定付出的代價，你要小心地把它算進去，不然的話，哎，你會看起來你的
機器好像做得很好，結果最後，好，比如說你拿去投資股市，發現，哎，怎麼做都做不好。
為什麼？你沒有好好地把你這個付出的這個主觀的代價，或者是偏見或者是什麼東西
去算進去。好，所以我們這邊跟大家講了，說，哎，我們在做這個轉換需要
付出的代價到底是什麼？那我們這邊呢要大家來算一算，如果 我今天做一個q次polynomial這個多項式的變換的話。
那我剛才有算過說，我的d~，okay, 這個 z空間裡面的實際維度到底是長什麼樣子。那請問如果今天q等於
50，然後d等於2的時候，到底我們要大多大的空間去？
好那大家代進去算一算之後，應該會得到正確的答案是2.
啊，也就是說我們原來也只是 這個2維的空間，現在呢，我們到一個多少維的空間？我們到一個1000多維的空間裡面去。
然後我們可能要付出，在1000多維的空間裡面代價，這其中有一個重大的問題就是
你的資料量夠不夠支撐1000多維的空間。對不對？我們這裏說2維的空間，你可能20個- 點就夠了。
那1000維的空間，你的20個點是肯定不夠的，你真的有，哎，這個，1萬，1萬個點- 來幫助你
在1000維的空間做學習的動作嗎？好，這是個很大的問題。
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
