Re: min and max, really intersection & union...
> From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
> To: "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx>,
> "Dominique Lohez" <dominique.lohez@xxxxxxx>
> Cc: <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: min and max
> Date: Wed, 25 May 2011 11:28:18 -0500
>
> (in response to Dan's interesting post on min and max):
>
> Although it seems rare that Arnold and myself agree, I think he's the one
> that once said "when we agree, we agree". On the issue of decorations for
> min and max, I *do* agree with Arnold that these operations should be
> treated as normal binary arithmetic operations. Below is a snippet from
> Arnold made at the beginning of the year on this topic:
>
My read of Arnold's argument is that it is not so much a
comment on min & max as interval functions as it is about
using min & max among the Reals together with a helper
function to implement intersection & union.
But it DOES beg the question of the static interpretation
of intersection & union. So let me see if I can answer
that question as I did for max.
One could (indeed, people DO) define xx \interset yy as
if ((zz \subset xx) && (zz \subset yy)) then zz
else empty. For all zz. (I.e, maximal such zz.)
This form is just as much a selection function as is max.
But since the selection criteron is to select only that
which is in BOTH operands, I argue that the decoration
should be the worst of the decorations of its operands.
If one defines xx \union yy as
if ((xx \subset zz) && (yy \subset zz)) then zz
else empty. For minimal zz.
Then, for much the same reason, this argues that one
should also decorate this result with the worst of both
operands.
On the other hand, one does not know exactly WHERE any
non-(defined&continuous) location happened among the
operands. This argues for the best decoration to be
selected for the result.
Is this ignoring important information or is the former
introducing false positives as before?
Not a great argument I agree. But I'm not clear on this
yet.
Perhaps one of you has some compelling argument.
If so, trot it out.
Dan
>
> Arnold Neumaier wrote:
> > Nate Hayes wrote:
> >> John Pryce wrote:
> >>> I do not expect this scheme to receive universal acclaim. For one thing,
> >>> it is not child's play to grasp the specifications. For another, I have
> >>> followed the Neumaier approach to the mathematics. I found this easier
> >>> to
> >>> follow than the Hayes approach which disagrees with it in various ways.
> >>> I
> >>> hope, at the implementation level it does the most important things that
> >>> Nate requires.
> >>
> >> ...I'm pleased with the progress; and I see your skill with the technical
> >> writing continues to be a service to all of us.
> >
> > You gave three interesting and important examples that help to clarify
> > the usage of the decorated semantics.
> >
> >
> > (i) Intersection of objects
> > ---------------------------
> >
> > > We are currently examining the application of decorations to
> > > Constructive
> > > Solid Geometry (CSG):
> > > http://en.wikipedia.org/wiki/Constructive_solid_geometry
> > > This relies heavily on the interval lattice operations min and max. For
> > > example, a solid object may be represented by an implicit function f.
> > Then
> > > the set of all f < 0 is inside the object, f > 0 is outside the
> > object, and
> > > f = 0 are points on the surface of the solid object. If A and B are two
> > > solid objects and fA and fB are their respective implicit functions,
> > > then
> > > the intersection between A and B is defined
> > > A intersect B = max(fA,fB)
> > > and the union between A and B is defined by
> > > A union B = min(fA,fB).
> >
> > Here
> > A = {x | A(x)<=0},
> > B = {x | B(x)<=0},
> > where A(x), B(x) are arithmetic expressions, and an inequality is
> > supposed to be false if a subexpression is undefined.
> > We want to deduce information about
> > C := A intersect B,
> > D := A union B.
> > Since
> > C = {x | C(x)<=0}, where C(x)=max(A(x),B(x)),
> > D = {x | D(x)<=0}, where D(x)=min(A(x),B(x)),
> > this can be handled by ordinary interval evaluation of arithmetic
> > expressions, using min and max as binary arithmetic operations as in the
> > Level 1 text draft. We just evaluate the interval extension and at the
> > end check the decorated range enclosure.
> >
> > No change in the semantics is needed, no false conclusions are generated
> > by the algorithm for deciding whether a box xx is inside or outside C or
> > D, or whether no decision is possible.
> >
>
> So in this sense, min and max are treated like, say, addition in regards to
> how the decorations need to propagate.
>
> Regards,
>
> Nate
>
>
>
>
> ----- Original Message -----
> From: "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx>
> To: "Dominique Lohez" <dominique.lohez@xxxxxxx>
> Cc: <stds-1788@xxxxxxxxxxxxxxxxx>; "Dan Zuras Intervals"
> <intervals08@xxxxxxxxxxxxxx>
> Sent: Wednesday, May 25, 2011 10:45 AM
> Subject: Re: What is your philosophy? Tracking or Static?
>
>
> >> Date: Wed, 25 May 2011 17:06:12 +0200
> >> From: Dominique Lohez <dominique.lohez@xxxxxxx>
> >> To: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>
> >> CC: "<stds-1788@xxxxxxxxxxxxxxxxx>" <stds-1788@xxxxxxxxxxxxxxxxx>
> >> Subject: Re: What is your philosophy? Tracking or Static?
> >
> > Dominique is correct in that we often choose examples
> > which are mathematically difficult when perhaps some
> > simpler example would suffice for this argument.
> >
> > Very well, let me see if I can come up with one off
> > the top of my head.
> >
> > f(x,y,z) = max(x,y,z)
> >
> > Now, max() is basically a selection function. It is
> > formally equivalent to:
> >
> > max(x,y) = if x < y then y else x
> >
> > Therefore, it takes on the properties of the selected
> > thing no matter what happened to the unselected thing.
> > Indeed, code like:
> >
> > if x < 0 then sqrt(-x) else sqrt(x)
> >
> > DEPENDS on the not taken path having no effect on the
> > taken path.
> >
> > Therefore, I argue that the result of max() should be
> > decorated with the selected thing (or things, in the
> > case of overlapping intervals) & discard the unselected
> > items.
> >
> > So, what is the answer to f(sqrt([-2,-1]),sqrt([-1,1]),
> > sqrt([4,9]))?
> >
> > The intermediate result is max({empty,undefined},
> > {[0,1],discontinuous},{[2,3],defined&continuous}).
> >
> > The tracking philosophy would have us return {[2,3],
> > undefined}. The static philosophy would have us return
> > {[2,3],defined&continuous}.
> >
> > Which is more imformative? The one that correctly tells
> > us that SOME calculation was undefined even though it did
> > not participate in the final result? Or the one that WAS
> > the final result?
> >
> > Note that the answer is NOT a slam dunk. It COULD be that
> > one of the unselected answers WAS unselected due to a bug
> > in the code as easily as because the programmer always
> > intended that it not be selected. Tracking warns us of
> > both the bug & the false positive. Static ignores both.
> >
> > So it requires some thought to decide which is best.
> >
> > What do you think?
> >
> > Dan
> >
> >>
> >> George,
> >> IMHO your examples are not illustrative of argument in favor of some
> >> philosophy.
> >> They show how problems must be reformulated when interval arithmetic is
> >> aimed
> >> Corliss, George a écrit :
> >> > Dan,
> >> >
> >> > Thank you for the useful characterization. I, too, began assuming
> >> > tracking, but I am coming more to the static view.
> >> >
> >> > Early in AD, a frequently cited difficulty was scaling:
> >> >
> >> > x is a vector
> >> > s = max(|x|)
> >> > x = x / s // Normalize
> >> > y = lots of computations
> >> > y = y * s // Rescale back
> >> >
> >> > Is y a differentiable function of x? AD is forced to assume not.
> >> > Intervals can help decide this question more precisely, but the analogy
> >> > is whether we care about the history or only the result.
> >> >
> >> When x is replaced with a box X, the scaling factor must be calculated
> >> for the box as a whole, so it a constant for all the vector in the box.
> >> So the problematic dependence of s with a particular vector is removed.
> >>
> >> > Or, suppose
> >> > x is a scalar
> >> > f(x) = sign(x)
> >> > y = 0 * f(x)
> >> >
> >> > Is y a continuous function of x?
> >> >
> >> This problem is ill-posed.
> >> The interval arithmetic provide a correct enclosure of the exact result.
> >> Since sign is discontinuous , the continuity is definitely lost for
> >> future calculation
> >> exactly in the same way a the result of a interval arithmetic
> >> calculation may provide a heavy overestimation of the the exact result.
> >>
> >> The rule must be
> >> the system must not lie
> >> Nothing more.
> >>
> >> Best regards,
> >>
> >> Dominique
> >>
> >> > I am becoming a static-ist.
> >> >
> >> > George
> >> >
> >> > On May 25, 2011, at 6:17 AM, Dan Zuras Intervals wrote:
> >> >
> >> >
> >> >>> Date: Tue, 24 May 2011 19:05:38 -0500
> >> >>> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
> >> >>> To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> >> >>> CC: John Pryce <j.d.pryce@xxxxxxxxxxxx>,
> >> >>> stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> >> >>> Subject: Re: Ar we succeeding?
> >> >>>
> >> >>> All,
> >> >>>
> >> >>> Does someone else also have an opinion concerning this (please)?
> >> >>>
> >> >>> Baker
> >> >>>
> >> >>>
> >> >> Baker, et al,
> >> >>
> >> >> I find I do have an opinion on this. And as long as Nate's
> >> >> motion is in its discussion period, now is as good a time
> >> >> as any to discuss it.
> >> >>
> >> >> Let me put it in the form of a question I put to Nate:
> >> >>
> >> >> Is your philosophy about decorations a tracking approach or
> >> >> a static approach?
> >> >>
> >> >> There seem to be two schools of thought about the meaning
> >> >> of decorations.
> >> >>
> >> >> There is the TRACKING school in which decorations are the
> >> >> maximal (most pessimistic) result of the tree of evaluations
> >> >> that led up to the result to which they are attached. That
> >> >> is, every exceptional or noteworthy incident in that tree is
> >> >> recorded for all to see whether it is relevant to the final
> >> >> result or not.
> >> >>
> >> >> Then there is the STATIC school in which decorations are
> >> >> information concerning the current result only. Earlier
> >> >> decorations may pass through to this result if they still
> >> >> apply & may be discarded if they do not. In this case the
> >> >> decoration must be able to be interpreted in the context
> >> >> of the final result whatever happened before.
> >> >>
> >> >> (In either school, the decoration must be ordered WRT to
> >> >> subsets of arguments. I believe this is both necessary &
> >> >> sufficient for an FTDIA to be proved.)
> >> >>
> >> >> I asked this question of Nate because his motion seemed to
> >> >> be primarily of the tracking school but with some static
> >> >> features thrown in.
> >> >>
> >> >> I think we need to be consistent on this point. As much
> >> >> for our own understanding as to explain the meaning of
> >> >> decorations to the rest of the world.
> >> >>
> >> >> I will admit that I started out in the Tracking school.
> >> >> But some remarks I've heard in this forum & privately have
> >> >> suggested to me that the Static school might serve us better
> >> >> as a standard.
> >> >>
> >> >> So I ask of all of you: Which philosophy should we espouse?
> >> >> Tracking or Static?
> >> >>
> >> >> I believe that once we decide this many of our more
> >> >> difficult questions will fall out as obvious.
> >> >>
> >> >> Yours,
> >> >>
> >> >> Dan
> >> >>
> >> >
> >> > Dr. George F. Corliss
> >> > Electrical and Computer Engineering
> >> > Marquette University
> >> > P.O. Box 1881
> >> > 1515 W. Wisconsin Ave
> >> > Milwaukee WI 53201-1881 USA
> >> > 414-288-6599; GasDay: 288-4400; Fax 288-5579
> >> > George.Corliss@xxxxxxxxxxxxx
> >> > www.eng.mu.edu/corlissg
> >> >
> >> >
> >> >
> >>
> >>
> >> --
> >> Dr Dominique LOHEZ
> >> ISEN
> >> 41, Bd Vauban
> >> F59046 LILLE
> >> France
> >>
> >> Phone : +33 (0)3 20 30 40 71
> >> Email: Dominique.Lohez@xxxxxxx
> >