文档介绍：PLA and POCKET
问题描述--------算法思想设计描述------伪代码-----复杂度分析---------编程-----上机调试--------实验分析------结论,本文是采用这样的顺序描述算法的。
本文所写算法对应于一个NP-Hard问题,主要采用近似求解算法和贪心算法的思想。
这对应于机器学****中Binary Classification,PLA ,Pocket Algorithm
问题描述:
银行发信用卡问题。现有一群人,数量为N,(N很大),假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有(对应第i个人的信息,相应的我们可以认为是这个人的一些个人数据的量化值,比如年龄、学历、收入、工作年限等等, -1 对应于)。如果y是-1,则对应于银行没有给他发信用卡。如果是y=1,则是发给了它信用卡。现在由这样的一推数据如何得到一个函数,有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断,一边给银行提供发卡的依据。
, ,这里我们可以叫他测试数据集。对于银行,他之前会设置一个发信用卡的门限值threshold.
算法描述和伪代码表述:
之前我们都是用PLA(perception learning algorithm):它是针对于线性可分的训练集的。也就是这样的所有的数据,比如说是二维数据点,可以用一条直线将他们分成两派,一片是可发卡的数据,直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较,作差为正则发卡,为负则不发卡。
这里假设一个Hypothesis datasets ,每计算一次都是一个H,如果有错则修正,一直到所有的数据都没有错误,这样的H就是我们的未知的目标函数f。
对于h,
这里h可以化简一下,

PLA的算法描述是:wt是类似于那条直线的法向量,()是一个人的数据记录
for t=0,1,2,3....
find a mistake of wt called (
)
try to correct the mistake by
对于线性可分数据集PLA算法是收敛的证明:
,t是代表第t次得到的结果或者第t次所用的数值。
(1)这里是单增的,如果从向量角度看,两个向量内积越大,如果排除其模值得快速增大,可以看做是其角度在不断的调整,逐渐变得同向。(2)就是证明其模值变化有限。
(2)
这里可以认为每次增加的步长有限,同时也说明两个向量的内积越来越大,不是因为其模值快速变化所致。因此可以看出最终得到的Wt是收敛的(对于线性可分数据集)。
而且可以算出t的取值:

而且:

则
这是线性可分数据集的PLA终止时的T的次数表达式。

PLA算法对于线性可分的数据源是可以最后能得到目标函数的。但是对于线性不可分的数据集,它不会自动的停止。对于非线性不可分的数据集,如果对其分类,它将是一个NP-Hard问题。这里的Pocket算法,则是一种近似算法,他是用贪心算法,每次将PLA修正的wt与pocket记录的pwt比较,对于所有数据集犯错最少的那个作为新的pwt,这样PLA一直进行,得到修正的值wt与pwt比较,如果wt的犯错少,则将pwt更新为wt。如果进行的Pocket算法运行时间足够长,因此我们就可以找到一个算错尽可能少的pwt。并以此来进行对于测试数据集的分类。
Pocket算法如果对于线性可分数据集,它会自动停止,并且得到一个wt,线性可分数据集,然后用于测试。
本文主要是采用pocket算法():
//%
initialize pocket weights pwt
for t=0,1,2,....
//%find a (random) mistake of wt called (xn(t),yn(t))
while !flag
d<-(Maxnum-1)*rand()+1;
//%X[d] representative the d row datas
x[d][1]=1,x[d][2..n]=X[d][1..n-1];
y=X[d][n],
if sign(Wt'*x[d])~=y
flag<-true;

//%try to correct the mistake by

//%if Wt+1 makes fewer mistakes than replace pwt with Wt+