Font Size: a A A

An Alternative Multiplicative Updates Algorithm For Quadratic Programming In Support Vector Machines

Posted on:2019-06-09Degree:MasterType:Thesis
Country:ChinaCandidate:Y ZhouFull Text:PDF
GTID:2428330566983401Subject:Control Science and Engineering
Abstract/Summary:PDF Full Text Request
Support vector machine(SVM)is an important branch of machine learning,having made rapid progress since proposed.The multiplicative update rule is one of the innovative iterative tools for solving the objective function of SVM,such that having attracted the attention of many researchers.In recent years,SMO(Sequential Minimum Optimization)algorithm is the main support vector machine implementation framework.Although the algorithm is fast,its programming complexity.In order to facilitate programming easily,Sha Fei put forward multiplicative updates for nonnegative quadratic programming.They are easy to operate and program and all variables of quadratic programming can be run in parallel unlike the SMO algorithm,in which only two variables can be iterated at a time.Moreover,it's low requirements for computer hardware.The solution of objective function of support vector machine can be equivalent to optimization of quadratic programming with constraints.By applying the new algorithm to support vector machines,the algorithm provides a directly optimized multiplicative updating rule,which does not require a fixed working subset,does not need to carefully examine the learning rate of each step,and in which all variables can be iterated in pa rallel.And direct method is used to solve the quadratic programming with sum constraint and the iterative formula of constraint coefficients.Further,the multiplicative update rule is deduced and applied to support vector machine.Theoretical and experimental results show that compared with the Sha Fei framework,the SMO is faster than Sha's.In this paper,a new multiplicative update algorithm is proposed to solve the problem of the low speed of Sha Fei's framework.First,on the basis of Sha Fei's framework a new auxiliary function is constructed,and a new multiplicative update rule is proposed.Compared with the Sha Fei's framework,the algorithm is easier to program because it has no square root computation in the algorithm.The theoretical basis of the rule is to decompose the symmetric and semipositive definite matrix into positive and negative components of the matrix and construct auxiliary functions for them respectively.The auxiliary function construction method of positive part is similar to that in Sha Fei's framework.The difference is that the negative part's auxiliary function is constructed by a simple linear function instead of a logarit hmic function,and a new multiplicative update rule is derived.Second,I use Newton method to solve the sum constraint coefficients,in quadratic programming with sum constraints.Experimental results show that compared with the Sha Fei's framework,it can greatly improve the speed of optimization.In application of support vector machine,on the premise of generally consistent accuracy,the computational time of the proposed method is reduced to about half of the Sha's method.Theoretical and experimental results show that the algorithm greatly o ptimizes the convergence time of SVM and shortens the computation time of SVM in general.
Keywords/Search Tags:support vector machine, nonnegative quadratic programming, multiplicative update rule, sum constraints, Newton method
PDF Full Text Request
Related items