機(jī)器學(xué)習(xí)PLA算法

1、PLA and POCKET問題描述 算法思想設(shè)計(jì)描述-偽代碼-復(fù)雜度分析 編程-上機(jī)調(diào)試實(shí)驗(yàn)分析-結(jié)論，本文是采用這樣的順序描述算法的。本文所寫算法對(duì)應(yīng)于一個(gè) NP-Hard問題，主要采用近似求解算法和貪心算法的思想。這對(duì)應(yīng)于機(jī)器學(xué)習(xí)中Binary Classification , PLA , Pocket Algorithm問題描述：銀行發(fā)信用卡問題?，F(xiàn)有一群人，數(shù)量為 N , (N很大)，假設(shè)他們在一個(gè)銀行中的登記記錄數(shù)據(jù)我們已經(jīng)得到。對(duì)于每個(gè)人記錄的數(shù)據(jù)有Xj=(x 1,x2,.,xn)(對(duì)應(yīng)第i個(gè)人的信息，相應(yīng)的x1,x2,.,xn我們可以認(rèn)為是這個(gè)人的一些個(gè)人數(shù)據(jù)的量化值，比如年齡

2、、學(xué)歷、收入、工作年限等等，他們會(huì)對(duì)應(yīng)于一組數(shù)值如0.94544 0.42842 0.79833 0.16244 -1對(duì)應(yīng)于為兇，知乂4, y )。如果y是-1，則對(duì)應(yīng)于銀行沒有給他發(fā)信用卡。如果是 y=1 ,則是發(fā)給 了它信用卡。現(xiàn)在由這樣的一推數(shù)據(jù)如何得到一個(gè)函數(shù)，有這些訓(xùn)練集得到這個(gè)目標(biāo)函數(shù)。并用這個(gè)目標(biāo)函數(shù)作用于對(duì)于一群待發(fā)信用卡的人作出判斷，一邊給銀行提供發(fā)卡的依據(jù)。具體數(shù)據(jù)見附錄 Q18Train.m為訓(xùn)練數(shù)據(jù)集，Q18TestData.m為待判斷數(shù)據(jù)集，這里我們可以叫他測試數(shù)據(jù)集。對(duì)于銀行，他之前會(huì)設(shè)置一個(gè)發(fā)信用卡的門限值threshold.算法描述和偽代碼表述：之前我們都是用

3、PLA (perception learning algorithm )：它是針對(duì)于線性可分的訓(xùn)練集的。也就是這樣的所有的數(shù)據(jù)，比如說是二維數(shù)據(jù)點(diǎn)，可以用一條直線將他們分成兩派，一片是可發(fā)卡的數(shù)據(jù)，直線另一側(cè)則是不可發(fā)卡數(shù)據(jù)。 將用戶數(shù)據(jù)加權(quán)求和與門限值相比較，作差為正則發(fā)卡，為負(fù)則不發(fā)卡。這里假設(shè)一個(gè) Hypothesis datasets，每計(jì)算一次都是一個(gè)H ,如果有錯(cuò)則修正，一直到所有的數(shù)據(jù)都沒有錯(cuò)誤，這樣的H就是我們的未知的目標(biāo)函數(shù)f。dh(x) =sign(Z wx -threshold),對(duì)于h,1, x>0sign(x)=0,x£0這里h可以化簡一下，-thre

4、shold可以當(dāng)做w0,因此對(duì)應(yīng)丁 x0=1dh(x) =sign(' x),i =0h(x) =sign(WTX)-1y“1PLA的算法描述是：Wt是類似于那條直線的法向量，(xn(t),yn(t)是一個(gè)人的數(shù)據(jù)記錄for t=0,1,2,3.find a mistake of wt called (x n(t), y n (t)sign(WTtXn(t) =yn(t)try to correct the mistake by叫 1 Wtyn(t)X n(t)對(duì)于線性可分?jǐn)?shù)據(jù)集PLA算法是收斂的證明：Yn(t) WTf Xn(t)芝mjnYn WTf Xn0 , t是代表第t次得到的

5、結(jié)果或者第t次所用的 數(shù)值。WfTWt 1 =WfT(Wt yn(t)Xn(t)(1) 芝WfTWt +min ynWfTXnWt這里是單增的，如果從向量角度看，兩個(gè)向n-WfT Wt量內(nèi)積越大，如果排除其模值得快速增大，可以看做是其角度在不斷的調(diào)整，逐漸變得同向。(2)就是證明其模值變化有限。(2)|Wt J=|Wt +yn(t)Xn(t)|2= |Wt+2yn(t)WTtXn(t)+ |yn(t)Xn(t)|郁 Wt|2 +0+|yn(t)Xn(t)|2,(有錯(cuò)時(shí),)Wf作為法線的直線去判斷訓(xùn)練數(shù)據(jù)集是有錯(cuò)的，Usign(WTtXn(t) = yn(t) = yjt) WTt Xn(t 0

6、22Wt.1= Wt yn(t)Xn(t)|22£叫| -max ynXn22-Wt| -max Xn這里可以認(rèn)為每次增加的步長有限，同時(shí)也說明令 M = max n,2W.1WXn2M 兩個(gè)向量的內(nèi)積越2來越大，不是因?yàn)槠淠Ｖ悼焖僮兓?。因此可以看出最終得到的Wt是收斂的（對(duì)于線性可分?jǐn)?shù)據(jù)集）而且可以算出t的取值：WfTWt 1 =WfT(Wt yn(t)Xn(t)將t+1變成T有WfTWr_WfTWr4 min ynWfTXn n_WfTW"2 min ynWfTXn min ynWfTXnnn_WfTW0 TminynWfTXn n-Tmin ynWXn n而且：|

7、Wt<|Wt2 +max|xn|2紂 |Wo|+Tmax|x22T max xnnWfTWrTmn YnWTfXn帆|恤|Wf II 寸 max|Xn|2R2 = mnax XnWfYn：WfTXn，則T £R/2這是線性可分?jǐn)?shù)據(jù)集的 PLA終止時(shí)的T的次數(shù)表達(dá)式。PLA算法對(duì)于線性可分的數(shù)據(jù)源是可以最后能得到目標(biāo)函數(shù)的。但是對(duì)于線性不可分 的數(shù)據(jù)集，它不會(huì)自動(dòng)的停止。對(duì)于非線性不可分的數(shù)據(jù)集，如果對(duì)其分類，它將是一個(gè) NP-Hard問題。這里的Pocket算法，則是一種近似算法，他是用貪心算法，每次將 PLA修 正的wt與pocket記錄的pwt比較，對(duì)于所有數(shù)據(jù)集犯錯(cuò)最少的

8、那個(gè)作為新的pwt,這樣PLA一直進(jìn)行，得到修正的值 wt與pwt比較，如果 wt的犯錯(cuò)少，則將 pwt更新為wt。如果進(jìn) 行的Pocket算法運(yùn)行時(shí)間足夠長，因此我們就可以找到一個(gè)算錯(cuò)盡可能少的pwt。并以此來進(jìn)行對(duì)于測試數(shù)據(jù)集的分類。Pocket算法如果對(duì)于線性可分?jǐn)?shù)據(jù)集，它會(huì)自動(dòng)停止，并且得到一個(gè)wt,線性可分?jǐn)?shù)據(jù)集，然后用于測試。本文主要是采用pocket算法0 :/%funpocket2.m initialize pocket weights pwt for t=0,1,2,./%find a (random) mistake of wt called (xn(t),yn(t) wh

9、ile !flag d<-(Maxnum-1)*rand()+1;/%Xd representative the d row datasxd1=1,xd2.n=Xd1.n-1;Y=Xdn, if sign(Wt'*xd)=Y flag<-true;/%try to correct the mistake byWt1-Wt Yn(t)為(t)/%if Wt+1 makes fewer mistakes than replace pwt with Wt+1if funWtError(pwt,dataset)>funWtError(Wt+1,dataset)pwt=Wt+1

10、;until enough iterations t= Tmaxstop.return pwt (as Wpocket)%對(duì)應(yīng)于wn的訓(xùn)練集的錯(cuò)誤概率計(jì)算%funWtError.mfunWtError(wt1,dataset)dataset matrix n rows ,m colsxn1=1;while count<=nxn2.m=datasetcount1.m-1;yn=datasetcountm;if sign(wn1'*xn)=ynerrFlag<-=errFlag+1;count<-=count+1;reutrn errFlag/n;關(guān)于pocket算法的幾

11、點(diǎn)說明：(1) 對(duì)應(yīng)于上述算法，在 funpocket2.m中initialize pocket weights pwtfor t=0,1,2,./%find a (random) mistake of wt called (xn(t),yn(t)查找一個(gè)隨機(jī)的帶有錯(cuò)誤數(shù)據(jù)的 Wt,這樣隨機(jī)找是很慢的可以改進(jìn)一下，Wt,對(duì)應(yīng)于這個(gè)法向量，先判斷出相應(yīng)有錯(cuò)誤的數(shù)據(jù)集，然后再再從這里面進(jìn)行隨機(jī)，這樣的查找更快些。對(duì)應(yīng)于程序中的實(shí)現(xiàn)是采用了這種方式。而不是每次都隨機(jī)選一行的數(shù)據(jù)，判斷是不是有錯(cuò)，有錯(cuò)在更新，如果一直隨機(jī)都是沒錯(cuò)的那么就相當(dāng)?shù)暮馁M(fèi)時(shí)間。(2) pocket算對(duì)于線性不可分?jǐn)?shù)據(jù)集是不會(huì)終

12、止的，也就是說，他是一個(gè)NP問題。如果數(shù)據(jù)集大體上是線性可分?jǐn)?shù)據(jù)集，只有一部分點(diǎn)不可分，我們只需要運(yùn)行足夠長的時(shí)間，或者pwt進(jìn)行一定數(shù)量的替換，用這種T次更新取代完全更新到正確的t次數(shù)的近似和每次遇到好的Wt+1都才用貪心的算法替代pwt,這樣也能得到一個(gè)比較好的分線結(jié)果。復(fù)雜度分析對(duì)于近似算法解 NP問題，這里的時(shí)間復(fù)雜度:對(duì)于t-其時(shí)間復(fù)雜度為T(ti),find a (random) mistake of wt called (xn(t),yn(t) 時(shí)間復(fù)雜度為 T(Wti)對(duì)應(yīng)于wn的訓(xùn)練集的錯(cuò)誤概率計(jì)算 Ter(Wti)Tmax總的時(shí)間復(fù)雜度：T(n) =，T(ti), i 30

13、T(ti) =T(Wti) u(1)+2Ter(Wti)T(Wti) =(n +1)T十2 , I為一個(gè)向量與另一個(gè)向量的乘積所用時(shí)間。Ter(t) =(n 1)氣 3nT(n)=(Tmax+1)(n+1)Ti+2+e(1) + (n + 1)Ti+3n , T又是 n 的函數(shù)(一個(gè)多項(xiàng)式)，Tmax - A°°,T(n)-A上限為'的多項(xiàng)式函數(shù)。此時(shí)如果采用給出的偽代碼中的隨機(jī)選一個(gè)來判斷數(shù)據(jù)對(duì)于Wt是否有誤，這樣就像是非確定算法，采用猜測的形式將所有的可能性隨機(jī)的選一個(gè)，結(jié)果是YES/NO , NO時(shí)繼續(xù)隨機(jī)選取，猜算可以在多項(xiàng)式時(shí)間內(nèi)完成；驗(yàn)算其實(shí)就計(jì)算的有限

14、時(shí)間了0(1)0Tmax有限時(shí)，就是采用近似的算法，雖然并不一定能夠得到一個(gè)全局的滿足的Wt,但是對(duì)于絕大多數(shù)的點(diǎn)分類還是可以的，這就是我們想要的。因此，近似的貪心算法思想的pocket算法其時(shí)間復(fù)雜度是多項(xiàng)式的函數(shù)，可以在時(shí)間多項(xiàng)式內(nèi)完成。代碼編程(matlab實(shí)現(xiàn))%llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll%FunRandArray.mfunction arr= FunRandArray(Maxnum,repeatFlag)%Arr

15、aymaxnum,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.*clock)*rand(1);arr=(Maxnum-1).*rand(1,Maxnum)+1;arr1=ceil(arr(:,:

16、);flag=0;arr=arr1;%nature sequenceif repeatFlag=0for i=1:Maxnum arr(i)=i;endelse if repeatFlag=1else if repeatFlag=2%to change into the different data AllData=zeros(1,Maxnum);for i=1:Maxnum ALLData(i)=i;end%/%clear the same data in the arrfor i=1:Maxnum flag=0;for j=1:Maxnumif arr(i)=ALLData(j)flag=

17、1;ALLData(j)=-1;break;endendif flag=0 arr(i)=0;endend%/%add the no exist data but in 1-400 to the arr for i=1:Maxnumif arr(i)=0for j=1:Maxnumif ALLData(j)=-1 arr(i)=ALLData(j); ALLData(j)=-1; break;endendendendendend%/%funWtError.mfunction errDataSetLine,errPossablitiy=funWtError(Wn1,DataSet)n m=siz

18、e(DataSet);errFlag1=0;count=1;xn=ones(1,m);errDataSetLineTemp=zeros(1,n);while count<=nxn(1,2:m)=DataSet(count,1:m-1);yn1=xn*Wn1'if yn1=0%= not =yn1=-1;endif sign(yn1)=DataSet(count,m) %sign ()function errFlag1=errFlag1+1; errDataSetLineTemp(1,errFlag1)=count;endcount=count+1;enderrDataSetLin

19、e=zeros(1,errFlag1);errDataSetLine(1,:)=errDataSetLineTemp(1,1:errFlag1);errPossablitiy=errFlag1/n;%/%funWwtBestfunction pockWn,flag,errPossablitiy=funWwtBest(Wn1,Wn2,DataSet)n m=size(DataSet);errFlag1=0;errFlag2=0;flag=0;%0 Wn1 , 1 Wn2count=1;xn=ones(1,m);while count<=nxn(1,2:m)=DataSet(count,1:

20、m-1);yn1=xn*Wn1'yn2=xn*Wn2'if yn1=0%= not =yn1=-1;endif yn2=0yn2=-1;end%this is error because the sign function not use.%if yn1=DataSet(count,m)if sign(yn1)=DataSet(count,m)errFlag1=errFlag1+1;end% if yn2=DataSet(count,m)if sign(yn2)=DataSet(count,m)errFlag2=errFlag2+1;endcount=count+1;ender

21、rPossablitiy=errFlag1/n;pockWn=Wn1;if errFlag1>errFlag2pockWn=Wn2;flag=1;errPossablitiy=errFlag2/n;end%/%funPocket.mfunctionpockWn,Wn,count,updateTTs,errposs=funPocket(FData,FunRandArray,funWwtBest,updateTimes,WnrndFlag,DatasetFlag,nn)%parameters annotaion%to the input parameters requestif nargin

22、=0 |nargin=1 |nargin=2error('parameters number lacks');endif nargin=3updateTimes=200;WnrndFlag=0;DatasetFlag=0;n=1;endif nargin>7error('input parameters too larger');end%initial dataset1=FData;n m=size(dataset1);Wn=zeros(1,m);Wn(1,1)=0;if WnrndFlag=1rand('state',sum(100*cl

23、ock)*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;%count numbersnoequalCount=0;%pocketWnpockWn=zeros(1,m);updateTTs=0;errposs=0;%at the end the pockWn's error possiablityfilename1=strcat('aa_

24、',num2str(updateTimes*rand(1);filename1=strcat(filename1,'.txt')ffile1=fopen(filename1,'w');while updateTTs<updateTimes%from the 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 corres

25、poning the DataSet 's line labelerrDataSetLine,errPossTemp=funWtError(Wn,dataset1);nerr,merr=size(errDataSetLine);rand('state',sum(100*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=0ytemp=-1;endsigntemp=sign(ytemp);%sign

26、temp,dataset1(ResultRand(num),m)% num, xn,xn*Wn', signtemp,dataset1(num,m)%if signtemp=dataset1(ResultRand(num),m)%numif signtemp=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

27、='before',Wn,pockWntempWn,flag,errposs=funWwtBest(Wn,pockWn,dataset1);%a='after',Wn,tempWnif flag=0updateTTs=updateTTs+1;pockWn=tempWn;fprintf(ffile1,' %s tt','updateTTs');fprintf(ffile1,'%d tttrn', updateTTs);fprintf(ffile1,' %s tt','pocketWn'

28、);fprintf(ffile1,'%f tttrn',pockWn);updateTTs% else% Wn=pockWn;end%pockWn%count=1;endendfclose(ffile1);%pockWno/qIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII% pocketTrainTest.mfunctionerrAverage=pocketTrainTest(LoopNum,FDataTrain,F

29、DTest,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=zeros(1,m);Wn=zeros(1,m);for i=1:1:LoopNumpockWnTemp,Wn,count,updatenum,errposs=funPoc

30、ket(FData,FunRandArray,funWwtBest,upda teTimes,WnrndFlag,DatasetFlag,nn);errDataSetLine,errPossTemp=funWtError(pockWnTemp,FDataTest);%errPossTempavgerr=(avgerr*(i-1)+errPossTemp)/i%errPossTemperrPossArr(1,i)=errPossTemp;enderrAverage=mean(errPossArr(1,:);%/%pocketTrainTest.merrAverage=pocketTrainTes

31、t(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=zeros(1,m);Wn=zeros(1,m);filename=strcat('aa',num2str(updateTimes);filename=strca

32、t(filename,'.txt')ffile=fopen(filename,'w');%filenamefprintf(ffile,'%stt',T);fprintf(ffile,' %s tt','pockWnTemp');fprintf(ffile,'%stttrn','avgerr');for i=1:1:LoopNumipockWnTemp,Wn,count,updatenum,errposs=funPocket(FData,FunRandArray,funWwtBest,

33、upda teTimes,WnrndFlag,DatasetFlag,nn);errDataSetLine,errPossTemp=funWtError(pockWnTemp,FDataTest);%errPossTempavgerr=(avgerr*(i-1)+errPossTemp)/ifprintf(ffile,'%d t',i );fprintf(ffile,' %f t',pockWnTemp);fprintf(ffile,' %f rn',avgerr);%errPossTemperrPossArr(1,i)=errPossTemp;

34、enderrAverage=mean(errPossArr(1,:);fprintf(ffile,' %s t','errAverage:');fprintf(ffile,' %f t',errAverage);fclose(ffile);%/% pockettest.mfunction pockettest()tic;errAverage=pocketTrainTest(2,'Q18Train.m','Q18TestData.m',FunRandArray,funWwtBest,funWtError,50,0,0

35、,1) t1=toc;t1上機(jī)調(diào)試改正了其中的一些錯(cuò)誤。其中最明顯的一個(gè)錯(cuò)誤是符號(hào)函數(shù)的應(yīng)用，有個(gè)地方忘記應(yīng)用，導(dǎo)致所有的 Wt對(duì)應(yīng)于數(shù)據(jù)的錯(cuò)誤概率都是1,也就是即使最好的分線器，錯(cuò)誤概率也是1.通過分析可出錯(cuò)誤的地方是判斷錯(cuò)誤的函數(shù)里面忘記加上符號(hào)函數(shù)。實(shí)驗(yàn)分析errAverage=pocketTrainTest(2,'Q18Train.m','Q18TestData.m',FunRandArray,fun WwtBest,funWtError,50,0,0,1)更新50次得出的 Wt然后驗(yàn)證Testdata數(shù)據(jù)集，并且得出錯(cuò)誤概率，這樣運(yùn)行2個(gè)50次，所用時(shí)

36、間T=34214s,約為9小時(shí)30分，如果運(yùn)行100次更新，這樣運(yùn)行1次100 更新所用時(shí)間也差不多這么大。下面是2個(gè)50次更新的所得數(shù)據(jù)：結(jié)果如下:CoBAnd VindoYpocWn -2. 0000-2. 3518-3.5190-1, 90742, 3018avgert =0.1180i =2filenamel -aa_47* 2092* txt<'a NewJt A.0()0()0(%之前有個(gè)運(yùn)行100次更新的數(shù)據(jù)為:fiFl更新50次和更新100次也有可能得到相同的效果， 這都是隨機(jī)的選取錯(cuò)誤概率的原因, 因此我們還可以更新 100次，并且這樣跑上 2000次，得出一個(gè)

37、平均的錯(cuò)誤概率，最壞的情形就是一直在跑，最好的情形就是對(duì)于線性可分?jǐn)?shù)據(jù)集自動(dòng)結(jié)束。因此這里我們用平均情況來衡量即可。結(jié)論實(shí)踐證明：用近似算法模擬pocket,對(duì)于線性不可分?jǐn)?shù)據(jù)集可以得到一個(gè)比較好的pwt-分類器。如果設(shè)置 Tmax=50或者100,都可以，但是數(shù)值越大運(yùn)行時(shí)間越長。可以很好的 解決這個(gè)NP問題。K付錄:數(shù)據(jù)部分僅是部分?jǐn)?shù)據(jù)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

38、 -10.51412 0.92124 0.42323 0.097934-10.28147 0.71434 0.075309 0.9116 10.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.75625 10.60639 0.6256 0.69092 0.23644 -10.74736 0.58863 0.85253 0.496

39、88 -10.40388 0.92436 0.56477 0.44963 -10.90187 0.32117 0.74473 0.24326 -10.73095 0.2588 0.43453 0.97059 10.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.54932 10.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.556