Algorithms for Multiclass Classification and Regularized Regression

Multiclass classification and regularized regression problems are very common in modern statistical and machine learning applications. Multiclass classification problems require the prediction of class labels: given observations of objects that belong to certain classes, can we predict to which class a new object belongs? The regularized regression problem on the other hand is a variation of a common technique that measures how changes in independent variables influence an observed outcome. In regularized regression constraints are placed on the coefficients of the regression model to enforce certain properties in the solution, such as sparsity or limited size. In this dissertation several new algorithms are presented for both multiclass classification and regularized regression problems.

For multiclass classification an algorithm is presented that extends the binary support vector machine in a general way, while maintaining competitive performance and training time. Furthermore, accurate estimates of the Bayes error are applied to both meta-learning and the construction of so-called classification hierarchies: structures that decompose a multiclass classification into several binary classification problems.

For regularized regression problems a general algorithm is presented for problems where the regularization function is a measure of the size of the coefficients. In the proposed algorithm the nonconvexity in the problem is slowly introduced while iterating towards a solution. The empirical performance and theoretical convergence properties of the algorithm are analysed with numerical experiments that demonstrate that the algorithm can obtain globally optimal solutions.