---
# System prepended metadata

title: Ch2 Learning to Answer Yes/No
tags: [機器學習基石上：數學篇]

---

---
tags: 機器學習基石上：數學篇
---

# Ch2 Learning to Answer Yes/No

## Content
[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)


## [Perceptron Hypothesis Set](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/n6xnX/perceptron-hypothesis-set)


### Perceptron
<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/perceptron01.jpg) -->
![](https://i.imgur.com/CIQO7KF.png)
找出各個$x_i$的權重$w_i$, 並判斷$\sum\limits_{i=1}^{d}w_ix_i$是否大於threshold(門檻), 是則輸出1, 否則輸出0
- $sign()$: 判斷正負號, 大於0則輸出1, 小於0則輸出-1


- 可以將 $h(x) = \sum\limits_{i=1}^{d}w_ix_i - \mathrm {threshold}$ 表示為 $h(x) = \sum\limits_{i=1}^{d}w_ix_i + w_0x_0=\sum\limits_{i=0}^{d}w_ix_i$ , $w_0$值為(-threshold), $x_0$值為1

<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/perceptron02.jpg) -->
![](https://i.imgur.com/rPqdeVK.png)

- perceptrons 又可稱線性分類器

## [Perceptron Learning Algorithm (PLA)](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/GNlJL/perceptron-learning-algorithm-pla)

<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/PLA01.jpg) -->
![](https://i.imgur.com/AY0x4Rk.png)

### PLA如何逐步修正直線
當實際的結果(y)是正的，它(wx)跟我說負的，代表這個w跟x的角度夾角太大，修正的方式就是把它轉回來，把w跟x加起來成為新的w，那麼結果可能就會是正的，另外一種可能性，實際結果(y)是負的，結果它(wx)跟我說是正的，那代表w跟x的角度太小了 我就把w減掉x

<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/PLA02.jpg) -->
![](https://i.imgur.com/NpBBVRH.png)
- PLA的進行 看影片較清楚
- 注意: w在圖中為分界線的法向量

<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/PLAfact.jpg) -->
<!-- ![](https://i.imgur.com/pkFUZJd.png) -->
<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/PLA_q.jpg) -->
![](https://i.imgur.com/G6PkFM3.png)
Ans: 3
將 $w_{t+1} = w_t + y_nx_n$ 等號兩邊乘上 $y_nx_n$ 即可得知3正確
- ***雖然教授是說 $y_nx_n$，不過應該說是 $y_nx_n^T$ 比較嚴謹?***
- ***其實要說 $y_nx_n$ 也是可，不過這裡的「乘上」應該改稱為做「內積」***

## [Guarantee of PLA](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/XckQ1/guarantee-of-pla)

![](https://i.imgur.com/IKYD7NF.png)
- 假設完美的 weight 是 $w_f$
- 那麼一定成立 $y_n=\text{sign}(w_f^Tx_n)$
- 所以 $\min_\limits n y_nw_f^Tx_n>0$
- 那麼根據之前說的 update rule $w_{t+1}=w_t+y_{n(t)}x_{n(t)}$，兩邊乘上 $w_f^T$ 可以得知 $w_f^Tw_{t+1}>w_f^Tw_t$，我們得到的 $w_{t+1}$ 和 $w_f$ 的內積越來越大，「也許」代表 $w_{t+1}$ 和 $w_f$ 越來越接近？
    - 還不夠，因為如果 $w_{t+1}$ 的方向沒變，只是長度越來越長，也會導致內積越來越大
    - 所以接下來要證長度的部分


<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/plafact2.jpg) -->
![](https://i.imgur.com/IMbVdWW.png)
- 注意我們只在 $x_n$ 是錯的時候更新 $w$
- 利用上面這點證明了 $||w_{t+1}||^2 \leq ||w_t||^2+\max_\limits n \|y_nx_n\|^2$，在這還不能確定 ${w_{t+1}}$ 比 $w_t$ 更接近 $w_f$
- 我們需要證明，經過 $T$ 次更新後，$w_f$ 和 $w_T$ 的 cosine similarity 會大於等於 $\sqrt T$ 乘上某個常數，窩懶得證 0w0
    - 可能可以參考 youtube 影片下方留言或者 coursera 論壇
- 備註
    - ${w_f}^Tx_n$: $w_f$那條線與$x_n$點的距離(**_這樣說並不嚴謹，似乎是因為還要考慮 $w_0,x_0$?_**)
    - $\min_n(y_n{w_t}^Tx_n)$: 離線最近的點距離乘上y
    - $x_{n(t)}$, $y_{n(t)}$: 第t次算出w犯錯的那個點的x和y


![](https://i.imgur.com/La1ET5N.png)
- 懶得推導 0w0

## [Non-Separable Data](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/VbEdY/non-separable-data)


- $w_g\leftarrow \arg\min_\limits w\sum_\limits{i=1}^n [y_n\neq \text{sign}(w^Tx_n)]$
    - 很可惜的這是一個 NP-hard 的問題
- 因此我們不一定要找最好的線，只要找到不錯的線即可，其中一個做法就是 pocket algorithm

![](https://i.imgur.com/URBtmzY.png)
- 在PLA過程中, 把最好的weight(犯最少錯誤)存著(在pocket中)，再比較當前weight的表現，若當前 weight 較好，就更新 pocket 內容
- 通常用 pocket algorithm 時，會希望用隨機的方式去找 mistake
    - ***咦難道一般 PLA 不是這樣的嗎?***


### Fun Time: Pocket for PLA
![](https://i.imgur.com/6ZUCI3l.png)
- pocket 會比 PLA 慢，因為要花力氣去存 pocket，還要比較 pocket 和當前 line 的錯誤率









