A dimension adaptive sparse grid combination technique for machine learning


  • Jochen Garcke




We introduce a dimension adaptive sparse grid combination technique for the machine learning problems of classification and regression. A function over a $d$-dimensional space, which assumedly describes the relationship between the features and the response variable, is reconstructed using a linear combination of partial functions that possibly depend only on a subset of all features. The partial functions are adaptively chosen during the computational procedure. This approach (approximately) identifies the \textsc{anova} decomposition of the underlying problem. Experiments on synthetic data, where the structure is known, show the advantages of a dimension adaptive combination technique in run time behaviour, approximation errors, and interpretability. References
  • M. Griebel, M. Schneider, and C. Zenger. A combination technique for the solution of sparse grid problems. In P. de Groen and R. Beauwens, editors, Iterative Methods in Linear Algebra, pages 263--281. IMACS, Elsevier, North Holland, 1992. http://wissrech.ins.uni-bonn.de/research/pub/griebel/griesiam.ps.gz.
  • M. Hegland. Adaptive sparse grids. In K. Burrage and Roger B. Sidje, editors, Proc. of 10th Computational Techniques and Applications Conference CTAC-2001, volume 44 of ANZIAM J., pages C335--C353, 2003. http://anziamj.austms.org.au/V44/CTAC2001/Hegl.
  • M. Hegland, J. Garcke, and V. Challis. The combination technique and some generalisations. Linear Algebra and its Applications, 420(2--3):249--275, 2007. doi:10.1016/j.laa.2006.07.014.
  • Ian H. Sloan, Xiaoqun Wang, and Henryk Wozniakowski. Finite-order weights imply tractability of multivariate integration. Journal of Complexity, 20:46--74, 2004. doi:10.1016/j.jco.2003.11.003.
  • Jerome H. Friedman. Multivariate adaptive regression splines. Ann. Statist., 19(1):1--141, 1991. http://projecteuclid.org/euclid.aos/1176347963.
  • J. Garcke. Regression with the optimised combination technique. In W. Cohen and A. Moore, editors, Proceedings of the 23rd ICML, pages 321--328, 2006. doi:10.1007/s006070170007.
  • J. Garcke, M. Griebel, and M. Thess. Data mining with sparse grids. Computing, 67(3):225--253, 2001. doi:10.1007/s006070170007.
  • T. Gerstner and M. Griebel. Dimension-Adaptive Tensor-Product Quadrature. Computing, 71(1):65--87, 2003. doi:10.1007/s00607-003-0015-5.





Proceedings Computational Techniques and Applications Conference