Belief revision in Prolog

Given a whole bunch of Prolog clauses and facts – some of which contradict each other – I’m trying to work out a way of pruning the database to the maximal set of facts and clauses which are mutually compatible. This seems to go under the moniker “Belief Revision”.

I’d be grateful if you could point me toward some code written in Prolog to this end? I’ve found considerable theoretical work, but no Prolog code so far.

3 Likes

@emiruz Do you perhaps have an example set of clauses and facts? I am curious what is meant by contradictory in this case. To illustrate my point, if we have the following facts:

fruit(tomato) :- true. 
fruit(tomato) :- false.

?- fruit(tomato).
true ;
false.

These facts clearly contradict one another, but Prolog accepts them. To Prolog, this merely shows that one path exists proving fruit(tomato) is true. Would you want to remove the fact that implies false?

I fear we should interpret this a bit differently. A Prolog clause says “Body implies Head”. Multiple clauses are a disjunction, so this says (I think)

true implies fruit(tomato) OR false implies fruit(tomato).

Note that “false implies …” does not mean … is false. It is a logically irrelevant statement.

Back to the OP, Prolog does not allow for expressing something is false (classical negation). It only provides Negation as Failure, i.e., cannot prove, but might of course be true if we get new information. I don’t think a Prolog program can be inconsistent in the logical meaning. For that you need ASP or its Prolog embedded s(CASP). Here you can state something is false:

fruit(tomato).
-fruit(tomato).

See https://swish.swi-prolog.org/p/CPoRsEQH.swinb. In the notebook you can play around and verify yourself that introducing this contradiction makes everything related false.

3 Likes

If you try s(CASP) be careful to note the need for ? at the start of a query, which is not the same as the Prolog top level prompt, ?-. Forgetting to add that has bit many of us and caused much frustration.

Since I saw you had a GitHub repository regarding PubMed you might find this of value.

s(CASP) biological example

1 Like

I find it very useful to use constraints (clpr) to reason about truth or falsity. Here is an example that shows a theory with an internal contradiction

but the code does not prune away any incoherent clauses…

1 Like

Thank you – that helps. I’ll look at s(CASP). A short rejoinder:

  1. Is it possible to mimic negation using constraint handling rules by using not_f(X) as a negation of f(X) and having a rule like f(X), not_f(X) ==> fail. ? EDIT: No. I’ll answer my own question :slight_smile: Failing and negation are fundamentally different concepts. For some reason when learning this for the first time, they are very easy to blur.

  2. Is there some way that I could use constraint handling rules to “work around” contradictions? I.e. somehow give it enough degrees of freedom so that it can add constraints which make contradictions go away, and then see how it achieved it?

I’m trying to codify a map where locations have facts about them and points of interest (POI). I’m trying to get the knowledge store to a point where I can get Prolog to abduce a bunch of location agnostic defaults – things that tend to be – but are not necessarily – the case everywhere. A default could be something like “bike crime is high if there is a bike parking at the location and no police station at the location”.

In the real data, things like lower bike crime in places that have both a police station and a bike parking may be true in the main, but sometimes they are false. I want some way of eliminating all the contradicting information that preserves as much information as possible so that I can then try to abduce defaults from what remains. – At least that is the idea.

I’ve done something like this by statistical means which is my bread and butter – but I’m trying to understand what I can do with Prolog in this regard. I see a way with MIP programming or MaxSAT, but I’m a bit stuck on how to proceed – or even if its possible – with Prolog.

The only guess I can think to offer while trying to stay in the land of Prolog is to take a look at constraint handling rules (CHR).

Also Tips for CHR Programming might give some insight to CHR.

I have never used these yet but it has not been mentioned.

Yeah I had landed on that too (one of my questions above was on this topic), but I suspect it won’t be possible because contradictions could be complex and therefore there is nothing to rewrite to make them go away.

I found some algos for belief revision in terms of ASP: https://sat.inesc-id.pt/~mikolas/rcra17_asp.pdf

It seems they are originally from propositional logic, so I suspect they may be portable to Prolog.

Maybe you would find cplint interesting
http://cplint.ml.unife.it

You can use it to induce probabilistic clauses from examples. E.g. from data such as

lowCrime(place1)
policeStation(place2).
close(place1, place2).
notbikeParking(place3).
close(place1, place3).

lowCrime(place4).
policeStation(place5).
close(place4, place5).
notbikeParking(place6).
close(place4, place6).
...

You could get for example

0.7:: lowCrime(A):- 
   policeStation(B), 
   close(A, B),
   notbikeParking(C),
   close(C, A)

Read “Head is true with probability 0.7 if body is true”.

I think that its a solid suggestion but it is too similar to my existing paradigm. I.e. one could generate a CART4.5 decision tree using a feature matrix where each column is a predicate, and then selectively encode the branches of the generated tree as a Problog/Prolog programme. One could then use Prolog/Problog to reason further about the map. However, in reality at that point Prolog is consigned to just being a query interface.

I suppose the prospect I was after is getting to the final state by a formal reasoning system rather than my usual toolbox. I’m looking into CLASP – it looks like it has more capabilities in that direction.