---
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
<!--  -->
找出各個$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

<!--  -->

- perceptrons 又可稱線性分類器

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

<!--  -->

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

<!--  -->
- PLA的進行 看影片較清楚
- 注意: w在圖中為分界線的法向量

<!--  -->
<!--  -->
<!--  -->
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)

- 假設完美的 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}$ 的方向沒變，只是長度越來越長，也會導致內積越來越大
- 所以接下來要證長度的部分

<!--  -->
- 注意我們只在 $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

- 懶得推導 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

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

### Fun Time: Pocket for PLA
- pocket 會比 PLA 慢，因為要花力氣去存 pocket，還要比較 pocket 和當前 line 的錯誤率