We describe the process of interpreting tables at a general level that should be applicable to a wide variety of tables in a wide variety of text types. The implementation of the process was optimized specifically for military messages, and our examples come primarily from military messages. In Section 4 we discuss some problems that have to be faced as the implementation is extended to other domains.
The process of interpreting tables consists of five steps:
Each of these steps is discussed in turn.
Subheads. The subheads that were identified in the recognition phase are distributed through the records that they subsume, becoming another field in those records. For example, Table 1 is transformed into the following:
FIELD EXERCISES WERE CONDUCTED BY THE FOLLOWING UNITS:
UNIT HOME BASE LOCATION
21 MAY 94 1ST MECH INF BN FT SAM HOUSTON LAFAYETTE
21 MAY 94 2ND MECH INF BN FT LEWIS BATON ROUGE
22 MAY 94 3RD MECH INF BN MONTEREY LAFAYETTE
Recognizing Entity Type. The rules in the system that are used to recognize types of entities are applied to the individual items in the table. Any constraints on where the entity names can be located in a sentence are lifted. Where the item has an ambiguous type, multiple readings are maintained at this stage. In our application, the entity types includes dates, units, facilities and locations.
The system then seeks to resolve the ambiguities by maximizing the consistency of all the entities in the field across the records in the table. That is, for each field it is determined which type is consistent with the maximum number of items. For example, in the above table, it may be that MONTEREY is listed in the lexicon as both a facility and a location. Since the other two items are both facilities, the facility reading would be chosen for MONTEREY.
When it is impossible to interpret the items in a field in a consistent fashion, certain coercions are permitted. One of these coercions for the military message application is a coercion from locations to facilities. Suppose, for example, that MONTEREY were listed in the lexicon only as a location. Then since the other two items in that field are facilities and there is a legal coercion from locations to facilities, that coercion would be applied.
Although we do not recognize columns separated by only one space, we overcome this shortcoming by allowing more than one entity in each field of the table. For example, in Table 3, we would allow the field of the second column to contain the items ``Year Year''. These would then be treated as if they were two separate items.
Using Headers for Disambiguation. Limited use is made of headers for disambiguating the type of items in a field. The top line of the table has the same structure as every other line, but it is viewed as a possible header line, labelling each of the fields. If the items in that line are not recognizable entity names but are recognizable names of entity types, then the line is assumed to be a header. In some cases the name of the entity type provides the information for determining the entity type in that field. For example, in the fourth field of Table 3, LAFAYETTE could be either a ship or a location. The fact that the header says LOCATION leads us to conclude that the entities are locations, not ships. Similarly, UNIT leads us to conclude that the items in the second field are units, and HOME BASE that the items in the third field are facilities.
The headers are used only for disambiguation, rather than as the principal evidence for the type of the items in the field. The reasons for this are that frequently there are no headers, and that often when there are they do not provide an unambiguous or even interpretable identification of the entity type.
Hypothesizing the Most Plausible Relation. The central problem in interpreting tables is in discovering the implicit relation that obtains among the items in each record of the table, in a way that is consistent across the records of the table. By the time this stage of processing is reached, the items have been disambiguated as to type, in a way that is consistent across the records, so there is no problem in determining a relation that is consistent across the table. We only need to find the most likely relation among the set of entity types that occurs in the records.
This process necessarily requires a domain model. The model we use is a fairly general one--a labelled graph in which the nodes correspond to entity types and the arcs correspond to possible relations between them. The system places the entity types found in the records of the table in this graph and then seeks to minimize the spanning tree covering these nodes. The minimal spanning tree corresponds to the hypothesized relation among the entities. (This is called the Domain Information for the records of the table.) Where a connection cannot be formed, the item in the table is ignored. This seems appropriate; very often some information in the table falls outside the domain model.
In the military message application, the system must recognize the names of units, locations, facilities, equipment, and times, among other things. It must recognize relations among these entities, and it must recognize events in which these entities participate.
There is a limited set of possible relations among entities, such as
Unit is at Facility.
Unit is at Location.
Unit moves from Location to Location.
Facility is at Location.
Equipment is at Facility or Location.
Unit has Equipment.
An ``at'' relation or a ``move'' event is at a Time.
In Table 3, the minimal spanning tree linking up times, units, and locations is one corresponding to the unit being at the location at a time. Since it is known that the facilities listed are not at the locations listed, no connection can be found between the facilities and the other items. This field is discussed further in the next section.
This stage of the processing can be viewed as a limited, tractable form of abduction. The items in the table constitute the data to be explained. The graph encodes the possible explanations. Choosing the minimal spanning tree is a way of choosing a minimal, or a best, explanation.
Pretabular Sentences: The pretabular sentences are parsed and analyzed just as every other sentence in the text is. In ordinary text the system looks for particular patterns that represent events and relationships and builds up the corresponding Domain Information. The one difference is that where in ordinary sentences we are looking for patterns involving names of entity tokens, in the pretabular sentences we are also allowing patterns with entity types. For example, the pretabular sentence of Table 3 is just like the ordinary sentence
FIELD EXERCISES WERE CONDUCTED BY THE 1ST MECH INF BN.
For such an ordinary sentence the system builds a Domain Information encoding the type of event and the participants in the event. For a pretabular sentence, the same structure is built, but the entity types are only parameters, and the structure is instantiated once for each record of the table, with the parameterized entity replaced with the corresponding entity of the same type in that record. That is, for each record in the table, the Domain Information for that record is unified with the Domain Information for the pretabular sentence.
Our processing of pretabular sentences is done almost as an afterthought, after the relation among the elements in the table has already been hypothesized. One might think that instead the system should use the pretabular sentence to drive the interpretation of the table. There are three reasons this would not be a good idea. First, very often there is no pretabular sentence describing its structure. Second, most of the time the table contains more information than is described in the pretabular sentence. For example, in Table 3 the records contain fields for times, units, facilities, and locations, but only units are mentioned in the pretabular sentence. Third, the pretabular sentence frequently refers to entity types that are not found in the table.