Week 2 : Learning to Answer Yes/No

  • “Perceptron”(感知器) hypothesis :
    • $\mathcal{Y}$ : {+1(good), −1(bad)}, 0 ignored—linear formula $h ∈ \mathcal{H}$ are : $$\color{red}{h} (x) = sign((\sum^d_{i=1} \color{red}{w_i}x_i) − \color{red}{\text{threshold}}) $$$$ = sign((\sum^d_{i=1}\color{red}{w_i}x_i) + \color{blue}{(-\text{threshhold})\cdot (+1)})$$$$ = sign((\sum^d_{i=1}\color{red}{w_i}x_i) + \color{blue}{(w_o)\cdot (x_0)})$$$$ = sign(\color{red}{w^T}x)$$
    • Perceptrions(感知器) $\iff$ linear classifilers(線性分類器)
  • Select g from $\mathcal{H}$ :
    • 理想上 : $g(x_n) = f(x_n) = y_n$
    • 但$\mathcal{H}$太大
    • 嘗試 : 從g0開始，慢慢修正
  • Perception Learning Algorithm(PLA) :
    1. 找到線$\color{red}{w_t}$中的一個錯誤 : $\color{blue}{(x_{n(t)}, y_{n(t)})}$
      • $sign(\color{red}{w_t^T}\color{blue}{x_{n(t)}}) \neq \color{blue}{y_{n(t)}}$
    2. 修正該錯誤(調整向量) :
      • $\color{purple}{w_{t+1}} \leftarrow \color{red}{w_t^T} + \color{blue}{x_{n(t)}y_{n(t)}}$
    3. 循環至無錯誤發生
  • Linear Separable : 代表可以跑得完PLA
  • Pocket Algorithm : 初始化Pocket weights $\hat{x}$
    1. 找到線$w_t$中的一個(隨機)錯誤 : $(x_{n(t)}, y_{n(t)})$
    2. 修正該錯誤(調整向量) :
      • $w_{t+1} \leftarrow w_t+ x_{n(t)}y_{n(t)}$
    3. 若$w_{t+1}$的錯誤比$\hat{x}$少，則把$\hat{x}$用$w_{t+1}$取代
    4. 直到enough iterations
    5. return $\hat{x}$ (called $w_{\text{POCKET}}$)當作g
    • 特性 :
      • PLA的簡易修正版
      • 需要$\mathcal{D}$為Linear Separable
      • 但需要花額外時間，∵第三步需要check每個點