Graphics processing units in acceleration of bandwidth selection for kernel density estimation

• Autorzy: Andrzejewski W. , Gramacki A. , Gramacki J.
• Języki publikacji: EN

Abstrakty

EN

The Probability Density Function (PDF) is a key concept in statistics. Constructing the most adequate PDF from the observed data is still an important and interesting scientific problem, especially for large datasets. PDFs are often estimated using nonparametric data-driven methods. One of the most popular nonparametric method is the Kernel Density Estimator (KDE). However, a very serious drawback of using KDEs is the large number of calculations required to compute them, especially to find the optimal bandwidth parameter. In this paper we investigate the possibility of utilizing Graphics Processing Units (GPUs) to accelerate the finding of the bandwidth. The contribution of this paper is threefold: (a) we propose algorithmic optimization to one of bandwidth finding algorithms, (b) we propose efficient GPU versions of three bandwidth finding algorithms and (c) we experimentally compare three of our GPU implementations with the ones which utilize only CPUs. Our experiments show orders of magnitude improvements over CPU implementations of classical algorithms.

Słowa kluczowe

EN

bandwidth selection; graphics processing unit; probability density function; nonparametric estimation; kernel estimation

PL

szerokość pasmowa; programowalny procesor graficzny; funkcja gęstości prawdopodobieństwa; estymacja nieparametryczna; estymacja jądrowa

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2013
• Tom: Vol. 23, no. 4
• Strony: 869--885
• Opis fizyczny: Bibliogr. 31 poz., rys., tab., wykr.

Twórcy

autor

Andrzejewski W.

• Institute of Computer Science, Poznań University of Technology, Piotrowo 2, 60-965 Poznań, Poland

autor

Gramacki A.

• Institute of Computer Science and Electronics, University of Zielona Góra, Licealna 9, 65-417 Zielona Góra, Poland

autor

Gramacki J.

• Computer Center, University of Zielona Góra, Licealna 9, 65-417 Zielona Góra, Poland

Bibliografia

• [1] Andrzejewski, W., Gramacki, A. and Gramacki, J. (2013). Density estimations for approximate query processing on SIMD architectures, Technical Report RA 03/13, Poznań University of Technology, Poznań.
• [2] Blohsfeld, B., Korus, D. and Seeger, B. (1999). A comparison of selectivity estimators for range queries on metric attributes, Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, Philadelphia, PA, USA, pp. 239–250.
• [3] Bochkanov, S. and Bystritsky, V. (2013). ALGLIB, http://www.alglib.net.
• [4] Chapman, B., Jost, G. and van der Pas, R. (2007). Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation), MIT Press, Cambridge, MA.
• [5] Duong, T. (2004). Bandwidth Selectors for Multivariate Kernel Density Estimation, Ph.D. thesis, University of Western Australia, Perth.
• [6] Farooqui, N., Kerr, A., Diamos, G., Yalamanchili, S. and Schwan, K. (2011). A framework for dynamically instrumenting GPU compute applications within GPU Ocelot, Proceedings of the 4th Workshop on General Purpose Processing on Graphics Processing Units, GPGPU-4, Newport Beach, CA, USA, pp. 9:1–9:9.
• [7] Gramacki, A., Gramacki, J. and Andrzejewski, W. (2010). Probability density functions for calculating approximate aggregates, Foundations of Computing and Decision Sciences 35(4): 223–240.
• [8] Greengard, L. and Strain, J. (1991). The fast Gauss transform, SIAM Journal on Scientific and Statistical Computing 12(1): 79–94.
• [9] Harris, M. (2007). Optimizing parallel reduction in CUDA, http://developer.download.nvidia.com/assets/cuda/files/reduction.pdf.
• [10] Hendriks, H. and Kim, P. (2003). Consistent and efficient density estimation, in V. Kumar, M.L. Gavrilova, C.J.K. Tan and P. L’Ecuyer (Eds.), Proceedings of the 2003 International Conference on Computational Science and Its Applications, ICCSA 2003: Part I, Lecture Notes in Computer Science, Vol. 2667, Springer-Verlag, New York, NY, Berlin/Heidelberg, pp. 388–397.
• [11] Johnson, N., Kotz, S. and Balakrishnan, N. (1994). Continuous Univariate Distributions, Volume 1, Probability and Statistics, John Wiley & Sons, Inc, New York, NY.
• [12] Johnson, N., Kotz, S. and Balakrishnan, N. (1995). Continuous Univariate Distributions, Volume 2, Probability and Statistics, John Wiley & Sons, Inc, New York, NY.
• [13] Kulczycki, P. (2005). Kernel Estimators in Systems Analysis, Wydawnictwa Naukowo-Techniczne, Warsaw, (in Polish).
• [14] Kulczycki, P. (2008). Kernel estimators in industrial applications, in B. Prasad (Ed.), Studies in Fuzziness and Soft Computing. Soft Computing Applications in Industry, Springer-Verlag, Berlin, pp. 69–91.
• [15] Kulczycki, P. and Charytanowicz, M. (2010). A complete gradient clustering algorithm formed with kernel estimators, International Journal of Applied Mathematics and Computer Science 20(1): 123–134, DOI: 10.2478/v10006-010-0009-3.
• [16] Li, Q. and Racine, J. (2007). Nonparametric Econometrics: Theory and Practice, Princeton University Press, Princeton, NJ.
• [17] Łukasik, S. (2007). Parallel computing of kernel density estimates with MPI, in Y. Shi, G.D. van Albada, J. Dongarra and P.M.A. Sloot (Eds.), Computational Science—ICCS 2007, Lecture Notes in Computer Science, Vol. 4489, Springer, Berlin/Heidelberg, pp. 726–734.
• [18] NVIDIA Corporation (2012). NVIDIA CUDA programming guide, http://developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_Guide.pdf.
• [19] NVIDIA Corporation (2013). NVIDIA’s next generation CUDA compute architecture: Kepler GK110, http://www.nvidia.com/content/PDF/kepler/NVIDIA-Kepler-GK110-Architecture-Whitepaper.pdf.
• [20] Michailidis, P.D. and Margaritis, K.G. (2013). Accelerating kernel density estimation on the GPU using the CUDA framework, Applied Mathematical Sciences 7(30): 1447–1476.
• [21] Nelder, J.A. and Mead, R. (1965). A simplex method for function minimization, The Computer Journal 7(4): 308–313.
• [22] Raykar, V. and Duraiswami, R. (2006). Very fast optimal bandwidth selection for univariate kernel density estimation, Technical Report CS-TR-4774/UMIACS-TR-2005-73, University of Maryland, College Park, MD.
• [23] Raykar, V., Duraiswami, R. and Zhao, L. (2010). Fast computation of kernel estimators, Journal of Computational and Graphical Statistics 19(1): 205–220.
• [24] Sawerwain, M. (2012). GPU-based parallel algorithms for transformations of quantum states expressed as vectors and density matrices, in R. Wyrzykowski, J. Dongarra, K. Karczewski and J. Waśniewski (Eds.), Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, Vol. 7203, Springer-Verlag, New York, NY/Berlin/Heidelberg, pp. 215–224.
• [25] Sheather, S. (2004). Density estimation, Statistical Science 19(4): 588–597.
• [26] Silverman, B. (1986). Density Estimation for Statistics and Data Analysis, Chapman & Hall/CRC Monographs on Statistics & Applied Probability, London.
• [27] Silverman, B.W. (1982). Algorithm AS 176: Kernel density estimation using the fast Fourier transform, Journal of the Royal Statistical Society: Series C (Applied Statistics) 31(1): 93–99.
• [28] Simonoff, J. (1996). Smoothing Methods in Statistics, Springer Series in Statistics, Springer-Verlag, New York, NY/Berlin/Heidelberg.
• [29] Wand, M. and Jones, M. (1995). Kernel Smoothing, Chapman & Hall/CRC Monographs on Statistics & Applied Probability, Chapman&Hall, London.
• [30] Xavier, C. and Iyengar, S. (1998). Introduction to Parallel Algorithms, Wiley Series on Parallel and Distributed Computing, Wiley.
• [31] Yang, C., Duraiswami, R. and Gumerov, N. (2003). Improved fast Gauss transform, Technical Report CS-TR-4495, University of Maryland, College Park, MD.