Monotone Boolean Functions, Feasibility/Infeasibility, LP-type problems and MaxCon

• URL: http://arxiv.org/abs/2005.05490v1
• Date: Mon, 11 May 2020 23:51:15 GMT
• Title: Monotone Boolean Functions, Feasibility/Infeasibility, LP-type problems and MaxCon
• Authors: David Suter, Ruwan Tennakoon, Erchuan Zhang, Tat-Jun Chin and Alireza Bab-Hadiashar
• Abstract summary: 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.
• Score: 43.0008129048353
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper outlines connections between Monotone Boolean Functions, LP-Type problems and the Maximum Consensus Problem. The latter refers to a particular type of robust fitting characterisation, popular in Computer Vision (MaxCon). Indeed, this is our main motivation but we believe the results of the study of these connections are more widely applicable to LP-type problems (at least 'thresholded versions', as we describe), and perhaps even more widely. We illustrate, with examples from Computer Vision, how the resulting perspectives suggest new algorithms. Indeed, we focus, in the experimental part, on how the Influence (a property of Boolean Functions that takes on a special form if the function is Monotone) can guide a search for the MaxCon solution.

Related papers

• Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects [0.6554326244334868]
  The tree-width of a multivariate is the tree-width of the hypergraph with hyperedges corresponding to its terms. A representation of a Boolean function as the sign of a bounded tree-width is called a threshold representation.
  arXiv  Detail & Related papers  (2025-01-14T18:28:08Z)
• Bridging the Divide: Reconsidering Softmax and Linear Attention [116.34723260730405]
  We present two key perspectives to understand and alleviate the limitations of linear attention. We prove that linear attention is not injective, which is prone to assign identical attention weights to different query vectors. Secondly, we confirm that effective local modeling is essential for the success of Softmax attention, in which linear attention falls short.
  arXiv  Detail & Related papers  (2024-12-09T15:44:22Z)
• A Search for Nonlinear Balanced Boolean Functions by Leveraging Phenotypic Properties [3.265773263570237]
  We consider the problem of finding perfectly balanced Boolean functions with high non-linearity values. Such functions have extensive applications in domains such as cryptography and error-correcting coding theory. We provide an approach for finding such functions by a local search method that exploits the structure of the underlying problem.
  arXiv  Detail & Related papers  (2023-06-15T15:16:19Z)
• A Causal Framework to Quantify the Robustness of Mathematical Reasoning with Language Models [81.15974174627785]
  We study the behavior of language models in terms of robustness and sensitivity to direct interventions in the input space. Our analysis shows that robustness does not appear to continuously improve as a function of size, but the GPT-3 Davinci models (175B) achieve a dramatic improvement in both robustness and sensitivity compared to all other GPT variants.
  arXiv  Detail & Related papers  (2022-10-21T15:12:37Z)
• Tailored max-out networks for learning convex PWQ functions [0.0]
  In learning-based control, convex PWQ functions are often represented with the help of artificial neural networks. We show in this paper that convex PWQ functions can be exactly described by max-out-NN with only one hidden layer and two neurons.
  arXiv  Detail & Related papers  (2022-06-14T13:18:16Z)
• Revisiting Over-smoothing in BERT from the Perspective of Graph [111.24636158179908]
  Recently over-smoothing phenomenon of Transformer-based models is observed in both vision and language fields. We find that layer normalization plays a key role in the over-smoothing issue of Transformer-based models. We consider hierarchical fusion strategies, which combine the representations from different layers adaptively to make the output more diverse.
  arXiv  Detail & Related papers  (2022-02-17T12:20:52Z)
• 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)
• Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approach [84.29777236590674]
  We study the estimation of causal parameters when not all confounders are observed and instead negative controls are available. Recent work has shown how these can enable identification and efficient estimation via two so-called bridge functions.
  arXiv  Detail & Related papers  (2021-03-25T17:59:19Z)
• Consensus Maximisation Using Influences of Monotone Boolean Functions [40.86597150734384]
  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.
  arXiv  Detail & Related papers  (2021-03-06T22:01:06Z)
• IReEn: Reverse-Engineering of Black-Box Functions via Iterative Neural Program Synthesis [70.61283188380689]
  We investigate the problem of revealing the functionality of a black-box agent. We do not rely on privileged information on the black box, but rather investigate the problem under a weaker assumption of having only access to inputs and outputs of the program. Our results show that the proposed approach outperforms the state-of-the-art on this challenge by finding an approximately functional equivalent program in 78% of cases.
  arXiv  Detail & Related papers  (2020-06-18T17:50:48Z)

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.