Top

Published in:

2015 | OriginalPaper | Chapter

Large Scale Indefinite Kernel Fisher Discriminant

Authors : Frank-Michael Schleif, Andrej Gisbrecht, Peter Tino

Published in: Similarity-Based Pattern Recognition

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Indefinite similarity measures can be frequently found in bio-informatics by means of alignment scores. Lacking an underlying vector space, the data are given as pairwise similarities only. Indefinite Kernel Fisher Discriminant (iKFD) is a very effective classifier for this type of data but has cubic complexity and does not scale to larger problems. Here we propose an extension of iKFD such that linear runtime and memory complexity is achieved for low rank indefinite kernels. Evaluation at several larger similarity data from various domains shows that the proposed method provides similar generalization capabilities while being substantially faster for large scale data.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Transitive Assignment Kernels for Structural Classification

For multiclass problems a classical 1 vs rest wrapper is used within this paper.

For symmetric matrices we have \(\tilde{K}\tilde{K}^\top \) = \(\tilde{K}^\top \tilde{K}\).

An implementation of this linear time eigen-decomposition for low rank indefinite matrices is available at: http://www.techfak.uni-bielefeld.de/~fschleif/eigenvalue_corrections_demos.tgz.

In [18] various correction methods have been studied on the same data indicating that eigenvalue corrections may be helpful if indefiniteness can be attributed to noise.

An increase of the number of landmarks leads to a better kernel reconstruction in the Frobenius norm until the full rank of the matrix is reached. Landmarks have not been changed between methods but only for each dataset.

Also the runtime and model complexity are similar and therefore not reported in the following.

Alabdulmohsin, I.M., Gao, X., Zhang, X.: Support vector machines with indefinite kernels. In: Phung, D., Li, H. (eds.) Proceedings of the Sixth Asian Conference on Machine Learning, ACML 2014. JMLR Proceedings, Nha Trang City, Vietnam, 26–28 November 2014, vol. 39 (2014). JMLR.org

Boeckmann, B., Bairoch, A., Apweiler, R., Blatter, M.-C., Estreicher, A., Gasteiger, E., Martin, M., Michoud, K., O’Donovan, C., Phan, I., Pilbout, S., Schneider, M.: The SWISS-PROT protein knowledgebase and its supplement TrEMBL in 2003. Nucleic Acids Res. 31, 365–370 (2003)CrossRef

Chen, H., Tino, P., Yao, X.: Probabilistic classification vector machines. IEEE Trans. Neural Netw. 20(6), 901–914 (2009)CrossRef

Chen, H., Tino, P., Yao, X.: Efficient probabilistic classification vector machine with incremental basis function selection. IEEE TNN-LS 25(2), 356–369 (2014)

Chen, Y., Garcia, E.K., Gupta, M.R., Rahimi, A., Cazzanti, L.: Similarity-based classification: concepts and algorithms. JMLR 10, 747–776 (2009)MathSciNetMATH

Diethe, T., Hussain, Z., Hardoon, D.R., Shawe-Taylor, J.: Matching pursuit kernel fisher discriminant analysis. In: Dyk, D.A.V., Welling, M. (eds.) Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, AISTATS 2009. JMLR Proceedings, 16–18 April 2009, Clearwater Beach, Florida, USA, vol. 5, pp. 121–128 (2009). JMLR.org

Dubuisson, M., Jain, A.: A modified hausdorff distance for object matching. In: Proceedings of the 12th IAPR International Conference on Pattern Recognition, 1994. Vol. 1 - Conference A: Computer Vision amp; Image Processing., vol. 1, pp. 566–568, October 1994

Duin, R.P.: prtools, March 2012

Gisbrecht, A., Schleif, F.-M.: Metric and non-metric proximity transformations at linear costs. Neurocomputing (2015, to appear)

10.

Haasdonk, B.: Feature space interpretation of svms with indefinite kernels. IEEE Trans. Pattern Anal. Mach. Intell. 27(4), 482–492 (2005)CrossRef

11.

Haasdonk, B., Pekalska, E.: Indefinite kernel fisher discriminant. In: 19th International Conference on Pattern Recognition (ICPR 2008), 8–11 December 2008, Tampa, Florida, USA, pp. 1–4. IEEE Computer Society (2008)

12.

Ling, H., Jacobs, D.W.: Shape classification using the inner-distance. IEEE Trans. Pattern Anal. Mach. Intell. 29(2), 286–299 (2007)CrossRef

13.

Mokbel, B., Hasenfuss, A., Hammer, B.: Graph-based representation of symbolic musical data. In: Torsello, A., Escolano, F., Brun, L. (eds.) GbRPR 2009. LNCS, vol. 5534, pp. 42–51. Springer, Heidelberg (2009) CrossRef

14.

Neuhaus, M., Bunke, H.: Edit distance based kernel functions for structural pattern classification. Pattern Recogn. 39(10), 1852–1863 (2006)CrossRefMATH

15.

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

16.

Schleif, F.-M., Gisbrecht, A., Tino, P.: Probabilistic classification vector machine at large scale. In: Proceedings of ESANN 2015, pp. 555–560 (2015)

17.

Schleif, F.-M., Gisbrecht, A.: Data analysis of (non-)metric proximities at linear costs. In: Hancock, E., Pelillo, M. (eds.) SIMBAD 2013. LNCS, vol. 7953, pp. 59–74. Springer, Heidelberg (2013) CrossRef

18.

Schleif, F.-M., Tino, P.: Indefinite proximity learning - a review. Neural Computation (2015, to appear)

19.

Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195–197 (1981)CrossRef

20.

Williams, C.K.I., Seeger, M.: Using the nyström method to speed up kernel machines. In: NIPS 2000, pp. 682–688 (2000)

21.

Yang, J., Fan, L.: A novel indefinite kernel dimensionality reduction algorithm: weighted generalized indefinite kernel discriminant analysis. Neural Process. Lett. 40(3), 301–313 (2014). doi:10.1007/s11063-013-9330-9 CrossRef

22.

Zhang, K., Kwok, J.T.: Clustered nyström method for large scale manifold learning and dimension reduction. IEEE Trans. Neural Netw. 21(10), 1576–1587 (2010)CrossRef

Title: Large Scale Indefinite Kernel Fisher Discriminant
Authors: Frank-Michael Schleif
Andrej Gisbrecht
Peter Tino
Publisher: Springer International Publishing
Book: Similarity-Based Pattern Recognition
Print ISBN: 978-3-319-24260-6

Electronic ISBN: 978-3-319-24261-3

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-24261-3_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner