Re: (now VERY long) Re: Tetrits and "stickiness"
> Date: Fri, 16 Apr 2010 07:35:19 -0500
> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> CC: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>, stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: (now long) Re: Tetrits and "stickiness"
>
> Dan et al,
>
> On first reading, my own preference would be with your original
> tetrit proposal ({T,F} {T}, {F}, {}}, and duplicating it (with
> an extra bit) to have both a sticky copy and a non-sticky copy.
> The reason is because the proposal you just made seems less
> intuitive. Furthermore, although I may not fully understand
> it yet, it seems that it blurs the distinction between some
> points in the present arguments having the property while
> other points in the present arguments do not, versus points in
> the present arguments having the property while points in
> the past arguments do not.
>
> Baker
Baker,
You know, after Nate's last posting, I have been thinking
along similar lines. At least in so far as coming to a
greater understanding of the meaning of, & relationships
among these states. The 'blurred distinction' you speak of
is something that bothers me as well. Perhaps that can also
be cleared up by looking at all 3 bits.
This is going to be a very long note so get comfortable &
set aside some time to read it.
But if you want to skip it, the Reader's Digest version is
that I will conclude that Baker is right & we should have
all 3 bits for each decoration.
First, I disagree with Nate that there needs to be a total
ordering among the states in the sense of a ranking. Indeed,
there cannot be & maintain the FTIA.
Since Nate & I disagree on the T/F assignment of states,
let me refer to them by descriptive names rather than T/F
pairs.
And if I can use <<== as a shorthand for \subset, we must
have both of:
{noPointsAtAll} <<== {inDomain} <<== {bothInAndOut}
{noPointsAtAll} <<== {outDomain} <<== {bothInAndOut}
for subintervals of a given interval. But inDomain & outDomain
have no relationship with one another in this sense. And if
noPoints still represents only the empty interval, I realize
that it cannot come up in a branch & bound method but the
relationship must exist all the same to maintain the FTIA.
Also, I erred when I said that outDomain & bothInAndOut were
interconvertable WRT subintervals. While bothInAndOut can be
subsetted either to inDomain or outDomain, outDomain cannot be
subsetted to bothInAndOut. Nate pointed this out as well.
Still, there was something about the way he spoke of sticky
that bothered me & I have been cogitating on the matter for
the better part of a day to come to a better understanding
of just what bothered me. I fear it may be something that
is common in interval methods that might be exposed by the
use of decorated intervals.
Let me explain.
Let's start with some point function g() defined over the
Reals. More pedantically, let g be defined to take R into
R in any fashion at all really but it would be best to
confine our thinking to continuous functions defined on
some large contiguous subset of the Reals (like sqrt() on
[0,+oo), for example). This is generally written as:
g: R --> R
and an instance of the mapping is written as w = g(z).
Now, to be even MORE pedantic about it, this is considered
a mapping from some space called the z-space which is
equivalent to a subset of the Reals onto AN ENTIRELY
DIFFERENT SPACE called the w-space which also happens to
be equivalent to a subset of the Reals.
I realised that the thing that was nagging at me was a
casual way of thinking & speaking about things in the z
& w spaces as if they were the same thing.
They are not.
But I can see how this might be a natural thing to do.
After all, any fixed point algorithm counts on an
identification between the two spaces (essentially some
kind of mapping from w back to z) in order to properly
subset things in the z-space to narrow down your search
for the fixed point.
Also, if interval programmers are used to working with
undecorated intervals they would have no problem just
plugging some ww = gg(zz) back into something in the
z-space to find the next step. Say zz' = ww \and zz.
But, if you don't mind the criticism, this is sloppy
thinking. Natural & understandable but sloppy.
You have only to assign units to things to understand why.
Define g: t --> m to be the train schedule for a particular
train on a particular line. The input t-space (measured in
seconds) is equivalent to a subset of the Reals. The output
m-space (measured in meters or kilometers) is ALSO equivalent
to an ENTRELY DIFFERENT subset of the Reals. The function
g() maps the time onto the position of the train at that time.
So, m = g(t) is the train schedule.
Obviously information in the m-space has no business being
compared to (or added to) anything in the t-space. It is
meaningless to even consider such a thing.
And yet, we can meaningfully construct algorithms that map
from m-space to t-space. Newton's method is an example.
If I should want to discover the time (in secs) the train
will pass a particular place (in meters) that lies between
two stations I want to solve the equation g(t) - m0 = 0
where m0 is that place. The Newton's iteration works if
you pay attention to the units. Starting from an initial
guess t0 (in secs) we have:
t' (secs) <-- t0 (secs) -
(g(t0) - m0) (meters) / g'(t0) (meters/sec)
The derivative provides us with our mapping from m-space
back into t-space by giving us a mapping with the proper
units (meters/sec, in this case).
So things will work but one must not be sloppy.
Further, if we decorate the intervals, the decorations will
expose that sloppiness.
And this is the second thing that was nagging me about how
sticky things were being spoken of.
If decorations are to do their job of monitoring the 'health'
of the g: z --> w mapping, then if g is broken down into its
component parts:
g1: z --> z1, g2: z1 --> z2, ..., g: zn --> w,
the sticky property we seek is something that carries useful
information all along that path until we get to w.
The problem is that, once we get to w, the decorations we
have picked up along the way are a statement about the
mapping in w-space. And these statements HAVE NO MEANING
back in z-space.
(If we carried a decoration like 'leftTheTrack', if we find
that m > mEndOfTheLine, back into t-space it makes no sense
as there ARE no tracks or endOfTheLine in t-space.)
That means that if we were to plug a w object back into
a z object we would carry senseless decorations along with
us & contaminate our understanding of the z-space with
nonsense.
This is another part of a misunderstanding that is out there
whether stated or not.
An implication of this is that I believe we will need an
identity function of sorts. Something that maps a
decorated interval onto another decorated interval with
the same interval part but with the decorations part
'cleansed' of any meaning not appropriate to the interval
itself.
Specifically, 'identity' takes a decorated interval onto
a decorated interval. The domain of 'identity' is [entire].
It is everywhere continuous. The interval part of the result
is the same as the interval part of the operand. (Un)bounded
operands are mapped onto (un)bounded results. And all sticky
decorations are cleared on the mapping. (Perhaps others as
well but that will depend on the name of the decoration.
Let's lock that down at a later date, please.)
This means that some fixed point method can go ahead & use
ww = gg(zz) to narrow zz via mappings like zz' = identity(ww)
\and zz.
(In this case, identity() is performing the same function as
the derivative was performing in the Newton's iteration. So
now we can find WHEN the train left the track without being
screwed up by decorating all subsets of [tStart,tEnd] with
'leftTheTrack'.)
Which I believes cures ANOTHER problem I was having in my
discussion with Nate. Specifically the way he spoke of the
need for decorations to stick in a particular way in order
for branch & bound methods not to fail.
OK, now that I've gone through all that crap, let me turn
to the issue you raise of wanting to look at both of the
non-sticky bits for clarity's sake.
Let's do that very carefully & see what happens. Again, I am
making this up as I go along & don't really know how it will
come out yet.
(Actually, while I made it up as I went along, I made several
passes over it to correct stuff. Stuff I could find, anyway. :-)
Let me characterize these states in the T/F notation again
(forgive me Nate) not to foist that approach on anyone but
so that I can enumerate them & know that I've looked at
them all. Let me further write their meaning as if they
were being used in a dyadic function. It is not that
important, really, but it is easier to see the monadic
definition in the dyadic than the other way around.
And, since I think part of why my previous exposition was
'less intuitive' was due to the use of the generic 'property'
decoration, let me use 'domain' instead. That way we can all
easily see what we're talking about in our heads.
(After writing all of the following I realized that some of
the conclusions I draw are appropriate to the domain decoration
only. Specifically, which return [empty] & which do not. So
it may have been a mistake to confine this discussion just to
the domain decoration. But I've done it now. Let's look at it
& consider what it all means for the other decorations later.)
So, what do we have? (Remember, outSticky is the only one
that's sticky.)
Wait a minute. I am re-reading this after a break & I just
realize that or'ing outSticky with THIS operation's outDomain
loses us some potentially useful information. Namely whether
or not THIS operation had a domain problem. So I am going to
redefine it as follows & redo all that follows. Its more work
for me that you will never see but that's what I get for
writing this on the fly. :-)
The net effect is that we will go from 6 possible states to
8 & the new states differentiate between current domain errors
& previous ones.
+------ 'inDomain' = {There exists x in xx & y in yy such
| that (x,y) is in the domain of g(x,y)}
| +---- 'outDomain' = {There exists x in xx & y in yy such
| | that (x,y) is NOT in the domain of g()}
| | +-- 'outSticky' = outDomain(xx) \or outdomain(yy) \or
| | | outSticky(xx) \or outSticky(yy)
v v v Meaning
- - - -------
F F F No points, never was, [empty] & always has been.
F F T No points, also [empty], one operand was [empty] while
the other one was outDomain or outSticky. Looks like
this state can only be reached by a dyadic function.
I'm glad I decided to check that. :-)
F T F Completely outside the domain of this function but no
previous function had that problem. Returns [empty].
F T T Completely outside the domain of g(), also [empty],
also was outside the domain of some previous function.
T F F Completely inside the domain of g() & as well as inside
the domain of all previous functions. This is the
good state we all like to see.
T F T Completely inside the domain of g() but some previous
function was not so lucky. This is also a good state
of sorts. A domain error once happened but it hasn't
bothered g(). This may or may not be of interest to
the user but it looks like something that is good to
know.
T T F Both inside & outside the domain of g() but no previous
function suffered a domain error. Any problems are g's
fault alone. This state & the next are states you
likely start with in branch & bound methods.
T T T We have points both inside & outside the domain of g()
& had problems in the past. This is the other state
you start with on branch & bound.
So, of 8 possible, all 8 are now possible. (It was 6 before.)
The first 4 return [empty] & the last 4 return non-empty
results, entirely dependent on inDomain. Interesting. Every
other state (the ones with outSticky set) are 'sticky' states
in the sense that once you get into one it is not possible to
go back to a outSticky = F state for subsequent operations.
And, while ranking (in the sense of a total ordering) has no
meaning there are the following subset possibilities for
subintervals of a given interval. That is, what are the
possible decoration(g,xx) if xx <<== yy & we know
decoration(g,yy)? (And, xx != yy. Just to be clear. :-)
FFF <<== FTF <<== TTF
FFF <<== TFF <<== TTT
FFT <<== FTT <<== TTF
FFT <<== TFT <<== TTT
I have to admit this looks a little spooky to me. I'll think
on this a bit more later.
Ignoring subset issues, there IS a state transition diagram
from possible operand states to possible result states. Let
me enumerate the 8 monadics first before I tackle all 64
dyadics.
operand --> possible results
------- ----------------
FFF --> FFF
FFT --> FFT
FTF --> FFT
FTT --> FFT
TFF --> FTF, TFF, TTF
TFT --> FTT, TFT, TTT
TTF --> FTT, TFT, TTT
TTT --> FTT, TFT, TTT
It looks like FFF (empty, no errors) is a start state in the
sense that the only way to get there is to start there. One
state FFT (empty with a previous domain error) is a terminal
state in that once you get into it you cannot get out again.
The 4 non-sticky states (outSticky = F) preceed the 4 sticky
states (outSticky = T) in the sense that once you get into
the latter states you cannot get back to the former again.
And the 2 states TFT & TTT (inDomain = T, previous error) can
interconvert until they leave to a FTT (inDomain = F) which
becomes a FFT (kind of the universal empty) & stays there.
Nate, these interconverting states are not a problem for the
issue you raised. You were concerned with interconverting
states for the decorations of a single g(). These states can
interconvert in the sense of being able to transition to one
another along a g1 --> g2 --> ... --> g path. Thus each state
has some meaning in its context & no meaning in the previous
context. It contributes to the next context only with the
sticky bit. And since the sticky bit is set for both these
states, that ALSO has no meaning.
I can see I will need to draw a diagram before all this
becomes clear. But let me look at the dyadic transitions
first. It seems likely that it will become more complex
there.
One thing that IS clear is that the information of whether
or not there has been a domain error up to now is found in
(outDomain \or outSticky). Something to remember when it
comes to writing the predicates.
Hmm. I see I don't have to check all 64 possible states. For
even if g(x,y) does not commute with g(y,x) the decorations
DO commute. So I only need to check 36 states along the
upper triangular submatrix.
That's something.
Here goes:
(Tell ya what, ignore the table. Now that I come to fill it
out it turns out to be not too bad. Go ahead & skip to my
summary after the table.)
op1 x op2 --> possible results
--- --- ----------------
FFF x FFF --> FFF
FFF x FFT --> FFT
FFF x FTF --> FFT
FFF x FTT --> FFT
FFF x TFF --> FFT
FFF x TFT --> FFT
FFF x TTF --> FFT
FFF x TTT --> FFT
FFT x FFT --> FFT
FFT x FTF --> FFT
FFT x FTT --> FFT
FFT x TFF --> FFT
FFT x TFT --> FFT
FFT x TTF --> FFT
FFT x TTT --> FFT
FTF x FTF --> FFT
FTF x FTT --> FFT
FTF x TFF --> FFT
FTF x TFT --> FFT
FTF x TTF --> FFT
FTF x TTT --> FFT
FTT x FTT --> FFT
FTT x TFF --> FFT
FTT x TFT --> FFT
FTT x TTF --> FFT
FTT x TTT --> FFT
TFF x TFF --> FTF, TFF, TTF
TFF x TFT --> FTT, TFT, TTT
TFF x TTF --> FTT, TFT, TTT
TFF x TTT --> FTT, TFT, TTT
TFT x TFT --> FTT, TFT, TTT
TFT x TTF --> FTT, TFT, TTT
TFT x TTT --> FTT, TFT, TTT
TTF x TTF --> FTT, TFT, TTT
TTF x TTT --> FTT, TFT, TTT
TTT x TTT --> FTT, TFT, TTT
There that wasn't so painful was it.
It turns out there is a unique transition FFF x FFF --> FFF.
Kind of the 'virgin empties keep to themselves in pairs'
transition. Thus FFF may be regarded as the empty start
state.
All other combinations with at least one empty lead to FFT,
another empty with some previous outSticky retained. So FFT
is the terminal state for all things that go bad & eventually
return empty.
Among the non-empty states, there is the unique transition
TFF x TFF --> FTF, TFF, TTF. Which one depends on whether
(x,y) is outDomain, inDomain, or both, respectively for g().
So long as you continue to TFF x TFF --> TFF, nothing has
gone wrong ever, now or before. But as soon as you enter
either FTF or TTF, you have encountered a domain error so
your very next state will be a xxT sticky state. So TFF is
the start state for non-empty intervals.
All other non-empty combinations go to FTT, TFT, or TTT.
Again, depending on whether (x,y) is outDomain, inDomain,
or both.
So, that's not so bad after all.
I still want to draw a state transition diagram but I think
even the dyadic picture will be simple enough to read.
The subset ordering is the same as with the monadics.
FFF <<== FTF <<== TTF
FFF <<== TFF <<== TTT
FFT <<== FTT <<== TTF
FFT <<== TFT <<== TTT
And now I see what bothered me before: the sticky bit has no
meaning here in that among subsets there is no state transition
from one to another that retains decoration information. So I
think it might be best to ignore the 3rd bit & just say we have
FF <<== FT <<== TT &
FF <<== TF <<== TT
which is the same as
{noPointsAtAll} <<== {inDomain} <<== {bothInAndOut}
{noPointsAtAll} <<== {outDomain} <<== {bothInAndOut}
that we discussed before all this started.
OK, now that I've done all this work, let me cogitate on it
a bit more before I post it. Maybe something will come up
that I've missed.
Well, I've slept on it & the only new thing I've discovered
is something about the difference between this & the one that
Baker found 'less intuitive'.
You can convert from these states to the less intuitive form
by or'ing together the last two bits. Thus, the mapping is
FFF --> FF
FFT, FTF, FTT --> FT
TFF --> TF
TFT, TTF, TTT --> TT
And the old state diagram mostly works. But for one likely
important confusion. By conflating the TFT state (previous
domain error only) & the TTF state (domain error here)
together with the TTT state (both), we can no longer tell
them apart. While that might not seem too important for
branch & bound methods it IS important to debugging, IMHO.
If I can't tell where an error originates it becomes MUCH
harder to track it down. Or, for that matter, eliminate it
as unimportant.
So, I think maybe Baker is right. Perhaps we should keep all
3 bits around.
Two final thoughts.
First, after I was well into it, I realized that much of this
discussion is specific to the decoration 'domain'. In
particular, which states end up returning [empty] & which do
not. This would not happen for 'bounded' or 'continuous', for
example. Thus, the state transition diagram is likely to look
different for the other decorations. Something for a future
discussion, I think.
Finally, I have been working on making state transition graphs.
They are mostly just pretty pictures but since I think visually
they are a great help to me in understanding how all this works.
I am making them using Sage & its ability to plot directed
graphs. But they are crude & I don't have the bugs out of it
yet so I'll wait before I post them. Further, for all I know
you guys are going to hate this entire idea & all that work will
be for nothing. Another reason to wait.
OK, that's everything.
Sorry for the long post. I get carried away sometimes.
It probably won't be the last time. :-)
Take care,
Dan