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

發表於 更新於 分類於 ， 閱讀次數： Disqus：

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

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

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

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

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}\) 即可。

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"

  • 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的問題看來也是無解。

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 的最大整數，但在此為 \(Iverson\ bracket\) ，在括號內的邏輯條件為 True 則為 1，為 Flase 則為 0。↩︎