分类是机器学习的一个基本问题。大边际原理是设计分类算法的重要思想。以大边际原理为基础的支持向量机(SVM)已成功的应用于二分类,多分类,和更一般的层次化分类中。本文主要关注基于支持向量机的分类器设计,针对高维分类任务中的特征选择和层次分类问题,提出了快速算法和理论分析。首先,本文调查了支持向量机中特征选择的发展现状,回顾了相应的正则化技术,重点关注了双正则化支持向量机(DrSVM)模型。DrSVM模型可以在选择重要特征的同时保留相关度高的特征,有利于构造较优分类器。因此,大量研究工作聚焦于DrSVM模型的有效求解方法。然而,已有算法的计算复杂度均严重依赖于数据维度,无法有效处理高维分类任务。在前人工作的基础上,本文针对DrSVM模型,提出了高维数据下的快速算法。本文重新表述了相应的目标函数,并试图在其中应用乘子交替方向迭代求解方法。由于乘子交替方向迭代求解方法的内外双层迭代可能导致较高的计算代价,本文提出了一种单层迭代算法,从而使计算复杂度从O(nd2)降低为O(K(n3+nd)+n2d),其中K为迭代次数,n为样本个数,d为样本维数且d>>n。理论推导表明,本文提出的算法具有全局收敛性。其次,作为二分类和多分类的推广,本文研究了层次化分类问题。现在有许多模型和算法针对层次化分类,例如构造局部分类器,贝叶斯方法和层次化支持向量机(支持向量机在层次化分类中的推广)等。其中层次化支持向量机是当前使用最多的方法,因为它是全局分类器且能够保证分类层次间的一致性。层次化支持向量机的求解一般是转化为二次规划问题,从而利用二次规划问题的通用求解方法。然而,在层次分类任务中,输出空间的高维度提升了二次规划的规模。因此,通用算法计算代价极大。本文基于大边际原理,将层次化分类的支持向量机转化为最大最小优化问题,提出了一个称为硬感知器的算法(HP)。为提高预测精确度,本文构造了一个随机感知器(SP)算法,它是离线算法。该算法避免了层次化支持向量机非常多的约束所带来的计算上的代价。本文证明了如果数据集是可分的,那么经过有限步迭代之后,随机感知器将以很大的概率产生一个次优解。对于大样本和高维数据,本文设计了核形式的随机感知器(KSP),减少了计算复杂度。对于不可分的真实数据,KSP算法的实验结果达到了与层次化支持向量机相同的预测精度,并在运行时间上优于层次化支持向量机方法。