Voronoi Boundary Classification: A High-Dimensional Geometric Approach via Weighted Monte Carlo Integration

Vladislav Polianskii, Florian T. Pokorny
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:5162-5170, 2019.

Abstract

Voronoi cell decompositions provide a classical avenue to classification. Typical approaches however only utilize point-wise cell-membership information by means of nearest neighbor queries and do not utilize further geometric information about Voronoi cells since the computation of Voronoi diagrams is prohibitively expensive in high dimensions. We propose a Monte-Carlo integration based approach that instead computes a weighted integral over the boundaries of Voronoi cells, thus incorporating additional information about the Voronoi cell structure. We demonstrate the scalability of our approach in up to 3072 dimensional spaces and analyze convergence based on the number of Monte Carlo samples and choice of weight functions. Experiments comparing our approach to Nearest Neighbors, SVM and Random Forests indicate that while our approach performs similarly to Random Forests for large data sizes, the algorithm exhibits non-trivial data-dependent performance characteristics for smaller datasets and can be analyzed in terms of a geometric confidence measure, thus adding to the repertoire of geometric approaches to classification while having the benefit of not requiring any model changes or retraining as new training samples or classes are added.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-polianskii19a, title = {Voronoi Boundary Classification: A High-Dimensional Geometric Approach via Weighted {M}onte {C}arlo Integration}, author = {Polianskii, Vladislav and Pokorny, Florian T.}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {5162--5170}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/polianskii19a/polianskii19a.pdf}, url = {https://proceedings.mlr.press/v97/polianskii19a.html}, abstract = {Voronoi cell decompositions provide a classical avenue to classification. Typical approaches however only utilize point-wise cell-membership information by means of nearest neighbor queries and do not utilize further geometric information about Voronoi cells since the computation of Voronoi diagrams is prohibitively expensive in high dimensions. We propose a Monte-Carlo integration based approach that instead computes a weighted integral over the boundaries of Voronoi cells, thus incorporating additional information about the Voronoi cell structure. We demonstrate the scalability of our approach in up to 3072 dimensional spaces and analyze convergence based on the number of Monte Carlo samples and choice of weight functions. Experiments comparing our approach to Nearest Neighbors, SVM and Random Forests indicate that while our approach performs similarly to Random Forests for large data sizes, the algorithm exhibits non-trivial data-dependent performance characteristics for smaller datasets and can be analyzed in terms of a geometric confidence measure, thus adding to the repertoire of geometric approaches to classification while having the benefit of not requiring any model changes or retraining as new training samples or classes are added.} }
Endnote
%0 Conference Paper %T Voronoi Boundary Classification: A High-Dimensional Geometric Approach via Weighted Monte Carlo Integration %A Vladislav Polianskii %A Florian T. Pokorny %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-polianskii19a %I PMLR %P 5162--5170 %U https://proceedings.mlr.press/v97/polianskii19a.html %V 97 %X Voronoi cell decompositions provide a classical avenue to classification. Typical approaches however only utilize point-wise cell-membership information by means of nearest neighbor queries and do not utilize further geometric information about Voronoi cells since the computation of Voronoi diagrams is prohibitively expensive in high dimensions. We propose a Monte-Carlo integration based approach that instead computes a weighted integral over the boundaries of Voronoi cells, thus incorporating additional information about the Voronoi cell structure. We demonstrate the scalability of our approach in up to 3072 dimensional spaces and analyze convergence based on the number of Monte Carlo samples and choice of weight functions. Experiments comparing our approach to Nearest Neighbors, SVM and Random Forests indicate that while our approach performs similarly to Random Forests for large data sizes, the algorithm exhibits non-trivial data-dependent performance characteristics for smaller datasets and can be analyzed in terms of a geometric confidence measure, thus adding to the repertoire of geometric approaches to classification while having the benefit of not requiring any model changes or retraining as new training samples or classes are added.
APA
Polianskii, V. & Pokorny, F.T.. (2019). Voronoi Boundary Classification: A High-Dimensional Geometric Approach via Weighted Monte Carlo Integration. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:5162-5170 Available from https://proceedings.mlr.press/v97/polianskii19a.html.

Related Material