# 林軒田機器學習基石筆記 - 第一講、第二講
###### tags: `林軒田` `Maching Learning` `機器學習基石`

---

>* **本文討論內容請參考:
機器學習基石第一講 : The Learning Problem
機器學習基石第二講 : Learning to Answer Yes/No**
>
>* **本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義**
>

---

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

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

<br>

## Componemts of Machine Learning

* **Perceptron Hypothesis Set**
Perceptron指的是一種簡單的二元分類器 $\left( y\in\left\{+1,-1,0\right\}\right)$ ，而機器學習許多的概念都是由這最簡單的二元分類器而來。

$h(\mathbb{X})=sign(\sum\limits_{i=1}^{N}w_ix_i+threshold) =sign(\sum\limits_{i=0}^{N}w_ix_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}$即可。
<br>
## Perceptron Learning Algorithm (PLA)


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

在林軒田的課程中，講義的符號的一些細節常常會讓人忽略，然而讀到後面就會開始腦袋打結，例如 : 資料點$X$ (我自己習慣用$\mathbb{X}$) 與$x$的差別

在Step2中，以數學的觀點來看，第$t$次迭代找到的錯誤點$\left(\mathbb{X}_{n_{t}},y_{n_{t}}\right)$並非剛好就會是原始資料中的第$n$個資料，因此便在$n$下方再多一個下標$t$，以明確標示出每一個錯誤的點。

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

<br>
* PLA其實是一個極為理想的狀態，是否真正存在一個理想的$f$ 我們不能確定，而且現實的dataset絕大多數都會因為noise而不會Linear Separable

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

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

[^1]:$[\![a]\!]$雙方括號 :
可以表達為小於等於a的最大整數，但在此為 $Iverson bracket$ ，在括號內的邏輯條件為True則為1，為Flase則為0。
## 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}}$，而且每一次迭代都必須重新計算誤差量 )。
<br>