Large scale indefinite kernel fisher discriminant

Frank Michael Schleif; Andrej Gisbrecht; Peter Tino

doi:10.1007/978-3-319-24261-3_13

Large scale indefinite kernel fisher discriminant

Frank Michael Schleif^*, Andrej Gisbrecht, Peter Tino

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

Indefinite similarity measures can be frequently found in bioinformatics 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.

Original language	English
Title of host publication	Similarity-Based Pattern Recognition
Subtitle of host publication	Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015. Proceedings
Editors	Aasa Feragen, Marcello Pelillo, Marco Loog
Publisher	Springer
Pages	160-170
Number of pages	11
Volume	9370
ISBN (Electronic)	9783319242613
ISBN (Print)	9783319242606
DOIs	https://doi.org/10.1007/978-3-319-24261-3_13
Publication status	Published - 2015
Event	3rd International Workshop on Similarity-Based Pattern Recognition, SIMBAD 2015 - Copenhagen, Denmark Duration: 12 Oct 2015 → 14 Oct 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9370
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	3rd International Workshop on Similarity-Based Pattern Recognition, SIMBAD 2015
Country/Territory	Denmark
City	Copenhagen
Period	12/10/15 → 14/10/15

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

Access to Document

10.1007/978-3-319-24261-3_13

Personalised Medicine through Learning in the Model Space
Tino, P.
Engineering & Physical Science Research Council
1/10/13 → 31/03/17
Project: Research Councils

Cite this

Schleif, F. M., Gisbrecht, A., & Tino, P. (2015). Large scale indefinite kernel fisher discriminant. In A. Feragen, M. Pelillo, & M. Loog (Eds.), Similarity-Based Pattern Recognition : Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015. Proceedings (Vol. 9370, pp. 160-170). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9370). Springer. https://doi.org/10.1007/978-3-319-24261-3_13

Schleif, Frank Michael ; Gisbrecht, Andrej ; Tino, Peter. / Large scale indefinite kernel fisher discriminant. Similarity-Based Pattern Recognition : Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015. Proceedings. editor / Aasa Feragen ; Marcello Pelillo ; Marco Loog. Vol. 9370 Springer, 2015. pp. 160-170 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1efbd0fedb8a49ab9b768fcb8e9903d4,

title = "Large scale indefinite kernel fisher discriminant",

abstract = "Indefinite similarity measures can be frequently found in bioinformatics 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.",

author = "Schleif, {Frank Michael} and Andrej Gisbrecht and Peter Tino",

year = "2015",

doi = "10.1007/978-3-319-24261-3_13",

language = "English",

isbn = "9783319242606",

volume = "9370",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "160--170",

editor = "Aasa Feragen and Marcello Pelillo and Marco Loog",

booktitle = "Similarity-Based Pattern Recognition",

note = "3rd International Workshop on Similarity-Based Pattern Recognition, SIMBAD 2015 ; Conference date: 12-10-2015 Through 14-10-2015",

}

Schleif, FM, Gisbrecht, A & Tino, P 2015, Large scale indefinite kernel fisher discriminant. in A Feragen, M Pelillo & M Loog (eds), Similarity-Based Pattern Recognition : Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015. Proceedings. vol. 9370, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9370, Springer, pp. 160-170, 3rd International Workshop on Similarity-Based Pattern Recognition, SIMBAD 2015, Copenhagen, Denmark, 12/10/15. https://doi.org/10.1007/978-3-319-24261-3_13

Large scale indefinite kernel fisher discriminant. / Schleif, Frank Michael; Gisbrecht, Andrej; Tino, Peter.
Similarity-Based Pattern Recognition : Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015. Proceedings. ed. / Aasa Feragen; Marcello Pelillo; Marco Loog. Vol. 9370 Springer, 2015. p. 160-170 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9370).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Large scale indefinite kernel fisher discriminant

AU - Schleif, Frank Michael

AU - Gisbrecht, Andrej

AU - Tino, Peter

PY - 2015

Y1 - 2015

N2 - Indefinite similarity measures can be frequently found in bioinformatics 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.

AB - Indefinite similarity measures can be frequently found in bioinformatics 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.

UR - http://www.scopus.com/inward/record.url?scp=84945917688&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-24261-3_13

DO - 10.1007/978-3-319-24261-3_13

M3 - Conference contribution

AN - SCOPUS:84945917688

SN - 9783319242606

VL - 9370

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 160

EP - 170

BT - Similarity-Based Pattern Recognition

A2 - Feragen, Aasa

A2 - Pelillo, Marcello

A2 - Loog, Marco

PB - Springer

T2 - 3rd International Workshop on Similarity-Based Pattern Recognition, SIMBAD 2015

Y2 - 12 October 2015 through 14 October 2015

ER -

Schleif FM, Gisbrecht A, Tino P. Large scale indefinite kernel fisher discriminant. In Feragen A, Pelillo M, Loog M, editors, Similarity-Based Pattern Recognition : Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015. Proceedings. Vol. 9370. Springer. 2015. p. 160-170. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-24261-3_13

Large scale indefinite kernel fisher discriminant

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

Personalised Medicine through Learning in the Model Space

Cite this