Renata Wassermann on Belief Revision in DLs

I used some of Renata’s work in my thesis and we’ve corresponded on and off. One of her students is visiting us and she came and gave a talk! It was very nice.

One interesting bit was that did some experiments on partial meet vs kernel based revision and found “contrary to computer science intuition” partial meet generally is more efficient. Ok that’s a lot of jargon here’s an attempt to sort it succinctly.

Given a set of beliefs, B, (think propositional sentence ie things which can be true or false), and some sentence S which follows from B, how can we shrink B so S no longer follows? This isn’t easy! S may not be a member of B. S might be entailed by lots of different parts of B.

One approach is to find all the minimal subsets of B which entail S. Since they are minimal, we can break the entailment by deleting just one element. If we fix each subset then we have a fix for B. These subsets are called kernels (or justifications). They correspond nicely to typical debugging approaches.

Alternatively, we could try to build a maximal subset of B which doesn’t entail S. There will be many such subsets but obviously each does the job. Call such a set a remainder. We can just pick one remainder, or take the intersection of several (or all). If we take fewer than all we have partial meet contraction.

Now Renata said something that didn’t make sense to me ie that the reason kernal contraction has been preferred is that computer scientists think it’s more efficient because “kernels are smaller”. But…I’ve never heard that. The concepts are dual but kernels are easier for humans to deal will. They capture the logic of how the undesired entailment works. It never occurred to me to even ask which approach is more efficient. It depends on the nature of the sets!

One interesting bit is that a difference between debugging and revision folks is that debugging folks usually consider minimal repairs, ie, selections from the set of justifications that contain no repairs. This corresponds to full meet contraction which has a number of issues. If you go for partial meet then you have to do a bit of work to get an algorithm that finds desirable contractions compared to the remainder based approach.

Of course, even from a debugging perspective a partial meet approach might make sense. When you figure out a bug, you might make more changes than just the minimum one to fix the focus broken test. After all, you might get an insight about a particular function call and change how you call it everywhere. You might realise that a module is just irredeemably broken and replace it entirely.