Abstract
To solve big data problems which occur in modern data mining applications, a comprehensive approach is required that combines a flexible model and an optimisation algorithm with fast convergence and a potential for efficient parallelisation both in the number of data points and the number of features.
In this paper we present an algorithm for fitting additive models based on the basis expansion principle. The classical backfitting algorithm that solves the underlying normal equations cannot be properly parallelised due to inherent data dependencies and leads to a limited error reduction under certain circumstances. Instead, we suggest a modified BiCGStab method adapted to suit the special block structure of the problem. The new method demonstrates superior convergence speed and promising parallel scalability.
We discuss the convergence properties of the method and investigate its convergence and scalability further using a set of benchmark problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Garcke, J., Griebel, M., Thess, M.: Data mining with sparse grids. Computing 67(3), 225–253 (2001)
Pflüger, D.: Spatially Adaptive Sparse Grids for High-Dimensional Problems. Verlag Dr. Hut, München (2010)
Heinecke, A., Pflüger, D.: Emerging architectures enable to boost massively parallel data mining using adaptive sparse grids. International Journal of Parallel Programming, 1–43 (July 2012)
Xu, W.: Towards optimal one pass large scale learning with averaged stochastic gradient descent. CoRR, abs/1107.2490 (2011)
Bellman, R., Bellman, R.: Adaptive Control Processes: A Guided Tour. Rand Corporation. Research studies, Princeton University Press (1961)
Novak, E., Wozniakowski, H.: Tractability of Multivariate Problems, Volume I: Linear Information. European Mathematical Society, Zürich (2008)
Novak, E.: Tractability of multivariate problems, Volume II: Standard Information for Functionals. European Mathematical Society, Zürich (2010)
Novak, E., Wozniakowski, H.: Tractability of Multivariate Problems, Volume III: Standard Information for Operators. European Mathematical Society, Zürich (2012)
Novak, E., Woźniakowski, H.: Approximation of infinitely differentiable multivariate functions is intractable. Journal of Complexity 25, 398–404 (2009)
Hegland, M., Wasilkowski, G.W.: On tractability of approximation in special function spaces. J. Complex. 29, 76–91 (2013)
Hastie, T., Tibshirani, R.: Generalized Additive Models. Chapman & Hall/CRC Monographs on Statistics & Applied Probability. Taylor & Francis (1990)
Buja, A., Hastie, T., Tibshirani, R.: Linear smoothers and additive models. The Annals of Statistics 17, 453–510 (1989)
Chu, E., Keshavarz, A., Boyd, S.: A distributed algorithm for fitting generalized additive models. Optimization and Engineering 14, 213–224 (2013)
Hsu, D., Karampatziakis, N., Langford, J., Smola, A.: Parallel online learning, ch. 14. Cambridge University Press (2011)
Stone, C.J.: The dimensionality reduction principle for generalized additive models. The Annals of Statistics 14, 590–606 (1986)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edn. Springer Series in Statistics. Springer (2011)
Xia, Y.: A note on the backfitting estimation of additive models. Bernoulli 15, 1148–1153 (2009)
van der Vorst, H.: Bi-cgstab: A fast and smoothly converging variant of bi-cg for the solution of nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing 13(2), 631–644 (1992)
Paige, C., Saunders, M.: Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis 12(4), 617–629 (1975)
Harrison, D.J., Rubinfeld, D.L.: Hedonic housing prices and the demand for clean air. Journal of Environmental Economics and Management 5(1), 81–102 (1978)
Adelman-McCarthy, J.K., et al.: The fifth data release of the sloan digital sky survey. The Astrophysical Journal Supplement Series 172(2), 634 (2007)
Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. The Annals of Statistics 32, 407–499 (2004)
Friedman, J.H.: Multivariate adaptive regression splines. The Annals of Statistics 19, 1–67 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Khakhutskyy, V., Hegland, M. (2014). Parallel Fitting of Additive Models for Regression. In: Lutz, C., Thielscher, M. (eds) KI 2014: Advances in Artificial Intelligence. KI 2014. Lecture Notes in Computer Science(), vol 8736. Springer, Cham. https://doi.org/10.1007/978-3-319-11206-0_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-11206-0_24
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11205-3
Online ISBN: 978-3-319-11206-0
eBook Packages: Computer ScienceComputer Science (R0)