AI: Partial Unification in Open-World Reference Re

Question

When performing reference resolution on predicates describing the semantics of dialogue expressions, I need to be able to allow for partial unification due to working in an open world.

For example, consider the following scenario:

There is a blue box in front of you. We refer to this blue box using the id 3.

A set of predicates box(x)^blue(x) can easily resolve to the blue box you know about. Making this query will return 3

A set of predicates ball(x)^yellow(x) will not resolve to anything. This is fine.

But now consider ball(x)^yellow(x)^box(y)^blue(y)^behind(x,y) that is, the yellow ball behind the blue box.

We don't know about a yellow ball, but we do know about a blue box! Of course it's possible that there's no ball behind the known box and that another box was being spoken of. But we're pretty sure we know what box is being talked about.

I am working within a probabilistic framework in which I calculate the probability of each set of bindings satisfying the set of propositions; the reference resolution process then returns the most likely unifier/set of bindings. Unfortunately, when considering behind(x,y), my system wipes out the probability of 3 being bound to y because it does not know of any yellow balls behind the box with id 3.

Is there a way to do partial unification of predicates, so that the system determines that the most likely resolution of the statement is y/3 x/? i.e. y is bound to 3 and the identity of x is unknown?

Answer 1

A tentative solution (if anyone thinks of something better... please say so!)

When parsing a sentence, the parser may be able to establish that certain entities are more likely to be grounded than others. In this sentence, the box is more likely to be grounded than the ball. In the sentence fragment the brother of the king's gardener, the brother is least likely known, the gardener is more likely, and the king is the most likely.

If this information is reflected in the semantics or provided alongside them, they can inform a heuristic which can, in the face of an unresolved referential expression, try assuming references unknown in the provided order until the reference is successfully resolvable.

Answer 2

It seems to me the issue is not so much about partial unification of predicates. That is a regular part of unification, since we unify variables, not predicates, and predicates may involve multiple variables in which only some are unified.

The issue seems to be much more about open-world, as you pointed out, since the lack of knowledge about a yellow ball does not mean there are none.

Besides the references I already gave you in your other question Constraint Satisfaction with Uncertainty

for this particular problem you might want to look at these papers, which deal specifically with these very issues:

David Poole, First-order Probabilistic Inference: http://www.cs.ubc.ca/~poole/talks/ijcai-2011-tutorial/poole-liftedVE.pdf

de Salvo Braz et al, Lifted First-Order Probabilistic Inference http://reason.cs.uiuc.edu/eyal/papers/fopl-res-ijcai05.pdf