To quantify uncertainties associated with input parameters of a physical model, one often employs surrogate models. We rely on Polynomial Chaos (PC) surrogates that replace complex models in studies requiring prohibitively many simulations. However, the classical methods for uncertainty quantification and surrogate construction are challenged by the high dimensionality and nonlinearity of the models at hand. To alleviate these difficulties, select state-of-the-art tools from machine learning, such as Bayesian compressive sensing and random forest classifiers, are ported and enhanced, in order to build efficient sparse surrogate representations with quantified uncertainty. Application to an 80-dimensional climate land model shows promising results, leading to efficient global sensitivity analysis and dimensionality reduction.