TY - JOUR
T1 - Supervised low rank indefinite kernel approximation using minimum enclosing balls
AU - Schleif, Frank Michael
AU - Gisbrecht, Andrej
AU - Tino, Peter
PY - 2018/11/27
Y1 - 2018/11/27
N2 - Indefinite similarity measures can be frequently found in bio-informatics by means of alignment scores, but are also common in other fields like shape measures in image retrieval. Lacking an underlying vector space, the data are given as pairwise similarities only. The few algorithms available for such data do not scale to larger datasets. Focusing on probabilistic batch classifiers, the Indefinite Kernel Fisher Discriminant (iKFD) and the Probabilistic Classification Vector Machine (PCVM) are both effective algorithms for this type of data but, with cubic complexity. Here we propose an extension of iKFD and PCVM such that linear runtime and memory complexity is achieved for low rank indefinite kernels. Employing the Nyström approximation for indefinite kernels, we also propose a new almost parameter free approach to identify the landmarks, restricted to a supervised learning problem. Evaluations at several larger similarity data from various domains show that the proposed methods provides similar generalization capabilities while being easier to parametrize and substantially faster for large scale data.
AB - Indefinite similarity measures can be frequently found in bio-informatics by means of alignment scores, but are also common in other fields like shape measures in image retrieval. Lacking an underlying vector space, the data are given as pairwise similarities only. The few algorithms available for such data do not scale to larger datasets. Focusing on probabilistic batch classifiers, the Indefinite Kernel Fisher Discriminant (iKFD) and the Probabilistic Classification Vector Machine (PCVM) are both effective algorithms for this type of data but, with cubic complexity. Here we propose an extension of iKFD and PCVM such that linear runtime and memory complexity is achieved for low rank indefinite kernels. Employing the Nyström approximation for indefinite kernels, we also propose a new almost parameter free approach to identify the landmarks, restricted to a supervised learning problem. Evaluations at several larger similarity data from various domains show that the proposed methods provides similar generalization capabilities while being easier to parametrize and substantially faster for large scale data.
KW - Classification
KW - Indefinite kernel
KW - Indefinite learning
KW - Kernel fisher discriminant
KW - Low rank approximation
KW - Minimum enclosing ball
KW - Nyström approximation
UR - http://www.scopus.com/inward/record.url?scp=85053037192&partnerID=8YFLogxK
U2 - 10.1016/j.neucom.2018.08.057
DO - 10.1016/j.neucom.2018.08.057
M3 - Article
VL - 318
SP - 213
EP - 226
JO - Neurocomputing
JF - Neurocomputing
SN - 0925-2312
ER -