Learning Sign-Constrained Support Vector Machines
  Domain knowledge is useful to improve the generalization performance of
learning machines. Sign constraints are a handy representation to combine
domain knowledge with learning machine. In this paper, we consider constraining
the signs of the weight coefficients in learning the linear support vector
machine, and develop two optimization algorithms for minimizing the empirical
risk under the sign constraints. One of the two algorithms is based on the
projected gradient method, in which each iteration of the projected gradient
method takes $O(nd)$ computational cost and the sublinear convergence of the
objective error is guaranteed. The second algorithm is based on the Frank-Wolfe
method that also converges sublinearly and possesses a clear termination
criterion. We show that each iteration of the Frank-Wolfe also requires $O(nd)$
cost. Furthermore, we derive the explicit expression for the minimal iteration
number to ensure an $\epsilon$-accurate solution by analyzing the curvature of
the objective function. Finally, we empirically demonstrate that the sign
constraints are a promising technique when similarities to the training
examples compose the feature vector.
