Consensus Maximisation Using Influences of Monotone Boolean Functions

• URL: http://arxiv.org/abs/2103.04200v1
• Date: Sat, 6 Mar 2021 22:01:06 GMT
• Title: Consensus Maximisation Using Influences of Monotone Boolean Functions
• Authors: Ruwan Tennakoon, David Suter, Erchuan Zhang, Tat-Jun Chin, Alireza Bab-Hadiashar
• Abstract summary: MaxCon aims to find the largest subset of data that fits the model within some tolerance level. We show that influences of points belonging to the largest structure in data would generally be smaller under certain conditions. Results for both synthetic and real visual data experiments show that the MBF based algorithm is capable of generating a near optimal solution relatively quickly.
• Score: 40.86597150734384
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consensus maximisation (MaxCon), which is widely used for robust fitting in computer vision, aims to find the largest subset of data that fits the model within some tolerance level. In this paper, we outline the connection between MaxCon problem and the abstract problem of finding the maximum upper zero of a Monotone Boolean Function (MBF) defined over the Boolean Cube. Then, we link the concept of influences (in a MBF) to the concept of outlier (in MaxCon) and show that influences of points belonging to the largest structure in data would generally be smaller under certain conditions. Based on this observation, we present an iterative algorithm to perform consensus maximisation. Results for both synthetic and real visual data experiments show that the MBF based algorithm is capable of generating a near optimal solution relatively quickly. This is particularly important where there are large number of outliers (gross or pseudo) in the observed data.

Related papers

• From Maximum Cut to Maximum Independent Set [7.250073177017239]
  It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. It turns out that this strategy greatly improves the approximation for the independence number of random ErdHos-R'enyi graphs. It also exhibits perfect performance on a benchmark arising from coding theory.
  arXiv  Detail & Related papers  (2024-08-13T09:33:41Z)
• Convex Bounds on the Softmax Function with Applications to Robustness Verification [69.09991317119679]
  The softmax function is a ubiquitous component at the output of neural networks and increasingly in intermediate layers as well. This paper provides convex lower bounds and concave upper bounds on the softmax function, which are compatible with convex optimization formulations for characterizing neural networks and other ML models.
  arXiv  Detail & Related papers  (2023-03-03T05:07:02Z)
• The Theoretical Expressiveness of Maxpooling [4.028503203417233]
  We develop a theoretical framework analyzing ReLU based approximations to max pooling. We find that max pooling cannot be efficiently replicated using ReLU activations. We conclude that the main cause of a difference between max pooling and an optimal approximation, can be overcome with other architectural decisions.
  arXiv  Detail & Related papers  (2022-03-02T10:45:53Z)
• Maximum Consensus by Weighted Influences of Monotone Boolean Functions [40.38142264859375]
  This paper studies the concept of weighted influences for solving MaxCon. 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 sampling/weighting strategies, sampling with uniform measure concentrated on a particular (Hamming) level of the cube.
  arXiv  Detail & Related papers  (2021-12-02T03:16:10Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  We generalize the notion of a von Neumann winner to the multi-criteria setting by taking inspiration from Blackwell's approachability. Our framework allows for non-linear aggregation of preferences across criteria, and generalizes the linearization-based approach from multi-objective optimization. We show that the Blackwell winner of a multi-criteria problem instance can be computed as the solution to a convex optimization problem.
  arXiv  Detail & Related papers  (2021-05-05T03:23:11Z)
• Causal Collaborative Filtering [50.22155187512759]
  Causal Collaborative Filtering is a framework for modeling causality in collaborative filtering and recommendation. We show that many traditional CF algorithms are actually special cases of CCF under simplified causal graphs. We propose a conditional intervention approach for $do$-operations so that we can estimate the user-item causal preference.
  arXiv  Detail & Related papers  (2021-02-03T04:16:11Z)
• Fairness in Streaming Submodular Maximization: Algorithms and Hardness [20.003009252240222]
  We develop the first streaming approximation for submodular under fairness constraints, for both monotone and non-monotone functions. We validate our findings on DPP-based movie recommendation, clustering-based summarization, and maximum coverage in social networks.
  arXiv  Detail & Related papers  (2020-10-14T22:57:07Z)
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances [58.54078318403909]
  The min-max problem, also known as the saddle point problem, is a class adversarial problem which is also studied in the context ofsum games.
  arXiv  Detail & Related papers  (2020-06-15T05:33:42Z)
• Monotone Boolean Functions, Feasibility/Infeasibility, LP-type problems and MaxCon [43.0008129048353]
  This paper outlines connections between Monotone Boolean Functions, LP-Type problems and the Maximum Consensus Problem. We illustrate, with examples from Computer Vision, how the resulting perspectives suggest new algorithms. We focus, in the experimental part, on how the Influence can guide a search for the MaxCon solution.
  arXiv  Detail & Related papers  (2020-05-11T23:51:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.