Perceptron Learning Algorithm (PLA)
現(xiàn)在我們把看作是所有可能的感知機(jī)(Perceptron),把
看作其中的一個(gè)感知機(jī)假設(shè)弃酌。
那么氨菇，我們想要做的就是讓盡可能的接近target function
，理論上講在數(shù)據(jù)集
上矢腻，
是成立的门驾，也是必要的。
但是（感知機(jī)假設(shè)）是無(wú)限的多柑，那要怎么做呢奶是？
idea: start from some
(represent by its weight vector
),and 'correct' its mistakes on
以下是PLA流程：
For t = 0，1竣灌，...
- 找到被
劃分錯(cuò)誤的一個(gè)錯(cuò)誤點(diǎn)
聂沙，使得
- 令
，嘗試去修正這個(gè)錯(cuò)誤初嘹。
... 直到?jīng)]有分錯(cuò)的點(diǎn)為止及汉。此時(shí)令
舉例說(shuō)明：
Guarantee of PLA
首先講一下線性可分(Linear Separability)的概念：
- if PLA halts(意味著沒(méi)有錯(cuò)誤點(diǎn)了，這是必要條件)屯烦，
allows some
to make no mistakes
- call such
也就是說(shuō)坷随，Linear Separableexits perfect
such that
假設(shè)
實(shí)際上温眉，Gets More Aligned with
我們可以簡(jiǎn)單證明一下： -
correctly away from line:
?? -
update by any
??
???????
???????
并且， does not grow too fast
Because changed only when mistake
mistakes 'limits' growth,even when updating which 'longest'
?????
?????
?????
Note:start from ,after T mistake corrections：
Non-Separable Data
上面講述了PLA基于線性可分?jǐn)?shù)據(jù)的過(guò)程翁狐，而在現(xiàn)實(shí)生活中类溢，并不總是separable的。那么露懒，我們要怎么做才能使得
成立呢闯冷？
如果數(shù)據(jù)集如下圖所示，我們永遠(yuǎn)不可能畫(huà)一條直線完全分開(kāi)和
樣本懈词。
但是蛇耀，顯然，noise數(shù)據(jù)不會(huì)太多（太多了就沒(méi)意義了坎弯，對(duì)這份數(shù)據(jù)集而言）蒂窒，那么我們可以假設(shè)
所以，現(xiàn)在我們要做的象迎，就是找一條線荧嵌，使得錯(cuò)誤點(diǎn)數(shù)量盡可能少呛踊。
即
不幸的是，這是一個(gè)NP難題啦撮。我們只能去找一個(gè)近似的符合條件的g谭网。
這里我們引入Pocket算法
initialize pocket weights in
For t = 0赃春，1愉择，...
- 找到被
- 令
- 如果
劃分的錯(cuò)誤點(diǎn)比
少，那么replace
... 直到迭代到足夠次數(shù)為止狭吼。
此時(shí)令
