Fast pruning superfluous support vectors in SVMs

详细信息    查看全文

• 作者：Xun Liang^a ; ^b ; ^{xliang@ruc.edu.cn} ; ^{liangxun@pku.edu.cn} ; Yuefeng Ma^a ; Yangbo He^b ; Li Yu^a ; Rong-Chang Chen^c ; Tao Liu^a ; Xiaoping Yang^a ; Tung-Shou Chen^c
• 关键词：Superfluous support vectors ; Collinear support vectors ; Parallel support vectors ; Fast pruning ; Decision function ; Support vector machine
• 刊名：Pattern Recognition Letters
• 出版年：2013
• 出版时间：15 July, 2013
• 年：2013
• 卷：34
• 期：10
• 页码：1203-1209
• 全文大小：824 K

文摘

Support vector machines (SV machines, SVMs) often contain many SVs, which reduce runtime speeds of decision functions. To simplify the decision functions and improve SVM succinctness, the efforts to remove SVs in trained SVMs have been made. By meticulously designing some pruning coefficients and solving for the rest, this paper presents a simple method for fast removing superfluous SVs. The method empowers users to remove those SVs in a single iteration, thereby significantly enhancing the pruning speed of currently used methods, which remove the SVs one by one. The existence and uniqueness of the fast pruning coefficients are shown. The nexus of primal and dual optimizations is illustrated geometrically. The fast pruning method can also be applied to other kernel-based machines without any modifications. The computational complexity is discussed. Examples are given first and experiments on larger data sets demonstrate the effectiveness of the fast simplification method.