From: Jerry Hobbs ([email protected])
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