A faster cutting plane algorithm with accelerated line search for linear SVM. (July 2017)

• Record Type: Journal Article
• Authors: Chu, Dejun; Zhang, Changshui; Tao, Qing
• Is Part Of: Pattern recognition. Volume 67(2017:Jul.)
• Page Start: 127
• Page End: 138
• Publication Date: 2017-07
• Subjects: Linear support vector machine -- Binary classification -- Root finding -- Cutting plane algorithm; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2017.02.006
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Faster cutting plane algorithms with accelerated line search are proposed to solve linear SVM. It proposes a novel linear-time line search solver while the existing strategy spends O ( m log m ) time. An optimized explicit piecewise linear function finding algorithm for multiclass linear SVM is derived. It can be proved to reduce the total SVM training time. Experiments demonstrate the effectiveness of the proposed algorithm. Abstract: Cutting plane algorithm (CPA) is a generalization of iterative first-order gradient method, in which the objective function is approximated successively by supporting hyperplanes. CPA has been tailored to solve regularized loss minimization in machine learning by exploiting the regularization structure. In particular, for linear Support Vector Machine (SVM) embedding a line search procedure effectively remedies the fluctuations of function value and speeds up the convergence in practical issue. However, the existing line search strategy based on sorting algorithm takes O ( m log m ) time. In this paper, we propose a more effective line search solver which spends only linear time. It can be extended to multiclass SVM in which an optimized explicit piecewise linear function finding algorithm is prearranged. The total SVM training time is proved to reduce theoretically and experiments consistently confirm the effectiveness of the proposed algorithms.