机器学习pla算法.doc

.PLAandPOCKET问题描述--------算法思想设计描述------伪代码-----复杂度分析---------编程-----上机调试--------实验分析------结论,本文是采用这样的顺序描述算法的。本文所写算法对应于一个NP-Hard问题,主要采用近似求解算法和贪心算法的思想。这对应于机器学习中BinaryClassification,PLA,PocketAlgorithm问题描述:银行发信用卡问题。现有一群人,数量为N,(N很大),假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有1 2={(x ,x ,...,x )}i nX(对应第i个人的信息,相应的1 2x ,x ,...,xn我们可以认为是这个人的一些个人数据的量化值,比如年龄、学历、收入、工作年限等等,-1对应于1 2 3 4, , , ,x x x x y)。如果y是-1,则对应于银行没有给他发信用卡。如果是y=1,则是发给了它信用卡。现在由这样的一推数据如何得到一个函数,有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断,一边给银行提供发卡的依据。,,这里我们可以叫他测试数据集。对于银行,:之前我们都是用PLA(perceptionlearningalgorithm):它是针对于线性可分的训练集的。也就是这样的所有的数据,比如说是二维数据点,可以用一条直线将他们分成两派,一片是可发卡的数据,直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较,作差为正则发卡,为负则不发卡。这里假设一个Hypothesisdatasets,每计算一次都是一个H,如果有错则修正,一直到所有的数据都没有错误,这样的H就是我们的未知的目标函数f。对于h,1(x) sign( ),1sign(x)0, 0di iih wx thresholdx?? ???????,x>,0 0threshold w , x =1?可以当做因此对应于0(x) sign( ),di iih wx???(x) sign(W X)Th?11iy?????PLA的算法描述是:wt是类似于那条直线的法向量,((t), y (t)n nx)是一个人的数据记录fort=0,1,2,3....findamistakeofwtcalled((x (t), y (t))n nsign( X (t)) y (t)Tt n nW?)trytocorrectthemistakeby1 tW ---W (t) X (t)t n ny?? ?对于线性可分数据集PLA算法是收敛的证明:(t) W (t) min W 0T Tn f n n f nnY X Y X? ?,t是代表第t次得到的结果或者第t次所用的数值。(1)1 n(W y (t) X (t))W minWT Tf t f t nT Tf t n f nnTf tW W WW y W XW?? ?? ??Wt这里是单增的,如果从向量角度看,两个向量内积越大,如果排除其模值得快速增大,可以看做是其角度在不断的调整,逐渐变得同向。(2)就是证明其模值变化有限。(2)2 212 22 2(t) X (t)2 (t) W (t)+ y (t) X (t)0 y (t) X (t) , ( )t t n nTt n t n n nt