TL;DR
This paper introduces a new method for machine learning with "indefinite kernels," which are more flexible than traditional positive definite kernels and can capture complex domain-specific similarities. Their approach formulates a novel optimization problem that can be solved globally and efficiently, even with indefinite kernels, and allows for effective hyperparameter tuning.
What Problem Does This Paper Address?
Traditional kernel methods in machine learning rely on kernel functions that are "positive definite." This property ensures that the underlying feature space is well-behaved, allowing for efficient optimization and generalization guarantees. However, many real-world similarity measures, especially those derived from structured data (like strings or graphs), are not positive definite. Forcing these into a positive definite framework can lead to information loss. This paper addresses the challenge of learning effectively with these more general, indefinite kernels, which can represent richer similarity structures and potentially lead to better performance when positive definiteness is not naturally present or is difficult to establish.
Methods
The core contribution is a novel regularized risk minimization problem designed for learning in reproducing kernel Krein spaces. A key theoretical result is the application of a strong representer theorem to this problem. This theorem allows the learning problem to be reformulated as minimizing a quadratic form over a hypersphere. While this reformulated problem is generally non-convex, the authors present an algorithm that can find a globally optimal solution in time cubic in the number of training instances. This is achieved by adapting existing methods for optimizing quadratic forms over hyperspheres. Furthermore, they derive the gradient of the solution with respect to hyperparameters, enabling efficient hyperparameter tuning using standard optimization techniques. The approach also comes with a generalization bound based on Rademacher complexity.
Datasets
The paper evaluates its approach on:
- Synthetic experiments: Used to compare the proposed KREIN method against spectral transformations of indefinite kernels.
- Real-world vectorial datasets: Used to demonstrate the effectiveness of indefinite kernels on standard machine learning tasks.
- Structured data datasets: These datasets involve pairwise dissimilarities that are transformed into indefinite kernel matrices using a negative double-centering transformation. Examples include "coilyork," "balls 3D," "prodom," "chicken10," "protein," "zongker," "chicken25," "pdish57," "pdism57," and "woody50."
Key Insights and Ideas
- Indefinite kernels are powerful: The paper strongly suggests that indefinite kernels are not just a workaround but can be more effective than positive definite ones in certain scenarios, especially when dealing with structured data where natural similarity measures are often indefinite.
- Global optimality is achievable: Despite the non-convexity of the optimization problem arising from indefinite kernels, the authors demonstrate a method to find the guaranteed global optimum, which is crucial for reliable learning.
- Hyperparameter tuning made efficient: Deriving the gradient of the solution with respect to hyperparameters is a significant practical contribution, allowing for automated and efficient tuning, which is often a bottleneck in kernel methods.
- Krein spaces offer a principled framework: The use of Krein spaces provides a theoretical foundation for handling indefinite kernels, allowing for a consistent mathematical treatment and generalization analysis.
Key Results
- The proposed KREIN approach consistently outperforms state-of-the-art baselines on various classification and regression tasks, particularly those involving structured data and indefinite kernels.
- In synthetic experiments, the KREIN method showed superior performance compared to spectral transformations like clipping and shifting of the kernel spectrum.
- On specific real-world vectorial datasets (YACHT and AIRFOIL), indefinite kernels (RL-SIGMOID and DELTA-GAUSS) achieved statistically significantly better results than positive definite kernels.
- The algorithm finds a globally optimal solution in time cubic in the number of instances, which is efficient for kernel methods.
Limitations and Future Work
- OMCS-KREÏN limitations: The paper notes that an earlier approach, OMCS-KREÏN, which regularizes via the strong topology, can lead to hypotheses with large norms on the negative spectrum, potentially causing overfitting and failing to generalize. This highlights the importance of the proposed KREIN regularization via decomposition components.
- Numerical stability: While the paper presents a closed-form solution involving matrix inversion, it acknowledges that this can be numerically unstable for certain matrices. The preferred secular approach, however, is computationally efficient (O(n³)).
- Out-of-sample extension: The paper mentions that some spectral transformation approaches struggle with consistent out-of-sample extension, whereas their method, by working directly with the Krein space, implicitly handles this.
- Future work: The paper's success on structured data suggests further exploration in this domain. The efficient hyperparameter tuning mechanism could also be integrated into more complex learning pipelines.
Summary updated