دانلود مقاله ISI انگلیسی شماره 79013
ترجمه فارسی عنوان مقاله

یک الگوریتم سریع برای حمایت از هنجارهای ماشین های بردار تک هسته ایی.

عنوان انگلیسی
A fast algorithm for kernel 1-norm support vector machines
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
79013 2013 13 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Knowledge-Based Systems, Volume 52, November 2013, Pages 223–235

ترجمه کلمات کلیدی
تک نورم SVM؛ برنامه ریزی خطی؛ ایجاد ستون؛ الگوریتم نیوتن؛ تابع هسته
کلمات کلیدی انگلیسی
1-Norm SVM; Linear programming; Column generation; Newton algorithm; Kernel function
پیش نمایش مقاله
پیش نمایش مقاله  یک الگوریتم سریع برای  حمایت از هنجارهای ماشین های بردار تک هسته ایی.

چکیده انگلیسی

This paper presents a fast algorithm called Column Generation Newton (CGN) for kernel 1-norm support vector machines (SVMs). CGN combines the Column Generation (CG) algorithm and the Newton Linear Programming SVM (NLPSVM) method. NLPSVM was proposed for solving 1-norm SVM, and CG is frequently used in large-scale integer and linear programming algorithms. In each iteration of the kernel 1-norm SVM, NLPSVM has a time complexity of O(ℓ3), where ℓ is the sample number, and CG has a time complexity between O(ℓ3) and O(n′3), where n′ is the number of columns of the coefficient matrix in the subproblem. CGN uses CG to generate a sequence of subproblems containing only active constraints and then NLPSVM to solve each subproblem. Since the subproblem in each iteration only consists of n′ unbound constraints, CGN thus has a time complexity of O(n′3), which is smaller than that of NLPSVM and CG. Also, CGN is faster than CG when the solution to 1-norm SVM is sparse. A theorem is given to show a finite step convergence of CGN. Experimental results on the Ringnorm and UCI data sets demonstrate the efficiency of CGN to solve the kernel 1-norm SVM.