首页 > 代码库 > 02 Learning to Answer Yes/No
02 Learning to Answer Yes/No
Perceptron Learning Algorithm
感知器算法,
本质是二元线性分类算法,即用一条线/一个面/一个超平面将1,2维/3维/4维及以上数据集根据标签的不同一分为二。
算法确定后,根据W取值的不同形成不同的h,构成假设集合H。
如2维感知器算法,根据w0,w1,w2的不同取值,构成了不同的h,这些h最终构成H。注意为了方便表示,将阈值的负数记为w0,对应的数据点增加一维x0,恒为1。
而算法就是根据给定数据集D从H中选出与目标模式f最为相似的g。
更新规则/学习过程,
遍历数据集合,若遇到异常点,即由当前W更新为新的W,
若异常点的y值为+1,表明X与当前W的内积值为负,角度过大,更新后角度将会变小;若异常点的y值为-1,表明X与当前W的内积值为正,角度过小,更新后角度将会变大。
更新W的本质其实是从H中选出与f更为相似的h的过程。
注意,更新后不能保证异常点变为正常点,只是异常的程度小了点。
何时停止更新?
在当前W的情况下,遍历D中所有数据点,无异常点时停止更新。
一定能够保证能停止更新吗?即在当前W下无法找到一个新的W使得对应的h与f更为接近?
只要数据线性可分就能!
Wf与Wt的内积值随着更新次数的上升而增大,同时,Wt的模也在增大,
不过,内积增大的程度大于模的程度,保证了随着更新次数的上升,Wt与Wf越来越接近。
PLA的优缺点:
优点:简单、快速、任意维度;
缺点:假设数据线性可分,然而我们并不知道f,也就不知道是否可分,再来,要是知道线性可分,W也已经知道了,没有必要再用PLA了;
经过多少次更新才能收敛也不知道,如上证明,T与Wf有关,然而我们不知道Wf。
Pocket Algorithm
若数据线性不可分,为NP问题,
使用PA,即既然异常点无法避免,PA在H中找到一个使得异常点数目最小的h作为g。
注:O(nk)为多项式型时间复杂度,O(kn)/O(n!)/O(>n!)/...为指数型时间复杂度。
问题分为可解问题和不可解问题,多项式型时间复杂度的可解问题为P问题,验证时为多项式型时间复杂度的为NP问题,能否可解未知。
P问题肯定是NP问题,NP问题不一定是P问题。
PA,初始化W,放到口袋里,若遇到异常点,使用PLA的更新规则得到新的W,遍历数据集,若是新的W下异常点的数目更少,则用新的W替换旧的W放到口袋中,否则不替换,在原有W的前提下,继续遍历数据集,得到下一个异常点,重复上述过程,直到在遍历一轮数据集的过程中,口袋里的W从未变过,则停止。
口袋里放的永远是目前使得异常点最少的W。
如果数据集是线性可分的,PLA和PA都能够实现无异常点的分类,
但是PA的时间会长于PLA,因为多了比较遍历一轮数据所得异常点数目多少的过程。
02 Learning to Answer Yes/No