Semantics of AD?

[xiaobanni]

Thank you for your valuable contribution. I am a newbie in this area and have been using your materials to study ProbLog.

I tried the online inference provided at https://dtai.cs.kuleuven.be/problog/editor.html and entered the following code:

0.8 :: obstc(front).
0.2 :: obstc(left).
0.5 :: obstc(right).

0.9 :: crash :- obstc(front), act(accel).
0.4 :: crash :- obstc(left), act(left).
0.4 :: crash :- obstc(right), act(right).

0.1 :: act(nothing).
0.5 :: act(accel).
0.1 :: act(brake).
0.1 :: act(left).
0.2 :: act(right).

query(crash).

While the expected answer is 0.41, the program returned 0.39. Is there some misunderstanding on my part?

Thank you in advance.

[xiaobanni]

Ok, I've identified the key issue: we should use ";" instead of "." for Annotated Disjunctions.

However, this leads to a new question for me. What is the difference in the calculation logic of these two symbols? They appear to have the same calculation logic to me. I've constructed a more concise example for clearer explanation:

In the first scenario:

0.2 :: obstc(left).
0.5 :: obstc(right).
0.4 :: crash :- obstc(left), act(left).
0.4 :: crash :- obstc(right), act(right).
0.4 :: act(left).
0.6 :: act(right).
query(crash).

The result for the crash query is 0.14816.

In the second scenario:

0.2 :: obstc(left).
0.5 :: obstc(right).
0.4 :: crash :- obstc(left), act(left).
0.4 :: crash :- obstc(right), act(right).
0.4 :: act(left);
0.6 :: act(right).
query(crash).

The result for the crash query is 0.152.

What causes the difference in these results? Any materials for further study on this topic would be greatly appreciated. Thanks in advance.

[VincentDerk]

Annotated disjunctions have the semantics of mutual exclusivity.

This becomes apparent when you compare the results of

0.4 :: act(left); 0.6 :: act(right).
ex1 :- act(left), act(right).
ex2 :- act(left), not(act(right)).
ex3 :- not(act(left)), act(right).
ex4 :- not(act(left)), not(act(right)).

query(ex1).
query(ex2).
query(ex3).
query(ex4).

versus

0.4 :: act(left).
0.6 :: act(right).
ex1 :- act(left), act(right).
ex2 :- act(left), not(act(right)).
ex3 :- not(act(left)), act(right).
ex4 :- not(act(left)), not(act(right)).

query(ex1).
query(ex2).
query(ex3).
query(ex4).

Intuitively, you could say 0.4 :: a; 0.6 :: b. turns into a. with 0.4 probability, and turns into b. with 0.6 probability. Consequently, unless there is another rule that makes a or b true, a and b can never be true at the same time. This is in contrast with 0.4::a. 0.6::b. where both can be true.

To clarify the prior "unless" statement.

0.4 :: a; 0.6 :: b.
a :- ...

would allow both a and b to be true, in case b is made true due to the first line and a becomes true due to the second line.

[xiaobanni]

Thank you for your explanation. I will use the shortest example to thoroughly understand the previous question.

0.2 :: act(left);
0.7 :: act(right).
crash :- act(left).
crash :- act(right).
query(crash).

and

0.2 :: act(left).
0.7 :: act(right).
crash :- act(left).
crash :- act(right).
query(crash).

But after the sentence 'Consequently, unless there is another rule that makes a or b true…', do you mean that a subsequent code line can override the preceding one? In Problog, the sequence of lines is crucial. When we execute the first line, the probability of b being true is 0.6. However, a can also be made true by the rule's body, as shown in the following code:

0.4 :: a; 0.6 :: b.
a :- true.

query(a).
query(b).

[VincentDerk]

It is not a matter of overriding. I will elaborate.

First, it is important to note that 0.5::a. on itself does not state that a is true with probability 0.5. Semantically it states that with 0.5 probability a may be added to the program as a fact. There is a difference between the two statements when a can also become true due to another reason (e.g., when it also occurs in the head of a rule, or if you have the same probabilistic fact twice).

It takes longer to explain the semantics then, so often in papers we require the atom (e.g. a) of every probabilistic fact to be unique and to not occur as the head of any rule. When that is the case, then 0.5::a. basically boils down to saying that the probability of a is 0.5. In practice, ProbLog does however allow the atom of a probabilistic fact to also be used in the head of rule. The semantics in this case are better understood by imagining that the probabilistic fact will be rewritten such that the atom of each probabilistic fact is indeed unique. For example,

0.5::something.
0.4::a.
a :- something.

turns into

0.5::something.
0.4::causes_a.
a :- causes_a.
a :- something.

Returning to the annotated disjunction:

0.5::something.
0.4::a ; 0.6::b.
a :- something.

turns into

0.5::something.
0.4::causes_a ; 0.6::causes_b.
a :- causes_a.
b :- causes_b.
a :- something.

such that no atom appears as both a probabilistic fact and as the head of rule. Repeating my explanation of an AD, causes_a and causes_b appear together in an AD so with probability 0.4 this is equivalent to a rule that says causes_a. and with 0.6 probability it turns into causes_b. Therefor, causes_a and causes_b can never be true at the same time.

This same explanation can be used to understand why

0.4::a.
0.7::a.
query(a).

returns 0.4 + (1-0.4)*0.7 because it turns into

0.4::cause(1).
0.7::cause(2).
a :- cause(1).
a :- cause(2).
```.

[VincentDerk]

It is not a matter of overriding. I will elaborate.

First, it is important to note that 0.5::a. on itself does not state that a is true with probability 0.5. Semantically it states that with 0.5 probability a may be added to the program as a fact. There is a difference between the two statements when a can also become true due to another reason (e.g., when it also occurs in the head of a rule, or if you have the same probabilistic fact twice).

Not to confuse, but perhaps to be complete in case anyone else reads this, I should add there is another scenario where the probability of a being true is not 0.5, despite there being a statement 0.5::a.. Namely, when allowing negation in the head, the negation rule does override any other reason that could make a true. You could say a becomes true iff there is any cause for it become true AND no cause for it to not be true.

For example, in the program below you have 0.5::a. but the probability of a is 0.375 because when b is true, a becomes false.

0.5::a.
0.25::b.
\+a :- b.
query(a).

[xiaobanni]

Thanks for the elaborate and thorough explanation; it is such valuable learning material.