CS322 Fall 1997
Assignment 10
Due: 1:30pm, Friday 21 November 1997.
In this question, we will consider using integrity constraints and
consistency-based diagnosis in an infobot.
To answer a question from the web, we need to believe what the
information sources tell us. However information sources are sometimes
wrong. It is useful to be able to automatically determine which
information sources may be wrong when you get conflicting information.
In this question we will consider how integrity constraints and
assumables can be used to determine what errors there are in different
information sources.
In this question, we will use meaningless
symbols such as a,b,c,..., but in a real domain there will be
meaning associated with the symbols, such as a meaning "there is
skiing in Hawaii" and z meaning "there is no
skiing in Hawaii", or a meaning "butterflies don't eat anything"
and z meaning "butterflies eat nectar". We will use the
meaningless symbols in this assignment, because the computer doesn't
have access to the meanings, and must just treat them as meaningless
symbols.
Suppose you have the following information sources, and the
information they are providing to you:
- Source s1:
- Source s1 claims the following clauses are
true:
a <- h.
d <- c.
- Source s2:
- Source s2 claims the following clauses are
true:
e <- d.
f <- k.
z <- g.
j.
- Source s3:
- Source s3 claims the following clause is
true:
h <- d.
- Source s4:
- Source s4 claims the following clauses are
true:
a <- b & e.
b <- c.
- Source s5:
- Source s5 claims the following clause is
true:
g <- f & j.
- Yourself:
- Suppose that you know that the following clauses are
true:
false <- a & z.
c.
k.
Not every source can be believed, as together they produce a
contradiction.
- code the knowledge provided by the users into
cilog using assumables. To use a clause provided by one of the
sources, you need to assume that the source is reliable.
- use the program to find the conflicts about what sources are
reliable.
To find conflicts you can just ask false.
The general idea is to make the reliability of the source assumable.
This code implements this.
Here is a trace:
cilog: ask false.
Answer: false.
Assuming: [reliable(s_1),reliable(s_3),reliable(s_2),reliable(s_5)].
Runtime since last report: 20 ms.
[more,ok,how,help]: more.
Answer: false.
Assuming: [reliable(s_4),reliable(s_1),reliable(s_2),reliable(s_5)].
Runtime since last report: 20 ms.
[more,ok,how,help]: more.
No more answers.
Runtime since last report: 10 ms.
Thus there are two minimal conflicts:
[reliable(s1),reliable(s3),reliable(s2),reliable(s5)] and
[reliable(s4),reliable(s1),reliable(s2),reliable(s5)].
Suppose you would like to assume as few sources as
possible are unreliable.
- Which single sources, if they were unreliable could account for
the contradiction (assuming all other sources were reliable)?
- Which pairs of sources could account for the contradiction
(assuming all other sources were reliable) such that no single one of
them could account for the contradiction?
- Those elements that are in all conflicts can account for the
contradiction. This means that s1, s2 and s5 can account for
the contradiction.
- The only pair of sources that could account for the
contradiction are those obtained by pairing the elements of the two
conflicts that are not in the intersection of the conflicts. This
means that there is one such pair {s3,s4}.
How much time did you spend on each question? Was it reasonable? What
did you learn?