Solving large scale support vector machine problems using matrix splitting and decomposition methods.

摘要

Due to its rich variety of applications in classification, clustering, and regression, support vector machines (SVM) have been widely explored over the past few years. In practice, these problems are characterized by their large size and dense Hessian matrices. Therefore, fortified algorithms that take advantage of the problem and solution structure must be developed.; In the first part of this research, an algorithm based on the conjugate gradient method is developed for solving linear support vector regression (SVR) problems. Preliminary computational analysis showed that this algorithm works well on small and medium sized problems. However, the solution was seen to be highly sensitive to the parameters chosen. This has been a motivation to investigate a more robust SVM formulation. A unified approach is thus developed that not only is insensitive to the parameters used, but also uses a single solver to solve all the SVM problems of classification, regression and the later developed tolerancing problems. Further research efforts concentrate on the development of solution methodologies for solving the unified problem; a quadratic program with a knapsack and box constraints.; In the second part of this research, an augmented Lagrangian algorithm and a log-barrier algorithm are developed to solve the unified dual problem that relaxes the knapsack constraint. Motivated by the self correcting ability of iterative methods, a matrix splitting method (MSM) is developed that splits the Hessian matrix into two parts, one being a diagonal matrix, and the other being the difference between the Hessian and the diagonal matrix. The algorithm is modified to combine matrix splitting, gradient projection, and non-monotone line search. The proposed algorithm can not only solve large scale problems, but is fast, stable and robust. A decomposition method is further used to enhance the matrix splitting methodology. Extensive computational study is performed to solve the unified problem and study the properties of this new approach.; In the final part, a model called the support vector minimal zone formulation to solve tolerancing problems using the unified approach is developed. The proposed model is implemented to solve straightness and flatness tolerancing problems.; In this research, a unified approach has been developed to solve all the SVM problems, classification, regression, and tolerancing using a single solver. The proposed unified solver is robust and efficient, and is based on matrix splitting and decomposition methods.