Learning from Satisfying Assignments Using Risk Minimization
This work addresses the problem of estimating distributions over satisfying assignments of Boolean functions, which is relevant for researchers working on statistical machine learning and Boolean function analysis.
This paper addresses the problem of learning from satisfying assignments, aiming to approximate the uniform distribution over satisfying assignments of a low-complexity Boolean function or to estimate a continuous distribution restricted to the satisfying assignments of an unknown Boolean function. The authors achieve this by applying parameter estimation techniques from statistical machine learning, deriving results based on standard optimization algorithms for 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.