Sampling and Learning for Boolean Function
In this article, we continue our study on universal learning machine by introducing new tools. We first discuss boolean function and boolean circuit, and we establish one set of tools, namely, fitting extremum and proper sampling set. We proved the fundamental relationship between proper sampling set and complexity of boolean circuit. Armed with this set of tools, we then introduce much more effective learning strategies. We show that with such learning strategies and learning dynamics, universal learning can be achieved, and requires much less data.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Maximum Consensus by Weighted Influences of Monotone Boolean Functions
Robust model fitting is a fundamental problem in computer vision: used to pre-process raw data in the presence of outliers. Maximisation of Consensus (MaxCon) is one of the most popular robust criteria and widely used. R…
Easy and hard functions for the Boolean hidden shift problem
We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this p…
A Discrete Particle Swarm Optimizer for the Design of Cryptographic Boolean Functions
A Particle Swarm Optimizer for the search of balanced Boolean functions with good cryptographic properties is proposed in this paper. The algorithm is a modified version of the permutation PSO by Hu, Eberhart and Shi whi…
diff-SAT -- A Software for Sampling and Probabilistic Reasoning for SAT and Answer Set Programming
This paper describes diff-SAT, an Answer Set and SAT solver which combines regular solving with the capability to use probabilistic clauses, facts and rules, and to sample an optimal world-view (multiset of satisfying Bo…
Manthan: A Data Driven Approach for Boolean Function Synthesis
Boolean functional synthesis is a fundamental problem in computer science with wide-ranging applications and has witnessed a surge of interest resulting in progressively improved techniques over the past decade. Despite …
BIG-bench Machine Learning