Subject: [Ltru] weights in scored filtering

From: "Addison Phillips" <[email-masked]>
Date: Fri, 18 Nov 2005 14:29:39 -0800

> >
> >>[At the end of the section, after we've introduced the discussion of an
> >>ordered list and distance metric, add]
> >>
> >>When the set of matches is returned, the items are in descending order
> >>where the weight for each item is the priority in the language priority
> >>list divided by the distance metric. (If the filtering method does not
> >>supply a distance metric, then the distance metric is 1.) If the item
> >>matches multiple ranges, then its weight is the square root of the sum
> >>of squares of the individual weights for each range. If two items have
> >>the same weight, then their ordering is based on a case-insensitive
> >>ordering of the language tags.
> >>
> >>
> >[Addison Phillips]
> >
> >Ugh. Icky. Many items will have the same weight even in spite of this
> complex scheme.
> >
> >
> Can't get around that. If priorities are equal and there is no distance
> metric, then you essentially have an unordered list.

If I have two bits of content with the same tag, their values will be equal. The choice of what order they are returned in then is implementation specific, perhaps based on some other information (like FIFO or word frequency or...)
> 
> >I note that q weights in Accept-Language are always less than or equal to
> one and greater than or equal to zero. Your algorithm won't work correctly
> with those values (instead multiplication of the score works better).
> >
> 
> You're right that there is a numeric problem, but you can't multiply,
> because smaller distances are better, but lower priorities are *worse*.
> So you have to divide one way or another. Look at an example.

My bad. At that moment I was thinking in terms of the old version where zero was bad. Dunno why. You're correct.

> 
> Now, as I think about it, the simplest way is to still think of the
> results as distances, with the smallest distance being the best. Then
> the algorithm is
> 
> a) toss out any q weights that are zero. After all, that means that you
> give them *no* priority.

Uh... you made the point that a weight of zero has a meaning, one that works well with division: it is "never return content in this language". DIV/0 error is a good way to flag these items. As with:

  sr, q=1.0; sr-Latn, q=0.0; en, q=0.8

Means: I'd like Serbian, but never in Latin script, followed by English.

> 
> The square rooty stuff was just because distance metrics with multiple
> fields weight better when you treat them as dimensional vectors.
> However, in retrospect it is probably just simpler to take the minimum
> of the possible weights. So if Q matches X with a distance of, say, 2. Q
> matches Y with a distance of 10. Then the result would be the minimum, or
> 1.

For a given tag/range match, you get a score. The lowest score wins. A smart implementation has a threshold value. The first value above the threshold in the language priority list is the score for the content (perhaps even if a later range might score higher). A threshold of zero matches extended language range filtering.

One more fly in the ointment: a score of zero isn't open to coercion by weight. Consider this language priority list: "en; fr; de" and this tag: "fr-FR". The score for the tag with "fr" is zero and the fact that 'fr' is weighted lower than "en" has no effect on this.

I think it would be better if we could find an integer-only scoring scheme that deals with weights in some consistent manner. Perhaps: create scores for each tag vs. each range in the list. Then add the position in the list (starting at base zero) to the score. For the example above, the score for "fr-FR" is "1" and the score for "de" is "2".

Addison

Addison P. Phillips
Globalization Architect, Quest Software

Internationalization is not a feature.
It is an architecture. 

> -----Original Message-----
> From: Mark Davis [mailto:[email-masked]]
> Sent: 2005年11月18日 13:42
> To: Addison Phillips
> Cc: [email-masked]
> Subject: Re: [Ltru] draft-06 comments: choice of range
> 
> 
> 
> Addison Phillips wrote:
> 
> 
> >>A protocol which uses language priority lists MAY specify an alternative
> >>mechanism for computing the ordering.
> >>
> >>----
> >>
> >>A protocol which uses language ranges MAY specify additional rules about
> >>the semantics of "*";
> >>=>
> >>A protocol which uses language ranges MAY specify additional rules about
> >>the semantics of "*" or other tags;
> >>[no reason to restrict it]
> >>
> >>----
> >>
> >>Implementations or protocols sometimes might wish to use more
> >>sophisticated weights that
> >>=>
> >>Implementations or protocols sometimes MAY specify the use of
> >>alternative weights that
> >>
> >>
> >[Addison Phillips]
> >
> >Either "...protocols MAY..." or "... protocols sometimes might..."
> >
> >
> sometimes MAY => MAY
> 
> >I chose non-normative language initially to allow things without turning
> the whole section into RFC 2119 soup.
> >
> >
> >>----
> >>[Make subsections in Lookup. First language range lookup, then language
> >>priority list lookup, then extended language range lookup.]
> >>
> >>
> >[Addison Phillips]
> >
> >I think that's an awful idea.
> >
> >And make up your mind: we REMOVED extended language range lookup because
> it doesn’t make sense. Lookup is now cast as I suggested above: it is
> strictly a language priority list beast, but it starts by defined the
> match between a tag and a range.
> >
> >
> Lemme relook at it, but it seems to me that you are doing it, but *via*
> transforming it. (but more in a separate message anyway).
> 
> >>----
> >>Other examples of lookup might include:
> >>=>
> >>Other examples of lookup include:
> >>[the examples *do* include. no need to be tentative ;-)]
> >>
> >>
> >[Addison Phillips]
> >
> >Okay.
> >
> >
> >>----
> >>
> >>If this language range is the only one in the language priority list, it
> >>matches the default content. If this language range is followed by other
> >>language ranges, it should be skipped.
> >>[doesn't address  *;*]
> >>
> >>
> >[Addison Phillips]
> >
> >Yes, it does... iteratively.
> >
> >
> You're right.
> 
> >
> >
> >>=>
> >>All "*" language tags are removed from language priority list. If there
> >>is nothing left, then it matches the default content.
> >>
> >>
> >[Addison Phillips]
> >
> >That's "ranges" in your first sentence.
> >
> >
> >>----
> >>
> >>5. (default content or the empty tag)
> >>=>
> >>5. (default)
> >>[explain below what this is. it is also otherwise odd that 1-4 are tags,
> >>but then this is 'content']
> >>
> >>
> >[Addison Phillips]
> >
> >Okay.
> >
> >
> >>----
> >>
> >>When performing lookup using a language priority list, the progressive
> >>search MUST proceed to consider each language range before finding the
> >>default content or empty tag. The default content might be content with
> >>no language tag (or with an empty value, as with xml:lang in the XML
> >>specification), or it might be a particular language designated for that
> >>bit of content.
> >>
> >>One common way to provide for default content is to allow a specific
> >>language range to be set as the default for a specific type of request.
> >>This language range is then treated as if it were appended to the end of
> >>the language priority list, rather than after each item in the language
> >>priority list.
> >>
> >>=>
> >>[reword for clarity. Funny thing: when I first read 'might be content
> >>with no language tag' I read it as the verb "be content with", like "be
> >>happy with". The empty tag is not a valid language tag, so we should say
> >>"und", then say that a system can use alternatives. Here is the text.]
> >>
> >>
> >[Addison Phillips]
> >
> >No, not 'und' (and I *hate* 'und'). 'Und' would be an example of an
> implementation specific decision. Personally I would prefer never to see
> 'und' content being used as a default.
> >
> >
> Well, "" is illegal as a language-tag, so I was just using it as a
> stand-in because we don't have a language tag for "root".
> 
> >>When performing lookup using a language priority list, the progressive
> >>search MUST consider each language range before finding the default. The
> >>default might be specified as "und" (or be indicated with an empty
> >>value, as with xml:lang in the XML specification, or with "root" as in
> >>some systems), or it might be specified as a particular language range.
> >>This language range is thus treated as if it were appended to the end of
> >>the language priority list, rather than after each item in the language
> >>priority list.
> >>
> >>
> >[Addison Phillips]
> >
> >I prefer not to make this change. I think it delves too closely into the
> implementation specific.
> >
> >
> It can't be left as it is. Other alternatives?
> 
> >>----
> >>
> >>5. (return default content)
> >>a. ja-JP
> >>b. ja
> >>c. (empty tag or other default content)
> >>
> >>5. (default)
> >>a. ja-JP
> >>b. ja
> >>c. und
> >>
> >>
> >[Addison Phillips]
> >
> >How about:
> >
> >5. (default content lookup)
> >   a. ja-JP
> >   b. ja
> >   c. (implementation defined)
> >
> >
> That works.
> 
> >>----
> >>
> >>Wildcard values in an extended language range are supposed to match any
> >>value
> >>=>
> >>Wildcard values in an extended language range match any value
> >>
> >>
> >[Addison Phillips]
> >
> >No, they are *supposed* to match, but in this case they don't. They match
> the empty value.
> >
> >
> I read that differently. When you say "supposed to match", it sounds
> like there is a choice, that there are some values that they don't
> match. Like the US is "supposed to" disallow torture.
> 
> >>----
> >>
> >>Add
> >>
> >>
> >>      3.3.x. Distance Metric Lookup
> >>
> >>Distance metric lookup is performed by producing an ordered list of
> >>filtered results as specified in 3.2.2, then returning the first item.
> >>
> >>
> >[Addison Phillips]
> >
> >I think we'd best not go down that path. Among other things: it won't
> work. Distance metric filtering can produce items with identical scores...
> >
> >
> Ok, drop it.
> 
> >
> >
> >>----
> >>
> >>Mark
> >>
> >>P.S. I still think that the extended range lookup doesn't quite work,
> >>but I'll send that in a separate message.
> >>
> >>
> >[Addison Phillips]
> >
> >No, it doesn't work and we eliminated it. We've mapped extended ranges
> onto basic ranges, which do work, producing different results than the
> language priority list might lead one to expect.
> >
> >
> Let me look this over again.

_______________________________________________
Ltru mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ltru

---

From: Mark Davis <[email-masked]>
Date: Fri, 18 Nov 2005 17:37:05 -0800

We can do an integer only approach. Convert the q's into round(100/q).

For filtering, we can't assume anything about the order of items in the 
list that have the same q values. I have en, de, fr, it, nl. But my 
English is significantly better than my German, which is somewhat better 
than my French, which is significantly better than my Italian, etc.

For lookup, we and everybody I know just uses the q values to reorder 
the list. Then throws them away. So for lookup, ordering is very important.

Mark

>Means: I'd like Serbian, but never in Latin script, followed by English.
good point.

>I think it would be better if we could find an integer-only scoring scheme that deals with weights in some consistent manner. Perhaps: create scores for each tag vs. each range in the list. Then add…
Don't think that works.