Finetuning greedy kernel models by exchange algorithms
Article Sidebar
Published
Sep 21, 2024
Main Article Content
Abstract
Kernel based approximation offers versatile tools for high-dimensional approximation, which can especially be leveraged for surrogate modeling. For this purpose, both ``knot insertion'' and ``knot removal'' approaches aim at choosing a suitable subset of the data, in order to obtain a sparse but nevertheless accurate kernel model.In the present work, focussing on kernel based interpolation, we aim at combining these two approaches to further improve the accuracy of kernel models, without increasing the computational complexity of the final kernel model. For this, we introduce a class of kernel exchange algorithms (KEA). The resulting KEA algorithm can be used for finetuning greedy kernel surrogate models, allowing for an reduction of the error up to 86.4% (17.2% on average) in our experiments.
Article Details
How to Cite
Iske, A., & Wenzel, T.
(2024).
Finetuning greedy kernel models by exchange algorithms.
Proceedings Of The Conference Algoritmy, , 1 - 10.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/algoritmy/article/view/2138/1021
Section
Articles
References
[1] S. De Marchi, R. Schaback, and H. Wendland. Near-optimal data-independent point locations for radial basis function interpolation. Advances in Computational Mathematics, 23(3):317–330, 2005.
[2] L. Demaret, N. Dyn, and A. Iske. Image compression by linear splines over adaptive triangulations. Signal Processing, 86(7):1604–1616, 2006.
[3] L. Demaret and A. Iske. Adaptive image approximation by linear splines over locally optimal delaunay triangulations. IEEE Signal Processing Letters, 13(5):281–284, 2006.
[4] L. Demaret and A. Iske. Optimal N -term approximation by linear splines over anisotropic delaunay triangulations. Mathematics of Computation, 84(293):1241–1264, 2015.
[5] F. Döppel, T. Wenzel, R. Herkert, B. Haasdonk, and M. Votsmeier. Goal-Oriented Two-Layered Kernel Models as Automated Surrogates for Surface Kinetics in Reactor Simulations. Chemie Ingenieur Technik, 2024.
[6] S. Dutta, M. W. Farthing, E. Perracchione, G. Savant, and M. Putti. A greedy non-intrusive reduced order model for shallow water equations. Journal of Computational Physics, 439:110378, 2021.
[7] G. E. Fasshauer and M. J. McCourt. Kernel-based Approximation Methods using MATLAB, volume 19. World Scientific Publishing Company, 2015.
[8] M. S. Floater and A. Iske. Multistep scattered data interpolation using compactly supported radial basis functions. Journal of Computational and Applied Mathematics, 73(1-2):65–78, 1996.
[9] M. S. Floater and A. Iske. Thinning algorithms for scattered data interpolation. BIT Numerical Mathematics, 38:705–720, 1998.
[10] R. Franke. A critical comparison of some methods for interpolation of scattered data. Technical report, Monterey, California: Naval Postgraduate School., 1979.
[11] B. Haasdonk, H. Kleikamp, M. Ohlberger, F. Schindler, and T. Wenzel. A New Certified Hierarchical and Adaptive RB-ML-ROM Surrogate Model for Parametrized PDEs. SIAM Journal on Scientific Computing, 5(3):A1039–A1065, 2023.
[12] D. S. Hochbaum. Approximation algorithms for NP-hard problems. ACM Sigact News, 28(2):40–52, 1997.
[13] T. Hofmann, B. Schölkopf, and A. J. Smola. Kernel methods in machine learning. The Annals of Statistics, 36(3):1171 – 1220, 2008.
[14] E. J. Kansa. Multiquadrics — A scattered data approximation scheme with applications to computational fluid-dynamics. II. Solutions to parabolic, hyperbolic and elliptic partial differential equations. Computers & Mathematics with Applications, 19(8-9):147–161, 1990.
[15] F. Marchetti. The extension of Rippa’s algorithm beyond LOOCV. Applied Mathematics Letters, 120:107262, 2021.
[16] F. Marchetti and E. Perracchione. Efficient Reduced Basis Algorithm (ERBA) for kernel-based approximation. Journal of Scientific Computing, 91(2):41, 2022.
[17] S. Müller. Komplexität und Stabilität von kernbasierten Rekonstruktionsmethoden (Complexity and Stability of Kernel-based Reconstructions). PhD thesis, Fakultät für Mathematik und Informatik, Georg-August-Universität Göttingen, 2009.
[18] M. Pazouki and R. Schaback. Bases for kernel-based spaces. Journal of Computational and Applied Mathematics, 236(4):575–588, 2011.
[19] S. Rippa. An algorithm for selecting a good value for the parameter c in radial basis function interpolation. Advances in Computational Mathematics, 11:193–210, 1999.
[20] G. Santin and B. Haasdonk. Convergence rate of the data-independent P -greedy algorithm in kernel-based approximation. Dolomites Research Notes on Approximation, 10:68–78, 2017.
[21] G. Santin and B. Haasdonk. Kernel methods for surrogate modeling. In P. Benner, S. Grivet-Talocia, A. Quarteroni, G. Rozza, W. Schilders, and L. M. Silveira, editors, Model Order Reduction, volume 2. De Gruyter, 2021.
[22] G. Santin, T. Wenzel, and B. Haasdonk. On the optimality of target-data-dependent kernel greedy interpolation in Sobolev Reproducing Kernel Hilbert Spaces. arXiv preprint arXiv:2307.09811, 2023.
[23] R. Schaback and H. Wendland. Adaptive greedy techniques for approximate solution of large RBF systems. Numerical Algorithms, 24(3):239–254, 2000.
[24] I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008.
[25] H. Wendland. Scattered Data Approximation, volume 17 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2005. [26] T. Wenzel, F. Marchetti, and E. Perracchione. Data-driven kernel designs for optimized greedy schemes: A machine learning perspective. SIAM Journal on Scientific Computing, 46(1):C101–C126, 2024.
[27] T. Wenzel, G. Santin, and B. Haasdonk. A novel class of stabilized greedy kernel approximation algorithms: Convergence, stability and uniform point distribution. Journal of Approximation Theory, 262:105508, 2021.
[28] T. Wenzel, G. Santin, and B. Haasdonk. Analysis of target data-dependent greedy kernel algorithms: Convergence rates for f-, f· P-and f/P-greedy. Constructive Approximation, 57(1):45–74, 2023.
[2] L. Demaret, N. Dyn, and A. Iske. Image compression by linear splines over adaptive triangulations. Signal Processing, 86(7):1604–1616, 2006.
[3] L. Demaret and A. Iske. Adaptive image approximation by linear splines over locally optimal delaunay triangulations. IEEE Signal Processing Letters, 13(5):281–284, 2006.
[4] L. Demaret and A. Iske. Optimal N -term approximation by linear splines over anisotropic delaunay triangulations. Mathematics of Computation, 84(293):1241–1264, 2015.
[5] F. Döppel, T. Wenzel, R. Herkert, B. Haasdonk, and M. Votsmeier. Goal-Oriented Two-Layered Kernel Models as Automated Surrogates for Surface Kinetics in Reactor Simulations. Chemie Ingenieur Technik, 2024.
[6] S. Dutta, M. W. Farthing, E. Perracchione, G. Savant, and M. Putti. A greedy non-intrusive reduced order model for shallow water equations. Journal of Computational Physics, 439:110378, 2021.
[7] G. E. Fasshauer and M. J. McCourt. Kernel-based Approximation Methods using MATLAB, volume 19. World Scientific Publishing Company, 2015.
[8] M. S. Floater and A. Iske. Multistep scattered data interpolation using compactly supported radial basis functions. Journal of Computational and Applied Mathematics, 73(1-2):65–78, 1996.
[9] M. S. Floater and A. Iske. Thinning algorithms for scattered data interpolation. BIT Numerical Mathematics, 38:705–720, 1998.
[10] R. Franke. A critical comparison of some methods for interpolation of scattered data. Technical report, Monterey, California: Naval Postgraduate School., 1979.
[11] B. Haasdonk, H. Kleikamp, M. Ohlberger, F. Schindler, and T. Wenzel. A New Certified Hierarchical and Adaptive RB-ML-ROM Surrogate Model for Parametrized PDEs. SIAM Journal on Scientific Computing, 5(3):A1039–A1065, 2023.
[12] D. S. Hochbaum. Approximation algorithms for NP-hard problems. ACM Sigact News, 28(2):40–52, 1997.
[13] T. Hofmann, B. Schölkopf, and A. J. Smola. Kernel methods in machine learning. The Annals of Statistics, 36(3):1171 – 1220, 2008.
[14] E. J. Kansa. Multiquadrics — A scattered data approximation scheme with applications to computational fluid-dynamics. II. Solutions to parabolic, hyperbolic and elliptic partial differential equations. Computers & Mathematics with Applications, 19(8-9):147–161, 1990.
[15] F. Marchetti. The extension of Rippa’s algorithm beyond LOOCV. Applied Mathematics Letters, 120:107262, 2021.
[16] F. Marchetti and E. Perracchione. Efficient Reduced Basis Algorithm (ERBA) for kernel-based approximation. Journal of Scientific Computing, 91(2):41, 2022.
[17] S. Müller. Komplexität und Stabilität von kernbasierten Rekonstruktionsmethoden (Complexity and Stability of Kernel-based Reconstructions). PhD thesis, Fakultät für Mathematik und Informatik, Georg-August-Universität Göttingen, 2009.
[18] M. Pazouki and R. Schaback. Bases for kernel-based spaces. Journal of Computational and Applied Mathematics, 236(4):575–588, 2011.
[19] S. Rippa. An algorithm for selecting a good value for the parameter c in radial basis function interpolation. Advances in Computational Mathematics, 11:193–210, 1999.
[20] G. Santin and B. Haasdonk. Convergence rate of the data-independent P -greedy algorithm in kernel-based approximation. Dolomites Research Notes on Approximation, 10:68–78, 2017.
[21] G. Santin and B. Haasdonk. Kernel methods for surrogate modeling. In P. Benner, S. Grivet-Talocia, A. Quarteroni, G. Rozza, W. Schilders, and L. M. Silveira, editors, Model Order Reduction, volume 2. De Gruyter, 2021.
[22] G. Santin, T. Wenzel, and B. Haasdonk. On the optimality of target-data-dependent kernel greedy interpolation in Sobolev Reproducing Kernel Hilbert Spaces. arXiv preprint arXiv:2307.09811, 2023.
[23] R. Schaback and H. Wendland. Adaptive greedy techniques for approximate solution of large RBF systems. Numerical Algorithms, 24(3):239–254, 2000.
[24] I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008.
[25] H. Wendland. Scattered Data Approximation, volume 17 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2005. [26] T. Wenzel, F. Marchetti, and E. Perracchione. Data-driven kernel designs for optimized greedy schemes: A machine learning perspective. SIAM Journal on Scientific Computing, 46(1):C101–C126, 2024.
[27] T. Wenzel, G. Santin, and B. Haasdonk. A novel class of stabilized greedy kernel approximation algorithms: Convergence, stability and uniform point distribution. Journal of Approximation Theory, 262:105508, 2021.
[28] T. Wenzel, G. Santin, and B. Haasdonk. Analysis of target data-dependent greedy kernel algorithms: Convergence rates for f-, f· P-and f/P-greedy. Constructive Approximation, 57(1):45–74, 2023.