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 first course of the two would focus more on mathematical tools, and the other course would focus more on algorithmic tools. [機器學習旨在讓電腦能由資料中累積的經驗來自我進步。我們的兩項姊妹課程將介紹各領域中的機器學習使用者都應該知道的基礎演算法、理論及實務工具。本課程將較為著重數學類的工具，而另一課程將較為著重方法類的工具。]
Weighted Classification
Loading...
来自 国立台湾大学 的课程
機器學習基石上 (Machine Learning Foundations)---Mathematical Foundations
350 评分
从本节课中
第八講: Noise and Error
learning can still happen within a noisy environment and different error measures
与讲师见面
Hsuan-Tien Lin, 林軒田教授 (Professor)
資訊工程學系 (Computer Science and Information Engineering)
好，那所以從這裡出發呢，我們就跟大家講 另外一個機器學習裡面的問題。
我們剛剛學過，我們之前學過了二元分類 那現在呢，不同的錯誤有不同的這個重要性，我們把它叫做
「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 的目標，就是
教給大家更多有趣的機器學習的演算法，那歡迎大家下一次回來，謝謝。
[音樂]
[音樂]
[音樂]
