1.1
On the Web we can nd a vast amount of structured data, represented in
tables that contain relevant information. Despite the huge corpus of such tables
on di erent topics, they set limitations on arti cial intelligence tasks, such as
semantic search and query answering. This is the reason why some approaches
started to propose extraction, annotation and transformation of tabular data
into machine-readable formats. In particular, in the last years, there has been a
ton of works on the annotation of tabular data, also known as Semantic Table
Interpretation (STI), which can be mainly classi ed as supervised (they exploit
already annotated tables for training) [
annotate tables, such as semantic classi cation of columns, which classi es a column either as a literal or as a named entity. Besides the approach, we propose MantisTable tool, a web interface and an open source Semantic Table Interpretation tool that automatically annotates, manages and makes the semantic of tables accessible to humans and machines. This tool is independent of any particular context. Additional built-in guidance functionalities help to avoid common pitfalls and to create correct annotations. Although a STI contains several steps, as will be explained in the next section, the key feature of our approach is the involvement of all the STI steps that run fully automatically. This approach and tool were developed by one PhD student and two master's students. 1.2
The MantisTable approach implements STI steps through ve phases: 0. Data Preparation, which aims to prepare the data inside the table; 1. Column Analysis, whose tasks are the semantic classi cation, that assigns types to columns (NE-column or L-column), and the detection of the subject column (S-column); 2. Entity Linking, which deals with mappings between cells and entities in a
KG; 3. Predicate Annotation, whose task is to nd relations, in the form of predicates, between the main column and the other columns to set the overall meaning of the table; 4. Concept and Datatype Annotation, which deals with mappings between columns and semantic elements (concepts or datatypes) in a KG.
To describe each phase of the STI approach we consider Table 12, which lists video games with additional information, such as publisher, release date, etc.
Table 1. Table with a list of video games extracted from Round 1.
Title Donkey Kong Country Super Castlevania IV DoReMi Fantasy: Milon's DokiDoki Adventure Hudson Soft 2008-09-05 (900 Wii Points) ...
Publisher EU Release Date AU Release Date PEGI ACB Nintendo 2006-12-08 2006-12-07 7 G Konami 2006-12-29 2006-12-29 3 PG 2008-09-05 3
G
Data Preparation aims to clean and uniform data inside the table.
Transformations applied to tables are as follows: deletion of HTML tags and some
characters (i.e. " `), transformation of text into lowercase, deletion of text in
brackets, resolution of acronyms and abbreviations, and normalisation of units
of measurement. To decipher acronyms and abbreviations, the Oxford English
Dictionary3 is used. The normalisation of units of measurement is performed by
applying regular expressions, as described in [
Column Analysis whose tasks are the semantic classi cation that assigns types to columns that are named entity (NE-column) or literal column (Lcolumn), and the detection of the subject column (S-column). The rst step of the Column Analysis phase is to identify good L-column candidates. To accomplish this task, we consider 16 regular expressions that identify several Regextypes (e.g. numbers, geo coordinate, address, hex color code, URL). If the number of occurrences of the most frequent Regextype in a column exceeds a given threshold, that column is annotated as L-column, otherwise, it is annotated as NE-column. The second step deals with the subject column detection that takes into account the identi ed NE-columns. We can de ne the S-column as the main column of the table based on di erent statistic features, like Average Number of Words (aw) in each cell, Fraction of Empty Cells (emc) in the column, Fraction of Cells with Unique content (uc) and Distance from the First NE-column (df). These features are combined to compute the subcol(cj ) score for each NE-column as follows: emcnorm(cj ) subcol(cj ) = 2ucnorm(cj ) + awnorm(cj ) pdf (cj ) + 1 (1)
The column with the highest score will be selected as the S-column for the considered table. The values of the features for the S-column detection related to the video games table (Table 1) are shown in Table 2. In this case the Title column is the S-column of the table (Table 3).
Entity Linking deals with mappings between the content of cells and entities in the KG. The original version of MantisTable used a naive approach: we employed a SPARQL query considering only the entities for which, within the values of rdf:type, it was possible to nd the label of the winning class. If more than one entity was returned for a cell, the one with a smaller edit distance (i.e. Wagner-Fischer distance) was taken. Between Round 3 and Round 4 we developed a more e ective approach, which is described below. In the new approach we consider the table entities row by row. To discover the mappings for each cell in a row we take a set of eligible entities from the KG. We de ne as eligible all the entities which label contains the cell's content or contains the cell's tokens as shown in Listing 1.1. By converting this information to a graph representation we nd all the paths that, starting from a eligible entity of the cell's subject, enter into a eligible entity of the cell's object of the row. To increase the accuracy we also try to match the literal cells with the literals in the subject cell's candidate entities: that is, we seek for a match between literals in the table and eligible entities by using a simple matching algorithm. This algorithm distinguishes between three main datatypes: dates, numbers and strings. While dates and strings are matched exactly, numeric matching is done using an approximated matching algorithm: a pair of numbers makes a match if the distance (the absolute di erence) between the two is less than a threshold. To pick the winning entities we apply to each path a score de ned in the following way:
P Sr(pi) = jjpijj + (1 jjpijj X editDistance(tx(j; r); ej;r)) j (2) where P Sr is the path score of row r, pi is an eligible path found, jjpijj is the length of the path de ned as the number of vertices contained in the path and editDistance(tx(j; r); ej;r) is the edit distance (Levenshtein) between cell content and eligible entity. Then eventually we take the path with the maximum score.
Listing 1.1. SPARQL query to retrieve a set of eligible entities for a cell's content. ??ss ?rpdfs?:o.label ? label .
? label <bif : contains > '(< cell value >) '. } UNI??OssN ?r{pdfs?o:.label ? label .
? label <bif : contains > '(< token > AND <token > [ AND <token >]) '. } UNION {
OPTIO?NaAlLtNa{me rdfs : label ? lab .
???slaalb?tNpa<m?beoif.:dbcoon:twaiiknisP>age'R(e<dtiokreenct>s A?NDs. <token > [ AND <token >]) '.
Predicate Annotation, whose task is to nd relations in the form of predicates, between the Subject column and the other columns, to set the overall meaning of the table. MantisTable approach considers the set of predicates found in the Entity Linking phase and takes the predicate with maximum frequency.
columns headers and semantic elements (concepts or datatypes) in a KG. Our approach reuse the information extracted by the linking phase (linked entities).
For each winning entity (Eij ) we pick the associated concepts (rdf:type), then for each column we build a dictionary Cj where each rdf:type have associated the number of rows of the table containing that concept divided by the total number of entities found for that column. We use a threshold set at 40% of the maximum score, the concepts with a score lower then this threshold are discarded. Table 4 show an example of this scoring.
With the concept list obtained in this way, we build a concept graph representing the hierarchy between them as shown in Figure 1. To identify the winning connected component within this graph, we take the maximum result of the following formula (connected component score) applied to each component: CCScore(CCi) =
X conceptScore(n) n2CCi (3) therefore therefore
where CCi is the ith connected component and conceptScore is a function that returns the corresponding concept score.
After this step, in order to complete the column annotation task we pick the path of the winning connected component which maximizes the score. We de ne the path's score in the following way, where p is a path of concepts de ned as c1; c2; ; cn.
n pathScore(p) = X conceptScore(pi)
i
This method is being used to reinforce the identi cation of winning concepts in spite of the presence of noisy data or contingent errors in the knowledge base.
Without loss of generality let's consider the example in Table 4 and Figure 1. To calculate the score for the Person and Place connected components we calculate CCScore as in Equation 3.
CCScore(P ersonCC) = conceptScore(P erson) + conceptScore(Athlete)+ conceptScore(P olitician) + conceptScore(Golf P layer) (4) CCScore(P laceCC) = conceptScore(P lace) + conceptScore(P opulatedP lace)+ conceptScore(Settlement) + conceptScore(City) CCScore(P ersonCC) = 0:7 + 0:3 + 0:3 + 0:5 = 1:8
CCScore(P laceCC) = 0:3 + 0:3 + 0:3 + 0:3 = 1:2 so the winning connected component will be PersonCC.
Now let's see how path's score on PersonCC is computed. Let's pick some paths on this connected component de ned as p1 = P erson; P olitician and p2 = P erson; ; Golf P layer, then the score is computed in the following way: score(p1) = conceptScore(P erson) + conceptScore(P olitician) score(p2) = conceptScore(P erson) + conceptScore(Athlete)+
conceptScore(Golf P layer) score(p1) = 0:7 + 0:5 = 1:2 score(p2) = 0:7 + 0:3 + 0:3 = 1:3 so our method choose the p2 path as the winning concept annotation. 2
As described above, the MantisTable approach has been integrated into a web application developed with Python and the Django. A MongoDB database acts as table and KG repository. The code is freely available through a Git repository4. In order to achieve the scalability of the application, and therefore improve e ciency, MantisTable has been installed in a Docker container to achieve parallelisms at the application level and to facilitate the deployment on servers. The management of resources is performed by using Task Queues (i.e. Celery Workers5). The ve phases of the STI have been modularly implemented, allowing an easy replacement or extension by other developers. 2.1
To participate in the challenge we made some changes as follows: i) MantisTable was originally developed to support the JSON format for loading tables and for exporting results. In order to take part in the challenge, we developed a new parser for managing the CSV tables. During this phase, we encountered several problems in the management of di erent characters encoding; ii) since target columns (columns to be annotated) were provided during the challenge, we disabled most of the Column Analysis phase (i.e. subject column detection); iii) our solution was made to identify just one correct Class per column, so we made a new export script with di erent criteria for the selection of concepts, also considering the hierarchy of these in the KG.
3
In this section, the MantisTable approach's results in Round 1, Round 2, Round 3 and Round 4 of the challenge will be discussed. F1 and F2 in the following tables are referred to F1-Score and Precision for CEA and CPA Tasks in every Round and CTA in Round1 while they are referred to AH-Score and AP-score for CTA task in the Rounds from 2 to 4.
In the rst round MantisTable achieved the results in Table 5. The results are good, in particular in the CEA task. In the second round MantisTable achieved the results in Table 6.
In Round 2 we particularly focused on the CTA task because it was crucial to our initial algorithm for the other steps; we used the results of the Concept Annotation to lter the results in the CEA and CPA tasks. About the CEA task, it is possible that during the parsing and the cleaning of data some rows were misplaced in di erent indexes. We didn't have much time to look into it but we are sure that we could have done a better job in this task using other resources for disambiguation (e.g. DBpedia or Wikidata). Most of the considerations we did in Round 2 are no longer valid with the new approach.
In the third round MantisTable achieved the results in Table 7. The results are better than the previous round both in the precision and in the F1-Score but the CEA and CPA tasks still have low precision due to too many falsepositives: regarding the CEA task our approach did not have enough contextual information to discriminate between eligible entities, while for the CPA task our approach su ered for the entity linking.
In the fourth round MantisTable achieved the results in Table 8. To overcome the lack of contextual information needed by the linking phase, we changed our approach as described in the previous sections gaining a considerable precision boost for both the CEA and CPA tasks compared to previous rounds.
The results of CEA and CPA tasks with the new method are shown in tables 9 and 10.
Unlike the state of the art approaches, MantisTable i) provides a comprehensive solution to support all annotations steps; ii) provides an unsupervised method to annotate independent tables; iii) generates context for disambiguation; iv) provides a tool to support STI work ow and a tool to support the evaluation by providing validation indicators which are both publicly available. In relation to the results obtained in Round 4, we are going to change the work ow of our tool to better implement the methods for the CEA and CPA tasks. We are also going to develop a way to process tables via remote API calls to allow easier third party integration.