Fast Computational Algorithms And Theoretical Analysis In Large-Margin Classification Models

Classification is a basic task in machine learning. Large-margin principle is the basic idea to design effective algorithms for classification. Support vector machines (SVM) is a well known classifier of this kind. It has been successfully used in binary classification, multi-classification, and more generally the hierarchical classification. In this thesis, we focus on the algorithms designing based on SVM. We propose more efficient algorithms for feature selection in SVM and hierarchical classification, and give theoretical analysis.Firstly, this thesis surveys the feature selection in SVM. We review the regularization method in feature selection, and focus on the double regularization which is the combining of l1and l2norm. Doubly regularized SVM (DrSVM) is employed to select the important features while retaining the highly correlated features, which is beneficial for constructing good classifier. Thus many algorithms are developed for the DrSVM model. The problem with current algorithms is that computational complexity largely depends on the dimension of output space. Based on the work of former researchers, we explore efficient algorithms for the high dimensional DrSVM model. We reform the original DrSVM objective func-tion and recall alternative directional method of multipliers (ADMM) algorithm. Then the derived algorithm has an inner loop and is time costly. We design algorithms which have only one loop. These algorithms transform the high dimensional problems to small-scale problems and reduce the computational complexity from O(nd2) to O(K(n3+nd)+n2d) with K the number of iterations, n the number of samples and d the dimension of input vector. We analyse the theoretical guarantees and prove its global convergence.Secondly, as a general form of binary and multi-classification, we investigated the problem of hierarchical classification (HC). There are many existing models and algorithms for solving HC problem, such as constructing local classifiers, bayesian framework and hi-erarchical SVM. And hierarchical SVM is the most popular used method, since it produces global classifier and guarantees consistent prediction output. However, hierarchical SVM is usually transformed to dual form, a quadratic programming (QP), and the number of vari-ables in QP is huge if the dimension of output space is high. In this thesis, we transform the hierarchical SVM to minmax problem and design a so-called hard perceptron (HP) al-gorithm based on large-margin. Based on HP algorithms, we develop stochastic perceptron algorithm (SP), and then form a so-called KSP algorithm by kernel trick. Being Differ-ent from the popular perceptron algorithms, the algorithms proposed here are all for batch learning. The KSP algorithm can avoids the high computational complexity cost by large amount of constraints in hierarchical SVM. We prove SP and KSP algorithms produce sub optimal solution after finite iterations with large probability. Experiments on real datasets show that SP or KSP can achieve almost the same accuracy as hierarchical SVM classifiers and have great advantage in CPU running time.