[Machine Learning Foundations] Lecture 2: Learning to Answer Yes/No

Machine Learning Foundations Notes
Lecture 2: Learning to Answer Yes/No
Instructor: Hsuan-Tien Lin

Perceptron Hypothesis Set

回到上一單元中核發信用卡的問題，現在我們要介紹假設 $H$ 到底會長什麼樣子？
A Simple Hypothesis Set: the Perceptron 感知器
- features of customer 把每一個申請者用一個多個維度的向量 $x = (x_{1}, x_{2}, …, x_{d})$ 來表示，其中每個維度有不同正面或負面的影響，決定銀行是否核發信用卡給這個申請者
- 把每個維度乘上它的權重 $w_{i}$，經過綜合計算之後給申請者一個分數，如果分數超過某個標準就核發信用卡給他，如果沒有就不發卡
- 結果 $y$ 為了簡單起見，用 1 來表示好，-1 來表示不好，所以我們要電腦做的事情就是讓電腦先算出一堆分數，減掉設定的門檻值，如果結果是正的就是好的，負的就是不好的
- 不同的權重 $w$、不同的門檻，會造出不同的假設 $h$
把 $h(x)$ 整理一下，把門檻值 threshold 視為是一個權重，就可以將 $h(x)$ 整理成兩個向量內積
再具體一點，$h$ 到底長什麼樣子?
- 在圖中，$x$ 對應到一個點，$y$ 對應到這個點是畫 o 還是 x，而 $h$ 是圖中的線，每一條線都是不一樣的預測
- 從幾何的角度來看 perceptron 就是平面上一條條的線，另一個說法就是線性分類器，點單來說就是回答是非題（分成兩類）

Perceptron Learning Algorithm (PLA)

How to select $g$ from $H$? $H$可以想像成平面上所有的線，也就是所有的 perceptron，那要如何從這些線裡面找出最接近 $f$ 的那個 $g$ 呢？
- 我們不知道 $f$，但我們知道資料是從 $f$ 產生的，所以我們可以要求 $g$ 跟 $f$ 至少在我們看過的資料裡面是很接近的，甚至一模一樣，也就是說把 $g$ 送來預測現有資料裡的 $x$ 的話，可以馬上就得到理想的 $y$
- 很難，因為 $H$ 是無限的
- start from some $g_{0}$, and ‘correct’ its
  mistakes on $D$ 換個角度想，如果我們先隨便找一條線，雖然這條線可能不太好，但是我們可以慢慢修正它，讓它越來越接近我們要的結果，這時候就可以用到 PLA
- will represent $g_{0}$ by its weight vector $w_{0}$
Perceptron Learning Algorithm (PLA)
- 一開始有一條線 $w_{0} = 0$，代表什麼都不知道
- 如果這條線還不完美，我們一定可以找得到資料中的某一個點 $(x_{n(t)}, y_{n(t)})$，使這條線 $w_{t}$ 犯了錯誤，所謂犯了錯誤表示用 $w_{t}$ 去跟 $x_{n(t)}$ 做預測（內積），得到的正負號跟理想中的正負號不一樣
- 既然犯了錯就要想辦法修正，犯錯有兩種可能
  - 要的是正的，給的是負的，代表 $w$ 和 $x$ 的角度太大 –> $w+x$ 讓角度變小
  - 要的是負的，給的是正的，代表 $w$ 和 $x$ 的角度太小 –> $w-x$ 讓角度變大
  - 如此重複修正，到不再犯錯為止，而最終結果叫做 $w_{PLA}$ 也就是 $g$
要如何簡單地判斷它到底還有沒有錯誤？
- Cyclic PLA: 輪流檢查每一個點，如果點沒有錯就看下一個，有錯的話就修正，如果所有的點都檢查過了沒有犯錯，表示已經沒有錯誤
視覺化來看 PLA 怎麼修正 $H$ (slides p.10)
- 為什麼分割線會和 $w_{t}$ 垂直？
  - 從公式　$w \cdot x = w^{T}x= \left | \overrightarrow{w} \right | \left | \overrightarrow{x} \right | cos(\Theta )$ 可以知道當 $w$ 和 $x$ 的夾角 $\Theta$ 小於 90 度時，結果為正（o），反之結果為負（x），因此垂直線等於 90 度時，就是正與負的分界了。
PLA 的一些問題
- 它一定會停下來嗎? 什麼時候會停？
- 就算真的停下來了，所得到的 $g$ 會跟 $f$ 相近嗎？

Guarantee of PLA

PLA 什麼時候會停下來？
- If PLA halts, (necessary condition) $D$ allows some $w$ to make no mistake
- PLA 終止條件：沒有再犯任何錯誤，也就是說原本的資料必需要有一條線可以切開 –> linear separable 線性可分
Assume linear separable $D$, does PLA always halt?
- 想像 $w_{f}$ 是我們的目標，這條線很完美，可以把資料切開
- $\min_{n} y_{n} w_{f}^{T} x_{n}$ 表示每個點跟這條線的距離 $w_{f}^{T} x_{n}$乘上那個點理想的分類（我們想要它在哪一邊）$y_{n}$ 都要大於 0
- 也就是說 PLA 每次選到犯錯的那個點，也會滿足前述的限制
- 我們就可以對 $w_{f}^{T}$ 和 $w_{t+1}$ 做內積，衡量它們是否接近，內積的值越大，某種程度上代表它們越接近。但是內積越大有可能是因為向量的長度比較長，所以接著要處理向量長度的問題
PLA Fact: $w_{t}$ does not grow too fast
- PLA 的重點 $w_{t}$ changed only when mistake
- $w_{t}$ 不會成長太快，它只會靠 $\left | y_{n(t)}x_{n(t)} \right |^{2}$ 來成長（任意選到的犯錯的點）
- constant?
這小節的 Fun Time 本來還看不懂，但只要推出上面的常數這題就不難了

Non-Separable Data

More about PLA
- 如果資料是線性可分， PLA 一次選一個錯誤來修正，我們發現 $w_{f}$ 和 $w_{t}$ 成長很快，而 $w_{t}$ 成長緩慢，綜合以上兩點證明了 PLA 會停止
- PLA 的好處：快、實作簡單、可以用在多維的資料
- PLA 的壞處：
  1. 先假設了資料是線性可分，但不知道這個假設是否正確，這個假設是存在 $w_{f}$ 但如果已經知道了 $w_{f}$ 還做 PLA 做什麼？但是如果要知道這個假設是否正確，必須要找一個 $w_{f}$ 出來，這樣會陷入一個循環，所以某種角度我們其實不知道 PLA 會不會停下來
  2. 就算真的有 $w_{f}$ 存在，那 PLA 多久會停下來？雖然剛剛推導出了 $R$ 和 $\rho $，但是 $\rho $ 是根據 $w_{f}$ 來的，但我們還是不知道 $w_{f}$ 在哪裡
Learning with Noisy Data
- 收集資料的過程中可能會有一些雜訊，拿到的資料不見得是線性可分
- 如何在有雜訊、不是線性可分的狀況下還是找到一條好的線來區分資料呢？
Line with Noise Tolerance
- 假設雜訊相對於真正想學的 $f$ 是小的，代表在資料上 $y$ 和 $f$ 要有一定的對應程度
- 如果要找 $g$ 和 $f$ 很像的話，在資料上也要滿足 $y$ 和 $g$ 很相像
- 找一條犯的錯誤最少的線當作 $g$ –> 可惜這是一個 NP-hard 的問題
Pocket Algorithm
- modify PLA algorithm (back lines) by keeping best weights in pocket 想像成我們一直把我們認為最好的線抓在手上，每找到一條新的線就和手上的比，如果新的線比較好（犯的錯誤比較少），就拿新的

Summary

Perceptron Hypothesis Set: hyperlanes/linear classifiers in $\mathbb{R}^{d}$
Perceptron Learning Algorithm (PLA): correct mistakes and improve iteratively
Guarantee of PLA: no mistake eventually if linear separable
Non-separable Data: hold somewhat ‘best’ weights in pocket (pocket PLA)
Slides: http://www.csie.ntu.edu.tw/~htlin/mooc/doc/02_present.pdf