Font Size: a A A

Optimization Problems In Support Vector Machines

Posted on:2005-10-25Degree:DoctorType:Dissertation
Country:ChinaCandidate:C H ZhangFull Text:PDF
GTID:1116360122488963Subject:Management Science and Engineering
Abstract/Summary:PDF Full Text Request
In recent years, Support Vector Machines (SVMs) have become increasingly popular techniques in machine learning. Based on the statistical learning theory and optimization theory, SVMs have been successfully applied to many fields such as pattern recognition, regression and etc.Training an SVM amounts to solving a convex quadratic programming problem. In this paper we do some researches on SVMs by the optimization theory and method. We point out some basic drawbacks in the optimization problems of SVMs and make some improvements to them. Up to now, most studies are centered on the statistical learning theory and some applications. The research on SVMs from the optimization point of view is also at the beginning in the world. Therefore, our study is very important on the theoretical and practical aspects of SVMs.The main works in this paper are as follows:1. Based on the analysis of the basic ideas and some standard algorithms of SVMs, we find that the reasoning to derive the existing algorithms have some basic drawbacks. Some improvements have been made on the strict theoretical foundation of SVMs in this paper.2. In some cases, the usual methods for determining the thresholds of decision functions in SVMs do not work. The new formula to compute the thresholds are proposed for any cases.3. The Generalized Support Vector Machines (GSVMs) was proposed by Mangasarian, but it can not be degenerated to the standard SVMs. In fact, the former only consider the strict convex programming, while the latter considers the convex programming. We extend the optimization problem of GSVMs to the convex programming.4. The variation of SVMs is very efficient, but lack of the corresponding statistical learning theory. We make some improvements on it.As an efficient method to solve the optimization problems in SVMs, Newton-PCG algorithmhas been introduced. Newton-PCG algorithm is very efficient for solving the unconstrained optimization problems. We considered an integer one-dimensional optimization problem appeared in Newton-PCG method. The efficiency of Newton-PCG algorithm is depended on the optimal value of this problem. A simple and efficient algorithm is established to solve this problem and its optimal value is estimated in this paper.
Keywords/Search Tags:Support Vector Machines, Wolfe Dual, KKT Conditions, Newton-PCG Algorithm
PDF Full Text Request
Related items