Learning from Satisfying Assignments Using Risk Minimization
In this paper we consider the problem of Learning from Satisfying Assignments introduced by \cite{1} of finding a distribution that is a close approximation to the uniform distribution over the satisfying assignments of a low complexity Boolean function $f$. In a later work \cite{2} consider the same problem but with the knowledge of some continuous distribution $D$ and the objective being to estimate $D_f$, which is $D$ restricted to the satisfying assignments of an unknown Boolean function $f$. We consider these problems from the point of view of parameter estimation techniques in statistical machine learning and prove similar results that are based on standard optimization algorithms for Risk Minimization.
Code (0)
등록된 구현이 없습니다.
Tasks
parameter estimationSimilar Papers 제목 키워드 기반
The Long, the Short and the Random
We furnish solid evidence, both theoretical and empirical, towards the existence of a deterministic algorithm for random sparse $\#\Omega(\log n)$-SAT instances, which computes the exact counting of satisfying assignment…
Logical Boltzmann Machines
The idea of representing symbolic knowledge in connectionist systems has been a long-standing endeavour which has attracted much attention recently with the objective of combining machine learning and scalable sound reas…
Inductive logic programmingLearning from satisfying assignments under continuous distributions
What kinds of functions are learnable from their satisfying assignments? Motivated by this simple question, we extend the framework of De, Diakonikolas, and Servedio [DDS15], which studied the learnability of probability…
Differentially Private Empirical Risk Minimization Revisited: Faster and More General
In this paper we study the differentially private Empirical Risk Minimization (ERM) problem in different settings. For smooth (strongly) convex loss function with or without (non)-smooth regularization, we give algorithm…
Are You Satisfied by This Partial Assignment?
Many procedures for SAT and SAT-related problems -- in particular for those requiring the complete enumeration of satisfying truth assignments -- rely their efficiency on the detection of partial assignments satisfying a…