好，那所以從這裡出發呢，我們就跟大家講另外一個機器學習裡面的問題。我們剛剛學過，我們之前學過了二元分類那現在呢，不同的錯誤有不同的這個重要性，我們把它叫做「Weighted Classification」有重要性，weight 就是權重。這個 weight 跟我們這個 PLA 裡面那個線的那個 weight 不一樣，我們現在權重是在各種不同的情形下，有不同的權重。那像在我們剛才 CIA 這個例子裡面兩個情形，有一個情形的權重是 1，另外一個情形的權重其實是 1000 這種錯誤，比其他的錯誤貴 1000 倍。這就好像什麼好像大家在那個考卷上有沒有，有的題目配分比較重，有的題目配分是 1000 分，有的題目配分只有 1 分。好所以這是，每一個考試，或每一個 example，或每一個 case 有不同的這個配分好那這個 cost，OK 這個我們叫做 Cost Matrix，我們把它叫做成本的這個矩陣，那這個成本的矩陣呢，有人也把它叫做錯誤矩陣，也就是 Error Matrix，或者把它叫做 loss，loss 是損失的意思。那 cost, loss, error 其實對我們來說都是類似的意思，簡單來說是我們想要讓它越小越好，那你會在不同的書或者論文上看到不同的名字，但它們基本上代表的是類似的意思那在我們這個課裡面，我們盡量用 error，就是錯誤來代表那今天如果，我們剛才在剛才這個練習裡面有跟大家講過如果 CIA 在意的是這樣的錯誤矩陣的話那麼它的 E in，應該要長這個樣子，也就是說...對不起是它的 E out，應該要長這個樣子，說什麼呢說你看看，你的錯誤是發生在 y 等於正 1 的時候，還是 y 等於負 1 的時候。如果今天是 y 等於正 1 的時候，你就收 1 的錯誤費就好了，但是如果今天是 y 等於負 1 的時候，你就要扣他 1000 分，你就要扣 1000 的錯誤費那今天如果是 E in 的話，也是類似的，那差別只是我現在看的是 yn 跟 xn，而不是一般沒有看過的這個 y 跟 x 好那這種問題，我們把它叫做 Weighted Classification 這個 weight 也就是我們中間看到的這個部分說在不同的例子上，我們這邊的不同例子是，正 1 的例子跟負 1 的例子，我們算說它到底有多少錯誤這件事情的算法，是不一樣的。也就是說，好像有點像這樣我們現在是說 y x 例子，如果你今天有不同的顧客，不同的顧客有不同的重要性，這也是一種對不對，所以- 你在衡量每一個例子的時候，有的例子你給它權重高一點代表它比較重要，有的例子你給它權重低一點，代表它比較不重要好，那我們來看看，我們要怎麼樣解這樣的問題說解這樣的問題什麼意思？我們現在想，我們之前做過這麼多的推導等等我想像大家相信我說 VC 還是可以用 VC 還是可以用的話，我們就只剩下一個難題是什麼，我們要讓 E in 越小越好 E in 越小越好這樣的話，那麼如果 VC 可以用的話我們就有理由相信，跟它相關的 E out 也會是小的好所以這個 E in，跟我們原來使用 0/1 的時候的 E in 不太一樣，這個 E in 會把這些 weight，這些權重放進去，那為了區分，所以我把它叫做 E in w，OK 我在上面寫了一個 w 代表說它是一個有權重的版本。好那我要怎麼樣讓 E in 越小越好呢？我們來想想，我們學過些什麼演算法。我們學過 PLA PLA 要怎麼樣讓 E in w 越小越好呢 PLA 不管啊，你如果把 PLA 跑完，PLA 跑完以後 E in 是多少？E in 是零，原來的 E in 是零。 E in w 當然也是零，零就是最小的那個數字所以 PLA 根本不用管權重，你就讓它照跑就對了，照跑跑完了以後，你就會得到那個 E in 是零 E in w 是零的然後就開開心心的。不過大部分的時候不是這樣，例如說你如果今天不是線性可分的資料，那你的 PLA 跑不完怎麼辦你說那我看看我的 pocket 演算法好了，pocket 演算法裡面有什麼步驟跟原來的那個 0/1 跟 E in 有關的，你說跟原來0/1 E in 有關的，喔有啊，就是那個如果今天我新找到的 w 比我口袋裡那個好的話，我就把我口袋裡那個換掉那我可不可以就改這步就好，有可能啊，所以你現在就說我新找到這個 w，跟我口袋裡那個比比的時候我不再是比它們有幾個錯誤，是在比說它們這個加權錯誤 E in w 到底哪個比較好，比較好的話，如果我新找到的 w 比較好的話，我就把我口袋裡那個換掉好，這是個簡單的想法，我相信說反正大家學過這兩個algorithm 你現在熟悉的話，你可能可以想得出來說，那是不是就這樣做就好那問大家的問題是這樣，我們在原來設計 pocket 的方法的時候我們跟大家講，雖然我們沒有證明這件事，但我們跟大家講說它可以讓 E in 0/1 盡可能的小，然後它有一些理論上的保證等等那現在你新改的這個演算法到底你對 E in w，你對這個加權的 E in 到底有多少的保證你不能說一個演算法拿來，然後我就改一行這好像是你的人工智慧，對不起你的工人智慧，你腦袋的智慧說可以做的事情那它理論上的保證真的是這個樣子嗎？那接下來我們跟大家講的方式，就是我怎麼樣修改 pocket 演算法，讓它能夠得到跟原來的 pocket 有類似的理論的保證怎麼出發呢？我們就要把 E in w 這個加權的跟我們原來的 E in，原來 E in 的 0/1 扯上關係，扯上關係什麼意思？我們現在問題是這個，我們現在問題是說如果負 1 的有錯的話，我們就收它 1000 倍的錯誤如果正 1 的有錯，那就是 1 倍，我們的資料長這個樣子，然後我們要在這樣的狀況下算 E in w 如果我現在想像，我拿到另外一組資料是長這個樣子它說什麼呢，我在原來這個資料裡面，如果是正 1 的我就不管它如果是負 1 的，我就把它複製 1000 倍，資料要複製 1000 倍很簡單吧，這個你如果手動的話就複製貼上複製貼上做 1000 次，或你寫個程式把它複製 1000 倍也可以總之，如果你先不在乎資料量膨脹等等的那你原來一個資料拿來，正 1 的留著，負 1 的複製 1000 倍，我想這個大家都做得到複製了 1000 倍以後怎麼樣如果我們考慮，好我今天有個 G 好了，或有個 H 好了，這個 H 犯的錯誤這個 H 如果在 X2 上面犯了一個錯誤犯了什麼錯誤，也就是說今天是負 1 它說是正 1，這是一個 False Accept，False Accept，它犯了一個 False Accept 的錯誤是怎麼樣在這個新的資料上，因為我已經把這一個點複製了 1000 次所以它只要在一個點上犯錯誤，其他 1000 個點通通都也會犯錯誤，所以在這個新的資料上我們會收它多少個錯誤成本？我們會收它 1000 倍的錯誤成本，如果一個錯誤 1 塊錢的話它會付 1000 塊錢。好所以任何一個在負 1 上犯錯誤的 hypothesis 在這個新的資料上，都會被收 1000 塊錢那如果在正 1 上犯錯誤呢？在正 1 上犯錯誤，反正就是收一塊錢好所以這個時候，我只要在新的資料上說什麼不管是 False Reject 或 False Accept，我都收一塊錢我在新的資料上面收的錢，就跟我在舊的資料上面用這個 Matrix 收錢的方法得到一糢一樣的結果好所以這樣的話怎麼樣，我就只要想辦法在新的資料上把那個收一塊錢，每一種錯誤都收一塊錢的方式做好就好，什麼叫每一種錯誤都收一塊錢？啊，就是我們學過的 0/1 所以我在新的資料上，把 0/1 的 error 做好就代表我在舊的資料上把我這個我有這些權重的衡量方式把它做好，這兩個是同等的好，也就是說我們做的事情是什麼，只要我們做了這個拷貝的動作複製了 1000 次，也就是說我把這個負 1 的複製 1000 次那麼我就可以做到左邊跟右邊是一模一樣的那怎麼辦，我右邊有沒有好的演算法可以做？有啊，什麼？pocket 我已經證明了 pocket 演算法在右邊是可以做的，當然我們沒有真的證明，但是我想要說服大家說，pocket 演算法在右邊那邊是可以用的，那麼這樣我就可以用這樣的觀念來設計一個不一樣的 pocket 在左邊也可以用，然後這兩個 pocket 會是對等的。好，什麼意思呢？也就是說我們就想要做複製的動作，最簡單的是什麼？最簡單的是你做複製，複製完以後丟到一個 pocket 然後就解決了。但是你說我要做這樣的複製動作的話要花例如說記憶體的成本啊，要花硬碟啊等等，花時間所以一般我們不會真的做複製的動作，而是我們在設計演算法的時候，我們腦袋裡想著我們有- 這個複製的動作如果有這個複製的動作，那麼配合原來的 pocket 演算法你就可以得到一個新的演算法，這個新的演算法就要做什麼事情呢？好，首先它要做一個事情是 weighted pocket replacement 也就是說你今天要決定你要不要把口袋裏那個換掉的時候，你要用 Ein w 來決定，這跟我們剛才講過就是那個我們腦袋裏想到那個修改好，這是簡單的，但是因為我們假想我們把負1的那些複製1000次，所以實際上在 pocket 裏面還有一步跟這些被複製1000次的東西有關，就是我們到底要有多頻繁的拜訪每一個點，對不對，pocket 下面有個PLA，這個PLA要做什麼？說我拜訪拜訪這個點的時候，這個我現在隨機的拜訪這個點，在拜訪下一個點，看看它有沒有錯誤，那因為我複製了1000次，所以我在拜訪點的時候，這些被我複製1000次的，因k要有 1000倍的機率，對吧，跟原來比起來的話，可能要更高的機率來被拜訪到，也就是說我要常常檢查負1的很多錯誤，就要少一點檢查正1的有沒有錯誤，好，至少如果你相信我剛才做這個 virtual copying 也就是說這個複製的這個動作的推導的話，你會相信說一個合理的設計 weighted pocket algorithm 也就是說用考慮權重的 pocket algorithm 的方法，是要做這兩步的更改，一步是我要換掉的時候，我要用Ein w 來做檢查，另外一部則是我拜訪那些權重高的點的機率要增加，因為這就對應到我把原來那些資料複製了很多很多次，當然，你想像這個機率增加，所以你也可以想像說如果今天不是1000，不是一個整數，例如說今天是11.26 那你也可以把機率增加成11.26倍，那這樣你就可以解決說權重如果不是整數的話，要怎麼樣子做？好，那這樣的方式，這個我們叫 systematic route 也就是說有系統的把一個方法延伸，OK，延伸成在另外一個問題使用，那有的有的書上或有的研究上要把它叫做 reduction 這跟大家在做資訊科學裏面，這個理論科學裏面的這些問題間互相轉換，其實是類似的，每一個問題轉換成另外一個問題來解決，那這樣的方式這個在 weighted classification 有權重的分類問題裏面的轉換，我們未來會在很多的演算法裏面還會看到或者說，我們其實是可以我們未來如果教平常的二元分類演算法，大家也可以用這樣的方式把它延伸成有權重的方式。好，那最後呢，再給大家一個這個簡單的 ques 說如果今天是 CIA的這個例子，然後呢，但是我們來看看什麼呢，我們來看看說在CIA這個例子裏面，我們的資料的數量到底會造成什麼歌樣的影響？例如說，想像我們的資料庫裏面目前只有10筆入侵者的指紋資料，但是有這個99萬，99萬多筆這個你的指紋的資料，好，這是一個很常見的情形，問入侵者畢竟很少見，所以你會有很少的入侵者的資料，然後- 你會很多自己的資料，如果在這樣的狀況下，然後配合CIA的這個錯誤衡量，那我們來看看做什麼呢？如果我今天有一個 hypothesis，它總是跟你說正1，總是跟你說正1的意思是什麼，總是跟你說可以用，它總會跟你說可以用，然後我們來看看說，它到底要付出多少的錯誤的代價。好那這個大家做的選擇之後，大家算一算，應該會發現說答案是2，0.01，也就是說是一個還蠻小的數字，那說5啊，所以糟糕了，糟糕了是什麼意思？總是說正1什麼，其實不管是你，還是這個入侵者，你的 hypothesis 偶爾也會說它可以使用這個 CIA的資料庫，可以進入CIA的資料庫。好，所以這不是謬，總是說正1，對我們來說應該是一個很爛的 hypothesis，但是你的電腦搞不好覺得它還不錯，好，這個問題實際上就是出現在我們有非常不平衡，我們一般叫 unbalanced 的資料，這個 unbalanced 的資料就算，好，例如說，我們這個CIA有一些不同的權重，但因為 unbalanced 所以還會跑出一些其他的問題來，那通常調整這些權重，是解決這種不平衡資料的一個方式，如果你把權重作適合調整，也學就可以避免說今天一個這麼簡單總是說可以用的這個 hypothesis 的製造出來的這些問題，好，那我們在這邊跟大家講了 Noise 跟 Error 我們說到說在有雜訊的狀況下呢，我們可以想像的是說我們使用一個 and Probabilistic 的 function 我們叫 P of y give x，我們叫做目標的 distribution 來做描述，那麼，在錯誤的方面呢，我們若配合錯誤的定義的話，那我們就可以得到到底我們真正想要的那個 Target 所以理想化那個 Target 是長什麼樣子？好，但是呢，這個錯誤需要由使用者來給那這個使用者有時候不太能夠給出，所以我們就講到說在我們涉及演算法的時候，我要用們可能要用要麼就能說服我們自己的方式，要麼就是要用比較friendly 好做的方式，來提供說我們錯誤的衡量是什麼，那麼最後呢，我們講到說一個很常見的錯誤衡量是對false positive, false accept 跟 false reject 有不同的要收不同的費用，那麼收不同的費用的時候，我們就說我們可以把這個問題轉成這個我們原來熟悉的 zero one 的問題，那用什麼呢？用所謂的 virtual copying 的方式就是說你好像把你的 example 複製了很多份，好，那這邊呢，總結掉了我們講的這個跟機器學習比較理論相關的這個 foundation 的部分，接下來我相信大家迫不及待想要學更多的機器學習的演算法。那這裡會是我們未來3到4個 lecture 的目標，就是教給大家更多有趣的機器學習的演算法，那歡迎大家下一次回來，謝謝。 [音樂] [音樂] [音樂]

Weighted Classification

機器學習基石上 (Machine Learning Foundations)---Mathematical Foundations

Meet the Instructors