From: Jerry Hobbs (hobbs@ai.sri.com)
Date: 08/29/02
Below is a description of a treatment of temporal granularity that
emerged from a discussion I had with Rich Fikes and Richard Waldinger.
It is intended to be an element of a DAML ontology of time. I would
value any feedback anyone feels moved to provide.
Thanks.
-- Jerry Hobbs
Temporal Granularity
Useful background reading for this note includes
Richard Fikes and Qing Zhou, "A Reusable Time Ontology"
Jerry Hobbs, "Granularity", IJCAI-85, or
http://www.ai.sri.com/~hobbs/granularity-web.pdf
Jerry Hobbs et al., "A DAML Ontology of Time",
http://www.ai.sri.com/daml/daml-time-29jul02.text
Very often in reasoning about the world, we would like to treat an
event that has extent as instantaneous, and we would like to express
its time only down to a certain level of granularity. For example, we
might want to say that the election occurs on November 5, 2002,
without specifying the hours, minutes, or seconds. We might want to
say that the Thirty Years' War ended in 1648, without specifying the
month and day.
For the most part, this can be done simply by being silent about the
more detailed temporal properties. Suppose we have the function
"time-span-of(e)=t" relating events to temporal entities, the relation
"temporal-description-of(d,t)" relating a temporal entity to a
description of the clock and calendar intervals it is included in, and
the functions "second-of(d)", "minute-of(d)", "hour-of(d)",
"day-of(d)", "month-of(d)", and "year-of(d)". Suppose we know that an
event occurs on a specific day, but we don't know the hour, or it is
inappropriate to specify the hour. Then we can specify the day-of,
month-of, and year-of properties, but not the hour-of, minute-of, or
second-of properties. For example, for the election e, we can say
time-span-of(e) = t, temporal-description-of(d,t), day-of(d) = 5,
month-of(d) = 11, year-of(d) = 2002
and no more. We can even remain silent about whether t is an instant
or an interval.
Sometimes it may be necessary to talk explicitly about the granularity
at which we are viewing the world. For that we need to become clear
about what a granularity is, and how it functions in a reasoning
system.
A granularity G on a set of entities S is defined by an
indistinguishability relation, or equivalently, a cover of S, i.e. a
set of sets of elements of S such that every element of S is an
element of at least one element of the cover. We will identify the
granularity G with the cover.
(A G,S)[cover(G,S) <--> (A x)[x in S <--> (E s)[s in G & x in s]]]
Two elements of S are indistinguishable with respect to G if they are
in the same element of G.
(A x1,x2,G)[indisting(x1,x2,G) <--> (E s)[s in G & x1 in s & x2 in s]]
A granularity can be a partition of S, in which case every element of
G is an equivalence class. The indistinguishability relation is
transitive in this case. A common case of this is where the classes
are defined by the values of some given function f.
(A G,S)[G = f-gran(S,f)
<--> [cover(G,S) & (A x1,x2)[indisting(x1,x2,G)
<--> f(x1) = f(x2)]]]
For example, if S is the set of descriptions of instants and f is the
function "year-of", then G will be a granularity on the time line that
does not distinguish between two instants within the same calendar
year.
A granularity can also consist of overlapping sets, in which case the
indistinguishability relation is not transitive. A common example of
this is in domains where there is some distance function d, and any
two elements that are closer than a given distance a to each other are
indistinguishable. We will suppose d takes two entities and a unit u
as its arguments and returns a real number.
(A G,S)[G = d-gran(S,a)
<--> [cover(G,S) & (A x1,x2)[indisting(x1,x2,G)
<--> d(x1,x2,u) < a]]]
For example, suppose S is the set of instants, d is duration of the
interval between the two instants, the unit u is *Minute*, and a is 1.
Then G will be the granularity on the time line that does not
distinguish between instants that are less than a minute apart. Note
that this is not transitive, because 9:34:10 is indistinguishable from
9:34:50, which is indistinguishable from 9:35:30, but the first and
last are more than a minute apart.
Both of these granularities are uniform over the set, but we can
imagine wanting variable granularities. Suppose we are planning a
robbery. Before the week preceeding the robbery, we may not care what
time any events occur. All times are indistinguishable. The week
preceeding the robbery we may care only what day events take place on.
On the day of the robbery we may care about the hour in which an event
occurs, and during the robbery itself we may want to time the events
down to ten-second intervals. Such a granularity could be defined as
above; the formula would only be more complex.
The utility of viewing the world under some granularity is that the
task at hand becomes easier to reason about, because distinctions that
are possible in the world at large can be ignored in the task. One
way of cashing this out in a theorem-proving framework is to treat the
relevant indistinguishability relation as equality. This in effect
reduces the number of entities in the universe of discourse and makes
available rapid theorem-proving techniques for equality such as
paramodulation.
We can express this assumption with the axiom
(1) (A x1,x2)[indisting(x1,x2,G) --> x1 = x2]
for the relevant G. For a temporal ontology, if 0-length intervals
are instants, this axiom has the effect of collapsing some intervals
into instants.
There are several nearly equivalent ways of viewing the addition of
such an axiom -- as a context shift, as a theory mapping, or an an
extra antecedent condition.
Context shift: In some formalisms, contexts are explicitly
represented. A context can be viewed as a set of sentences that are
true in that context. Adding axiom (1) to that set of sentences
shifts us to a new context.
Theory mapping: We can view each granularity as coinciding with a
theory. Within each theory, entities that are indistinguishable with
respect to that granularity are viewed as equal, so that, for example,
paramodulation can replace equals with equals. To reason about
different granularities, there would be a "mediator theory" in which
all the constant, function and predicate symbols of the granular
theories are subscripted with their granularities. So equality in a
granular theory G would appear as the predicate "=_G" in the mediator
theory. In the mediator theory paramodulation is allowed with "true"
equality, but not with the granular equality relations =_G. However,
invariances such as
if x =_G y, then [p_G(x) implies p_G(y)]
hold in the mediator theory.
Extra antecedent condition: Suppose we have a predicate
"under-granularity" that takes a granularity as its one argument and
is defined as follows:
(A g)[under-granularity(g)
<--> (A x1,x2)[indisting(x1,x2,g) --> x1 = x2]]
Then we can remain in the theory of the world at large, rather than
moving to a subtheory. If we are using a granularity G, rather than
proving a theorem P, we prove the theorem
under-granularity(G) --> P
If the granularity G is is transitive, and thus partitions S, adding
axiom (1) should not get us into any trouble. However, if G is not
transitive and consists of overlapping sets, such as the episilon
neighborhood granularity, then contradictions can result. When we use
(1) with such a granularity, we are risking contradiction in the hopes
of efficiency gains. Such a tradeoff must be judged on a case by case
basis, depending on the task and on the reasoning engine used.
This archive was generated by hypermail 2.1.4 : 08/29/02 EDT