There has been a substantial recent focus on the concept of probabilistic programming [6] towards its positioning as a prominent paradigm for advancing and facilitating the development of machine-learning applications.4 A probabilisticprogramming language typically consists of two components: a speci cation of a stochastic process (the prior), and a speci cation of observations that restrict the probability space to a conditional subspace (the posterior). This paper gives a brief overview of Probabilistic Programming DataLog (PPDL), a recently proposed declarative framework for specifying statistical models on top of a database, through an appropriate extension of Datalog [1]. By virtue of extending Datalog, PPDL o ers a natural integration with the database, and has a robust declarative semantics, that is, semantic independence from the algorithmic evaluation of rules, and semantic invariance under logical program transformations. It provides convenient mechanisms to allow common numerical probability functions as rst-class citizens in the language; in particular, conclusions of rules may contain values drawn from such functions.
The semantics of a PPDL program is a probability distribution over the possible
outcomes of the input database with respect to the program. These outcomes are
minimal solutions with respect to a related program that involves existentially
quanti ed variables in conclusions. Observations are incorporated by means of
logical integrity constraints. As argued in [
Our example is inspired by the burglar example of Pearl that has been frequently used for illustrating probabilistic programming. This example models a statistical process of alarming due to burglaries and earthquakes, and the goal is ? Taub Fellow { supported by the Taub Foundation 4 An e ort in this direction is led by DARPA's Probabilistic Programming for Advancing Machine Learning (PPAML) program.
House id city NP1 Napa NP2 Napa YC1 Yucaipa
id city NP3 Napa YC1 Yucaipa
name burglaryrate Napa 0:03 Yucaipa 0:01
unit NP1 YC1 YC2 to estimate the likelihood that a given collection of alarms indicates these alarming events. Consider a database consisting of the following relations: House(h; c) represents houses h and their location cities c, Business(b; c) represents businesses b and their location cities c, City(c; r) represents cities c and their associated burglary rates r, and ObservedAlarm(x) represents units (houses or businesses) x where the alarm went o . These are the EDB relations that are not changed by the program. Figure 1 shows an instance over the schema. Now consider the PPDL program P in Figure 2, where some rules use the Flip distribution in their heads. The rst rule states, intuitively, that for every fact of the form City(c; r), there must be a fact Earthquake(c; y) where y is drawn from the Flip (Bernoulli) distribution with the parameter 0:01. The fourth rule states that a burglary happens in a unit (house or business) with probability r, where r is a number that represents the rate of burglaries in the city of the unit (note that we represent by Burglary(x; c; 1) and Burglary(x; c; 0) the fact that a Burglary did, respectively, did not happen at unit x in city c; likewise for Earthquake and Trig). Finally, c1 is a constraint stating that Alarm and ObservedAlarm have the same tuples.
We now address the semantics of a program. What does it mean for a rule
head like Earthquake(c; Flip[0:01]) to be satis ed ? What if this fact is derived
by multiple, or even equivalent, rules? Do we need to sample more than once?
The probabilistic semantics of the above PPDL program is established via an
extension to Datalog, named Datalog9, where rule heads can have existential
quanti ers. Datalog9 rules (a.k.a. existential rules, which are syntactically
isomorphic to tuple-generating dependencies), have been used extensively in many
areas, including data exchange [
Unit(x; c) ; Earthquake(c; 1)
Burglary(x; c; 1) 7. Alarm(x) Trig(x; 1) 8. Earthquake(c; d) EarthquakeF2lip(c; d; p) 9. Burglary(x; c; b) BurglaryF3lip(x; c; b; p) 10. Trig(x; y) TrigF2lip(x; y; p) program P gives rise to the Datalog9 program Pb in Figure 3. Note that this program does not take into account the constraints. To illustrate the translation, note how rule 6 in P becomes rule 6 in Pb. A special, distributional relation symbol Trig2Flip is created for Trig that captures the intention of the rule: whenever the premise holds (there is a Burglary at a unit x), then there exists a fact Trig2Flip(x; y; 0:9) where y is drawn from a Bernoulli distribution with parameter 0:9. Rule 10 is implicitly added to update Trig with the content of Trig2Flip, where the additional parameter (i.e., the above 0.9) is projected out.
In the absence of constraints, a possible outcome of an input database
instance I (a \possible world") is a minimal super-instance of I that satis es
the rules of the program. One possible outcome of the input instance in
Figure 1 with respect to the rules of P is the database instance formed by the
input instance and the relations in Figure 4. Each tuple of a distributional
relation has a weight, which is the probability of the random choice made for that
fact. For presentation's sake, the sampled values are under the attribute name
draw . Ignoring the constraints (c1 in the example), the probability of this
outcome is the product of all of the numbers in the columns titled \w(f )," that is,
0:01 0:99 0:03 0:4. Note that this multiplication is an instance of the
chain rule Pr(A1 ^ ^ An) = Pr(A1) Pr(A2jA1) : : : , and does not re ect an
assumption of independence among the involved draws. One needs to show that
this formula gives a proper probability space (i.e., the probabilities of all possible
worlds sum up to 1). We do so via an adaptation of the chase procedure [
Constraints, such as c1 in our example, do not trigger generation of tuples, but rather have the semantics of conditional probability: violating possible worlds (where Alarm is di erent from ObservedAlarm) are eliminated, and the probability is normalized across the remaining worlds. Hence, we unify the concept of observations in Bayesian statistics with that of integrity constraints in databases.
In summary, a PPDL program associates to every given input instance a probability distribution over possible outcomes. One can then, for example, ask for the marginal probability of an event such as Burglary(NP1). Standard techniques city Napa Yucaipa
EarthquakeF2lip draw param w(f ) 1 0:01 0:01 0 0:01 0:99
city draw Napa 1 Yucaipa 0
unit NP1 NP2
unit city NP1 Napa NP2 Napa NP3 Napa YU1 Yucaipa from the probabilistic programming literature (analytical, as lifted inference, or sampling-based, as MCMC) can be used to answer such questions. 3
Currently, PPDL semantics supports only discrete numerical distributions (e.g.,
Poisson). But even then, the space of possible outcomes may be uncountable (as
possible outcomes may be in nite). We have de ned a probability measure over
possible outcomes by applying the known concept of cylinder sets to a
probabilistic chase procedure. We have also shown that the resulting semantics is robust
under di erent chases; moreover, we have identi ed conditions guaranteeing that
all possible outcomes are nite (and then the probability space is discrete) [
Acknowledgements We are thankful to Molham Aref, Vince Barany, Todd J. Green and Emir Pasalic Zografoula Vagena for insightful discussions and feedback on this work. We are grateful to Kathleen Fisher and Suresh Jagannathan for including us in DARPA's PPAML initiative; this work came from our e orts to design translations of probabilistic programs into statistical solvers.