DeepProbLog: Neural Probabilistic Logic Programming

Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, Luc De Raedt

DTAI, KU Leuven (BLG)

Probabilistic reasoning & High representational power

​

• Probabilistic reasoning allows for uncertainty and robustness
• BUT! flexiblity may be a problem
• Differentiable models have high representational power
• BUT! robustness may be a problem

Probabilistic reasoning & High representational power

​

• Probabilistic reasoning allows for uncertainty and robustness
• BUT! flexiblity may be a problem
• Differentiable models have high representational power
• BUT! robustness may be a problem

Why not merge the two?

ProLog

ProLog

Logic programming language, defines:

• variables: {v₁, …, v_l}
• terms: {t₁, …, t_m}, T := c | v | f(u₁, …, u_k)
• atoms: q(t_i, …, t_n)
• clauses: h :- b₁, …, b_i

ProLog tasks: Inference

Is a given clause h :- b₁, …, b_i true?

• bottom-up (from given evidence to target clause)
• top-down (from target clause to given evidence)

​

Two key elements:

• grounding realizing variable assignments
• compilation generation of the inference space

​

Top-down inference: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

|

&

Pro(b)Log

Now with probabilities

ProbLog

Prolog, with probabilities!

• variables: {v₁, …, v_l}
• terms: {t₁, …, t_m}, T := c | v | p::f(u₁, …, u_k)
• atoms: p::q(t_i, …, t_n)
• clauses: p::h :- b₁, …, b_i

ProbLog tasks: Inference

Is a given clause h :- b₁, …, b_i true?

• top-down (from target clause to given evidence)
• Sentential Decision Diagram¹
• inference tree as before, but with attached probabilities

​

​

[1] SDD: A new canonical representation of propositional knowledge bases Darwiche and Marquis, IJCAI 2011

* http://bit.ly/2pO9W6m

Top-down inference: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

|

&

0.2

0.1

0.5

Top-down inference: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

|

&

0.2

0.1

0.5

0.3

Top-down inference: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

|

&

0.2

0.1

0.5

0.3

0.15

(a)Pro(b)Log

Now with semirings

Algebraic ProbLog²

Associate each element in a ProbLog program with a semiring element.

​

[2] An Algebraic Prolog for Reasoning about Possible Worlds�Kimmig et al, AAAI 2011

​

(A, ⊕, ⊗, 0^⊕, 0^⊗)

• A element of the semiring
• ⊕ semiring +
• ⊗ semiring x
• 0^⊕ semiring null element for ⊕
• 0^⊗ semiring null element for ⊗

Gradient semiring

Credit assignment on premises:

• assign error to each premise
• propagate error across the inference model

Gradient => Differentiable!

Gradient semiring: AND

• Cross product between probabilities and gradients
• Require initial gradients

Gradient semiring: OR

• Sum of gradients
• Require initial gradients

Gradient semiring: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

|

&

0.2

0.1

0.5

0.3

0.15

<0, 1.0, 0>

<1.0, 0, 0>

Gradient semiring: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

0.2

0.1

0.5

0.3

0.15

-

-

???

<0, 0, 1.0>

⊕

???

-

⊗

target clause

gradient

probability

<0, 1.0, 0>

<1.0, 0, 0>

Gradient semiring: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

0.2

0.1

0.5

0.3

0.15

-

-

<0.1, 0.2, 0>

<0, 0, 1.0>

⊕

-

target clause

gradient

probability

???

⊗

<0, 1.0, 0>

<1.0, 0, 0>

Gradient semiring: an example

calls(mario)

alarm

hears_alarm(mario)

earthquake

burglary

0.2

0.1

0.5

0.3

0.15

-

-

<0.1, 0.2, 0>

<0, 0, 1.0>

⊕

-

target clause

gradient

probability

⊗

<0.5, 0.5, 0.3>

Neural (differentiable) predicates

Gradient opens the door for differentiable predicates!

Neural predicates on probabilistic differentiable models:

nn(M, x, Y)

• nn family of predicates
• M differentiable probabilistic model
• x input record
• Y output space

Neural (differentiable) predicates

Gradient opens the door for differentiable predicates!

Neural predicates on probabilistic differentiable models:

nn(M, x, Y)

• nn family of predicates
• M differentiable probabilistic model
• x input record
• Y output space

nn(ResNet, , {0, .. 9})

Experiments

Finally no more ProLog

Tasks

• Addition
• ProbLog program implementing addition (1 digit and 2 digit numbers)
• Sort
• bubble sort, neural predicate predicts output of bubble step
• WAP
• {permute, swap, operation}: decide which to take next

Addition

Learn sum of two numbers: ProbLog vs Differentiable model

Sorting

Learn step of bubble sort: DeepProbLog vs Differentiable Forth

Take-home messages

• Learning with data + probabilistic logic programming shows�promising results
• faster convergence
• comparable results
• Differentiable logic is a thing
• hints at learning probabilities of given clauses