@article{Juba_2019, title={Polynomial-Time Probabilistic Reasoning with Partial Observations via Implicit Learning in Probability Logics}, volume={33}, url={https://ojs.aaai.org/index.php/AAAI/article/view/4785}, DOI={10.1609/aaai.v33i01.33017866}, abstractNote={<p>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 decide 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 key polynomial-time fragments of resolution. Thus, these fragments are also quite expressive.</p>}, number={01}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Juba, Brendan}, year={2019}, month={Jul.}, pages={7866-7875} }