Eintrag in der Universitätsbibliographie der TU Chemnitz
Volltext zugänglich unter
URN: urn:nbn:de:bsz:ch1-qucosa2-967411
Wagner, Theresa
Stoll, Martin ; Xi, Yuanzhe ; Porcelli, Margherita (Gutachter)
Additive Kernel Methods with Fourier Acceleration
Kurzfassung in englisch
Kernel matrices are crucial in many learning tasks, such as kernel ridge regression, support vector machines, or Gaussian process regression. One of the main computational bottlenecks when working with large-scale kernel-based learning is dealing with the large and typically dense kernel matrix. Depending on the dimension of the feature space, even computing all of its entries in a reasonable time becomes a challenging task. For such dense matrices, the cost of a matrix-vector product scales quadratically with the dimensionality if no customized methods are applied. Techniques dealing with fastapproximations of such kernel operations typically deteriorate in their performance if the feature space is high-dimensional. In this thesis, we realize evaluations with the kernel matrix via Fourier-accelerated approximations supported by rigorous error analysis. This matrix-free approach leverages the computational efficiency of the non-equispaced fast Fourier transform (NFFT), achieving nearly linear complexity for fixed accuracy. To deal with high-dimensional data sets, we introduce an additive kernel structure based on a feature grouping, decomposing the feature space into multiple sub-kernels that capture lower-order feature interactions only. This additive scheme enables the use of the proposed NFFT approach to maximize efficiency while, in theory, providing the potential to improve accuracy for many real-world data sets. We show that this procedure is also well suited to allow the approximation of the matrix that arises when the kernel is differentiated with respect to the kernel hyperparameters, a problem often found in the training phase of methods such as Gaussian processes. It significantly accelerates multiplications with the kernel matrices and derivative kernel
matrices and reduces memory cost by eliminating the need for costly Hadamard products of the Euclidean distance matrix and the kernel matrix arising from the differentiation. In addition, we use a preconditioning strategy based on low-rank approximations of the sub-kernels in this additive scheme, further speeding up the training phase and enhancing the overall efficiency and effectiveness of the resulting learning model. We analyze the performance of the additive kernel scheme with Fourier-accelerated kernel operations on kernel ridge regression, support vector machine, and Gaussian process regression models on several large-scale data sets.
| Universität: | Technische Universität Chemnitz | |
| Institut: | Professur Wissenschaftliches Rechnen | |
| Fakultät: | TU Chemnitz | |
| Dokumentart: | Dissertation | |
| Betreuer: | Stoll, Martin ; Nestler, Franziska | |
| DOI: | doi:10.60687/2025-0068 | |
| SWD-Schlagwörter: | Numerische lineare Algebra , Fourier-Transformation | |
| Freie Schlagwörter (Englisch): | Additive Kernels , Feature Grouping , Fourier Analysis , Kernel Derivatives , Preconditioning | |
| DDC-Sachgruppe: | Numerische Analysis | |
| Sprache: | englisch | |
| Tag der mündlichen Prüfung | 27.01.2025 | |
| OA-Lizenz | CC BY 4.0 |
