-We describe existing and anticipated future benefits of an end-to-end methodology for annotating formal RDF statements representing temporal knowledge to be extracted from text, as well as for authoring and validating test and/or application queries to exercise that knowledge. Extraction is driven by a target ontology of temporal and domain concepts supporting an intelligence analyst's timeline tool. Both the tool and the methodology are supported at several points by an implemented temporal reasoning engine, in a way that we argue ultimately advances machine reading technology by increasing both sophistication and quality expectations about temporal annotations and extraction.
Machine reading—that is, automatic extraction of formal knowledge from natural language text—has been a longstanding goal of artificial intelligence. Effective extraction into RDF has the potential to make targeted knowledge accessible in the semantic web. We recently supported a largescale evaluation of temporal knowledge extraction from text by providing RDF/OWL ontology for target statements and a corresponding reasoning engine for query answering. Along the way, we discovered… • How inference could improve annotation—the manual extraction of formal temporal statements—and question authoring for evaluation or for applications. • How, coupled with annotation and question authoring processes, inference could ultimately drive more sophisticated machine reading capabilities.
II. TEMPORAL KNOWLEDGE REPRESENTATION AND
REASONING FOR TIMELINE DEVELOPMENT
Our temporal logic is based loosely on the event calculus
[
A time interval is a convex collection of time points— intuitively, an unbroken segment of a time line. Time intervals begin and end with time points, which may be constrained relative to each other or relative to a calendar. The ontology includes a rich set of relational properties over time points and intervals, and the reasoning engine will calculate tightest inferable bounds between any two points and will detect contradictory time point relation sets.
A fluent is an object-level, domain statement (e.g., FluentA: attendsSchool(Jansa LubljanaUniversity)) whose truth value is a function of time. It is taken to be true at time points where it holds and not to be true at time points where it does not hold. We reify a fluent in an observation—a meta-level statement whose object is a fluent, whose subject is a time interval, and whose predicate is a holds property (e.g., holdsThroughout(FluentA Interval1), when FluentA is observed over Interval1, corresponding to, say, September, 1980).
The events of interest to us, which we call transition events, occur at individual time points and may cause one or more fluents to change truth value. We represent events (like the birth of Jansa) as objects with attribute properties like agent, patient, and location, and we relate events to time intervals with an occurs property (e.g., occursAt(BirthOfJansa Point2), where Point2 is associated with an interval corresponding to the date September 17, 1958). As usual with the event calculus, such events can initiate fluents (e.g., occursAt(BirthOfJansa Point2) initiates FluentB: alive(Jansa Interval3), where Interval3 is begun by Point2) or terminate them (e.g., DeathOfJansa… ). The temporal reasoning engine implements appropriate axioms to perform fluent initiation and termination.
Note that an observer may report information about the temporal extent of a fluent without communicating anything about initiation or termination. E.g., if text says Abdul and
know when Abdul or Hasan may have moved to or from
emigrated in 2007, we use the properties clippedBackward and clippedForward regarding the fluent residesInGPE-spec(Abdul BeirutLebanon) to indicate initiation and termination by anonymous (unrepresented) transition events, so that we can also initiate or terminate temporally under-constrained likefluent observations (e.g. Abdul lived in Beirut during the 1990s).
The reasoning engine’s implementation, using AllegroGraph, Allegro Prolog, and Allegro Common Lisp from Franz, Inc., can answer any conjunctive query. While not yet heavily optimized, it is at least fast enough to support machine reading system evaluation over newspaper articles where crossdocument entity co-reference is not required.
The combined extraction and reasoning capability was conceived to support an intelligence analyst’s timeline tool in which a GUI would be populated with statements about entities (e.g., persons) of interest extracted from text. Our evaluation of machine reading capabilities was based on queries similar to those we would have expected from such a tool’s API. It also supposed the analysts could formulate their own, arbitrary questions, such as Query 1: Find all persons who were born in
III. LESSONS LEARNED AND REALIZED IN IMPLEMENTATION This indirect, query answering style of machine reading evaluation makes it especially important that we perform effective quality control of formal queries in the context of the formal statements we expect to be extracted from answerbearing documents. We thus developed the test query validation approach illustrated in Figure 1. Considering Query 1’s formalization (see Figure 10 in section IV.B), it’s worth noting that we used the methodology illustrated here to debug a number of subtle errors occurring in our earlier (manual) formulations. When each such formulation did not result in the answers expected, we traced inference to identify a point of failure, corrected this, and then iterated until correct.
Our machine reading technologists told us early on that they preferred macro-level relational interfaces that would streamline away micro-level details of time points and intervals. We thus provide a language of flexible specification strings (spec strings) that expand to create time points, intervals, and relations inside our reasoning engine. We also provide ontology to associate the temporal aspects Completed, Ongoing, and Future with fluents (e.g., he used to live there vs. he is living there vs. he is going to live there) and with the reporting dates of given articles, to afford a relational interface reasonably close in form to natural language sources. For the Completed or Future aspects, we also can capture quantitative lag or lead information (e.g., he lived there five years ago or he will move in five days from now).
IV. LESSONS LEARNED WITH IMPLEMENTATION PROPOSED Here, we propose some further approach elements that we expect to lead to high-quality temporal annotations, including…
A. Interfaces and workflows deliberately designed to support capture of all statements specified as extraction targets (see section A) B. Graphical time map display including fluents and events (see section B) • On-line inference to elucidate interrelationships and potential contradictions • Visual feedback to let users help assure quality themselves • Time map-based widgets supporting user knowledge entry C. Technology adaptable to test or application question authoring (see section C) D. Quantitative temporal relation annotation evaluation (see section V.A).
Fluents are simple statements that we can readily represent in RDF. The example in Figure 2 focuses on the fluent about one Janez Jansa attending Ljubljana University—only on the fluent, not the full observation including temporal information (i.e., only that Jansa attends the school, not when). The technology needed to annotate such information is well understood and (excepting perhaps the last bullet about modality) has been well enough exercised that we may routinely expect good results. This includes multi-frame GUIs where a user can produce stand-off annotations by highlighting text and by clicking in drop-down boxes select relations, classes, and instances. In part because these tools have preceded reading for formal knowledge extraction, they may not use our intended representation internally—i.e., they may for historical reasons internally use a representation (e.g., XML that is not RDF) tailored to linguistic phenomena rather than associated with any formal ontology.
Diagnose KR&R issues. . e z i l a m r o F
Document Manually author selected statements to support expected inference.
Query Formalize query.
Answer(s)
Execute query to get results.
Apply temporal reasoning engine. . s r e w s n a e r a p m o C Figure 1. We validate test queries by making sure that natural language (NL) and formal knowledge representation (KR) versions of documents, queries, and answers agree, diagnosing and debugging as necessary.
Source text Reporting
date Dec 28, 2007… …Jansa graduated from Ljubljana University in 1984… …Jansa graduated from Ljubljana University…
Formalization 1. 2. 3. 4.
attendsSchool(Janez_Jansa Ljubljana_University) 1. Select one of time interval or point. 2. Capture any beginning date and backward
clipping info. 3. Capture any ending date and forward
clipping info. 4. Capture any duration info.
reporting date: a. Capture reporting aspect. b. Capture any reporting lag info.
Fluent clipped forward at ending point attendsSchool(Janez_Jansa Ljubljana_University)
There is no duration information. (We don’t know how long Jansa was at school.) • The ending point is well before the reporting date, so we skip to the next step. • There is no other relevant temporal information. • To indicate clipping, the graphic fills the time point symbol (making it solid).
Our reasoning engine expands the entered coarse date 1984 into earliest and latest possible calendar dates bounding the observation’s ending point. It also infers an upper bound on its beginning time point.
As illustrated in Figure 4, we invoke a similar workflow for event occurrence. Because our representation for events is simpler than that for observations, this workflow has fewer steps. Our ontology treats birth as a fluent transition event—it occurs at a given time point, and it causes a transition of the vital status of the person born (from FuturePerson to Alive). Our graphical representation here accordingly just depicts a single time point (not an interval). We can use basically the same workflow to capture a non-transition event (e.g., a legal trial) that occurs over more than one time point. BirthEvent(Janez_Jansa, Ljubljana) 1958-09-17 1. Select event type. 2. Specify argument identifiers,
respecting co-reference. 3. Select / highlight / designate
corresponding text. 4. Capture any hypothetical modality
info. 5. Capture any date info.
unconstrained w.r.t. reporting date:
Figure 5 illustrates a time map including both the birth
event and the school attendance fluent from earlier figures. It
also suggests functional requirements to be satisfied
automatically/by default and upon user demand. Note that we
now have automatically displayed—from on-line temporal
inference—a lower bound on the fluent observation’s
beginning date: Jansa could not have attended school until after
he was born. (The “day” time point granularity used in our
machine reading evaluation leads to some non-intuitive effects,
like not being alive until the day after one is born. We can
easily correct this using an interval constraint propagation
arithmetic including infinitesimals [
The time map displayed in Figure 6 includes all the information from the source text that is necessary to answer Query1. The last fluent observation (at bottom right, where Jansa is prime minister) exercises workflow steps that earlier time map elements don’t. We have no ending date for this observation, but we do have present tense reference to Jansa as the prime minister, so we appeal to the reporting aspect
on November 9, 2004, we can bound the observation’s beginning point.
Slovenia national election day 2004, per user-established relative temporal
reference Our user also has entered the election event. An election is not necessarily a fluent transition event, at least in that an elected candidate does not always take office immediately. So, we rely on the user to establish relative temporal reference between the election event and the fluent observation’s beginning. See the depicted constraint, whose entry is illustrated in Figure 7. Establishing relative temporal reference requires the selection of a pair of time points and/or intervals to be related and of an appropriate temporal relation between them. Here, we just need the time point at which the election occurs to be less than or equal to the time point at which Jansa takes office.
While a few common relations may be all that most users
will ever need, we do have a lot of relations [
Figure 8 shows formal statements that would be created directly by the user’s actions (i.e., not also including those created indirectly by inference) in entering the information reflected in our finished time map. We have highlighted fluents and some other key statements, each of which appears near several related statements. Our time map represents Jansa’s birth event in a non-standard way, repeated here in different color type, beside the italicized, standard statements. We have not similarly formalized the event of Jansa’s election as PM, and Figure 8 includes just statements about that event’s point of occurrence.
Clearly, we can do a lot of formal work for the user behind the scenes. 2000 2000
BirthEvent(?person, Ljubljana) 1950-01-01 1959-12-31
Query 1: Find all persons who were born in Ljubljana in the 1950s and attended Ljubljana University in the 1980s, the titles that they held, the organizations in which they held these titles, and the maximal known time periods over which they attended and held these titles. attendsSchool(?person Ljubljana_University) ?attendanceIntervalSpec 1980-01-01
1989-12-31 personHasTitleInOrganization(?person ?title ?org) ?titleIntervalSpec
We might reuse much of the same machinery in a question authoring interface, in which a user can formalize a query, as illustrated for Query1 in Figure 9. This time map display is even less cluttered than the one for this query’s supporting statements, for a couple of reasons.
• We are making general statements, rather than specific ones, so don’t use as many dates or long identifiers. Rather, we use variables (here beginning with ?). •
We are asking about only one answer (set of variable values satisfying the query) at a time. The supporting statements in our earlier time map include three separate sets of bindings for the variables ?title and ?org.
We have introduced intervals to represent the 1950s and the 1980s, and we have selected time point/interval relationships appropriate to the query’s conditions. These relationships are associated with particular idioms used in our formalization in Figure 10. hasPersonBorn(?birth ?person) hasBirthEventGPE-spec(?birth ?GPEspec) hasCityTownOrVillage(?GPEspec ljubljana_Ljubljana_Slovenia) hasTimeIntervalSpecString(?I_range_birth [1950-01-01,1959-12-31]) occursWithin(?birth ?I_range_birth) hasTimeIntervalSpecString(?I_range_school [1980-01-01,1989-12-31]) holdsWithin(?F_school ?I_range_school) maximallyHoldsThroughout(?F_school ?I_school) hasTimeIntervalSpecString(?I_school ?attendanceIntervalSpec) ?F_title: personHasTitleInOrganization(?person ?title ?org) maximallyHoldsThroughout(?F_title ?I_title) hasTimeIntervalSpecString(?I_title ?titleIntervalSpec) Our query asks about the “maximal known time periods” over which the fluents hold, and we associate (via a query authoring workflow step) an “interval spec” variable with each fluent’s observation interval. Per our formalization, this will be bound, on successful query execution, to a string that describes lower and upper bounds on the observation interval’s beginning point, ending point, and duration. The formalization uses the properties occursWithin (for born in the 1950s) and holdsWithin (for attended school in the 1980s) to accommodate the temporal relations selected for the query authoring time map. We know to use maximallyHoldsThroughout (vice the less restrictive holdsThroughout) for the fluents’ observation intervals because the query’s author has included (via the invoked widget) associated spec string variables.
Thus, it appears that we might enable non-specialists to author effective test queries (or, in a transition/application setting, domain queries), without requiring the intervention of a KR specialist. One angle on this proposed work might be to determine the extent to which readers who are not (temporal) knowledge representation specialists can perform such tasks consistently—alternatively, to determine the amount of training (e.g., pages of documentation, number of successfully completed test exercises) required to qualify an otherwise-nonspecialist to perform the task well. That said, rather than “dumb down” the task, to accommodate non-expert readers, we propose to ratchet up annotator performance expectations—to achieve the highest-quality results possible so that we can drive research regarding extraction of temporal knowledge by machines from text to new levels of sophistication. The machine reading researchers whose systems are under evaluation quite reasonably ask, before they embark on a mission of technological advancement, “Is this task feasible for humans, with acceptable consistency?” We’d like to answer that question in the best way that we can.
V. RELATED WORK AND PROPOSED ADVANCES
Beyond test questions and answers, the entire machine
reading community would benefit from having a large volume
of good temporal logic annotations available. Time is a key
topic in language understanding, engendering much current
community interest. TimeML [
Others have applied limited temporal reasoning in postprocessing of temporal annotations, to…
A. Compute the closure of qualitative pairwise time interval relations, as one step in assessing a machine reader’s precision and recall performance (see section A) B. Ascertain the global coherence of captured qualitative relations (see section B).
Our implementation can go further, as described below.
Evaluating temporal annotations typically has been limited
to (Allen’s [
Our temporal reasoning engine, which is point-based, naturally accommodates arbitrary bounds on the metric durations that separate time points and uses global constraint propagation to calculate earliest and latest possible dates/times for any point (including the beginning and ending points of all temporal intervals), as well as tightest bounds on durations.
This approach also usually affords sufficient global
perspective for a robust recall statistic. Adapting the standard
approach for evaluating interval relations [
Only when every member of a set of points is unrelated to the calendar (i.e., we have only point ordering and interval duration information) do we lack calendar bounds supporting meaningful recall assessment. Then, however, by choosing any point in a connected set to serve as a reference (in place of the calendar), we can apply the same approach as above.
It may reasonably be argued that at some threshold of representational complexity the brute force transitive closureand-spanning tree approach to computing recall and precision of an extracted knowledge base (set of statements) must become impractical. Our quantitative temporal statements are certainly richer than the typical qualitative ones, and (depending on knowledge base size) we may be pushing up against this threshold with them. Our query answering evaluation paradigm is more broadly applicable, presuming inference over extracted statements remains tractable—for the queries of interest.
Waiting until annotation is done to infer bounds and detect
contradictions neglects opportunities to give annotator’s (e.g.,
time map-based) feedback and receive their best-effort
corrections. As Bittar et al. [
We have outlined existing and anticipated future benefits of an end-to-end methodology for… • Annotating formal RDF statements representing temporal knowledge to be extracted from text • Authoring and validating test and/or application queries to exercise that knowledge.
These capabilities are supported by an implemented temporal reasoning engine. They and the engine are intended to support a timeline tool conceived for use by intelligence analysts. We have explained how these benefits can advance machine reading technology by increasing both sophistication and quality expectations about temporal annotations and extraction.
Thanks to other participants in DARPA’s Machine Reading research program—especially to other members of the SAIC evaluation team, including Global InfoTek (the author’s former employer).