Re: SNAF, NAF, and monotonicity [was: Comments on * DRAFT * Rules...]

Dan Connolly <connolly@w3.org> wrote:
>
> On Thu, 2005-08-25 at 00:00 -0400, Michael Kifer wrote:
> > Dan Connolly wrote:
> > >
> > > On Aug 24, 2005, at 8:11 PM, Michael Kifer wrote:
> > > [...]
> > > > No, you got me wrong. I do believe that nonmonotonicity is important,  
> > > > but
> > > > you already have it in the form of SNAF.
> > > 
> > > I'm having trouble understanding that. I see it shows up in several of  
> > > your recent messages, e.g.
> > > 
> > > "SNAF is nonmonotonic."
> > > http://lists.w3.org/Archives/Public/public-rule-workshop-discuss/ 
> > > 2005Aug/0029.html
> > > 
> > > My understanding is that SNAF is monotonic.
> > > 
> > > Earlier[1] we discussed this example rule...
> > > 
> > > { :car.auto:specification log:notIncludes {:car auto:color []}}
> > >      => {:car auto:color auto:black}.
> > > 
> > > That rule is monotonic; if the antecedent is true, the consequent  
> > > remains
> > > true regardless of how many other things are also true.
> > 
> > Hi Dan,
> > Welcome to the discussion! Yes, it is very important to get to the bottom
> > of it so that everybody will start speaking the same language.
> > 
> > No, the above rule is nonmonotonic. If you add a color specification to
> > that car then :car.auto:specification will now include a color
> > specification and log:notIncludes will become false. Therefore 
> >     :car auto:color auto:black
> > will no longer be derived.
> 
> I don't understand. I understand monotonicity to mean
> that if you can derive F from a set of formulas A,
> then you can also derive it from the set A union B for
> any set of formulas B.
> 
> You seem to be suggesting there's some set of formulas B
> that when added to my A causes F to no longer hold.
> 
> Exactly what is that set of forumlas B? 
> Feel free to answer using Flora-2 syntax if that's more convenient.
> 
> You say "If you add a color specification ..." which suggests that
> B is something like...
> 
>   car auto:color auto:red.
> 
> but that doesn't falsify the premise:
> 
>  :car.auto:specification log:notIncludes {:car auto:color []}

I guess, I wasn't clear enough.

For you to show that your language is monotonic, you have to show that

   Forall A,B,F such that  A |= F implies A union B |= F            (*)

So, you single example didn't prove (*). To refute your main claim,
I had to show the negation of (*), i.e., that

   Exist A,B,F such that   A |= F and  A union B |/= F              (**)

(|/= denotes "not entails").

So, I had to find A,B,F to demonstrate (**). I couldn't use your
example directly, because that particular example didn't provide me with
the appropriate A,B,F to demonstrate (**). (I only have to demo existence,
i.e., find one example, while you have to show (*) for all examples!)
So, I extended your example (or at least I thought that I did).

> Exactly what is that set of forumlas B? 
> Feel free to answer using Flora-2 syntax if that's more convenient.

Thanks for giving me an easy way out :-)
My example is indeed easier to use because it already has all the necessary
formulas in it.

Let me repeat this example for easier reference:

    We assume that the info about the cars (over which we are going to
    close off) is in module allAboutCars and the facts there have the form

    12345:car[color->red].
    45678:car[color->blue].
    ...

    The 12345 thing is supposed to be the vehicle id number or something.
    The first fact says that 12345 is an object in class car and the attribute
    color has the value red, etc.

    The above info on cars could be on some Web site, for example.

    Now, to express N3's
	this log:forAll :car.
	{ :car.auto:specification log:notIncludes {:car auto:color []}}
	    => {:car auto:color auto:black}.

    one would write something like this:

    ?X[realColor->?Color] :- ?X[color->?Color]@allAboutCars.      (***)
    ?X[realColor->black] :- not ?X.color[]@allAboutCars.          (****)

    The first rule says that if the module allAboutCars has an explicit color
    for a car, then it is the real color of that car. You don't have this rule
    in your N3 example, but of course it is easy to add.

    The second rule says that if allAboutCars says nothing about a particular
    car's color then its color is black. This is a counterpart of your default
    rule, which involves log:notIncludes.

Now, let us assume that all the above formulas constitute the set A in (**).

Let's suppose 00007 is a car on the allAboutCars site, for which no color
information is available. Let 00007[color->black] be our formula F in (**).

Because allAboutCars says nothing about the color of 00007, we conclude
that 00007.color[] is false (00007.color[] means that there is some value
for the color attr in object 00007. We didn't find any, so it's
false). Therefore, we derive 00007[color->black] using the rule
(****). (The rule (***) doesn't fire, since its premise is false.)
Therefore,

        A |= F

Now, let B be 00007[color->yellow], which we would like to add to the
allAboutCars site. Now, rule (***) fires, but (****) doesn't. So, we derive
00007[color->yellow], but we don't derive 00007[color->black]. Therefore,

        A union B |/= F

so it is nonmonotonic.


The same thing basically happens in your N3 example.

There auto:specification is an attribute, which returns a set of objects
(which would formally be treated as terms). Somewhere you will need to
have a set of formulas (which will be part of the set A), which
would say which specific cars have which specifications.

So, if you have a car whose spec doesn't include color then you will derive
{... auto:calor auto:black} for that car. But if you throw in another
formula (our B above), which will give a color spec to that car then
{ :car.auto:specification log:notIncludes {:car auto:color []}}
will not be satisfied and so the rule will not fire.

I should also say that it is dangerous for me to venture into making the
above claims about N3, since, as far as I know, N3 doesn't have a formal
logical semantics. So talking about logical entailment is taking too much
liberty. But I think I have intuitive understanding of the intent and armed
with the formal semantics of F-logic (which is close in spirit to N3) I
feel I am making a convincing informal argument for nonmonotonicity of the
informal semantics of N3.



> [...]
> > > Monotonicity is an important scaling property of a language, so I'm  
> > > very interested to understand this point.
> > 
> > I am not clear what does monotonicity have to do with scalability.
> 
> Monotonicity supports partial understanding: as
> long as a document D is written in a monotonic language, then
> I'm OK to act on any information I can find/understand in D, even if
> I can't understand all of it. If it's written in a non-monotonic
> language, then I can't be sure of any of the information I find
> there unless I know exactly what all of it means, along with all
> of the information it includes by reference.

In real life people and computer systems (e.g., databases) do it all the time.
Not clear why all this suddenly becomes inappropriate on the Web.

If I look at the Expedia web site and don't find a flight then I conclude
that I can't find this flight there at this moment. An hour later, a whole
block of seats gets released and -- lucky me -- the flight is there!
Can I understand "all of the info @expedia" now? or before? No, the flights
may disappear again.

So, I don't buy the above argument of yours.

> I suppose the connection to scalability is sketchy... it's mostly
> a strong intution, connected to notions like anarchic scalability
> from Fielding's thesis.
> http://www.ics.uci.edu/~fielding/pubs/dissertation/introduction.htm

I should look into this sometime, but it is hard for me to accept that the
real world (which is inherently nonmon) is not scalable. If it isn't then
the Web shouldn't be either.

> You might find this write-up of partial understanding and nearby
> language design issues useful...
> 
>  Web Architecture: Extensible Languages 
>  W3C Note 10 Feb 1998 
>  http://www.w3.org/TR/NOTE-webarch-extlang


This is about language design. I don't believe that this has much impact on
knowledge representation.


	--michael

Received on Thursday, 25 August 2005 20:30:51 UTC