A dimension adaptive sparse grid combination technique for machine learning

Abstract

We introduce a dimension adaptive sparse grid combination tech- nique for the machine learning problems of classification and regres- sion. A function over a d-dimensional space, which assumedly de- scribes the relationship between the features and the response vari- able, 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 ANOVA decomposition of the underlying problem. Experiments on synthetic data, where the structure is known, show the advantages of a dimension adaptive com- bination technique in run time behaviour, approximation errors, and interpretability.