A Classification Algorithm Based On Analytic Center Cutting Plane Method

This paper is based on the theory that the optimal solution of the support.vector machine corresponds to the analytic center of the version space.We introduce the Analytic Center Cutting Plane Method(ACCMP) to a classification algorithm proposed by Joachims,which is in order to solve the Large-Scale problem with sparse structure.In the paper,we propose two constraint delete rules which can delete the constraints of no use.The algorithm we propose aims at finding a small set of constraints from the full-sized optimization problem that ensures a sufficiently accurate solution.More precisely,we will construct a nested sequence of successively tighter relaxations of the original problem using cutting plane method.We will show that this is a valid strategy,since there always exists a polynomial sized subset of constraints so that the solution of the relaxed problem defined by this subset fulfills all constraints from the full optimization problem up to a precision∈.The implementation of the alternative algorithm is proved that what we have done has better performance than the primal algorithm.