1 / 11
文档名称:

机器学习pla算法.doc

格式:doc   大小:162KB   页数:11页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

机器学习pla算法.doc

上传人:文库旗舰店 2019/11/12 文件大小:162 KB

下载得到文件列表

机器学习pla算法.doc

文档介绍

文档介绍:PLA and POCKET问题描述--------算法思想设计描述------伪代码-----复杂度分析---------编程-----上机调试--------实验分析------结论,本文是采用这样的顺序描述算法的。本文所写算法对应于一个NP-Hard问题,主要采用近似求解算法和贪心算法的思想。这对应于机器学****中Binary Classification,PLA,Pocket Algorithm问题描述:银行发信用卡问题。现有一群人,数量为N,(N很大),假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有(对应第i个人的信息,相应的我们可以认为是这个人的一些个人数据的量化值,比如年龄、学历、收入、工作年限等等, -1对应于)。如果y是-1,则对应于银行没有给他发信用卡。如果是y=1,则是发给了它信用卡。现在由这样的一推数据如何得到一个函数,有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断,一边给银行提供发卡的依据。,,这里我们可以叫他测试数据集。对于银行,:之前我们都是用PLA(perceptionlearningalgorithm):它是针对于线性可分的训练集的。也就是这样的所有的数据,比如说是二维数据点,可以用一条直线将他们分成两派,一片是可发卡的数据,直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较,作差为正则发卡,为负则不发卡。这里假设一个Hypothesisdatasets,每计算一次都是一个H,如果有错则修正,一直到所有的数据都没有错误,这样的H就是我们的未知的目标函数f。对于h,这里h可以化简一下,PLA的算法描述是:wt是类似于那条直线的法向量,()是一个人的数据记录for t=0,1,2,3....findamistakeofwt called ()trytocorrectthemistakeby对于线性可分数据集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算法()://%=0,1,2,....//%finda(random)mistakeofwtcalled(xn(t),yn(t))while!flagd<-(Maxnum-1)*rand()+1;//%X[d]representativethedrowdatasx[d][1]=1,x[d][2..n]=X[d][1..n-1];y=X[d][n],ifsign(Wt'*x[d])~=yflag<-true;//%trytocorrectthemistakeby//%if Wt+1 makesfewermistakesthanreplacepwtwithWt+1 iffunWtError(pwt,dataset)>funWtError(Wt+1,dataset)pwt=Wt+1;until enoughiterationst= (asWpocket)  %对应于wn的训练集的错误概率计算%(wt1,dataset)datasetmatr