Machine Learning 共筆 Week 2

Learning to Answer Yes/No (機器怎麼解決是非題?)

H (hypothesis set) 會長什麼樣子?

• for x=(x1,x2,···,xd)
  每一個 x (feature of customer) 都當成一個向量
  年紀維度
  年收入維度
  工作年限… etc
• Y: +1(good), −1(bad) ,

公式應用:

權重 (w, weight) 與向量相乘 — 門檻 (看看總分有沒有超出門檻值)
成果是好的或是不好的 → 看 sign 的正負值

h(x) = sign (w0 + w1x1 + w2x2)

• 以上這個式子化成二維的圖會發現 h(x) 其實就是圖上的一條直線 (0 = x1 * someting + x2* something + 截距)

結論: 所以是非題其實就是線性的分類器

怎麼設計一個演算法來找出最好的線 h(x)? → PLA

• want g nearly close to f
• 找出一條線，在目前已知的資料裡，g 的 output 都能跟 f 一樣

1. 只想挑到最好的線可能會有無限種挑法
2. 一開始先挑一條線 g0 (並且使用 weight vector: w0) ，如果不夠好那我們就嘗試修正他，直到他不能再好為止
3. 如果這條線不夠好，這條線會在某個點犯錯 (xn, yn)
4. 接著修正 vector 的角度
5. w 和 x 的角度太寬或太窄可以相加或相減來修正
6. 直到所有數都跑完了還沒有遇到任何錯誤的時候就算成功了，此時 halt

課程中的二維圖範例:

1. 隨機找一條線
2. 找那條線垂直的法向量 → 開始試錯
3. 朝比較正確的那個方向修正 (轉線的角度)

PLA 的終止條件

找到一條線把所有的資料分開，就可以稱資料為 Linear Separability，PLA 就能停下來

PLA 的變形演算法: Pocket Algorithm

在不確定資料是不是線性可分的情況下，這個演算法比較有效率

• 用隨機的更新方式，找一條隨機的線
• 試著修正他
• 找到新的線的時候拿去跟舊的線比較誰錯的少，少的那個就放在自己的 pocket 裡，然後跑足夠的 iterations ，得出一個還算可以的答案

資料線性可分的情況下，Pocket Algorithm 會比 PLA 來得慢

• 要花力氣存資訊
• 要檢查所有的資料 (把資料帶進新的線和舊的線) 來比較哪一個比較好