Re: Nonmonotonic rules

>  > >Pat,
>>  >
>>  >This is a powerful statement, but I would like to see it backed up with
>>  >examples of purely monotonic rules that are worth publishing.
>>
>>  I would like to see an example of a nonmonotonic
>>  rule that is worth publishing.
>
>Notice that you are passing the buck and are refusing to back up your
>statements.

Well, true. But almost any implication would be 
an example of a monotonic rule, and such 
implications are ubiquitous. (True, many of them 
can be mapped directly into DL without using 
rules...) If its a penguin, it doesn't fly: 
that's monotonic.  If its a time-interval, its 
endpoint is later than its startpoint... choose 
your favorite implication.

>  > I'll offer you a
>>  challenge: show me a nonmonotonic rule, and I'll
>>  undertake to send you back a case where it would
>>  immediately produce a false answer.
>
>"Birds normally fly"
>"Sick birds normally don't"
>"Penguins don't fly"

1. Im working in a center that rescues and tries 
to fix and re-release damaged or injured 
endangered birds. Birds here normally don't fly.

2. Im a specialist in diseases of raptors arising 
from acid rain pollution, which causes 
infertility, taking part in a study involving 
tagging wild birds and checking their nests. 
Many, maybe all, of the birds we track are sick, 
but they all fly.

BTW, there is a terminological issue arising 
here.  In at least one reading, rules like this 
which are explicit about "normally" can be viewed 
as monotonic.  And the last example is monotonic 
on any reading (since it omits the "normally").

>...
>
>I think I know what your counter-case would be, but how would you express
>this kind of stuff monotonically? You would need a bunch of exceptions and
>every time you add another exception you would change some of your previous
>formulas.

No, there are many other alternatives.  You don't 
need to have an explicit list of exceptions, all 
that is required is that there is a reference to 
some proposition which 'stands for' the 
exceptions (or more exactly, the truth of any 
exceptional condition.) You could use for example 
McCarthy's circumscription technique, and 
transcribe them as 'normal birds fly', etc.., 
from which it then follows monotonically that a 
non-flying bird (such as a sick bird or penguin) 
is not a normal bird.  The pattern is more like:

foo is a normal bird
normal birds fly
->
foo flies

normal birds fly
not (foo  flies)
-> (modus tollens)
not (foo is a normal bird)

both of which are monotonic inferences. The nonmonotonic step then would be

foo is a bird
-?->
foo is a normal bird

And if you want to make an circumscription-style 
assumption that all your birds are normal (unless 
you have been told otherwise) then by all means 
go ahead: I don't want to prevent anyone DOING 
nonmonotonic inference in the privacy of their 
own inference engine. My point is only that the 
semantics underlying SWeb communication, the 
semantics built into the information exchange 
protocols, needs to be monotonic. As long as you 
have some explicit way to encode that 'normally' 
part of your rules, and so distinguish 'birds 
normally fly' from 'birds fly', then we have no 
disagreement. That is exactly what I want to do 
as well.

All that said, however, there is a real practical 
problem with 'normally' reasoning and 
circumscription, which is how to evaluate what 
happens when different notions of 'normal' (or 
'typical') clash. This is of course an old 
observation (interacting defaults, for example) 
but its being old doesn't make it go away.  And 
on the Web, the possibilities for communication 
breakdown are amplified. Birds normally fly most 
of the time, but if we are talking about birds in 
the Antarctic then its not so clear what counts 
as 'normal', etc.. Fact is, "normal" is kind of 
context-dependent in its meaning. It would be a 
lot safer, and more informative, if such a rule 
could mention explicitly an intended class  of 
birds, and say that normally *in that class*, 
birds fly; and then a reader (particularly a 
reader as dirt-stupid as your average SW agent) 
can be alerted to the dangers of applying it to a 
small subclass, or a different class altogether. 
It would be more informative and safer still if 
it could give actual statistics, like "over 95% 
of birds in the class fly".

If I may hazard an ad-hominem guess here for a 
second, I suspect that your use of the 
(Sweb-agent= human) analogy might be distorting 
your intuition. People like us are not 
consciously aware of using rules like "over 95% 
of birds in this class fly", and we certainly 
don't say things like that to one another. But 
(a) what people do is kind of irrelevant, and (b) 
it really is not clear what actually is going on 
inside people's heads when they reason: and (c) 
for sure, what is actually going on is a lot more 
complicated than what it 'feels' like to the 
thinker, or what people say to one another. We 
certainly don't think using natural language, and 
there is lots of evidence that we unconsciously 
do things like make fine-grained numerical 
estimates of relative likelihoods which we are 
quite unable to sense by introspection; and that 
when we do reason, we are using far, far more 
information than we are consciously aware of, or 
ever actually say explicitly to one another in 
natural language.

>This is not compositional. Furthermore, your monotonic rules are much less
>useful to me than the above non-monotonic ones.
>
>Note that the non-mon rules will give correct answer most of the time -- just
>like humans. Do you have a set of monotonic rules that gives a correct
>answer *all* the time?
>If I understand correctly what you have in mind, then your system will be
>giving the answer "I don't know" most of the time. In my view this is not
>as useful as giving a correct answer most of the time.

The system I prefer will be giving answers of the 
general form "assuming everything is normal, foo 
flies"  or maybe "assuming foo is a normal bird, 
..." where of course the qualification, being 
generic, could be understood or implicit in a 
real QA protocol (though it should be explicit 
for the reasoners under the hood.) And I would 
prefer it to have a more structured account of 
"normal", if at all possible.

>  > >The brittleness argument against non-monotonic reasoning is a red
>>  >herring.
>>
>>  I fundamentally disagree. It is absolutely central to the SWeb.
>
>Where is a proof of this statement?  I would consider believing this if
>you produce a useful and non-trivial example to back this up.
>The onus is on you, since you are the one making the sweeping statements :-)

Well, the point seems to be widely accepted, but 
it also seems kind of obvious. It has to do with 
publishing content on the Web. If A publishes X 
which is later read by B, and B has no access to 
any of the context that A is assuming, then the 
semantic protocols defining the information that 
is conveyed from A to B by X have to assume that 
this information is independent of the context. 
Since A cannot, by the very nature of the WWW 
architecture, possibly know what other 
information may be available to B and combined 
with X to draw conclusions, the meaning of X has 
to be monotonic.

>  > >People use non-monotonic reasoning in their daily life because it
>>  >is useful most of the time. I see no reason why Semantic Web should be
>>  >different.
>>
>>  I see many reasons.  Daily life is irrelevant
>>  (with that argument, we ought to have our SW
>>  agents talking in English): the point in what you
>>  say is that PEOPLE use these reasoning patterns.
>>  Sure, people do: people are a lot smarter than SW
>>  inference engines are likely to get; and people
>>  have access to exactly the relevant contextual
>>  background assumptions that the SW *formalisms*
>>  do not provide. You and I both know that SS
>>  numbers are unique identifiers and that lists of
>>  local cinemas are likely to be closed worlds for
>>  checking movie times, and so on (and on).  Put
>>  yourself in an alien cultural context where you
>>  don't know things like this, and you will
>>  probably behave very differently, or make
>>  terrible gaffes in your reasoning, or maybe both.
>>  If all this contextual information were to be
>>  made explicit, things like
>>  unique-name/closed-world reasoning would be
>>  monotonic.
>>
>>  In fact, I think that people almost never use
>>  true nonmonotonic reasoning. We use shortcuts,
>>  for sure (check out the 'recognition heuristic'):
>  > but we they find they are wrong, we acknowledge
>>  that they were wrong and change our minds;
>>  moreover, there are lots of well-documented
>>  effects in cognitive psychology which seem to
>>  show that even unconsciously, we are very
>>  sensitive to logical inconsistencies, eg the many
>>  varieties of 'cognitive dissonance'. That is
>>  fundamentally monotonic reasoning.  A true nonmon
>>  reasoner wouldn't even notice that it had a
>>  contradiction to resolve, and it wouldn't need to
>>  change its mind. We say: tweety is a bird, so
>>  tweety can fly. Oh, wait, tweety is a penguin: I
>>  was wrong, tweety can't fly. It would say: Tweety
>>  is a bird, tweety can fly, tweety is a penguin,
>>  now tweety can't fly.... so? (This is an aside.
>>  The main point is that people are a hell of a lot
>  > smarter than anyone knows how to automate, so
>>  what people do is irrelevant; and in any case, we
>>  don't really know what people do.)
>
>I don't know how to respond to these two paragraphs of belle letters.
>There is nothing concrete to argue with. You are assuming (or claiming?) that
>all contextual information can be made explicit

I was reacting to your argument to the effect 
that people do it, so the SW can do it.  You 
brought human performance into the discussion: if 
you think that empirical results in cognitive 
psychology constitute 'belles lettres' then maybe 
you should stick to topics you know something 
about.

>, and this is not my
>experience at all.
>
>In another recent message, you said:
>
>X-sender: phayes@mail.coginst.uwf.edu
>Message-id: <p06001f0bbc2cc3cb147d@[10.0.100.76]>
>>  Being able to use closed-world
>>  reasoning, unique-name reasoning, default reasoning, etc., in
>>  situations where you know they are OK to use, provides great
>>  benefits. What we need are ways to be able to take advantage of the
>>  computational merits of such efficient reasoning processes, but
>>  within a globally monotonic system of information exchange.
>
>So, you are acknowledging that certain forms of non-monotonic reasoning
>are useful and you want to adopt them. Pardon if I misunderstood.

There are patterns of reasoning that are useful. 
They are conventionally called nonmonotonic. In 
many cases (closed world, unique name) they are 
not intrinsically nonmonotonic. I want to find 
ways of making them useable in an overall 
monotonic framework.  Defaults are a rather 
tougher case, I will concede.

>  > >While I haven't seen any convincing examples of monotonic rules that would
>>  >cause me to want to send my agent and scoop them up, I do see reasons why I
>>  >might want to have non-monotonic knowledge to be published. This is
>>  >because most (if not all) rule-based applications that I've looked at use
>>  >some kind of non-monotonicity.
>>
>>  They use forms of reasoning that are
>>  conventionally thought of as nonmonotonic,
>>  because they rely on information that is
>>  conventionally not made explicit. If you do make
>>  it explicit, they are often monotonic.  What I am
>>  arguing is not to throw away or banish these
>>  useful reasoning patterns, but to find a way to
>>  incorporate them into a globally monotonic
>>  framework of information interchange.
>>
>>  Are you sure that they really USE
>>  nonmonotonicity? That is, they RELY on the fact
>>  that the reasoning pattern is indeed not
>>  monotonic, and would break if it were made
>>  monotonic?  (An example might be a system that
>>  did closed-world reasoning but treated its
>>  conclusions as defaults, so that when new items
>>  were added to the world the old conclusions would
>>  be overridden. Now, that might be plausibly
>>  argued to be USING nonmonotonicity, rather than
>>  just kind of accidentally happening to be
>>  nonmonotonic.)
>
>This is too subtle for me. What is the difference between "using"
>non-monotonic reasoning and "being" non-monotonic?

The point I am apparently not getting across is 
that many of these inference techniques are NOT 
inherently non-monotonic. Closed world reasoning 
, for example, is only non-monotonic when you 
refuse to identify the closure of the world as 
part of the hypothesis; similarly for 
negation-as-failure. It is one thing to say that 
these inference types are useful and should be 
supported: they are, and should. It does not 
however follow from this that SW inference must 
be nonmonotonic.

Even your examples would be fine with me as long 
as the rules do indeed somehow formally state the 
'normally' assumption. If I publish the claim 
that normally, birds fly, and you make an 
inference from that about a particular bird, then 
it is you who has made the assumption of 
normality.  This is not the same situation as me 
publishing the (unqualified) claim that birds 
fly, and then expecting, because Web logic is 
inherently nonmonotonic, that you will be able to 
understand that when I say birds fly, I don't 
actually mean that birds  fly.

Here's a way to understand the distinction 
operationally: A publishes the rule (birds fly), 
B reads and applies it to some case (bird foo), 
and the answer turns out to be wrong (foo doesnt 
fly).  What went wrong? The 'globally 
nonmonotonic logic' answer is: nothing is wrong. 
The answer I prefer is, if A said that birds fly, 
then A is wrong. If on the other hand A said, 
(normally, birds fly), then B made an assumption 
about foo (that it was normal) that turned out to 
be wrong.  The answer I want to avoid is, A didnt 
really mean what he seemed to mean, or that what 
A meant was somehow context-dependent in some 
invisible way. I want it to be possible for B's 
understanding of the content of A's rule to be 
unambiguous and independent of any context that A 
might be assuming.

>What I can say is that
>I haven't seen a rule-based system worth its salt, which is not using some
>sort of negation as failure somewhere.

Well, Im not sure what you consider to be a 
'rule-based system' but if 'rule' includes Horn 
clauses, then there are plenty of examples.

>Does it mean "using" rather than "being"? I am ok with that.
>Then what is the argument about?
>
>
>>  >If anything, I'd like them to be published
>>  >so I could steal them :-)
>>  >
>>  >Seriously, though, suppose there is a service, say, a travel reservation
>>  >service that specializes in multi-segment complex travel arrangements.
>>  >Of necessity, such a service is going to use a form of closed-world
>>  >assumption, since it will be looking only at a small subset of all
>>  >available resources and make its recommendations based on that incomplete
>>  >knowledge.
>>
>>  It will base its conclusion on what it knows, to
>>  be sure. That doesnt make it inherently
>>  closed-world reasoning.  Closed-world reasoning
>>  means that from a failure to find some atomic
>>  sentence, you *conclude* that it is *false*. You
>>  can make a recommendation based on what you know
>>  without drawing that conclusion.
>
>If the system makes inferences based on the fact that it failed to prove
>the contrary, then you are using closed-world reasoning.

Sure. I have no quarrel with closed-world 
reasoning; I just don't want to get it muddled up 
with open-world reasoning.  Closed world 
reasoning is monotonic provided you refer to the 
closed world as a suitable antecedent. I look up 
'Joe' in a DB called employees and don't find him 
there; AND I know the DB has all the employees in 
it. Joe's not being an employee is a monotonic, 
deductive consequence of all that. If you know 
explicitly that the list of facts you are 
searching through is complete, then NAF is 
logically valid. It only seems non-monotonic if 
you forget to mention the fact that the database 
is complete.  There is nothing inherently 
nonmonotonic about closed-world reasoning or 
unique-name reasoning or NAF.

>You are simply refusing to call a spade a spade.

I want to keep the spades distinct from the forks.

>  > >If it can't find a car rental somewhere, it will assume there
>>  >isn't one and will try to find the next best alternative.
>>
>>  No. It will assume that it can't rent a car and
>>  move on to the next alternative. That's not
>>  nonmonotonic: that's just being usefully
>>  pragmatic. If it published a conclusion that
>>  there were no rental cars (not that it couldnt
>>  find any - that is just flat true - but that
>>  there really were none), or if it drew a
>  > conclusion about some other matter from this
>>  assumption, then it would be nonmonotonic.  In
>>  practice if it is reporting directly to humans in
>>  a web-service context then the difference between
>  > "there are none" and "I know of none" is likely
>>  to not matter much since the human will treat the
>>  former as though it meant the latter: but it
>>  might make a lot of difference in, say, a
>>  homeland security application, or in a reasoner
>>  which is deciding agent security policy questions.
>
>If it can't find a car, it would recommend me to use hotel A.
>If the set of premises changes and some car shows up in the database then
>it would recommend hotel B and not A. This is non-monotonic.

If the conclusion has the form: given what I 
know, I recommend A, then it can be monotonic. 
Make the (changing) assumptions explicit, or even 
just provide an indexing device - a name for the 
assumption-set -  and it is, or can be, 
monotonic. It also would follow monotonically 
that when the advice changed, the assumptions on 
which is was based must have changed. (Obviously 
this is over-simplified: in real cases you might 
just have done more inference, and the inputs 
might have had conflicting requirements which 
were resolved differently, whatever. In fact in 
REALLY real cases, the advice given probably 
isn't a logical consequence of anything at all, 
monotonic or otherwise, as Drew likes to point 
out.)

>  > >Why would I want to have some specification of such a service published?
>>  >Because I might be able to reason about how the service works. This service
>>  >may require multiple interactions and my credit card may be charged several
>>  >times. I might determine, for example, that the service won't charge my
>>  >card unless there is a way to back out of the corresponding part of the
>>  >deal or there is travel insurance provided, or ....
>>
>>  OK to all that. But notice that is all META
>>  information about the service. You can
>>  monotonically express meta-information about
>>  anything, even C++ code.  That has nothing to do
>>  with the non-monotonicity of the rules used in
>>  the system itself.
>
>I was giving an example where it is useful to publish non-monotonic rules.
>You are saying is that in this example I am reasoning not "with" those
>rules, but rather "about" those rules.  Fair enough.
>
>Let's say I invoke this service as a query to find out something.
>Querying is reasoning, and if those rules use a form of negation
>as failure (which will be the case in most complex systems) then
>it would be an example of reasoning with published non-mon rules.
>

If I follow you here, you are saying that if the 
rules are nonmon, then the rules are nonmon. Hard 
to argue with that, but what is the point being 
made, exactly?

Pat

>	--michael 
>
>
>>  BTW, to do this kind of reasoning about any
>>  nontrivial system (monotonic or otherwise) is
>>  going to involve you in some heavy-duty
>>  reasoning.  To make your case here more strongly,
>>  you might try arguing that *that* reasoning has
>>  to be done non-monotonically.  I'd be interested
>>  to see any arguments made along those lines.
>>
>>  Pat
>>
>>  >
>>  >
>>  >	--michael 
>>  >
>>  >
>>  >pat hayes <phayes@ihmc.us> writes:
>>  >>
>>  >>  Re. the (forever ongoing and interminable) debate about the merits of
>>  >>  otherwise of nonmon reasoning.
>>  >>
>>  >>  Bottom line: nonmon reasoning is brittle (by definition) but can be
>>  >>  very efficient. So when you know it won't break, by all means use it.
>>  >>  But it seems to me that it is up to its proponents to justify or
>>  >>  explain how we can have nonmon formalisms being used in a Webbish
>>  >>  context, where the brittleness (or if you prefer,
>>  >>  context-sensitivity) seems on the face of it to be an unsurmountable
>>  >>  barrier to deployment, since there is no way for a reader of some
>>  >>  nonmon rules to know what the intended context is; and when used out
>>  >>  of context, nonmon rules are almost always wrong, and can produce
>>  >>  potentially dangerous errors. (Note, this is only referring to the
>>  >>  *publication* of nonmon rules on a Web, not to their *use* in some
>>  >>  application where it is known they are appropriate, or one is willing
>>  >>  to take the risk of using them in any case.)
>>  >>
>>  >>  So far, the only response Ive heard on this point is a kind of
>>  >>  blustery denial: a claim that the Sweb just isn't going to be like
>  > >>  the WWWeb, but more like an intranet, where all the users will just
>>  >>  know, or will be told by the owner, or will agree among themselves in
>>  >>  managers' meetings, which worlds are closed and which namespaces
>>  >>  satisfy the unique-names assumption and so on; so the problem will be
>>  >>  avoided by what might be called Web-external contextual agreements. I
>>  >>  refuse to take this answer seriously: it seems to me to just be a
>>  >>  statement to the effect that one is not working on the semantic web
>>  >  > at all.
>>  >>
>>  >>  Anyone got any other answers? Until someone has, I would suggest that
>  > >>  all talk about nonmon systems be ruled out of order.  Its not enough
>>  >>  to observe in a general kind of way that nonmon systems are useful
>>  >>  (no argument) or that they are in widespread use and all the best
>>  >>  companies have them and they make a lot of money (irrelevant) or that
>>  >>  they solve this or that famous problem (they usually don't, in any
>>  >>  case). There is a basic technical issue that needs to be addressed.
>>  >>  Address it, or else please shut up about them.
>>  >>
>>  >>  Pat
>>  >>
>>  >>  --
>>  >>  ---------------------------------------------------------------------
>>  >>  IHMC	(850)434 8903 or (650)494 3973   home
>>  >>  40 South Alcaniz St.	(850)202 4416   office
>>  >>  Pensacola			(850)202 4440   fax
>>  >>  FL 32501			(850)291 0667    cell
>>  >>  phayes@ihmc.us       http://www.ihmc.us/users/phayes
>>  >>
>>  >>
>>  >>
>>
>>
>>  --
>>  ---------------------------------------------------------------------
>>  IHMC	(850)434 8903 or (650)494 3973   home
>>  40 South Alcaniz St.	(850)202 4416   office
>>  Pensacola			(850)202 4440   fax
>>  FL 32501			(850)291 0667    cell
>>  phayes@ihmc.us       http://www.ihmc.us/users/phayes
>>
>>
>>


-- 
---------------------------------------------------------------------
IHMC	(850)434 8903 or (650)494 3973   home
40 South Alcaniz St.	(850)202 4416   office
Pensacola			(850)202 4440   fax
FL 32501			(850)291 0667    cell
phayes@ihmc.us       http://www.ihmc.us/users/phayes

Received on Friday, 16 January 2004 17:56:41 UTC