Vast amounts of information is encoded in structured tables found in documents, on the Web, and in spreadsheets or databases. Integrating or searching over this information bene ts from understanding its intended meaning. Evidence for a table's meaning can be found in its column headers, cell values, implicit relations between columns, caption and surrounding text but also requires general and domain-speci c background knowledge. We represent a table's meaning by mapping columns to classes in an appropriate ontology, linking cell values to literal constants, implied measurements, or entities in the linked data cloud (existing or new) and discovering or and identifying relations between columns. We describe techniques grounded in graphical models and probabilistic reasoning to infer meaning (semantics) associated with a table. Using background knowledge from the Linked Open Data cloud, we jointly infer the semantics of column headers, table cell values (e.g.,strings and numbers) and relations between columns and represent the inferred meaning as graph of RDF triples. We motivate the value of this approach using tables from the medical domain, discussing some of the challenges presented by these tables and describing techniques to tackle them.
This research was supported in part by NSF awards 0326460 and 0910838,MURI award FA9550-08-1-0265 from AFOSR, and a gift from Microsoft Research.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. This article was presented at the workshop Very Large Data Search (VLDS) 2011.
Copyright 2011
uments. Cafarella et al. [
Many real world problems and applications can bene t from
exploiting information stored in tables including evidence
based medical research [
Presently medical researchers perform keyword based search
on systems such as PubMed's MEDLINE which end up
producing many irrelevant studies, requiring researchers to
manually evaluate all of the studies to select the relevant ones.
Figure 1 obtained from [
In this paper, we present techniques to infer the intended
meaning of tables by jointly inferring the semantics of
column headers, table cell values (e.g., strings and numbers),
relations between columns, augmented with background
knowledge from open data sources such as the Linked Open
Data cloud [
Early work in table understanding focused on extracting
tables from documents and web pages [
Wang et al. [
Ventis et al. [
Limaye et al. [
The framework we present is complete automated interpretation of a table that focuses on all aspects of a table - column headers, row values, relations between columns. Our framework will not only tackle strings but also handle literals and work across multiple domains - web tables, medical and open government data.
One might be tempted to think that regular text processing might work with tables as well. After all tables also store text. However that is not the case. It is said that tables store information in a \structured form". It is this very structure used to represent the data, that hinders systems from understanding the intended meaning of a table. To di erentiate between text processing and table processing consider the the text \Barack Hussein Obama II (born August 4, 1961) is the 44th and current President of the United States. He is the rst African American to hold the o ce." The overall meaning can be understood from the meaning of words in the sentence. The meaning of each word can be can be recovered from the word itself or by using context of the surrounding words. Now consider the table in Figure 2 which has data on the eradication rates for di erent treatment regimens for a disease, in this case H-pylori. The abbreviations in the row header of the table represent the di erent treatment regimens and the abbreviations in the column headers represent the di erent types of analyses used in the clinical trial. The data values in the table indicate the number of patients cured for a particular regimen and under a particular analysis. There is often additional information encoded in the table which is not directly evident, for example in this table the drugs used in the treatment are some combination of a Proton pump inhibitor drug and antibiotics.
It is clear from this example that true meaning associated with a table is often encoded in its structure, column (and row) headers of the table, the relations implicit between the various columns and the values (string or literal) in the table. Evidence to what a table means may also come from the caption associated with it as well as the free text surrounding the table.
How does one interpret what the column (or row) headers, data values intend to convey? Expanding the abbreviations in the row headers will produce strings that map to existing entities from a knowledge base. For example OA will map to dbpedia:Omeprazole and dbpedia:Amoxicillin. A combination of drugs in the given string indicates that the string is a type of dosage or treatment regimens. Once all the row headers are disambiguated, using information from the Linked Open Data cloud, we can infer additional information encoded in the table that all the drugs are combination of a Proton pump inhibitor and antibiotics.
The numbers in the rst column of the table in Figure 2 and the way they are represented indicate that it is some form of a count/total. Using this evidence along with the City Baltimore Philadelphia New York
Boston
Mayor S.C.Rawlings-Blake
M.Nutter M.Bloomberg
T.Menino \City"@en is rdfs:label of dbpedia-owl:City. \State"@en is rdfs:label of dbpedia-owl:AdminstrativeRegion. \Baltimore"@en is rdfs:label of dbpedia:Baltimore. dbpedia:Baltimore a dbpedia-owl:City. \MD"@en is rdfs:label of dbpedia:Maryland.
dbpedia:Maryland a dbpedia-owl:AdministrativeRegion.
evidence provided by the row headers and the expanded form
of the abbreviation ITT, it can be inferred that the column
header maps to dbpedia:Intention to treat analysis which is
a type of yago:ClinicalTrials. Once it is known that the
row headers represent dosages and column one represents a
type of analysis in a clinical trials, it can be inferred that
the data values in column one represent eradication rate for
some disease for a given dosage. That some disease in our
example would be known from the caption of the table.
Consider the table shown in Figure 3. The column
headers suggest the type of information in the columns: city
and state might match classes in a target ontology such
as DBpedia [
Column four in this table presents literal values. The numbers in the column are values of the property dbpedia-owl:populationTotal and this property can be associated with the cities in column one. All the values in the column are in the range of 100,000. They provide evidence that the column may be representing the property population. Once relation between column one and column four is discovered, we can also look up on DBpedia, where the linked cities in column one will further con rm that the numbers represent population of the respective cities.
Producing an overall interpretation of a table is a complex task that requires developing an overall understanding of the intended meaning of the table as well as attention to the details of choosing the right URIs to represent both the schema as well as instances. We break down the process into following tasks: a) assign every column (or row header) a class label from an appropriate ontology b) link table cell values to appropriate LD entities, if possible c) discover relationships between the table columns and link them to linked data properties d) generate a linked data representation of the inferred data.
In the following sections, we rst present a baseline system that we developed to evaluate the feasibility in tackling the table interpretation problem. Later we present techniques for building a framework which overcomes the shortcomings in the baseline system and a framework grounded in the principles of graphical models and probabilistic reasoning. Finally we discuss challenges posed by tables in medical literature and present some techniques for dealing with them.
The baseline system is a sequential, multi-step framework
that rst maps every column header to a class from an
appropriate ontology. Using the predicted class as additional
evidence, it then links table cell values to entities from the
Linked Data Cloud. The nal step in the framework is
discovering relations between table columns and generating a
linked data representation of the table's meaning.
Mapping column header to class. In a typical well
formed table, each column contains data of a single
syntactic type (e.g., strings) that represent entities or values of
a common semantic type (e.g., people, places, yearly salary
in USD). The column's header, if present, may name or
describe the semantic type or perhaps a relation in which the
column values participate. The algorithm determines the
class for a table column based on the class of the individual
strings in the column. For all the cell values in every
column of the table, the algorithm submits a complex query to
the Wikitology [
Linking table cells to entities. Using the predicted class labels as additional evidence, for every table cell, the algorithm for linking table cell to entities, re-queries our KB. For every table cell, the KB returns the top N possible entities. For each of the top N entities, the algorithm generates a feature vector consisting of the entity's KB score, entity's Wikipedia page length, entity's page rank, the Levenshtein distance between the entity and the string in the query and the Dice score between the entity and the string. The set of feature vectors for each table cell are ranked using a SVMRank classi er. To the highest rank feature vector from SVM rank, two more features are added - the SVM rank score of the feature vector and the di erence in SVM-Rank scores between the top two feature vectors. A second SVM classi er decides whether to link the table cell to this top ranked entity or not. If the evidence is not strong enough, it is likely that the table cell is a new entity not present in the KB; this step is useful in discovery of new entities in a given table. If the evidence is strong enough, the table cell is linked to the top ranked entity returned by SVM-Rank. Discovering relation between columns. Once the table cells are linked, the framework identi es relations between table columns. For every pair of column, the algorithm generates a set of candidate relations from the relations that exist between the strings in each row of the two columns by querying DBpedia. The relation that gets majority vote is chosen as the relation between the columns.
Linked data representation. We have developed a
template for annotating and representing tables as linked RDF.
We choose the N3 serialization because it is compact and
readable. The second part of Figure 3 shows an example
of a N3 representation of a table. To associate the column
header with its predicted class label, the rdfs:label property
from RDF Schema [
Evaluation of the baseline system. The baseline system was evaluated against 15 tables obtained from Google Squared, Wikipedia and from a collection of tables extracted from the Web. Excluding the columns with numbers, the 15 tables have 52 columns and 611 entities for evaluation of our algorithms. We used a subset of 23 columns for evaluation of relation identi cation between columns.
In the rst evaluation of the algorithm for assigning class labels to columns, we compared the ranked list of possible class labels generated by the system against the list of possible class labels ranked by the evaluators. For 80.76 % of the columns the average precision between the system and evaluators list was greater than 0 which indicates that there was at least one relevant label in the top three of the system ranked list. The mean average precision for 52 columns was 0.411.For 75 % of the columns, the recall of the algorithm was greater than or equal to 0.6. We also assessed whether our predicted class labels were reasonable based on the judgement of human subjects. 76.92 % of the class labels predicted were considered correct by the evaluators. The accuracy in each of the four categories is shown in Figure 4. 66.12 % of the table cell strings were correctly linked by our algorithm for linking table cells. The breakdown of accuracy based on the categories is shown in Figure 4. Our dataset had 24 new entities and our algorithm was able to correctly predict for all the 24 entities as new entities not present in the KB. We did not get encouraging results for relationship identi cation with an accuracy of 25 %.
The baseline system makes local decision at each step of the framework. The disadvantage of such a system is that error percolates from the previous phase to the next phase which can lead to an overall poor interpretation of a table. To overcome this problem, we are developing a framework that performs joint inference over the evidence available in the table and jointly assign values to the column headers, table cell values and relations between columns.
Probabilistic graphical models [
Variables in the system. The column headers, the table cell values and the relations between columns in the table represent the set of variables in the table interpretation framework.
Graphical Representation. We choose a Markov network based graphical representation,since the interaction between the column headers, table cell values and relation between table columns are symmetrical. The interaction between a column header and cell values in the column is captured by inserting an edge between the column header and each of the values in the column in the graph. To correctly disambiguate what a table cell value is, evidence from the rest of the values in the same row can be used. This is captured by inserting edges between every pair of cell values in a given row. Similar interaction exists between the column headers and is captured by the edges between every pair of table column headers.
A parametrized Markov network. To represent the distribution associated with the graph structure, we need to parametrize the structure. One way to parametrize a Markov network is representing the graph as a factor graph. A factor graph is an undirected graph containing two types of nodes : variable nodes and factor nodes. The graph has edges only between the factor nodes and variable nodes. A factor node captures and computes the a nity between the variables interacting at that factor node. Variable nodes can also have associated \node potentials". Our parametrized graph (Figure 5) consists of two node potentials (associated with each of the column headers and table cell values) and three factor nodes.
The node potential for column header variable computes the a nity between the string in the column header and the class its being mapped to. The node potential for table cell value computes the a nity between the string in the table cell and the entity its being linked to. The function of the three factor node is as follows: the rst factor node computes a nity between the class being assigned to the column header and the entities linked to the cell values in the column; the second factor node computes the a nity between the classes that have been assigned to all the column headers; and the third factor node computes the a nity between the entities linked to the cell values in a given row. We are presently working on de ning the functions in the factor node that will compute the a nity between the values assigned to the various variables in the system.
Results of our baseline system demonstrated feasibility in interpreting tables as proposed above. In the following section we present techniques for dealing with challenges posed by tables in the medical literature and how such tables can be adapted to be processed using our existing techniques. Abbreviations. Tables from the medical literature tend to use abbreviations a lot, primarily to represent dosages, type of analyses used in the clinical trials, types of tests conducted and so on. Like in table 2, the meaning of the abbreviations are often encoded in the table caption. A pre-processing step would involve processing the table caption to generate abbreviations and their expansions and then replacing the abbreviations in the table.
Literals. Literals pose a unique challenge, especially for tables from medical literature. We demonstrated how strings in a column can be used as evidence in a table interpretation framework. But what about literals like numerical data values in a table? To begin with, the range of numbers in a given column can start providing evidence about what the column is. For example if the numbers are in the range of 100s' then the column could be percentages or ages. The row (or column) header may have additional clues. For example, in the case of percentages, the % sign maybe associated with the numbers in the table cell or it may be present in the row (or column) header in the table.
This brings us to next thing that needs to be extracted from such tables - units associated with numbers. The units associated with numerical data is either encoded in the row (or column) header of the table or caption of the table. An important step will be identifying the individual units to be associated with numerical data in the table.
Finally numerical data is often represented in pairs. Formats like number/count, number(%), % (number), number,unit are some examples of how numerical data is encountered in tables in medical literature. The meaning of this format is present again in the table caption or in the table header. Table Interpretation. A useful interpretation of tables used in meta-analysis would be identifying and linking the drugs used in the treatment, identifying the type of analyses performed, success rate, identifying and linking to the disease(s) under consideration, adverse events in the treatments if any and generating a linked data representation of it. Once the \pre-processing steps" mentioned above, some of our existing techniques can be adapted to link the row and column headers to either classes or entities from a knowledgebase and then generating the requisite linked data interpretation of the table.
Generating an explicit representation of the meaning implicit in tabular data will support automatic integration and more accurate search. Clues for a table's intended meaning are present in column and row headers, cell values, implicit relations between columns, and any descriptive text. We described general techniques grounded in graphical models and probabilistic reasoning to infer a table's meaning relative to a knowledge base of general and domain-speci c knowledge expressed in the Semantic Web language OWL. We represent a table's meaning as a graph of OWL triples where the columns have been mapped to classes, cell values to literals, measurements, or knowledge-base entities and relations to triples. One practical usecase we are studying is representing the meaning of tables found in papers from medical journals. We discussed some of the challenges presented by these tables and described techniques to tackle them.