Polynomial-time probabilistic reasoning with partial observations via implicit learning in probability logics
This provides an efficient method for probabilistic analysis in scenarios where explicit models are unavailable, though it is incremental as it builds on known polynomial-time refutability results.
The paper tackles the problem of probabilistic reasoning with partial observations by using bounded-degree fragments of sum-of-squares logic as a probability logic, showing that constraints and bounds can be implicitly learned in polynomial-time.
Standard approaches to probabilistic reasoning require that one possesses an explicit model of the distribution in question. But, the empirical learning of models of probability distributions from partial observations is a problem for which efficient algorithms are generally not known. In this work we consider the use of bounded-degree fragments of the "sum-of-squares" logic as a probability logic. Prior work has shown that we can decide refutability for such fragments in polynomial-time. We propose to use such fragments to answer queries about whether a given probability distribution satisfies a given system of constraints and bounds on expected values. We show that in answering such queries, such constraints and bounds can be implicitly learned from partial observations in polynomial-time as well. It is known that this logic is capable of deriving many bounds that are useful in probabilistic analysis. We show here that it furthermore captures useful polynomial-time fragments of resolution. Thus, these fragments are also quite expressive.