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
- 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) - Counterfactual Explanations for Oblique Decision Trees: Exact, Efficient
Algorithms [0.0]
We consider counterfactual explanations, the problem of minimally adjusting features in a source input instance so that it is classified as a target class under a given classification.
This has become a topic of recent interest as a way to query a trained model and suggest possible actions to overturn its decision.
arXiv Detail & Related papers (2021-03-01T16:04:33Z) - 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) - 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)
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.