Header logo is

Invariance of Neighborhood Relation under Input Space to Feature Space Mapping




If the training pattern set is large, it takes a large memory and a long time to train support vector machine (SVM). Recently, we proposed neighborhood property based pattern selection algorithm (NPPS) which selects only the patterns that are likely to be near the decision boundary ahead of SVM training [Proc. of the 7th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), Lecture Notes in Artificial Intelligence (LNAI 2637), Seoul, Korea, pp. 376–387]. NPPS tries to identify those patterns that are likely to become support vectors in feature space. Preliminary reports show its effectiveness: SVM training time was reduced by two orders of magnitude with almost no loss in accuracy for various datasets. It has to be noted, however, that decision boundary of SVM and support vectors are all defined in feature space while NPPS described above operates in input space. If neighborhood relation in input space is not preserved in feature space, NPPS may not always be effective. In this paper, we sh ow that the neighborhood relation is invariant under input to feature space mapping. The result assures that the patterns selected by NPPS in input space are likely to be located near decision boundary in feature space.

Author(s): Shin, H. and Cho, S.
Journal: Pattern Recognition Letters
Volume: 26
Number (issue): 6
Pages: 707-718
Year: 2005
Day: 0

Department(s): Empirical Inference
Bibtex Type: Article (article)

Digital: 0
Institution: Seoul National University, Seoul, Korea
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Invariance of Neighborhood Relation under Input Space to Feature Space Mapping},
  author = {Shin, H. and Cho, S.},
  journal = {Pattern Recognition Letters},
  volume = {26},
  number = {6},
  pages = {707-718},
  organization = {Max-Planck-Gesellschaft},
  institution = {Seoul National University, Seoul, Korea},
  school = {Biologische Kybernetik},
  year = {2005}