一. 假设集
h(x) = sign(∑wixi - threshold) = sign(wTx)
二. 学习算法
1. Cyclic PLA
|
For t = 0,1,... 1) find a naive/random mistake of wt called (xn(t),yn(t)) sign(wtTxn(t)) ≠ yn(t) 2) correct the mistake by wt+1 ← wt + yn(t)xn(t) ...until a full cycle of not encountering mistakes |
①如果每次改正错误及数据集D线性可分，wt的长度会缓慢增长，越来越接近目标wf直到停止.
②PLA实现简单，运行快速，可以工作于任何维度. 但D线性可分是假设，同时也不确定多久可以停止.
2. Pocket PLA
|
For t = 0,1,... 1) find a random mistake of wt called (xn(t),yn(t)) 2) correct the mistake by wt+1 ← wt + yn(t)xn(t) 3) if wt+1 makes fewer mistakes than w', w'← wt+1 ...until enough iterations, return w' |
①Pocket PLA适用于D非线性可分情形.
②如果D线性可分，因Pocket PLA需存储w'及检查w'与wt+1在D上哪个错误少，所以比Cyclic PLA慢.