[學習筆記3] 機器學習基石 - Learning to Answer Yes/No :: Non-Separable Data

Non-Linear Separability Problem

資料若屬於線性可分割(Linear separate)當然是最好

但是問題來了，真實世界裡總是不是那麼理想，總有幾個頑固份子破壞了和諧

若手上有今天非線性可分割的資料點該怎麼辦?

對於這些有雜訊存在的資料點，我們可以使用近似的方法，找到"最合適"的解


Pocket Algorithm - 與Greedy Algorithm近似的演算法

林軒田老師以小朋友手上有個玩具，還想要在抓其他的玩具來作比喻 (我 : 吃碗內看碗外)

Pocket Algorithm 是手上有一個近似解之後，再繼續尋找更合適的解

Pocket Algorithm( PLA的變形) 與 PLA的核心想法類似

但是運算上 Pocket Algorithm比 PLA演算法計算速度更久的原因在於 :

1.  但是Pocket演算法需要額外儲存目前已運算完的結果

2.  PLA演算法只要check目前這組裡面有什麼資料點分類錯誤，一找到就立刻更新權重值，直到找到最佳解就停止。但是Pocket演算法面對得可能是非線性可分割，因此需要檢查所有的分類結果，直到找到最適合的那組解為止。在相同事情上，Pocket演算法花費的時間會更久。

Learning to Answer Yes/No 小結

最後，對於前面的學習內容來個總結 : 

Perceptron Hypothesis Set (Set of candidate formula)與PLA演算法 

可以解決可線性分割(Linear Separability)的分類類別

至於非線性分割(Non-Linear Separability)的問題，則要仰賴Pocket演算法求得近似解

註 : 這邊的Perceptron模型就是H中的其中一個模型