Linear Programming Approach for the Inverse Problem of Support Vector Machines

It is well recognized that support vector machines (SVMs) would produce better classification performance in terms of generalization power. A SVM constructs an optimal separating hyper-plane through maximizing the margin between two classes in high-dimensional feature space. The inverse problem is how to split a given dataset into two clusters such that the margin between the two clusters attains the maximum. It is difficult to give an exact solution to this problem, so a genetic algorithm is designed to solve this problem. But the proposed genetic algorithm has large time complexity for the process of solving quadratic programs. In this paper, we replace the quadratic programming with a linear programming. The new algorithm can greatly decrease time complexity. The fast algorithm for acquiring the maximum margin can upgrade the applicability of the proposed genetic algorithm