Polynomial-time probabilistic reasoning with partial observations via
  implicit learning in probability logics
  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.
