Subject: [Ltru] Re: lookup/filtering semantics

From: "Kent Karlsson" <[email-masked]>
Date: Wed, 15 Feb 2006 01:52:50 +0100 (CET)

> > there has to be some sort of reason to believe that any
> > particular mathematical construct is relevant to the goals;
> > that hasn't been established.
>
> Admittedly Kent lost me with his reasoning, I didn't try hard

I'm sorry if I got you lost. But the different kinds of "less specific/
more specific" quite naturally falls out as an ordering, an ordering
that is partial. Defining "filtering" and "lookup" is then not far away.

> enough to get his points.  For the "embedded star" alternative
> I'd still like to see an example where that's clearly not the
> same as "unspecified subtag" for either filtering or matching.

Well, that depends on the details of the semantics, the ordering
in particular, that we decide upon.

> Unrelated, mathematical constructs aren't unimportant for the
> goals.  I felt comfortable with the old original concept of a
> "distance metric" in four dimensions (John's 8-4-2-1 proposal).

Not sure I'm comfortable with it. It's very very ad hoc. Not that that
can't work. But something like

	Distance(a, p) = sum[i=B+1, level(a), 2^(-i)] +
			  sum[j=B+1, level(p), 2^(-j)]
		where B = level(inf(a, p))

   where level(q) is the level of q in the c.p.o. seen as a tree,
   inf(a, b) is the greatest value less than both a and b (in the c.p.o.),
   and sum[i=x, y, e] is summation (usually written with a large sigma)

would seem less ad hoc (and more systematic and mathematical).
One could use a base greater than 2, or scale (strictly positive
scale factor) the result to get "nice" values; but that would not be
critical. I haven't tried it out, so it's just a first shot. The subdistance
values exponentially taper off with increasing level, and we just
add the distances of the two values to their largest common
"denominator".

> our five-dimensional case, where arbitrary numbers of variants
> could in theory trump anything (region, script, language).

Cannot happen in the above distance scheme.

The math here is rather trivial, and should not be too hard to follow.

		/kent k

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

---

From: r&d afrac <[email-masked]>
Date: Wed, 15 Feb 2006 02:32:30 +0100

At 01:52 15/02/2006, Kent Karlsson wrote:

>something like

I can only repeat my request for real examples.
They would permit to verify the adequation of your proposition, under 
which circumstances.
For example I am not sure that your remark about scaling is always 
exact in reality.
Let try to figure the languages mathematical space, are you sure it 
is orthonormed?
jfc

---

From: Mark Davis <[email-masked]>
Date: Tue, 14 Feb 2006 20:17:08 -0800

Actually, I think they are quite far away. The distance metric is like 
distance on a map; one can impose a partial ordering on locations, but 
they are artificial. An ordering of Chicago, New York, Seattle, Miami 
and San Diego (say from northern to southernmost) doesn't help me find 
the closest city to Seattle.

I think the discussion of ordering is irrelevant to the issue, and just 
clouds the water.

Mark

---

From: "Kent Karlsson" <[email-masked]>
Date: Wed, 15 Feb 2006 14:12:07 +0100 (CET)

Jefsey wrote:
> For example I am not sure that your remark about scaling
> is always exact in reality.

The scaling I mentioned is just to get "nicer" numbers. The only
importance it might have is if one wants to round to an integer,
and do not want to round too many values to the same integer.
As written (and with level('*') = 0), the expression would return
(real) values between 0.0 and 2.0.

> Let try to figure the languages mathematical space, are
> you sure it is orthonormed?

The distance model is highly simplified (which b.t.w. is based on
the 'basic' ordering; the 'extended' one cannot be seen as a tree).
The distance model in the -matching draft is also highly simplified.
(And we all know that, I hope.)

As hinted in the -matching draft ("For example, an implementation
might give a small distance to the difference [between] closely related
subtags") one could use a more sophisticated model, perhaps based on a
language family tree (or rather forest, as there is no known primordal
language). But actually doing that goes far beyond the goals of the
-matching document, I would think.

             /kent k

---

From: "Kent Karlsson" <[email-masked]>
Date: Wed, 15 Feb 2006 14:27:32 +0100 (CET)

Mark Davis wrote:
> Actually, I think they are quite far away.

How so? It might be an interesting experiment to ask someone
who knows something about discrete math to come up with a
mathematical model for what is in the -matching draft (and
the showing the -registry document, but without showing the
messages in this thread)...

> The distance metric is like

I'm not sure what you are trying to say here. But your ordering example
(which happens to be total, if we just count the city center points!)
is not at all related to closeness. But the ordering I gave for the
tags and tag patters precisely (for the 'basic' case at least, there
are some things to clear up for the 'extended' one) model the kind of
"closeness" that is wanted (prefix matching only for the 'basic' case).

> I think the discussion of ordering is irrelevant to the issue,
> and just clouds the water.

I happen to think quite the opposite. Do you think that using
structured programming clouds programs (that are much better written
using 'goto'?), or that BNFs clouds the description of formal syntax
that is better explained in English (or by a program, using 'goto',
written by someone who knows nothing about BNFs or formal grammars)?

Giving a formal semantics is a good thing, especially if it is simple
enough to be grasped at least by anyone knowing just a little bit
about math (orderings, sup/inf, a litte bit about sets, some arithmetic,
and a little bit about (discrete math) trees/forests); no degree in
math required.

The orderings (which aren't hard to understand) form just the
basis for the 'basic' and 'extended' versions of Lookup and
Filter given as math formulas rather than some explanation
in English prose. As indicated, the 'basic' ordering can also
be used as the basis for a (highly simpified, but so is the
current one in the draft) distance computation. So the orderings
are quite essential to basic lookup, basic filtering, extended
lookup, extended filtering, and the 'basic' ordering can be used
for a (somewhat different, but still about the same degree of
simplification) distance metric. So I would say that the orderings
are highly relevant, if you want to give a formal semantics
for these things. (It does not give any semantics to langauge
tags per se; that is an entirely different issue.)

		/kent k

---

From: John Cowan <[email-masked]>
Date: Wed, 15 Feb 2006 08:34:36 -0500

> -matching document, I would think.

Such a model would not be sophisticated but naive: in the absence of
Finnish content, for example, Swedish would be a far more sensible
fallback than Hungarian, though Hungarian is more closely related.
The mutual intelligibility between the three pairs of languages is the
same (namely, none at all), but for historical reasons more Finns happen
to know Swedish than Hungarian.

Similarly, fallbacks to Chinese, Russian, Arabic, Spanish, Hindi,
French, or English make the best sense for a vast number of languages,
and indeed English is probably a better fallback for French than any
other Romance language.

In practice such things are handled by language priority lists.

-- 
It was impossible to inveigle           John Cowan <[email-masked]>
Georg Wilhelm Friedrich Hegel           http://www.ccil.org/~cowan
Into offering the slightest apology     http://www.ap.org
For his Phenomenology.                      --W. H. Auden, from "People" (1953)

---

From: "Kent Karlsson" <[email-masked]>
Date: Wed, 15 Feb 2006 14:54:25 +0100 (CET)

Just to give a little bit of a feel for it all (and that it
is not irrelevant):

A (very small) part of the 'basic' ordering can be illustrated
like this (if you forgive me for the ASCII art):

        sv-Latn-SE                      en-Latn-GB
           |                               |
sv-SE   sv-Latn sv-FI            en-GB  en-Latn en-US
    \    |      /	            \    |     /
	sv				en
           \                          /
              \                    /
                   \           /
                         *

'*' is the least element (root if you like, zeroth level), single
(two or three letter) language codes are on the first level, etc.
ad infinitum (since arbitrary many variants are allowed).

It's a rather wide tree, since there are quite many language codes,
and the number of other codes aren't very small either.

The 'extended' ordering cannot be seen as a tree, but as a
rooted DAG (directed acyclic graph). It has "shortcuts" that
does not make it seem useful for defining any kind of sensible
distance metric, unless one has a more sopisticated notion
of "sublengths" than I used for 'Distance' before. (I might
come up with one, but not right now.)

		/kent k

---

From: "Kent Karlsson" <[email-masked]>
Date: Wed, 15 Feb 2006 14:58:27 +0100 (CET)

>> -matching document, I would think.

That is what the quote and example in -matching hints at, but I did
extrapolate.

> In practice such things are handled by language priority lists.

I agree. And I did cover langauge priority lists in my original post.

          /kent k

---

From: Frank Ellermann <[email-masked]>
Date: Wed, 15 Feb 2006 15:44:36 +0100

Kent Karlsson wrote:

> if you forgive me for the ASCII art

Certainly, it's much easier to "see" a rooted tree in ASCII
art than in the formula describing say the "distance" of its
nodes counting edges to get from A to B in this subtag tree ;-)

> rooted DAG (directed acyclic graph).

The "embedded stars" (not compressed to one) are apparently
an attempt to transform the DAG into a tree again, using the
"embedded stars" as special nodes.  The script-star and the
region-star.

> It has "shortcuts"

Corresponding to the stars.  The rooted tree and the DAG have
a problem with the variants.  For e.g. three variants "var01",
"var02", and "var03" ignoring all prior subtags, how do you
squeeze this in a tree ?  

You need nodes like var01, var02-var03, var03-var02 (!), etc.
The "distance" from var02-var03 to var03-var02 might be zero,
that could hurt the tree idea.

Or maybe you just enumerate all combinations eliminating all
combinations not in lexicographical order, that would remove
the var03-var02 case.

But that's something we didn't demand in 3066bis, so if it's
important for the matching draft we might need a step "sort
all specified variants in lexicographical order".

Actually I did that inth ABNF for the embedded star variant:

| langtag-pat   = (language-pat
|                 ["-" script-pat]
|                 ["-" region-pat]
|                 *("-" variant) ["-*"]
|                 *("-" extension-pat)
|                 ["-" privateuse])

The odd ["-*] in the variant-line tried to get rid of all but
at most one embedded star for variants,  What I really want to
say, the tree is a nice idea, but the variants are an obstacle.

                        Bye, Frank

---

From: "Kent Karlsson" <[email-masked]>
Date: Wed, 15 Feb 2006 18:35:48 +0100 (CET)

> nodes counting edges to get from A to B in this subtag tree ;-)

Yes.

> an attempt to transform the DAG into a tree again,

No, it cannot. Trying to draw some illustration defies
ASCII art (but I will try anyway), and I would be hard
pressed to produce anything sufficiently illustrative even
with a drawing. It becomes a mesh like structure. A tiny,
probably too tiny to be really illustrative, portion:

        sv-Latn-*,sv-Latn      en-Latn-*,en-Latn
             /        \         /           \
      sv-*,sv      *-Latn-*,*-Latn       en-*,en
            \              |             /
                  \        |       /
                           *

Trying anything larger, and the lines start criss-crossing.
(Formulas can sum it up rather nicely.)

This illustrates mostly the case where * aren't needed, especially
not the ones at the end. If one does not take prefix matching
rule, but instead require * (rather than empty) to get something
less than some non-empty part, the nodes/elements that do not end
in a * start coming out like a "fur" (and be leaves in the DAG).

> using the
> Corresponding to the stars.

Yes, *-Latn above, for instance. And these shortcuts would
make the inf operation I used select a bifurcation node
at too high a level, making the computed distance much
too short.

> The rooted tree and the DAG have

Where does anything say that the order of variant subtags
would not be taken into account? Not in the -matching draft,
as far as I can see. Both the 'basic' scheme and the 'extended'
scheme consider different orders of the variant subtags to be
different. (But I'm not sure about the current 'scored filtering'.)

         /kent k

---

From: "Addison Phillips" <[email-masked]>
Date: Wed, 15 Feb 2006 10:00:45 -0800

> in a * start coming out like a "fur" (and be leaves in the DAG).

The only place stars are needed are at the front (where you cannot omit the
subtag and to prevent any confusion regarding the other type of two-letter
code in regions). Otherwise they are just fancy placeholders. See other
message for a proposal for new ABNF that expresses this.

Note that originally, omitting "*" at the end meant "no more subtags after
the one specified", that is "zh-CN" matched "zh-Hant-CN" but not
"zh-CN-fubar".

Addison 

Addison Phillips
Internationalization Architect - Yahoo! Inc.

Internationalization is an architecture.
It is not a feature.

---

From: Frank Ellermann <[email-masked]>
Date: Wed, 15 Feb 2006 19:27:40 +0100

> No, it cannot.

Maybe not for your purpose.  But generally it could be as
simple as this (starting with your tree):

1 - replace 'root' "*" by e.g. an empty string.
2 - add "*" to each set of tags used to define a level, that
    get's us a language-*, an extlang-*, a script-*, the works
3 - build new tree, and maybe add a rule that the "distance"
    between adjacent nodes A and B is zero if A or B are a "*",
    otherwise it's one.  
4 - For non-adjacent nodes A and B define "distance" as the sum
    of distances between the nodes on the way from A and B (for
    a tree there's no question which way ;-)

I don't say that this makes sense wrt matching / filtering, but
we can decompose your DAG into a tree.  Otherwise a "which way"
question could be interesting (= where you said "shortcut").

>> The "distance" from var02-var03 to var03-var02 might be
>> zero, that could hurt the tree idea.
 
> would not be taken into account?

Checking... at the end of 2.2.5 we said:

| Most variants that share a prefix are mutually exclusive.  For
| example, the German orthographic variations '1996' and '1901' SHOULD
| NOT be used in the same tag, as they represent the dates of different
| spelling reforms.  A variant that can meaningfully be used in
| combination with another variant SHOULD include a 'Prefix' field in
| its registry record that lists that other variant.  For example, if
| another German variant 'example' were created that made sense to use
| with '1996', then 'example' should include two Prefix fields: "de"
| and "de-1996".

In other words my problem *-var02-var03 vs. *-var02-var02 was
a bad idea, it violated a SHOULD, and I got what I deserved for
that stunt, sorry.  

All variants that are not mutually exclusive SHOULD have some
preferred order, var02-var03 or var03-var02 is "wrong", maybe
both if these variants are mutually exclusive.

Probably we're better off if we treat all regions, variants,
and extensions as "additional noise" for matching / filtering,
and focus on getting it right for languages and scripts up to
the future <extlang>.  Plus the basic LTR case.  

There is no reason to expect that <region> is "more important"
than <variant> or <extension>.  Maybe a specified <extension>
is the most important part of a tag after language and script.

Why not go for three dimensions language - script - garbage ?

                           Bye, Frank