Algorithms for Sparse Support Vector Machines

Many problems in classification involve huge numbers of irrelevant features. Variable selection reveals the crucial features, reduces the dimensionality of feature space, and improves model interpretation. In the support vector machine literature, variable selection is achieved by l1 penalties. These convex relaxations seriously bias parameter estimates toward 0 and tend to admit too many irrelevant features. The current article presents an alternative that replaces penalties by sparse-set constraints. Penalties still appear, but serve a different purpose. The proximal distance principle takes a loss function L(β) and adds the penalty ρ2dist(β,Sk)2 capturing the squared Euclidean distance of the parameter vector β to the sparsity set Sk where at most k components of β are nonzero. If βρ represents the minimum of the objective fρ(β)=L(β)+ρ2dist(β,Sk)2, then βρ tends to the constrained minimum of L(β) over Sk as ρ tends to ∞. We derive two closely related algorithms to carry out this strategy. Our simulated and real examples vividly demonstrate how the algorithms achieve better sparsity without loss of classification power. Supplementary materials for this article are available online.分类任务中常存在海量无关特征。变量选择（variable selection）能够甄别核心特征、降低特征空间维度并提升模型可解释性。在支持向量机（support vector machine）相关文献中，变量选择通常通过l1惩罚项实现。这类凸松弛方法会使参数估计向0产生显著偏倚，且倾向于保留过多无关特征。本文提出一种替代方案，以稀疏集约束替代惩罚项。惩罚项仍会被采用，但发挥全然不同的作用。邻近距离（proximal distance）原理以损失函数L(β)为基础，新增惩罚项ρ²dist(β,S_k)²，该惩罚项衡量参数向量β到稀疏集S_k的欧氏距离平方，其中S_k表示β至多存在k个非零分量的参数集合。若β_ρ为目标函数f_ρ(β)=L(β)+ρ²dist(β,S_k)²的极小值点，则当ρ趋近于无穷大时，β_ρ将收敛至L(β)在S_k上的约束极小值。本文推导了两种紧密关联的算法以实现该策略。我们通过仿真与真实数据集实验，直观展示了该算法如何在不损失分类性能的前提下实现更优的稀疏性。本文的补充材料可在线获取。