Tuesday, October 23, 2007

Entailment status and learning

Here is something that came up at the review session today that is probably bears repeating to a wider audience.

Consider an agent which has a current knowledge base KB, and you are trying to "tell" it another fact f

We can distinguish between three types of entailment status between KB and f:

1. KB |= f  [the agent is being told what it already implicitly knows]

2. KB |= ~f  [the agent is being told the opposite of what it already implicitly knows]

3. Neither 1 nor 2. [The agent is being told something "completely new" ]

Let us ask the question---in which of these cases can you say that the agent "learned" something?

In case 3 ( i.e., the KB neither entails f nor entails ~f), it is easy to see that f is truly new knowledge being added to the agent.
So, learning clearly occurs here. This is called "knowledge level learning".

In case 2, KB already entails ~f. Now the agent is being told f is true. If it goes ahead and adds f, then it will have an inconsistent
KB. To resolve the inconsistency, either the agent should refuse to believe f, or "lobotomize"  itself so that it can no longer prove ~f.
To do the latter, the agent needs to consider all ways of proving ~f and for each of those proofs, remove at least one axiom taking part in the
proof (so that that proof doesn't go through). Thus, in this case, the agent "learns" what part of its existing knowledge base is faulty and should
be thrown out-- (this is called "theory revision"). It is obvious that we do it ourselves..

In case 1, f is already entailed by the KB, so in a sense there is no learning taking place (the agent is being told what it already knows). However,
if checking the entaiment of f takes a long time, then remembeing the proved theorem can improve the agent's performance (in as much as it can
stop it from having to do this computation again). This is a form of "speedup learning" (and the "factor tables" that are computed and stored by the variable
elimination algorithm we just talked in the class is a form of speedup learning).


ps: If you are wondering "By what stretch of imagination can this stuff be construed as 'review', I offer you the following quote from Northern Exposure
      (for those of you old enough to have seen the show ;-)

  "My student came to me with a desire to know the time, and
    I taught her how to make a watch"
                                -Chris in the morning..

No comments: