Subject: Re: Comments on draft-ietf-conneg-feature-syntax-00.txt

From: Graham Klyne <[email-masked]>
Date: Thu, 22 Oct 1998 15:24:46 +0100

Koen,

Thanks for your comments -- my responses and further questions are below...

At 21:22 21/10/98 +0200, Koen Holtman wrote:
>I find the draft quite readable overall, but I am probably not an
>average reader in this respect, as I have an extensive background in
>this kind of logic (my CS department is very big on this kind of stuff
>even for a European CS department).  Maybe the average
>reader/implementer will find it quite frightening, especially if a
>treatment of q factors (or another way to choose in ambiguous
>situations) is also added.

I can appreciate this concern.

Almost everything we do in computing and networking is based on some
theoretical foundation.  Mostly, we can simply assume or reference the
foundation and do the engineering that depends upon it.  In this case, I
could not find any established theoretical work that underpinned the
particular requirements, so I felt it was necessary to include some
supporting material in the memo.  There was much more (in my earlier
-algebra- drafts) that has been removed and replaced by the present section
3 which is intended to be more descriptive.  I felt section 5.1 was needed
as an example of how the required processing could be achieved (lacking
knowledge of applicable published algorithms that could be cited).

I myself do not have an extensive background in this kind of material:  my
approach was based on some small previous experience of using Prolog to
solve a CAD problem, and some hurried reading of logic textbooks.  As such,
I have tried to avoid introducing theoretical material that did not seem
important to the problem, but it's sometimes difficult to tell what is and
is not relevant to the overall picture.

I was drawn into some of the "symbolic logic" elements because I felt that
what was needed was something that achieved some of the goals of a Prolog
implementation, but without actually enumerating values in a database (or
set):  hence the need to deal with and manipulate symbolic expressions.  I
cannot see any way of avoiding this.

Treatment of q-values within this framework was avoided primarily to avoid
the additional complexity.  And because it seemed that there are several
possible interpretations, without any one being obviously "correct".  Thus,
the view presented in this memo (or will be when some accidentally-removed
text is reinstated) is that q-values are applied *only* at the top-level,
and no rules for combining them are provided.  (Formally, one might say
that a q-value is applied to each disjunction in the canonical disjunctive
normal form, and nowhere else.)

You may notice that, in recent exchanges, we have softened the line on
q-value combinations to allow future experimentation with formal combining
rules for them.

>  I think that having a generic symmetric
>framework with q factors is quite valuable in itself, but there is a
>definite risk that such a framework will be too complex to get
>deployed.  I would like to hear opinions of other readers on this
>issue.

Me to.

But for the time being, I think we need to concentrate on getting the basic
framework right, and presented effectively, without additional complexity.

>From a high level point of view I would like to see a framework that
>is powerful enough to make TCN feature negotiation a special case.

So would I.

>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.

>  It should be doable on theoretical
>grounds but I have no real idea about the complexity of the resulting
>notational system.  And of course the is the point of choosing a
>particular fuzzy-set-intersection operator.  (Note that TCN feature
>negotiation can be thought of as computing a set intersection between
>a fuzzy and a crisp set of feature collections.)

If I'm undersanding you correctly, I feel likewise, and I would like to
think that we can experiment with these ideas within the basic framework
that recognizes the existence of q-values but does not impose a (single)
interpretation on them.  But I do believe that trying to handle the fuzzy
issues now would complicate the basic framework.

In the meanwhile, this framework does seem to successfully address some
real requirements we have for identifying fax recipient capabilities.

>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.]]]

>4.2.1: For brevity you could drop the discussion of named predicates,
>or move it to an appendix.

I agree that it interrupts the main flow of the document.

The notation is used in other documents (mainly for convenience), so I
think named predicates should be retained.  Thus, I propose to move it to a
separate section after the discussion of feature set matching.  I also
propose to promote the feature set matching description to be the entire
content of section 5.

>5.1: As noted before, though you define a syntax for q values, you do
>not define a semantics.

Yes.  I'll add a note clarifying this here.

>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))

>5.1.1: item 5.1: 'just one feature value' should be 'just one feature
>tag'.

Indeed it should.  Thanks.

>5.1.4: this canonicalisation step is done too early to be of any real
>benefit, especially because:

I agree that my approach is not necessarily the best one.  But allow me to
try and explain my rationale:

>5.1.5: you forgot the rules for handling negation ( !filter ).

One of the points of 5.1.4 is that it eliminates all negations.

>5.1.7: I would omit 5.1.4 and invent new rules here starting from the
>=, !=, <= and >= operators.  I think the result would be shorter. 

This is certainly a possible approach.  And it might be better -- I'm not
certain.

An earlier working verson of this work took this approach, but I found that
I ended up with a large number of combining rules to deal with the possible
combinations of relational operators and negations.  It was a kind of
combinatorial explosion.  Section 5.1.4 was introduced in an attempt to
reduce the number of combinations;  I must confess that I did not achieve
as great a reduction as I originally hoped, but I did achieve some reduction.

It was based on the central observation that the usual comparison predicates:

   <  <=  ==  !=  >=  >

are redundant for ordered values, and don't accurately capture every
possibility for unordered values.  For a given pair of ordered values,
exactly one of three possible relations must hold:  <, ==, >.  To express
this with Boolean predicates requires at least two predicates.  But two
predicates can express four possibilities so even that would be redundant.
For unordered values, exactly one of ==, != must be true (where != is quite
distinct from < and >).  This gives a total of 4 possible relationships
between any pair of values:  <, ==, !=, >, which can be expressed exactly
using two Boolean predicates.

Thus, I ended up with the framework proposed that reduces the relational
operators to exactly two predicates (LE and GE), together with their
negations (NL and NG).

This in turn reduces the number of rules needed in 5.1.7 from
6+5+4+3+2+1=21 to 4+3+2+1=10.  (I found it convenient at the time to list
separate rules for ordered and unordered values:  eventually, I think these
could be combined.)

#g

------------
Graham Klyne
([email-masked])

---

From: [email-masked] (Koen Holtman)
Date: Wed, 28 Oct 1998 20:36:28 +0100 (MET)

>At 21:22 21/10/98 +0200, Koen Holtman wrote:
[....adding q factors....]
>suggesting incorporation of q-values (or similar) into the set-combining

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.

>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.

>   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.

---

From: [email-masked] (Koen Holtman)
Date: Wed, 28 Oct 1998 21:12:26 +0100 (MET)

[Oops, forgot one point in my previous message]

>At 21:22 21/10/98 +0200, Koen Holtman wrote:
[...]
>One of the points of 5.1.4 is that it eliminates all negations.

As far as I can see the syntax allows constructs like

  (!(& a=5 b=7 (| c=8 d=9)))

and these are not eliminated.

Koen.

---

From: Al Gilman <[email-masked]>
Date: Wed, 28 Oct 1998 15:18:37 -0500 (EST)

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