Maximum Consensus by weighted influences of Monotone Boolean functions

Document Type

Conference Proceeding

Publication Title

Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition



First Page


Last Page





School of Science / Centre for Artificial Intelligence and Machine Learning (CAIML)


Australian Research Council

Grant Number

ARC Numbers : DP200101675, DP200103448


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.


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.



Access Rights