Overview of the Research Field of Indefinite Learning

Motivation

Kernel methods like support vector machine (SVM), kernel principal component analysis (kPCA) or gaussian processes are popular tools in Machine Learning. The backbone of these approaches is the famous kernel trick, i.e., that a possibly infinite dimensional feature space is accessible via an inner product – the kernel function. The content object, all methods work with, is the kernel matrix, which must be positive-semi-definite (psd), so that a Hilbert space is induced. The field of indefinite learning emerges from the issue of indefinite kernels (kernel matrix or kernel function), which violate the assumptions of the kernel theory, by inducing a Krein space instead of a Hilbert space. Justifications for existence of such matrices can be given in the context of bioinformatics, local learning or consequences of approximation.

Main questions in this field are:

What is the source of indefiniteness?
Does it contain relevant information for the problem at hand?
How to adopt the established methods so that they can handle these (non-metric/non-psd) matrices?
How to optimize in the domain of non-convex loss-functions?
How to correct the eigenspectrum of the indefinite matrix to be psd - effective and damage-free

In the days of big data, computational complexity and memory efficiency is mainly discussed in terms of matrix approximation. Already successful approximation techniques, like Nyström approximation, have been extended to the indefinite case with proven error-bounds.

Open Issues are often:

providing a reasonable out-of-sample extension, so that the model can be used for unseen data
improving on the approximation errors with efficient sampling strategies
adopting the already established methods, in particular their optimization problem and most important, finding efficient algorithms in the context of large-scale learning

Relevant Researchers

Alphabetic (incomplete) list of researchers, who contributed to the field of indefinite learning. Research groups with co-authors are aligned.

Difeng Cai, Emory University

Gaelle Loosli, PobRun

Cheng Soon Ong, CSIRO

Ronny Luss, IBM

Alexandre D’aspremont, École normale supérieure - PSL

Katharina Morik, TU Dortmund

Dino Oglic, AstraZeneca

Thomas Gärtner, TU Wien

Elzbieta Pekalska, University of Manchester

Robert P.W. Duin, Delft University of Technology\ Bernard Haasdonk, Uni Stuttgart

Frank-Michael Schleif, UAS Würzburg

Peter Tino, University of Birmingham\ Andrej Gisbrecht, Aalto University\ Maximilian Münch, UAS Würzburg

Johan Suykens, KU Leuven

Siamak Mehrkanoon, Maastricht Univ.\ Fanghui Liu, Swiss Federal Institute of Technology in Lausanne\ Xiaolin Huang, Shanghai Jiao Tong Univ.

Recent Publications

Publications obtained via Google-Scholar (keywords: reproducing kernel krein space, indefinite nyström approximation, non-psd kernel, indefinite learning, indefinite SVM) since 2017 group as follows:

Large Scale Learning

Schleif, Frank-Michael, Andrej Gisbrecht, and Peter Tino. "Supervised low rank indefinite kernel approximation using minimum enclosing balls." Neurocomputing 318 (2018): 213-226.
Oglic, Dino, and Thomas Gärtner. "Scalable learning in reproducing kernel krein spaces." International Conference on Machine Learning. PMLR, 2019.
Andrej Gisbrecht, Frank-Michael Schleif. "Metric and non-metric proximity transformations at linear costs." Neurocomputing 167: 643-657 (2015)
Liu, Fanghui, et al. "Fast learning in reproducing kernel krein spaces via signed measures." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
Cai, Difeng, James Nagy, and Yuanzhe Xi. "Fast and stable deterministic approximation of general symmetric kernel matrices in high dimensions." arXiv preprint arXiv:2102.05215 (2021).
Heilig, Simon, Maximilian Münch and Frank-Michael Schleif. „Memory Efficient Kernel Approximation for Non-Stationary and Indefinite Kernels.” 2022 International Joint Conference on Neural Networks (IJCNN).

Krein Space Methods

Schleif, Frank-Michael, and Peter Tino. "Indefinite core vector machine." Pattern Recognition 71 (2017): 187-195.
Huang, Xiaolin, et al. "Indefinite kernels in least squares support vector machines and principal component analysis." Applied and Computational Harmonic Analysis 43.1 (2017): 162-172.
Huang, Xiaolin, et al. "Classification With Truncated L1 Distance Kernel." IEEE transactions on neural networks and learning systems 29.5 (2017): 2025-2030.
Mehrkanoon, Siamak, Xiaolin Huang, and Johan AK Suykens. "Indefinite kernel spectral learning." Pattern Recognition 78 (2018): 144-153.
Schleif, Frank-Michael, Christoph Raab, and Peter Tino. "Sparsification of indefinite learning models." Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). Springer, Cham, 2018.
Liu, Fanghui, et al. "Indefinite kernel logistic regression with concave-inexact-convex procedure." IEEE Transactions on Neural Networks and Learning Systems 30.3 (2018): 765-776.

Proxy Learning, Spectral Transformation, Embedding Methods

Liu, Fanghui, et al. "Robust kernel approximation for classification." International Conference on Neural Information Processing. Springer, Cham, 2017.
Münch, Maximilian, Christoph Raab, and Frank-Michael Schleif. "Encoding of Indefinite Proximity Data: A Structure Preserving Perspective." International Conference on Pattern Recognition Applications and Methods. Springer, Cham, 2020.
Münch, Maximilian, et al. "Scalable embedding of multiple perspectives for indefinite life-science data analysis." 2021 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2021.

Machine learning for non-metric proximity data