机器学习PLA算法

1、PLA and POCKET问题描述-算法思想设计描述-伪代码-复杂度分析-编程-上机调试-实验分析-结论，本文是采用这样的顺序描述算法的。本文所写算法对应于一个NP-Hard问题，主要采用近似求解算法和贪心算法的思想。这对应于机器学习中Binary Classification，PLA ，Pocket Algorithm问题描述：银行发信用卡问题。现有一群人，数量为N，（N很大），假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有（对应第i个人的信息，相应的我们可以认为是这个人的一些个人数据的量化值，比如年龄、学历、收入、工作年限等等，他们会对应于一组数值如0.94544

2、 0.42842 0.79833 0.16244 -1 对应于）。如果y是-1，则对应于银行没有给他发信用卡。如果是y=1，则是发给了它信用卡。现在由这样的一推数据如何得到一个函数，有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断，一边给银行提供发卡的依据。具体数据见附录Q18Train.m为训练数据集， Q18TestData.m为待判断数据集，这里我们可以叫他测试数据集。对于银行，他之前会设置一个发信用卡的门限值threshold.算法描述和伪代码表述：之前我们都是用PLA（perception learning algorithm）：它是针对于线性可分的

3、训练集的。也就是这样的所有的数据，比如说是二维数据点，可以用一条直线将他们分成两派，一片是可发卡的数据，直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较，作差为正则发卡，为负则不发卡。这里假设一个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

4、 对于线性可分数据集PLA算法是收敛的证明：，t是代表第t次得到的结果或者第t次所用的数值。 （1）这里是单增的，如果从向量角度看，两个向量内积越大，如果排除其模值得快速增大，可以看做是其角度在不断的调整，逐渐变得同向。（2）就是证明其模值变化有限。（2）这里可以认为每次增加的步长有限，同时也说明两个向量的内积越来越大，不是因为其模值快速变化所致。因此可以看出最终得到的Wt是收敛的（对于线性可分数据集）。而且可以算出t的取值：而且： 则这是线性可分数据集的PLA终止时的T的次数表达式。 PLA算法对于线性可分的数据源是可以最后能得到目标函数的。但是对于线性不可分的数据集，它不会自动的停止。对于

5、非线性不可分的数据集，如果对其分类，它将是一个NP-Hard问题。这里的Pocket算法，则是一种近似算法，他是用贪心算法，每次将PLA修正的wt与pocket记录的pwt比较，对于所有数据集犯错最少的那个作为新的pwt，这样PLA一直进行，得到修正的值wt与pwt比较，如果wt的犯错少，则将pwt更新为wt。如果进行的Pocket算法运行时间足够长，因此我们就可以找到一个算错尽可能少的pwt。并以此来进行对于测试数据集的分类。Pocket算法如果对于线性可分数据集，它会自动停止，并且得到一个wt，线性可分数据集，然后用于测试。本文主要是采用pocket算法（）：/%funpocket2.mi

6、nitialize pocket weights pwtfor t=0,1,2,. /%find a (random) mistake of wt called (xn(t),yn(t)while !flagd<-(Maxnum-1)*rand()+1;/%Xd representative the d row datas xd1=1,xd2.n=Xd1.n-1;y=Xdn,if sign(Wt'*xd)=yflag<-true;/%try to correct the mistake by/%if Wt+1 makes fewer mistakes than replac

7、e pwt with Wt+1 if funWtError(pwt,dataset)>funWtError(Wt+1,dataset)pwt=Wt+1;until enough iterations t= stop.return pwt (as Wpocket)%对应于wn的训练集的错误概率计算%funWtError.m funWtError(wt1,dataset)dataset matrix n rows ,m colsxn1=1;while count<=nxn2.m=datasetcount1.m-1;yn=datasetcountm;if sign(wn1'*xn

8、)=ynerrFlag<-=errFlag+1;count<-=count+1;reutrn errFlag/n;关于pocket算法的几点说明：（1）对应于上述算法，在funpocket2.m中initialize pocket weights pwtfor t=0,1,2,./%find a (random) mistake of wt called (xn(t),yn(t)查找一个随机的带有错误数据的Wt，这样随机找是很慢的可以改进一下，Wt，对应于这个法向量，先判断出相应有错误的数据集，然后再再从这里面进行随机，这样的查找更快些。对应于程序中的实现是采用了这种方式。而不是每

9、次都随机选一行的数据，判断是不是有错，有错在更新，如果一直随机都是没错的那么就相当的耗费时间。（2）pocket算对于线性不可分数据集是不会终止的，也就是说，他是一个NP问题。如果数据集大体上是线性可分数据集，只有一部分点不可分，我们只需要运行足够长的时间，或者pwt进行一定数量的替换，用这种T次更新取代完全更新到正确的t次数的近似和每次遇到好的Wt+1都才用贪心的算法替代pwt，这样也能得到一个比较好的分线结果。复杂度分析对于近似算法解NP问题，这里的时间复杂度：对于，其时间复杂度为，find a (random) mistake of wt called (xn(t),yn(t)时间复杂度

10、为对应于wn的训练集的错误概率计算总的时间复杂度：，为一个向量与另一个向量的乘积所用时间。 ，又是n的函数（一个多项式），。此时如果采用给出的伪代码中的随机选一个来判断数据对于Wt是否有误，这样就像是非确定算法，采用猜测的形式将所有的可能性随机的选一个，结果是YES/NO，NO时继续随机选取，猜算可以在多项式时间内完成；验算其实就计算的有限时间了。有限时，就是采用近似的算法，虽然并不一定能够得到一个全局的满足的Wt，但是对于绝大多数的点分类还是可以的，这就是我们想要的。 因此，近似的贪心算法思想的pocket算法其时间复杂度是多项式的函数，可以在时间多项式内完成。代码编程(matlab实现)%

11、/%FunRandArray.m function arr= FunRandArray(Maxnum,repeatFlag)%Arraymaxnum,if not input ,the repeatflag=1%repeatFlag=0 %generate the the navie cycly data set%repeatFlaf=1 % ,generate the rand ,arr may have the same data%repeatFlaf=2 %generate the the rand data set visit, rand('state',sum(100

12、.*clock)*rand(1); arr=(Maxnum-1).*rand(1,Maxnum)+1; arr1=ceil(arr(:,:); flag=0; arr=arr1;%nature sequence if repeatFlag=0 for i=1:Maxnum arr(i)=i; end else if repeatFlag=1 else if repeatFlag=2 %to change into the different data AllData=zeros(1,Maxnum); for i=1:Maxnum ALLData(i)=i; end %/ %clear the

13、same data in the arr for i=1:Maxnum flag=0; for j=1:Maxnum if arr(i)=ALLData(j) flag=1; ALLData(j)=-1; break; end end if flag=0 arr(i)=0; end end %/ %add the no exist data but in 1-400 to the arr for i=1:Maxnum if arr(i)=0 for j=1:Maxnum if ALLData(j)=-1 arr(i)=ALLData(j); ALLData(j)=-1; break; end

14、end end end end end end%/%funWtError.mfunction errDataSetLine,errPossablitiy=funWtError(Wn1,DataSet)n m=size(DataSet);errFlag1=0;count=1;xn=ones(1,m);errDataSetLineTemp=zeros(1,n);while count<=n xn(1,2:m)=DataSet(count,1:m-1); yn1=xn*Wn1' if yn1=0 %= not = yn1=-1; end if sign(yn1)=DataSet(cou

15、nt,m) %sign ()function errFlag1=errFlag1+1; errDataSetLineTemp(1,errFlag1)=count; end count=count+1;enderrDataSetLine=zeros(1,errFlag1);errDataSetLine(1,:)=errDataSetLineTemp(1,1:errFlag1);errPossablitiy=errFlag1/n;%/%funWwtBestfunction pockWn,flag,errPossablitiy=funWwtBest(Wn1,Wn2,DataSet)n m=size(

16、DataSet);errFlag1=0;errFlag2=0;flag=0;%0 Wn1 , 1 Wn2count=1;xn=ones(1,m);while count<=n xn(1,2:m)=DataSet(count,1:m-1); yn1=xn*Wn1' yn2=xn*Wn2' if yn1=0 %= not = yn1=-1; end if yn2=0 yn2=-1; end %this is error because the sign function not use. %if yn1=DataSet(count,m) if sign(yn1)=DataSe

17、t(count,m) errFlag1=errFlag1+1; end % if yn2=DataSet(count,m) if sign(yn2)=DataSet(count,m) errFlag2=errFlag2+1; end count=count+1;enderrPossablitiy=errFlag1/n;pockWn=Wn1;if errFlag1>errFlag2 pockWn=Wn2; flag=1; errPossablitiy=errFlag2/n;end%/%funPocket.mfunction pockWn,Wn,count,updateTTs,errposs

18、=funPocket(FData,FunRandArray,funWwtBest,updateTimes,WnrndFlag,DatasetFlag,nn)%parameters annotaion%to the input parameters requestif nargin=0 |nargin=1 |nargin=2 error('parameters number lacks');endif nargin=3 updateTimes=200; WnrndFlag=0; DatasetFlag=0; n=1;endif nargin>7 error('inp

19、ut parameters too larger');end%initial dataset1=FData;n m=size(dataset1);Wn=zeros(1,m);Wn(1,1)=0;if WnrndFlag=1 rand('state',sum(100*clock)*rand(1); Wn(2,m)=rand(1,m-1);end%training set visiting sequence%ResultRand=zeros(1,n);%ResultRand=FunRandArray(n,DatasetFlag);xn=ones(1,m);count=0;%

20、count numbersnoequalCount=0;%pocketWnpockWn=zeros(1,m);updateTTs=0;errposs=0;%at the end the pockWn's error possiablityfilename1=strcat('aa_',num2str(updateTimes*rand(1);filename1=strcat(filename1,'.txt')ffile1=fopen(filename1,'w');while updateTTs<updateTimes %from the

21、 error DataSet (some Wn) rand select a Xi %errDataSetLine is arr1.errFlag, %arr1= the first number of Xi not satisfying yn=xn*Wn' %the number corresponing the DataSet 's line label errDataSetLine,errPossTemp=funWtError(Wn,dataset1); nerr,merr=size(errDataSetLine); rand('state',sum(10

22、0*clock)*rand(1); num=ceil(merr-1)*rand(1)+1); xn(2:m)=dataset1(errDataSetLine(1,num),1:m-1); ytemp=xn*Wn' if ytemp=0 ytemp=-1; end signtemp=sign(ytemp); %signtemp,dataset1(ResultRand(num),m) % num, xn,xn*Wn', signtemp,dataset1(num,m) %if signtemp=dataset1(ResultRand(num),m) %num if signtemp

23、=dataset1(errDataSetLine(1,num),m) %Wn(1,1:m)=Wn(1,1:m)+nn.*xn(1,1:m)*dataset1(ResultRand(num),m); Wn(1,1:m)=Wn(1,1:m)+nn*dataset1(errDataSetLine(1,num),m).*xn(1,1:m); %a='before',Wn,pockWn tempWn,flag,errposs=funWwtBest(Wn,pockWn,dataset1); %a='after',Wn,tempWn if flag=0 updateTTs=u

24、pdateTTs+1; pockWn=tempWn; fprintf(ffile1,' %s tt','updateTTs'); fprintf(ffile1,'%d tttrn', updateTTs); fprintf(ffile1,' %s tt','pocketWn'); fprintf(ffile1,'%f tttrn',pockWn); updateTTs % else % Wn=pockWn; end %pockWn %count=1; endendfclose(ffile1);%po

25、ckWn %/% pocketTrainTest.m function errAverage=pocketTrainTest(LoopNum,FDataTrain,FDTest,FunRandArray,funWwtBest,funWtError,updateTimes,WnrndFlag,DatasetFlag,nn)FData=load(FDataTrain);%n m=size(FData);FDataTest=load(FDTest);avgerr=0;errPossArr=zeros(1,LoopNum);%pockWn=zeros(LoopNum,m);pockWnTemp=zer

26、os(1,m);Wn=zeros(1,m);for i=1:1:LoopNum pockWnTemp,Wn,count,updatenum,errposs=funPocket(FData,FunRandArray,funWwtBest,updateTimes,WnrndFlag,DatasetFlag,nn); errDataSetLine,errPossTemp=funWtError(pockWnTemp,FDataTest); %errPossTemp avgerr=(avgerr*(i-1)+errPossTemp)/i %errPossTemp errPossArr(1,i)=errP

27、ossTemp;enderrAverage=mean(errPossArr(1,:);%/%pocketTrainTest.m errAverage=pocketTrainTest(LoopNum,FDataTrain,FDTest,FunRandArray,funWwtBest,funWtError,updateTimes,WnrndFlag,DatasetFlag,nn)FData=load(FDataTrain);%n m=size(FData);FDataTest=load(FDTest);avgerr=0;errPossArr=zeros(1,LoopNum);pockWnTemp=

28、zeros(1,m);Wn=zeros(1,m);filename=strcat('aa',num2str(updateTimes);filename=strcat(filename,'.txt')ffile=fopen(filename,'w');%filenamefprintf(ffile,'%s tt','i');fprintf(ffile,' %s tt','pockWnTemp');fprintf(ffile,'%s tttrn','avgerr&#

29、39;);for i=1:1:LoopNum i pockWnTemp,Wn,count,updatenum,errposs=funPocket(FData,FunRandArray,funWwtBest,updateTimes,WnrndFlag,DatasetFlag,nn); errDataSetLine,errPossTemp=funWtError(pockWnTemp,FDataTest); %errPossTemp avgerr=(avgerr*(i-1)+errPossTemp)/i fprintf(ffile,'%d t',i ); fprintf(ffile,

30、' %f t',pockWnTemp); fprintf(ffile,' %f rn',avgerr); %errPossTemp errPossArr(1,i)=errPossTemp;enderrAverage=mean(errPossArr(1,:);fprintf(ffile,' %s t','errAverage:');fprintf(ffile,' %f t',errAverage);fclose(ffile);%/% pockettest.mfunction pockettest()tic;errAv

31、erage=pocketTrainTest(2,'Q18Train.m','Q18TestData.m',FunRandArray,funWwtBest,funWtError,50,0,0,1) t1=toc;t1上机调试改正了其中的一些错误。其中最明显的一个错误是符号函数的应用，有个地方忘记应用，导致所有的Wt对应于数据的错误概率都是1，也就是即使最好的分线器，错误概率也是1.通过分析可出错误的地方是判断错误的函数里面忘记加上符号函数。实验分析errAverage=pocketTrainTest(2,'Q18Train.m','Q18T

32、estData.m',FunRandArray,funWwtBest,funWtError,50,0,0,1) 更新50次得出的Wt然后验证Testdata数据集，并且得出错误概率，这样运行2个50次，所用时间T=34214s，约为9小时30分，如果运行100次更新，这样运行1次100更新所用时间也差不多这么大。下面是2个 50次更新的所得数据：结果如下：之前有个运行100次更新的数据为：更新50次和更新100次也有可能得到相同的效果，这都是随机的选取错误概率的原因，因此我们还可以更新100次，并且这样跑上2000次，得出一个平均的错误概率，最坏的情形就是一直在跑，最好的情形就是对于线

33、性可分数据集自动结束。因此这里我们用平均情况来衡量即可。结论实践证明：用近似算法模拟pocket，对于线性不可分数据集可以得到一个比较好的pwt-分类器。如果设置Tmax=50或者100，都可以，但是数值越大运行时间越长。可以很好的解决这个NP问题。附录：数据部分仅是部分数据Training datasets （Q18Train.m）0.94544 0.42842 0.79833 0.16244-10.85365 0.084168 0.5682 0.49221-10.17095 0.82127 0.98444 0.51486-10.51412 0.92124 0.42323 0.097934-

34、10.28147 0.71434 0.075309 0.911610.46295 0.64512 0.96324 0.31516-10.97789 0.80155 0.90235 0.74203-10.41825 0.69419 0.46246 0.31523-10.75203 0.20264 0.8765 0.47593-10.31767 0.16814 0.97148 0.7562510.60639 0.6256 0.69092 0.23644-10.74736 0.58863 0.85253 0.49688-10.40388 0.92436 0.56477 0.44963-10.9018

35、7 0.32117 0.74473 0.24326-10.73095 0.2588 0.43453 0.9705910.50315 0.41884 0.026094 0.916231Q18TestData.m0.62926 0.32783 0.010417 0.7310210.32368 0.61439 0.42097 0.025626-10.15968 0.83346 0.97515 0.32762-10.023526 0.30292 0.014961 0.9228810.45804 0.7452 0.83406 0.5493210.2076 0.8426 0.41797 0.0027624-10.89481 0.30394 0.45773 0.007992-10.37353 0.26077 0.50573 0.22075-10.87324 0.29592 0.13117 0.4076-10.55605 0.36385 0.92008 0.13382-10.58155 0.73471 0.014257 0.27127-10.66163 0.13357 0.58564 0.3