David Buchman

UAI Conference 2017 Conference Paper

Why Rules are Complex: Real-Valued Probabilistic Logic Programs are not Fully Expressive

• David Buchman
• David Poole 0001

This paper explores what can and cannot be represented by probabilistic logic programs (PLPs). Propositional PLPs can represent any distribution because they can be acyclic. For relational domains with fixed populations, the probabilistic parameters can be derived as the solutions to polynomial equations. Unfortunately, sometimes they only have complexvalued solutions. Thus PLPs, even with arbitrarily real-valued parameters, cannot represent all distributions. Moreover, they cannot approximate all distributions. Allowing the parameters to be complex numbers, we present a natural truly-cyclic canonical representation that with probability 1 can represent all distributions for (propositional or) relational domains with fixed populations, and, unlike standard representations, has no redundant parameters.

KR Conference 2016 Short Paper

Negation Without Negation in Probabilistic Logic Programming

• David Buchman
• David Poole

Probabilistic logic programs without negation can have cycles (with a preference for false), but cannot represent all conditional distributions. Probabilistic logic programs with negation can represent arbitrary conditional probabilities, but with cycles they create logical inconsistencies. We show how allowing negative noise probabilities allows us to represent arbitrary conditional probabilities without negations. Noise probabilities for non-exclusive rules are difficult to interpret and unintuitive to manipulate; to alleviate this we define “probability-strengths” which provide an intuitive additive algebra for combining rules. For acyclic programs we prove what constraints on the strengths allow for proper distributions on the non-noise variables and allow for all non-extreme distributions to be represented. We show how arbitrary CPDs can be converted into this form in a canonical way. Furthermore, if a joint distribution can be compactly represented by a cyclic program with negations, we show how it can also be compactly represented with negative noise probabilities and no negations. This allows algorithms for exact inference that do not support negations to be applicable to probabilistic logic programs with negations. Programs We use capital letters for random variables, and lower-case letters for them being true, e. g., b means B = true. A (probabilistic) rule has the form p: head ← body, where p is a probability, head is a positive literal, and body is a conjunction of other, positive or negative, literals. When p = 1, it can be omitted, and the rule is called a deterministic rule. The probabilistic aspect is captured using a set of special “noise” variables N1, N2,..., NN. Each noise variable appears exactly once as a rule head, in special probabilistic rules called probabilistic facts with the form pi: ni. Other probabilistic rules are actually only syntactic sugar: p: head ← body is short for p: ni and head ← ni ∧ body, where Ni is a new noise variable not used by any other rule. A program is a multiset of rules. For convenience, we sometimes treat programs as sets; however, unions may produce programs with recurring rules. A program with no noise variables is a deterministic program. Programs can be either cyclic or acyclic. A model is an assignment to all the variables, represented as a set of positive literals. We use the stable-model semantics (Gelfond and Lifschitz 1988). We take the semantics of a deterministic program to be its unique stable model. If it does not have a unique stable model, we call the program “(logically) inconsistent”. Inconsistency only arises in cyclic programs, when a cycle of rules contains a negation (Apt and Bezem 1991). A deterministic program realization (DPR) for a program R is a deterministic program derived from R by having every probabilistic fact pi: ni either omitted or converted to the deterministic ni. The semantics of a probabilistic program is a distribution over its 2N DPRs, where, inde-

AAAI Conference 2015 Conference Paper

Representing Aggregators in Relational Probabilistic Models

• David Buchman
• David Poole

We consider the problem of, given a probabilistic model on a set of random variables, how to add a new variable that depends on the other variables, without changing the original distribution. In particular, we consider relational models (such as Markov logic networks (MLNs)), where we cannot directly define conditional probabilities. In relational models, there may be an unbounded number of parents in the grounding, and conditional distributions need to be defined in terms of aggregators. The question we ask is whether and when it is possible to represent conditional probabilities at all in various relational models. Some aggregators have been shown to be representable by MLNs, by adding auxiliary variables; however it was unknown whether they could be defined without auxiliary variables. For other aggregators, it was not known whether they can be represented by MLNs at all. We obtained surprisingly strong negative results on the capability of flexible undirected relational models such as MLNs to represent aggregators without affecting the original model’s distribution. We provide a map of what aspects of the models, including the use of auxiliary variables and quantifiers, result in the ability to represent various aggregators. In addition, we provide proof techniques which can be used to facilitate future theoretic results on relational models, and demonstrate them on relational logistic regression (RLR).

KR Conference 2014 Conference Paper

Relational Logistic Regression

• Seyed Mehran Kazemi
• David Buchman
• Kristian Kersting
• Sriraam Natarajan
• David Poole

crime (which depends on how many other people could have committed the crime) (Poole 2003) we could consider the population to be the population of the neighbourhood, the population of the city, the population of the country, or the population of the whole world. It would be good to have a model that does not depend on this arbitrary decision. We would like to be able to compare models which involve different choices. • The population can change. For example, the number of people in a neighbourhood or in a school class may change. We would like a model to make reasonable predictions as the population changes. We would also like to be able to apply a model learned at one or a number of population sizes to different population sizes. For example, models from drug studies are acquired from very limited populations but are applied much more generally. • The relevant populations can be different for each individual. For example, the happiness of a person may depend on how many of her friends are kind (and how many are not kind). The set of friends is different for each individual. We would like a model that makes reasonable predictions for diverse numbers of friends. Logistic regression is a commonly used representation for aggregators in Bayesian belief networks when a child has multiple parents. In this paper we consider extending logistic regression to relational models, where we want to model varying populations and interactions among parents. In this paper, we first examine the representational problems caused by population variation. We show how these problems arise even in simple cases with a single parametrized parent, and propose a linear relational logistic regression which we show can represent arbitrary linear (in population size) decision thresholds, whereas the traditional logistic regression cannot. Then we examine representing interactions among the parents of a child node, and representing non-linear dependency on population size. We propose a multi-parent relational logistic regression which can represent interactions among parents and arbitrary polynomial decision thresholds. Finally, we show how other well-known aggregators can be represented using this relational logistic regression.

IJCAI Conference 2013 Conference Paper

Probabilistic Reasoning with Undefined Properties in Ontologically-Based Belief Networks

• Chia-Li Kuo
• David Buchman
• Arzoo Katiyar
• David Poole

This paper concerns building probabilistic models with an underlying ontology that defines the classes and properties used in the model. In particular, it considers the problem of reasoning with properties that may not always be defined. Furthermore, we may even be uncertain about whether a property is defined for a given individual. One approach is to explicitly add a value “undefined” to the range of random variables, forming extended belief networks; however, adding an extra value to a random variable’s range has a large computational overhead. In this paper, we propose an alternative, ontologically-based belief networks, where all properties are only used when they are defined, and we show how probabilistic reasoning can be carried out without explicitly using the value “undefined” during inference. We prove this is equivalent to reasoning with the corresponding extended belief network and empirically demonstrate that inference becomes more efficient.

ICML Conference 2011 Conference Paper

On Autoencoders and Score Matching for Energy Based Models

• Kevin Swersky
• Marc'Aurelio Ranzato
• David Buchman
• Benjamin M. Marlin
• Nando de Freitas