Subject: Extension path and fuzzy sets

From: Graham Klyne <[email-masked]>
Date: Thu, 29 Oct 1998 15:13:26 +0000

Al,

Broadly speaking, I think I agree with what you say.  But to try and avoid
storing up possible misunderstanding for the future, I'd like to try and
put it as I see it:

The algebraic framework, as defined, is purely Boolean/non-fuzzy.  Its
purpose is to identify the set of _all_ possible feature collection
candidates for a message transfer.

There is, _in addition_, a q-value annotation whose intent is to provide a
basis for selection among the possible alternatives.  The semantics
associated with this value are very sparse:  range [0..1], higher values
preferred and 1=>ideal.  Implied, but not explicit, is the idea that 0 =>
not acceptable.

The -syntax- document explicitly avoids defining any rules for combining
q-values, so they are only useful in the framework (as-defined) when
applied to members of a top-level disjunction.  But the later definition of
further combining rules is not prohibited.

I believe that there is a posible isomorphism between the -syntax-
framework with additional q-value combining rules, and a fuzzy-set
extension mechanism, hence this framework is sufficient for such future
developments while avoiding getting caught up in their potential
complexities.  Specifically, the isomorphish is achieved by asserting that
a q-value of 0 is equivalent to FALSE value for the predicate
siub-expression to which it is applied.  Any other q-value (i.e. in the
range (0,1]) corresponds to a TRUE value.  Application of q-values must
observe these restructions, and combining rules must preserve them.

Thus, I assert, the Boolean operations described by the -syntax- framework
can be applied, together with suitable additional q-value combining rules,
and the resulting expression will be a disjunctive normal form in which
each disjunction has an assocuated q-value that corresponds to the
"inclusion value" it would have in a corresponding fuzzy set framework.

A final point I should note:  when you say:

>When you have defined relational operators on numbers, you can
>start using numbers (in your algebra) for preferences in addition
>to Booleans.

I do fear a misunderstanding here.  The relational operators on numbers are
part of the predicate logic framework and always yield Boolean results.
Numbers used as q-values are completely distinct, and are (in general)
applied independently of any numbers that may appear in the predicates.

At 15:18 28/10/98 -0500, Al Gilman wrote:
>Very briefly, I want to re-assert my extension path concept.
>
>When you have defined relational operators on numbers, you can
>start using numbers (in your algebra) for preferences in addition
>to Booleans.
>
>Ultimately, the negotiation boils down to Boolean attributes on
>the choices: do this, don't do that.
>
>The fuzzy algorithm doesn't even have to be public, but the
>operators in it have to be available for policy declaration so
>that blending the policies asserted by the two parties reduces to
>the choice (or non-inferior choice list).
>
>Extension datatypes are introduced as object classes with methods
>that reduce the domain of what remains to what had been defined
>before.  This extension process is rooted in Boolean.  Ordinals
>on numbers are in the IOC; cardinal operations are experimental
>and for future clarification.
>
>Fuzzy logic can be generated as a special case of this extension
>path.
>
>FWIW 
>
>Al
>
>to follow up on what Koen Holtman said:
>> From [email-masked]  Wed Oct 28 14:43:56 1998
>> From: [email-masked] (Koen Holtman)
>> Message-Id: <[email-masked]>
>> Subject: Re: Comments on draft-ietf-conneg-feature-syntax-00.txt
>> To: [email-masked] (Graham Klyne)
>> Date: Wed, 28 Oct 1998 20:36:28 +0100 (MET)
>> Cc: [email-masked], [email-masked]
>> In-Reply-To: <[email-masked]> from
"Graham Klyne" at Oct 22, 98 03:24:46 pm
>> X-Mailer: ELM [version 2.4 PL23]
>> Sender: [email-masked]
>> Precedence: bulk
>
>> Graham Klyne:
>> >
>> >Koen,
>> >
>> >Thanks for your comments -- my responses and further questions are
below...
>> >
>> >
>> >At 21:22 21/10/98 +0200, Koen Holtman wrote:
>> [....adding q factors....]
>> >>On a mathematical level this would mean changing from boolean logic to
>> >>fuzzy set logic.  You would go from set-intersection between two sets
>> >>of feature collections to fuzzy-set-intersection between two fuzzy
>> >>sets of feature collections.
>> >
>> >I'm not certain what you mean by 'fuzzy set logic'.  The closest I can
find
>> >in my references is replacement of Boolean true/false by some
>> >probability-of-truth value.  I'm not sure how this could be used as a
>> >mathematical relation for set selection and partitioning.  I think you are
>> >suggesting incorporation of q-values (or similar) into the set-combining
>> >framework.
>> 
>> I think I can best explain what I have in mind by taking a simplified
>> example.  Suppose that there are only two feature tags x and y (for
>> the sreen dimensions).  A single feature collection can then be
>> expressed as a tuple (x,y), e.g. (640,480).
>> 
>> The feature set F of a sender or recipient can then be presented, in
>> your non-fuzzy framework, as a function F from tuples (x,y) to a
>> boolean.  F(x,y)==true if the feature collection is in the set.
>> 
>> In your framework, with a sender feature set Fs and a recipient
>> feature set Fr, the result of the negotiation process is then a tuple
>> (x,y) for which
>>  Fs(x,y) AND Fr(x,y) == true.
>> 
>> of course Fs and Fr are represented by boolean predicates in your
>> framework.
>> 
>> To fuzzify the whole business, the functions F should not longer map
>> to a boolean but to the real number interval [0...1].  For an (x,y)
>> considered 'perfect quality' by the sender, Fs(x,y) would be 1.  For
>> 'moderate quality', it would be 0.8 or somesuch.  Essentially a q
>> value is assigned to each and every feature collection.
>> 
>> Now, in this fuzzy system the result of the negotiation process is a
>> tuple (x,y) for which
>> 
>>  Fs(x,y) FUZZY-AND Fr(x,y) is maximal.
>> 
>> With FUZZY-AND an operator like * or min or max or average ( (lambda
>> x,y. (x+y)/2) ).  * and average usually work quite well.  Note that
>> different operators may make different (x,y) values the maximal one if
>> the situation has many combinations which are (for the human observer)
>> more or less equivalent.
>> 
>> Again, Fs and Fr would be represented by predicates, this time fuzzy
>> predicates.  An example of such a predicate, in C-like notation, would
>> be
>> 
>>  ((x==640 && y==480) ? 1 : 0)
>> 
>> (which is the exact equivalent of the non-fuzzy (& x=640 y=480) ).  A
>> more interesting fuzzy predicate would be
>> 
>>  ((x==640 && y==480) ? 1 : 0) * 1.0 +
>>  ((x==320 && y==240) ? 1 : 0) * 0.5
>> 
>> Of course, computing normal forms etc. for such beasts is more
>> complicated than in the boolean case, and I think we should stay away
>> from that at least for the time being.  Documenting the basic
>> principles of fuzzy negotiation as I did above may be a nice addition
>> to the syntax draft though, because this allows one to describe how
>> various systems are limiting cases.
>> 
>> >>Some specifics:
>> >>
>> >>Section 2.  It would be good to mention in a note that TCN uses the
>> >>term 'feature set' in a different way.  In TCN a feature set is
>> >>mathematically somewhere between a feature collection and a feature
>> >>set in your terminology.
>> >
>> >OK.  And I note I am remiss in not more clearly citing and crediting the
>> >influence of your TCN work on this.  I'll put that right.
>> >
>> >[[[Aside:  I don't think there is a "between" feature collection and
>> >feature set:  if it's not a feature collection (i.e. one specific value
per
>> >feature tag) then I think it has to be a feature set.]]]
>> 
>> TCN 'feature sets' are feature sets in your sense of course, but not
>> every one of your feature sets could be expressed as a TCN feature
>> set.
>> 
>> >>5.1: You talk about propositional calculus vs. predicate calculus in
>> >>the note.   I do not know exactly which calculus you mean with
>> >>propositional calculus.  Could you give a reference?
>> >
>> >I'll add a citation.
>> >
>> >By "propositional calculus", I mean Boolean expressions that combine
>> >independent atomic propositions:
>> >
>> >   e.g.  (A&B)|(C&D)
>> >
>> >By "predicate calculus", I mean Boolean expresions that combine predicates
>> >that may refer to other (typically non-Boolean) variables:
>> >
>> >   e.g.  (A(x)&B(y))|(C(x)|D(y))
>> 
>> Hmm, with these definitions of predicate and propositional calculus,
>> if you consider things like 'pix-x=500' to be one atomic proposition,
>> then propositional calcululus would be powerful enough to handle your
>> case.
>> 
>> 
>> >#g
>> 
>> Koen.
>> 
>
>
------------
Graham Klyne
([email-masked])

---

From: Al Gilman <[email-masked]>
Date: Fri, 30 Oct 1998 09:27:39 -0500 (EST)

to follow up on what Graham Klyne said:

> Broadly speaking, I think I agree with what you say.  But to
> try and avoid storing up possible misunderstanding for the
> future, I'd like to try and put it as I see it:

Excellent idea.  Let's see if I can shrink the ambiguity...

> candidates for a message transfer.

The algebraic framework, as initially defined, contains only the
Boolean class.  Is it intended to be extensible?  I would have
said that "to identify the set of _all_ possible feature
collection candidates for a message transfer" is its _initial
capability_, not its ultimate purpose.  

Its purpose is -- what?  To describe information derivation
patterns?  Patterns of information relationship?  To declare
knowledge fragments that can be combined into an automated
process of shrinking choice ambiguity.  In this sense, the
assertion of a q-value shares this mission with the assertion of
boolean combiners.

One of the purposes of an algebra is for different relationships
to be added into the negotiation process from different sources.
Not just the information source and sink players of the eventual
transfer, but protocol and resource technology definitions, and
standard operating procedure conventions within small
communities.

> There is, _in addition_, a q-value annotation whose intent is
> to provide a basis for selection among the possible
> alternatives.  The semantics associated with this value are
> very sparse: range [0..1], higher values preferred and
> 1=>ideal.  Implied, but not explicit, is the idea that 0 => not
> acceptable.

Let's leave the question as to whether q=0 is better or worse than
<option not mentioned> to explicit statements.  Unless I am told,
I don't know how an implementer of the framework will handle this.

> "inclusion value" it would have in a corresponding fuzzy set framework.

To the extent that I understand fuzzy logic, this is exactly in
agreement with what I understand.

Detail note: binding 0 to FALSE is optional in the above scenario.  It
works either way.

> I do fear a misunderstanding here.  The relational operators on
> numbers are part of the predicate logic framework and always
> yield Boolean results.  Numbers used as q-values are completely
> distinct, and are (in general) applied independently of any
> numbers that may appear in the predicates.

Yes, this is where differences in bias creep in.  To me, saying
that the q-values are completely distinct from number classes in
other applications is misleading or at least wasteful.  Wasteful
because the information lost has possible usefulness.  To say
that they are always applied independently of any numbers that
may appear in feature definitions and predicates is unduly
restrictive of function.

The hypothesis that I am working from is that reasonable
combining rules for q-values can be viewed as algebraic (whith
fuzzy logic an example) for the right definition of a topology on
these values.  Ordinals have a different topology from cardinals.
But they have a topology.  And it is the topology of preference
that the conventions using [0...1] and selected operators needs
to capture.

This suggests that we can absorb the q-factor-combining and
final-choice-selection steps into an the algebraic or value-flow
framework shared with the existing boolean algebra, once more
pieces of the definition have been put in place.

They are disconnected now, but they are not disconnected for any
valid purpose.  The eventual integration into a single functional
flow with user-registered reductions applied as a matter of
course is desirable to keep alive as a possible outcome.

The issue of negotiation, of reconciling policy profiles to
arrive at a deal, is all over the place these days.

It's true that if it isn't simple, implementors won't implement
it; but if it doesn't fit into the global flow users won't use
it, very long.  Something better will roll right over it.

Grand challenge problem: can a set of peers without a designated
autocrat schedule the next meeting through asynchronous
interactions without a synchronous meeting to discuss it?

BCP is you must decide the next meeting in a meeting, or it just
gets too hairy.

Al