林軒田機器學習基石筆記 - 第一講、第二講

tags: 林軒田 Maching Learning 機器學習基石

---

• 本文討論內容請參考:
  機器學習基石第一講 : The Learning Problem
  機器學習基石第二講 : Learning to Answer Yes/No

• 本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義

---

• Learning : 從觀察開始，經由腦內轉化，形成有用的技能。
  Machine Learning : 利用電腦模擬上述的過程，稱之。

• Machine Learning 本質 :
  存在潛藏模式可以被學習，但我們無法明確給訂規則及定義，因此利用過往資料讓機器自行學習判斷。

Componemts of Machine Learning

• Perceptron Hypothesis Set
  Perceptron指的是一種簡單的二元分類器

  $(y\in \{+1,-1,0\})$ ，而機器學習許多的概念都是由這最簡單的二元分類器而來。
  $h(\mathbb{X})=sign(\sum _{i=1}^N{w}_i{x}_i+threshold)=sign(\sum _{i=0}^N{w}_i{x}_i)=sign({\mathbb{W}}^T\mathbb{X})$

  在此處可以清楚看見，決定

  $h$的因素在於
  $w_i$及
  $threshold$，也就是
  $\mathbb{W}$，因此在往後的課程中，討論hypothesis的重點將會放在
  $\mathbb{W}$上面

• Geometric Meaning of

  $h$

$\mathbb{W}$會很容易讓人誤會是那一條分類線(超平面)，嚴格說起來也是沒錯，但嚴謹一點來說，應該指的是其法向量，這也呼應到上面講的，任何一個

$h$ ，都能唯一找到一個

$\mathbb{W}$，當我們要找

$h$，也就只要專注在找出對應的

$\mathbb{W}$即可。

Perceptron Learning Algorithm (PLA)

$$PLA\mathrm{其}\mathrm{實}\mathrm{就}\mathrm{是}\mathrm{經}\mathrm{由}\mathrm{不}\mathrm{斷}\mathrm{的}\mathrm{修}\mathrm{正}\mathrm{錯}\mathrm{誤}\mathrm{最}\mathrm{終}\mathrm{求}\mathrm{得}\mathrm{一}\mathrm{個}\mathrm{完}\mathrm{美}\mathrm{分}\mathrm{類}\mathrm{器}\mathrm{的}\mathrm{迭}\mathrm{代}\mathrm{過}\mathrm{程}。$$

在林軒田的課程中，講義的符號的一些細節常常會讓人忽略，然而讀到後面就會開始腦袋打結，例如 : 資料點

$X$ (我自己習慣用

$\mathbb{X}$) 與

$x$的差別

在Step2中，以數學的觀點來看，第

$t$次迭代找到的錯誤點

$({\mathbb{X}}_{n_t},y_{n_t})$並非剛好就會是原始資料中的第

$n$個資料，因此便在

$n$下方再多一個下標

$t$，以明確標示出每一個錯誤的點。

• 經過這樣一系列的迭代過程，PLA最終真的會停止(halt)嗎?
  是的，只要我們手中的Dataset是線性可分(Linear Separable)，最後PLA必然會收斂，這就是所謂的 " Perceptron Convergence Theorem"

  
  
  

• PLA其實是一個極為理想的狀態，是否真正存在一個理想的

  $f$ 我們不能確定，而且現實的dataset絕大多數都會因為noise而不會Linear Separable

  如果我們真的找不到完美的分類器，那麼可以退而求其次，找出誤差最小的總可以了吧!

  $${\mathbb{W}}_g=arg\underset{\mathrm{\forall }\mathbb{W}}{min}\sum _{n=1}^N[[y_n\ne ({\mathbb{W}}^T\mathbb{X}+b)]]$$^[1]
  $$\mathrm{很}\mathrm{遺}\mathrm{憾}\mathrm{的}，\mathrm{這}\mathrm{是}\mathrm{一}\mathrm{個}NP-Hard\mathrm{的}\mathrm{問}\mathrm{題}\mathrm{看}\mathrm{來}\mathrm{也}\mathrm{是}\mathrm{無}\mathrm{解}。$$

Pocket Algorethm

這是一種PLA的變形演算法，過程與PLA大致都相同，一樣要經過迭代程序，但不同的地方在於 : 「PLA目的在找出一個絕對好的分類器，但Pocket則是找出相對好的即可。」

每一次的迭代過程，都把新的

${\mathbb{W}}_t$跟上一個

${\mathbb{W}}_{t-1}$做比較，誤差量相對小的就把她暫時當成目前最好的分類器

$\tilde{\mathbb{W}}$放在Pocket中，雖然經過不斷的迭代，但Pocket中的

$\tilde{\mathbb{W}}$絕對是"當下"最好的分類器。

[Remark] Pocket演算法不見得最終會 halt (因為現實資料並不見得線性可分)，那麼停止的條件便只能用人為來判斷迭代次數，只要我們認為迭代次數夠多了就可以停止Pocket Algorithm

這樣的演算法，便能克服在現實狀況中會遇到的問題。

但是這也不是非常完美的方式，這樣的演算法的計算時間相對PLA要來的久 ( 因為要不斷儲存

$\tilde{\mathbb{W}}$，而且每一次迭代都必須重新計算誤差量 )。

---

1. $[[a]]$雙方括號 :
   可以表達為小於等於a的最大整數，但在此為
   $Iversonbracket$ ，在括號內的邏輯條件為True則為1，為Flase則為0。 ↩︎