Solving nonlinear svm in linear time? A nyström zpproximated svm with applications to image classification

Ming Hen Tsai, Yi Ren Yeh, Yuh-Jye Lee, Yu Chiang Frank Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

In this paper, we improve the efficiency of kernelized support vector machine (SVM) for image classification using linearized kernel data representation. Inspired by Nyström approximation, we propose a decomposition technique for converting the kernel data matrix into an approximated primal form. This allows us to apply the approximated kernelized data in the primal form of linear SVMs, and achieve comparable recognition performance as nonlinear SVMs do. Several benefits can be observed for our proposed method. First, we advance basis matrix selection for decomposing our proposed approximation, which can be viewed as fea-ture/instance selection with performance guarantees. More importantly, the proposed selection technique significantly reduces the computation complexity for both training and testing. Therefore, the resulting computation time is comparable to that of linear SVMs. Experiments on two benchmark image datasets will support the use of our approach for solving the tasks of image classification.

Original languageEnglish
Title of host publicationProceedings of the 13th IAPR International Conference on Machine Vision Applications, MVA 2013
PublisherMVA Organization
Pages5-8
Number of pages4
ISBN (Print)9784901122139
StatePublished - 20 May 2013
Event13th IAPR International Conference on Machine Vision Applications, MVA 2013 - Kyoto, Japan
Duration: 20 May 201323 May 2013

Publication series

NameProceedings of the 13th IAPR International Conference on Machine Vision Applications, MVA 2013

Conference

Conference13th IAPR International Conference on Machine Vision Applications, MVA 2013
Country/TerritoryJapan
CityKyoto
Period20/05/1323/05/13

Fingerprint

Dive into the research topics of 'Solving nonlinear svm in linear time? A nyström zpproximated svm with applications to image classification'. Together they form a unique fingerprint.

Cite this