机器学习pla算法

《机器学习pla算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-PLAandPOCKET问题描述--------算法思想设计描述------伪代码-----复杂度分析---------编程-----上机调试--------实验分析------结论，本文是采用这样的顺序描述算法的。本文所写算法对应于一个NP-Hard问题，主要采用近似求解算法和贪心算法的思想。这对应于机器学习中BinaryClassification，PLA，PocketAlgorithm问题描述：银行发信用卡问题。现有一群人，数量为N，（N很大），假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有（对应第i个人的信息，相应

2、的我们可以认为是这个人的一些个人数据的量化值，比如年龄、学历、收入、工作年限等等，他们会对应于一组数值如0.945440.428420.798330.16244-1对应于）。如果y是-1，则对应于银行没有给他发信用卡。如果是y=1，则是发给了它信用卡。现在由这样的一推数据如何得到一个函数，有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断，一边给银行提供发卡的依据。具体数据见附录Q18Train.m为训练数据集，Q18TestData.m为待判断数据集，这里我们可以叫他测试数据集。对于银行，他之前会设置一个发信用卡的

3、门限值threshold.算法描述和伪代码表述：之前我们都是用PLA（perceptionlearningalgorithm）：它是针对于线性可分的训练集的。也就是这样的所有的数据，比如说是二维数据点，可以用一条直线将他们分成两派，一片是可发卡的数据，直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较，作差为正则发卡，为负则不发卡。这里假设一个Hypothesisdatasets，每计算一次都是一个H，如果有错则修正，一直到所有的数据都没有错误，这样的H就是我们的未知的目标函数f。对于h，.---这里h可以化简一下，PLA的算法描述是：w

4、t是类似于那条直线的法向量，（）是一个人的数据记录fort=0,1,2,3....findamistakeofwtcalled()trytocorrectthemistakeby对于线性可分数据集PLA算法是收敛的证明：，t是代表第t次得到的结果或者第t次所用的数值。（1）这里是单增的，如果从向量角度看，两个向量内积越大，如果排除其模值得快速增大，可以看做是其角度在不断的调整，逐渐变得同向。（2）就是证明其模值变化有限。（2）.---这里可以认为每次增加的步长有限，同时也说明两个向量的内积越来越大，不是因为其模值快速变化所致。因此可以看出最终得到的

5、Wt是收敛的（对于线性可分数据集）。而且可以算出t的取值：而且：.---则这是线性可分数据集的PLA终止时的T的次数表达式。PLA算法对于线性可分的数据源是可以最后能得到目标函数的。但是对于线性不可分的数据集，它不会自动的停止。对于非线性不可分的数据集，如果对其分类，它将是一个NP-Hard问题。这里的Pocket算法，则是一种近似算法，他是用贪心算法，每次将PLA修正的wt与pocket记录的pwt比较，对于所有数据集犯错最少的那个作为新的pwt，这样PLA一直进行，得到修正的值wt与pwt比较，如果wt的犯错少，则将pwt更新为wt。如果进行的

6、Pocket算法运行时间足够长，因此我们就可以找到一个算错尽可能少的pwt。并以此来进行对于测试数据集的分类。Pocket算法如果对于线性可分数据集，它会自动停止，并且得到一个wt，线性可分数据集，然后用于测试。本文主要是采用pocket算法（）：//%funpocket2.minitializepocketweightspwtfort=0,1,2,....//%finda(random)mistakeofwtcalled(xn(t),yn(t))while!flagd<-(Maxnum-1)*rand()+1;//%X[d]representat

7、ivethedrowdatasx[d][1]=1,x[d][2..n]=X[d][1..n-1];y=X[d][n],ifsign(Wt'*x[d])~=yflag<-true;//%trytocorrectthemistakeby//%ifWt+1makesfewermistakesthanreplacepwtwithWt+1iffunWtError(pwt,dataset)>funWtError(Wt+1,dataset).---pwt=Wt+1;untilenoughiterationst=stop.returnpwt(asWpocket)%

8、对应于wn的训练集的错误概率计算%funWtError.mfunWtError(wt1,dataset)datasetma