Voronoi density estimator for high-dimensional data: Computation, compactification and convergence

Vladislav Polianskii, Giovanni Luca Marchetti, Alexander Kravberg, Anastasiia Varava, Florian T. Pokorny, Danica Kragic
Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180:1644-1653, 2022.

Abstract

The Voronoi Density Estimator (VDE) is an established density estimation technique that adapts to the local geometry of data. However, its applicability has been so far limited to problems in two and three dimensions. This is because Voronoi cells rapidly increase in complexity as dimensions grow, making the necessary explicit computations infeasible. We define a variant of the VDE deemed Compactified Voronoi Density Estimator (CVDE), suitable for higher dimensions. We propose computationally efficient algorithms for numerical approximation of the CVDE and formally prove convergence of the estimated density to the original one. We implement and empirically validate the CVDE through a comparison with the Kernel Density Estimator (KDE). Our results indicate that the CVDE outperforms the KDE on sound and image data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v180-polianskii22a, title = {Voronoi density estimator for high-dimensional data: Computation, compactification and convergence}, author = {Polianskii, Vladislav and Marchetti, Giovanni Luca and Kravberg, Alexander and Varava, Anastasiia and Pokorny, Florian T. and Kragic, Danica}, booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence}, pages = {1644--1653}, year = {2022}, editor = {Cussens, James and Zhang, Kun}, volume = {180}, series = {Proceedings of Machine Learning Research}, month = {01--05 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v180/polianskii22a/polianskii22a.pdf}, url = {https://proceedings.mlr.press/v180/polianskii22a.html}, abstract = {The Voronoi Density Estimator (VDE) is an established density estimation technique that adapts to the local geometry of data. However, its applicability has been so far limited to problems in two and three dimensions. This is because Voronoi cells rapidly increase in complexity as dimensions grow, making the necessary explicit computations infeasible. We define a variant of the VDE deemed Compactified Voronoi Density Estimator (CVDE), suitable for higher dimensions. We propose computationally efficient algorithms for numerical approximation of the CVDE and formally prove convergence of the estimated density to the original one. We implement and empirically validate the CVDE through a comparison with the Kernel Density Estimator (KDE). Our results indicate that the CVDE outperforms the KDE on sound and image data.} }
Endnote
%0 Conference Paper %T Voronoi density estimator for high-dimensional data: Computation, compactification and convergence %A Vladislav Polianskii %A Giovanni Luca Marchetti %A Alexander Kravberg %A Anastasiia Varava %A Florian T. Pokorny %A Danica Kragic %B Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2022 %E James Cussens %E Kun Zhang %F pmlr-v180-polianskii22a %I PMLR %P 1644--1653 %U https://proceedings.mlr.press/v180/polianskii22a.html %V 180 %X The Voronoi Density Estimator (VDE) is an established density estimation technique that adapts to the local geometry of data. However, its applicability has been so far limited to problems in two and three dimensions. This is because Voronoi cells rapidly increase in complexity as dimensions grow, making the necessary explicit computations infeasible. We define a variant of the VDE deemed Compactified Voronoi Density Estimator (CVDE), suitable for higher dimensions. We propose computationally efficient algorithms for numerical approximation of the CVDE and formally prove convergence of the estimated density to the original one. We implement and empirically validate the CVDE through a comparison with the Kernel Density Estimator (KDE). Our results indicate that the CVDE outperforms the KDE on sound and image data.
APA
Polianskii, V., Marchetti, G.L., Kravberg, A., Varava, A., Pokorny, F.T. & Kragic, D.. (2022). Voronoi density estimator for high-dimensional data: Computation, compactification and convergence. Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 180:1644-1653 Available from https://proceedings.mlr.press/v180/polianskii22a.html.

Related Material