Skip to main content

2018 | OriginalPaper | Buchkapitel

Sparsification of Indefinite Learning Models

verfasst von : Frank-Michael Schleif, Christoph Raab, Peter Tino

Erschienen in: Structural, Syntactic, and Statistical Pattern Recognition

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The recently proposed Krĕin space Support Vector Machine (KSVM) is an efficient classifier for indefinite learning problems, but with a non-sparse decision function. This very dense decision function prevents practical applications due to a costly out of sample extension. In this paper we provide a post processing technique to sparsify the obtained decision function of a Krĕin space SVM and variants thereof. We evaluate the influence of different levels of sparsity and employ a Nyström approach to address large scale problems. Experiments show that our algorithm is similar efficient as the non-sparse Krĕin space Support Vector Machine but with substantially lower costs, such that also large scale problems can be processed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Obtained by evaluating k(xy) for training points x, y.
 
2
A similar strategy for KSVM may be possible but is much more complicated because typically quite many points are support vectors and special sparse SVM solvers would be necessary.
 
Literatur
1.
Zurück zum Zitat Alabdulmohsin, I.M., Cissé, M., Gao, X., Zhang, X.: Large margin classification with indefinite similarities. Mach. Learn. 103(2), 215–237 (2016)MathSciNetCrossRef Alabdulmohsin, I.M., Cissé, M., Gao, X., Zhang, X.: Large margin classification with indefinite similarities. Mach. Learn. 103(2), 215–237 (2016)MathSciNetCrossRef
3.
Zurück zum Zitat Geoffrey, Z.Z., Davis, M., Mallat, S.G.: Adaptive time-frequency decompositions. SPIE J. Opt. Eng. 33(1), 2183–2191 (1994) Geoffrey, Z.Z., Davis, M., Mallat, S.G.: Adaptive time-frequency decompositions. SPIE J. Opt. Eng. 33(1), 2183–2191 (1994)
4.
Zurück zum Zitat Gisbrecht, A., Schleif, F.-M.: Metric and non-metric proximity transformations at linear costs. Neurocomputing 167, 643–657 (2015)CrossRef Gisbrecht, A., Schleif, F.-M.: Metric and non-metric proximity transformations at linear costs. Neurocomputing 167, 643–657 (2015)CrossRef
5.
Zurück zum Zitat Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)CrossRef Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)CrossRef
6.
Zurück zum Zitat Hassibi, B.: Indefinite metric spaces in estimation, control and adaptive filtering. Ph.D. thesis, Stanford University, Department of Electrical Engineering, Stanford (1996) Hassibi, B.: Indefinite metric spaces in estimation, control and adaptive filtering. Ph.D. thesis, Stanford University, Department of Electrical Engineering, Stanford (1996)
7.
Zurück zum Zitat Hodgetts, C.J., Hahn, U.: Similarity-based asymmetries in perceptual matching. Acta Psychol. 139(2), 291–299 (2012)CrossRef Hodgetts, C.J., Hahn, U.: Similarity-based asymmetries in perceptual matching. Acta Psychol. 139(2), 291–299 (2012)CrossRef
8.
Zurück zum Zitat Ling, H., Jacobs, D.W.: Shape classification using the inner-distance. IEEE Trans. Pattern Anal. Mach. Intell. 29(2), 286–299 (2007)CrossRef Ling, H., Jacobs, D.W.: Shape classification using the inner-distance. IEEE Trans. Pattern Anal. Mach. Intell. 29(2), 286–299 (2007)CrossRef
9.
Zurück zum Zitat Loosli, G., Canu, S., Ong, C.S.: Learning SVM in Krein spaces. IEEE Trans. Pattern Anal. Mach. Intell. 38(6), 1204–1216 (2016)CrossRef Loosli, G., Canu, S., Ong, C.S.: Learning SVM in Krein spaces. IEEE Trans. Pattern Anal. Mach. Intell. 38(6), 1204–1216 (2016)CrossRef
10.
Zurück zum Zitat Luss, R., d’Aspremont, A.: Support vector machine classification with indefinite kernels. Math. Program. Comput. 1(2–3), 97–118 (2009)MathSciNetCrossRef Luss, R., d’Aspremont, A.: Support vector machine classification with indefinite kernels. Math. Program. Comput. 1(2–3), 97–118 (2009)MathSciNetCrossRef
11.
Zurück zum Zitat Mwebaze, E., Schneider, P., Schleif, F.-M., et al.: Divergence based classification in learning vector quantization. Neurocomputing 74, 1429–1435 (2010)CrossRef Mwebaze, E., Schneider, P., Schleif, F.-M., et al.: Divergence based classification in learning vector quantization. Neurocomputing 74, 1429–1435 (2010)CrossRef
12.
Zurück zum Zitat Olshausen, B.A., Field, D.J.: Sparse coding with an overcomplete basis set: a strategy employed by V1? Vis. Res. 37(23), 3311–3325 (1997)CrossRef Olshausen, B.A., Field, D.J.: Sparse coding with an overcomplete basis set: a strategy employed by V1? Vis. Res. 37(23), 3311–3325 (1997)CrossRef
13.
Zurück zum Zitat Ong, C.S., Mary, X., Canu, S., Smola, A.J.: Learning with non-positive kernels. In: (ICML 2004) (2004) Ong, C.S., Mary, X., Canu, S., Smola, A.J.: Learning with non-positive kernels. In: (ICML 2004) (2004)
14.
Zurück zum Zitat Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27th Asilomar Conference on Signals, Systems and Computers, vol. 1, pp. 40–44, November 1993 Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27th Asilomar Conference on Signals, Systems and Computers, vol. 1, pp. 40–44, November 1993
15.
Zurück zum Zitat Pekalska, E., Duin, R.: The Dissimilarity Representation for Pattern Recognition. World Scientific, Singapore (2005)CrossRef Pekalska, E., Duin, R.: The Dissimilarity Representation for Pattern Recognition. World Scientific, Singapore (2005)CrossRef
16.
Zurück zum Zitat Pekalska, E., Haasdonk, B.: Kernel discriminant analysis for positive definite and indefinite kernels. IEEE Trans. Pattern Anal. Mach. Intell. 31(6), 1017–1031 (2009)CrossRef Pekalska, E., Haasdonk, B.: Kernel discriminant analysis for positive definite and indefinite kernels. IEEE Trans. Pattern Anal. Mach. Intell. 31(6), 1017–1031 (2009)CrossRef
17.
Zurück zum Zitat Scheirer, W.J., Wilber, M.J., Eckmann, M., Boult, T.E.: Good recognition is non-metric. Pattern Recogn. 47(8), 2721–2731 (2014)CrossRef Scheirer, W.J., Wilber, M.J., Eckmann, M., Boult, T.E.: Good recognition is non-metric. Pattern Recogn. 47(8), 2721–2731 (2014)CrossRef
18.
Zurück zum Zitat Schleif, F.-M., Tiño, P.: Indefinite proximity learning: a review. Neural Comput. 27(10), 2039–2096 (2015)CrossRef Schleif, F.-M., Tiño, P.: Indefinite proximity learning: a review. Neural Comput. 27(10), 2039–2096 (2015)CrossRef
19.
Zurück zum Zitat Schleif, F.-M., Tiño, P.: Indefinite core vector machine. Pattern Recogn. 71, 187–195 (2017)CrossRef Schleif, F.-M., Tiño, P.: Indefinite core vector machine. Pattern Recogn. 71, 187–195 (2017)CrossRef
20.
Zurück zum Zitat Schnitzer, D., Flexer, A., Widmer, G.: A fast audio similarity retrieval method for millions of music tracks. Multimed. Tools Appl. 58(1), 23–40 (2012)CrossRef Schnitzer, D., Flexer, A., Widmer, G.: A fast audio similarity retrieval method for millions of music tracks. Multimed. Tools Appl. 58(1), 23–40 (2012)CrossRef
21.
Zurück zum Zitat Srisuphab, A., Mitrpanont, J.L.: Gaussian kernel approx algorithm for feedforward neural network design. Appl. Math. Comp. 215(7), 2686–2693 (2009)CrossRef Srisuphab, A., Mitrpanont, J.L.: Gaussian kernel approx algorithm for feedforward neural network design. Appl. Math. Comp. 215(7), 2686–2693 (2009)CrossRef
22.
Zurück zum Zitat Tsang, I.H., Kwok, J.Y., Zurada, J.M.: Generalized core vector machines. IEEE TNN 17(5), 1126–1140 (2006) Tsang, I.H., Kwok, J.Y., Zurada, J.M.: Generalized core vector machines. IEEE TNN 17(5), 1126–1140 (2006)
23.
Zurück zum Zitat UCI: Skin segmentation database, March 2016 UCI: Skin segmentation database, March 2016
24.
Zurück zum Zitat Vapnik, V.N.: The Nature of Statistical Learning Theory. Statistics for Engineering and Information Science. Springer, New York (2000)CrossRef Vapnik, V.N.: The Nature of Statistical Learning Theory. Statistics for Engineering and Information Science. Springer, New York (2000)CrossRef
Metadaten
Titel
Sparsification of Indefinite Learning Models
verfasst von
Frank-Michael Schleif
Christoph Raab
Peter Tino
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-97785-0_17