Maximum Consensus by weighted influences of Monotone Boolean functions
Author Identifier
Erchuan Zhang
https://orcid.org/0000-0002-4005-5431
David Suter
https://orcid.org/0000-0001-6306-3023
Giang Truong
https://orcid.org/0000-0002-7690-7739
Syed Zulqarnain Gilani
Document Type
Conference Proceeding
Publication Title
Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
Volume
2022-June
First Page
8954
Last Page
8962
Publisher
IEEE
School
School of Science / Centre for Artificial Intelligence and Machine Learning (CAIML)
RAS ID
54185
Funders
Australian Research Council
Grant Number
ARC Numbers : DP200101675, DP200103448
Abstract
Maximisation of Consensus (MaxCon) is one of the most widely used robust criteria in computer vision. Tennakoon et al. (CVPR2021), made a connection between MaxCon and estimation of influences of a Monotone Boolean function. In such, there are two distributions involved: the distribution defining the influence measure; and the distribution used for sampling to estimate the influence measure. This paper studies the concept of weighted influences for solving MaxCon. In particular, we study the Bernoulli measures. Theoretically, we prove the weighted influences, under this measure, of points belonging to larger structures are smaller than those of points belonging to smaller structures in general. We also consider another 'natural' family of weighting strategies: sampling with uniform measure concentrated on a particular (Hamming) level of the cube. One can choose to have matching distributions: the same for defining the measure as for implementing the sampling. This has the advantage that the sampler is an unbiased estimator of the measure. Based on weighted sampling, we modify the algorithm of Tennakoon et al., and test on both synthetic and real datasets. We show some modest gains of Bernoulli sampling, and we illuminate some of the interactions between structure in data and weighted measures and weighted sampling.
DOI
10.1109/CVPR52688.2022.00876
Access Rights
free_to_read
Comments
Zhang, E., Suter, D., Tennakoon, R., Chin, T. J., Bab-Hadiashar, A., Truong, G., & Gilani, S. Z. (2022). Maximum Consensus by Weighted Influences of Monotone Boolean Functions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 8964-8972. https://doi.org/10.1109/CVPR52688.2022.00876
An open access version of this paper is provided by the Computer Vision Foundation.