Classification and regularization in learning theory

Abstract

In this thesis, we study classification algorithms generated by regularization schemes. The design of these algorithms and their error analysis are fully discussed. These algorithms are based on convex risk minimization with Tikhonov regularization. They need an admissible convex loss function, a hypothesis space and a regularizer. We first discuss the admissibility of convex loss functions and their properties. Comparison theorems are discussed and new ones are established. Then we investigate the hypothesis space and regularizer. It is shown that support vector machines (SVMs) and regularized boosting are typical examples of these algorithms. We also introduce the regularization scheme in multi-kernel spaces, a new classification algorithm. As for the error analysis, we consider two classes of models according to whether the hypothesis space and the regularizer are sample independent or dependent. For the regularization scheme with sample-independent hypothesis space and regularizer, we introduce a regularization approach. The error is decomposed into the sum of the sample error and the regularization error. The consistency, error bounds and learning rates are explicitly given. In the error analysis, we introduce the projection operator by the special feature of classification problems and choose a proper projection level according to the structure of the loss function. Together with probability inequalities, we obtain the best convergence rates. Thus refined error analysis is established in a regularization framework. For the regularization scheme with sample-dependent hypothesis space and regularizer, the analysis is much more difficult due to the lack of regularization error. We overcome this difficulty by defining the regularization error respect to the union of all possible hypothesis spaces. Then the difficulty is transferred to the comparison be tween the solution and the optimizer over this union. Such comparisons are different for different models. Here we only focus on the linear programming SVM model. For this particular model, we establish a stepping stone that relates the solution of the linear programming SVM with that of the 1-norm soft margin SVM when Mercer kernels are used. This stepping stone helps make the comparisons and lead to the error decomposition. Then the consistency of this algorithm follows and learning rates are available.

Date of Award	15 Jul 2005
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Dingxuan ZHOU (Supervisor)