Effective and efficient Semantic Table Interpretation using TableMiner +

3.1. Legacy tabular data to linked data

Research on converting tabular data in legacy data sources to linked data format has made solid contribution toward the rapid growth of the LOD cloud in the past decade [6,12,19,30]. The key difference from the task of Semantic Table Interpretation is that the focus is on data generation rather than interpretation, since the goal is to pragmatically convert tabular data from databases, spreadsheets, and similar data structures into RDF. Typical methods require manually (or partially automated) mapping the two data structures (input and output RDF), and they do not link data to existing concepts, entities and relations from the LOD cloud. As a result, the implicit semantics of the data remain uncovered.

3.2. General NLP and IE

Some may argue to use the general purpose NLP/IE methods for Semantic Table Interpretation, due to their highly similar objectives. This is infeasible for a number of reasons. First, state-of-the-art methods [17,31] are typically tailored to unstructured text content that is different from tabular data. The interdependence among the table components cannot be easily modeled in such methods [22]. Second and particularly for the tasks of Named Entity Classification and Relation Extraction, classic methods require each target semantic label (i.e., concept or relation) to be pre-defined and learning requires training or seed data [28,40]. In Semantic Table Interpretation however, due to the large degree of variations in table schemata (e.g., Limaye et al. [21] use a dataset of over 6,000 randomly crawled Web tables of which no information about the table schemata is known a priori), defining a comprehensive set of semantic concepts and relations and subsequently creating necessary training or seed data are infeasible.

A related IE task tailored to structured data is wrapper induction [9,18], which automatically learns wrappers that can extract information from regular, recurrent structures (e.g., product attributes from Amazon webpages). In the context of relational tables, wrapper induction methods can be adapted to annotate table columns that describe entity attributes. However, they also require training data and the table schemata to be known a priori.

3.3. Table extension and augmentation

Table extension and augmentation aims at gathering relational tables that contain the same entities but cover complementary attributes of the entities, and integrate these tables by joining them on the same entities. For example, Yakout et al. [38] propose InfoGather for populating a table of entities with their attributes by harvesting related tables on the Web. The users need to either provide the desired attribute names of the entities, or example values of their attributes. The system can also discover the set of attributes for similar entities. Bhagavatula et al. [1] introduce WikiTables, which given a query table and a collection of other tables, identifies columns from other tables that would make relevant additions to the query table. They first identify a reference column (e.g., country names in a table of country population) in the query table to use for joining, then find a different table (e.g. a list of countries by GDP) with a column similar to the reference column, and perform a left outer join to augment the query table with an automatically selected column from the new table (e.g., the GDP amounts). Lehmberg et al. [20] create the Mannheim Search Joins Engine with the same goal as WikiTables but focus on handling tens of millions of tables from heterogeneous sources.

The key difference between these systems and the task of Semantic Table Interpretation is that they focus on integration rather than interpretation. The data collected are not linked to knowledge bases and ambiguity still remains.

3.4. Semantic Table Interpretation

Hignette et al. [14,15] and Buche et al. [2] propose methods to identify concepts represented by table columns and detect relations present in tables in a domain-specific context. An NE-column is annotated based on two factors: similarity between the header text of the column and the name of a candidate concept; plus the similarities calculated for each cell in the column and each term in the hierarchical paths containing the candidate concept. For relations, they only detect the presence of semantic relations in the table without specifying the columns that form binary relations.

Venetis et al. [35] annotate table columns and identify relations between the subject column and other columns using types and relations from a database constructed by mining the Web using lexico-syntactic patterns such as the Hearst patterns [13]. The database contains co-occurrence statistics about the subject and object of triples, such as the number of times the word ‘cat’ and ‘animal’ extracted by the pattern ⟨ ? , such as , ? ⟩ representing the is-a relation between concept and instances. A maximum likelihood inference model predicts the best type for a column to be the one maximizing the probability of seeing all the values in the column given that type for the column. Such probability is computed based on the co-occurrence statistics gathered in the database. Relation interpretation follows the same principle.

Likewise, Wang et al. [36] argue that tables describe a single entity type (concept) and its attributes and therefore, consist of an entity column (subject column) and multiple attribute columns. The goal is to firstly identify the entity column in the table, then associate a concept from the Probase knowledge base [37] that best describes the table schema. Essentially this allows annotating the subject NE-column and literal-columns using properties of the concept, also identifying relations between the subject column and other columns. Probase is a probabilistic database built in the similar way as that in Venetis et al. [35] and contains an inverted index that supports searching and ranking candidate concepts given a list of terms describing possible concept properties, or names describing possible instances. The method heavily depends on these features and the probability statistics gathered in the database.

Muñoz et al. [26] extract RDF triples for relational tables from Wikipedia articles. The cells in the tables must have internal links to other Wikipedia articles. These are firstly mapped to DBpedia named entities based on the internal links, then to derive relations between two entities on the same row and from different columns, the authors query the DBpedia dataset for triples in the form of ⟨ subject , ? , object ⟩ , where subject and object are replaced by the two mapped entities. Any predicates found in the query result are considered as relations between the two entities. The work is later extended in Muñoz et al. [27] by adding a machine learning process to filter triples that are likely to be incorrect, exploiting features derived from both the knowledge base and the text content from the target cells.

Zwicklbauer et al. [46] use a simple majority vote model for column classification. Each candidate entity in the cells of the column casts a vote to the concept it belongs to, and the one that receives the most votes is the concept used to annotate the column. They show that for this very specific task, it is unnecessary to exhaustively disambiguate each cell in a column. Instead, comparable accuracy can be obtained by using a fraction of the cells from the column. However, the sample size is arbitrarily decided.

Syed et al. [7] deal with all three annotation tasks using DBpedia and Wikitology [34], the latter of which contains an index of Wikipedia articles describing entities and a classification system that integrates several vocabularies including the DBpedia ontology, YAGO, WordNet6

Limaye et al. [21] propose to model table components and their interdependence using a probabilistic graphical model. The model consists of two components: ‘variables’ that model different table components, and ‘factors’ that are further divided into node factors modeling the compatibility between the variable and each of its candidate, and edge factors modeling the compatibility between the variables believed to be correlated. For example, given an NE-column, the header of the column is a variable that takes values from a set of candidate concepts; and each cell in the column is a variable that takes values from a set of candidate entities. The node factor for the header could model the compatibility between the header text and the names of each candidate concept; while the edge factor could model the compatibility between any candidate concept for the header and any candidate entity from each cell. The strength of compatibility could be measured using methods such as string similarity metrics [11] and semantic similarity measures [43]. Then the task of inference amounts to searching for an assignment of values to the variables that maximizes the joint probability. A unique feature of this method is that it solves the three annotation tasks simultaneously, capturing interdependence between various table components at inference, while other methods either tackle individual annotation tasks or tackles each separately and sequentially.

Mulwad et al. [24] argue that computing the joint probability distribution in Limaye’s method is very expensive. Built on the earlier work by Syed et al. [7] and Mulwad et al. [23,25], they propose a light-weight semantic message passing algorithm that applies inference to the same kind of graphical model. This is similar to TableMiner⁺ in the way that the UPDATE phase of TableMiner⁺ can be considered as a similar semantic message passing process. However, TableMiner⁺ is fundamentally different since it (1) adds a subject column detection algorithm; (2) deals with both NE-columns and literal-columns, while Mulwad et al. only handle NE-columns; (3) uses an efficient approach bootstrapped by sampled data from the table while Mulwad et al. build a model that approaches the task in an exhaustive way; (4) defines and uses context around tables as features while Mulwad et al. has used knowledge base specific features; (5) uses different methods for scoring and ranking candidate entities, concepts and relations; and (6) models interdependence differently which, if transforms to an equivalent graphical model, would result in fewer factor nodes.

Existing Semantic Table Interpretation methods have several limitations. First, they have not considered using features from out-table context, which is highly generic and generally available. Instead, many have used knowledge base specific features that are difficult or impossible to generalize. For example, the co-occurrence statistics used by Venetis et al. [35] and Wang et al. [36] are unavailable in knowledge bases such as YAGO, DBpedia, and Freebase. Methods such as Limaye et al. [21] and Mulwad et al. [24] use the concept hierarchy in their knowledge bases. However, Freebase does not have a strict concept hierarchy. These methods can become less effective when adapted to different knowledge bases, as we shall show later.

Second, no existing methods explicitly address efficiency, which we argue as an important factor in Semantic Table Interpretation tasks. Current methods are non-efficient because they typically adopt an exhaustive strategy that examines the entire table content, e.g., column classification depends on every cell in the column. This results in quadratic growth of the number of computations and knowledge base queries with respect to the size of tables, as such operations are usually required for every pair of candidates, e.g., candidate relation lookup between every pair of entities on the same row [24,26,27], or similarity computation between every pair of candidate entity and concept in a column [21]. This can be redundant as Zwicklbauer et al. [46] have empirically shown that comparable accuracy can be obtained by using only a fraction of data (i.e., sample) from the column. However, there remains the challenge to automatically determine the optimal sample size and elements.

Further, existing methods are incomplete, since they either only tackle certain annotation tasks [35,36], or only deal with NE-columns [7,21,23–25].

In an attempt to address some of the above issues, we previously developed a prototype TableMiner [42] that is able to annotate NE-columns and disambiguate entity cells in an incremental, mutually recursive and bootstrapping approach seeded by automatically selected sample from a table. And in Zhang [41] we further explored different methods for selecting the sample and its effect on accuracy. This work joins the two and largely extends them in a number ways: (1) adding a new algorithm for subject column detection and for relation enumeration; (2) revising the column classification and entity disambiguation processes (primarily in the UPDATE process); (3) performing significantly more comprehensive experiments to thoroughly evaluate the new method; and (4) releasing both the dataset and software to encourage future research.

6.1. Preprocessing

Subject column detection begins by classifying cells from each column (denoted by T j ) into one of the data types: ‘empty’, ‘named entity’, ‘number’, ‘date expression’, ‘long text’ (e.g., sentence, or paragraph), and ‘other’. This is done by using simple regular expressions that examine the syntactic features of cell text, such as number of words, capitalization, mentions of months or days in a week. A vast amount of literature can be found on this topic [2,14,15]. Then each column is assigned a most frequent datatype by counting the number of cells belonging to that type. The only exception is that a column is empty only if all cells are empty.

Next, if a candidate NE-column has a column header that is a preposition word, it is discarded. An example like this is shown in Fig. 4, where the columns ‘For’ and ‘Against’ are clearly not subject columns but rather form relations with the subject column ‘Batsman’. OPEN IN VIEWER

Context match score (cm) for a column T j counts the frequency of the column header’s composing words in the header’s context: (3) cm ( T j ) = ∑ x j ∈ X j ∑ w ∈ bow ( T j ) freq ( w , x j ) × wt ( x j ) where x j ∈ X j are different types of context for the header of column T j , bow ( T j ) returns the bag-of-words representation of the column header’s text l ( T j ) , and wt ( x j ) is the weight given to a specific type of context. Intuitively, the more frequent a column header text is repeated in the table’s context the more likely it is the subject column of the table. The context elements used for computing cm include webpage title, table caption and surrounding paragraphs.

Web search score (ws) of a column gathers evidence from the Web to predict the likelihood of it being the subject column, and it is contributed by individual rows in the table. Given a table row T i , a query string is firstly created by concatenating all text content from cells on this row, i.e., l ( T i , j ) for all j. Then the query is sent to a search engine to retrieve the top n webpages. Let P denote these webpages, then each NE-cell that composes the query receives a score as: (4) ws ( T i , j ) = countp ( T i , j , P ) + countw ( T i , j , P ) countp ( T i , j , P ) = ∑ p ∈ P ( freq ( l ( T i , j ) , p title ) × 2 (5) + freq ( l ( T i , j ) , p snippet ) ) countw ( T i , j , P ) = ∑ p ∈ P ∑ w ∈ bowset ( T i , j ) 1 | bow ( T i , j ) | (6) × ( freq − ( w , p title ) × 2 + freq − ( w , p snippet ) ) countp sums up the frequency of the cell text l ( T i , j ) in both the titles ( p title ) and snippets ( p snippet ) of returned webpages. Frequency in titles are given double weight as they are considered to be more important. countw firstly transforms cell text into a set of unique words bowset ( T i , j ) , then counts frequency of each word. freq − ensures those occurrences of w that are part of occurrences of l ( T i , j ) are eliminated and not double counted. bow ( T i , j ) returns the bag-of-words representation of the cell text.

For each row, the cell that receives the highest score is considered to be containing the subject entity for the row. The intuition is that the query should contain the name of the subject entity plus contextual information of the entity’s attributes. When searched, it is likely to retrieve more documents regarding the subject entity than its attributes, and the subject entity is also expected to be repeated more frequently. Example 1.

For the first content row in the example table, we create a query by concatenating text from the 1st, 3rd and 4th cells on the row (only NE-columns are candidates of subject columns), i.e., ‘big deal on madonna street, mario monicelli, marcello mastroianni’. This is searched on the Web to return a list of documents. Then for each document, we count the frequency of each phrase in the title and snippet and compute countp for each corresponding cell. Next, take the 1st cell for example, ‘big deal on madonna street’ is transformed to a set of unique words {‘big’, ‘deal’, ‘madonna’, ‘street’}, and we count the frequency of each word in the titles and snippets of each document to compute countw. If any occurrence is part of an occurrence of the whole phrase that is already counted in countp, we ignore them. Likewise, we repeat this for the 3rd and 4th cells. Finally, we find that the 1st cell receives the highest Web search score, and we mark it as the subject entity for this row.

In principle the Web search score of a column ws ( T j ) simply adds up ws ( T i , j ) for every row i in the column. However, this is practically inefficient and extremely resource consuming as Web search APIs typically has limited quota. In fact, it is also unnecessary. Again using the example table, we do not need to read all 60 rows to decide the column ‘Title’ as the subject column. Therefore, we compute Web search scores of a column in the context of the I-Inf algorithm. To do so, we simply need to define D as the collection of table rows T i , and each key-value pair as ⟨ T j , ws ( T j ) ⟩ .

Features (except df ) are then normalized into relative scores by the maximum score of the same feature type. Next, they are combined to compute a final subject column score subcol ( T j ) and the column with the highest score is chosen as subject column. subcol ( T j ) = 1 df ( T j ) + 1 × ( uc norm ( T j ) + 2 ( cm norm ( T j ) (7) + ws norm ( T j ) ) − emc norm ( T j ) ) where norm indicates normalized scores. uc, cm and ws are all indicative features of subject column in a table. However, uc is given half the weight of cm and ws. This is rather arbitrary and the intuition is that subject columns do not necessarily contain unique values at every row [35], hence uc is a weaker indicator than others. A column that contains empty cells is penalized, and the total score is normalized by its distance from the left-most NE-column as subject columns tend to appear on the left and before columns describing subject entities’ attributes.

An alternative approach would be to train a machine learning model using these features to predict subject column. However, we did not explore this extensively as we want to keep TableMiner⁺ unsupervised. Also we want to focus on creating semantic annotations in tables in this work.

Preliminary column annotations depend on cold-start disambiguation of the cells in the sample. For this reason, we hypothesize that a good sample should contain cells that are ‘easy’ to disambiguate, such that it is more likely to obtain high disambiguation accuracy, which then may contribute to high classification accuracy. We further hypothesize that a cell makes an easy disambiguation target if: (1) we can create rich feature representation of its candidate entities, or its context, or both; and (2) the text content is less ambiguous hence fewer candidates are retrieved (i.e., if a name is used by one or very few entities). Previously, we introduced four methods based on these hypothesis and have shown that they have comparable performance in terms of both accuracy and efficiency. Here we choose the method based on ‘feature representation size’, which is slightly more balanced.

Given an NE-column, each cell is firstly given a preference score. Then the rows containing these cells are re-ordered based on the descending order of the scores. Since preliminary column classification follows an incremental, iterative procedure using the I-Inf algorithm until convergence, effectively by changing the order of the cells (and rows), a different set of cells could have been processed by the time of convergence (thus a different sample is used). And this possibly results in different classification outcome.

To compute the preference score of each cell, we firstly introduce a ‘one-sense-per-discourse’ hypothesis in the context of a non-subject NE-column. One-sense-per-discourse is a common hypothesis in sense disambiguation. The idea is that a polysemous word appearing multiple times in a well-written discourse is very likely to share the same sense [8]. Though this is widely followed in sense disambiguation in free texts, we argue that it is also common in relational tables: given a non-subject column, cells with identical text are extremely likely to express the same meaning (e.g., same entity or concept). Note that one-sense-per-discourse is more likely to hold in non-subject columns than subject-columns, as the latter may contain cells with identical text content that expresses different meanings. A typical example is the Wikipedia article ‘List of peaks named Bear Mountain’,9

OPEN IN VIEWER

Fig. 5.

One-sense-per-discourse does not always hold in subject-columns.

The principle of one-sense-per-discourse allows us to treat cells with identical text content as singleton, to build a shared and combined in-table context by including the rows of each cell. As a result, we can create a larger and hence richer feature representation based on the enlarged context. Next, we count the number of features in the feature representation of a cell and use the number as the preference score.

OPEN IN VIEWER

Next, with the table rows re-arranged by sample ranking, TableMiner⁺ proceeds to classify the column using the I-Inf algorithm. Using Algorithm 1, D contains the ranked list of cells from the column where each element d is an individual cell; for a key-value pair the key (k) is a candidate concept for the column, and the value v is the confidence score. The process operation (line 6) performs cold-start disambiguation of a cell to generate candidate concepts and compute their scores (Section 7.2.1); the update operation (line 7) takes the output of cold-start disambiguation from a cell and updates the set of candidate concepts for the entire column (Section 7.2.2). This repeats until convergence.

7.2.3. Repetition and convergence

The above processes are repeated in the context of I-Inf until convergence is detected by comparing the set of candidate concepts from the current and previous iterations. The end output of this process is c j + the winning concept used to annotate the column.

Example 4.

Following Example 3 we continue to classify the ‘Director’ column in the table shown in Fig. 6. Starting from the first cell ‘Dino Risi’, we retrieve candidate entities and compute a confidence score for each. Assuming the winning entity is the Freebase topic ‘fb:/m/0j_nhj’, we then extract its associated concepts and compute confidence score for each concept. Some of the concepts are ‘Film director (fb:/film/director)10

¹⁰

All examples are superficial and adapted based on real data.

’, ‘Film writer (fb:/film/writer)’, and ‘Award nominee (fb:/award/award_nominee)’. Then as we proceed to the second and third cells, no new concepts are added and the scores of existing concepts are updated. Suppose that the winning entity for the fourth cell is ‘Mario Monicelli (fb:/m/041kw5)’ and the associated concepts are ‘Film writer (fb:/film/writer)’ and ‘TV personality (fb:/tv/tv_personality)’. Here the score of ‘Film writer’ is further updated and ‘TV personality’ is added as candidate concept for the column. Assuming that we reach convergence at this point as the change of scores of candidate concepts compared to the previous iteration is neglectable, and the highest scoring candidate concept is ‘Film writer’. We therefore stop at the fourth cell and annotate the column as ‘Film writer (fb:/film/writer)’.

7.3. Preliminary cell disambiguation

Next, c j + is used as constraint to perform preliminary cell disambiguation in the column. The process re-starts from the first cell in the column. For cells that have already passed a cold-start disambiguation process during preliminary column classification, we simply need to re-select the highest scoring candidate entities satisfying the condition: con ( e i , j ) ∩ { c j + } ≠ ∅ . For any new cells, disambiguation follows the same procedure as cold-start disambiguation (Section 7.2.1) with one modification: candidate generation uses c j + as a filter to select only entities that are associated with c j + as disambiguation candidates. Compared to the exhaustive strategy adopted by state-of-the-art methods, this reduces computation by cutting down the number of candidate entities for consideration.

Disambiguation of each new cell generates a set of concepts, of which some can be new while others may already exists in C j . By the end of the process, C j is updated by: (1) adding newly derived concepts; (2) for those already exist in C j at the beginning, revising their confidence scores. This changes C j and in some cases, causes the winning concept for the column to be inconsistent from that at the beginning of the preliminary cell disambiguation stage. This is handled by the UPDATE phase to be discussed in the following section.

Example 5.

Following Example 4, we use ‘Film writer (fb:/film/writer)’ as constraint to disambiguate the cells in the column. For the four cells already processed in Example 4, we simply re-select from their candidate entities the highest scoring one that is also an instance of this concept. To disambiguate the new cell ‘Nanni Loy’, we only consider candidate entities that are instances of the concept for the column:‘Film writer’. Assuming that the winning entity is ‘fb:/m/02qmpfs’. Then its associated concepts ‘Film writer’, ‘Film director (fb:/film/director)’, ‘Film actor (fb:/film/actor)’ are used to further update the candidate concepts on the column. At the end of the process, it is likely that the highest scoring concept for the column has changed to ‘Film director (fb:/film/director)’.

8. NE-column interpretation – The UPDATE phase

Once the LEARNING phase is applied to all NE-columns in the table, the UPDATE phase begins to enforce interdependence between classification and disambiguation within each column as well as across different columns. This is done by an iterative optimization process shown in Algorithm 2. Note that our previous work [42] only captures interdependence between classification and disambiguation within each separate column. Here we improve it by also capturing cross-column interdependence with a notion of ‘domain consensus’. OPEN IN VIEWER

Algorithm 2

UPDATE

8.1. Domain representation

In each iteration, the process starts with creating a bag-of-words representation of the domain using the winning entities from all cells ( E ) in the table at the current iteration (line 4 in Algorithm 2): (16) bow ( domain ) ← ⋃ i , j defbow ( e i , j + ) where defbow denotes ‘definitional’ bag-of-words, and takes a definitional sentence about an entity and converts it into a bag-of-words representation in the same way as bow ( · ) . A definitional sentence is commonly found in almost any knowledge base. For example, WordNet has a one-sentence definition for every synset; the first sentence in an Wikipedia article usually defines an entity [16]; this also applies to the description of a Freebase topic (e.g., a concept or named entity) or a DBpedia resource. The idea is that the definitional sentence provides a focused description of the entity, likely to contain informative words about the general domain it is related to. In particular, it often contains words forming hypernymy relation with the entity [16,44]. For example, the Freebase definitional sentence about the English city ‘Sheffield’ contains words11

¹¹

http://www.freebase.com/m/0m75g, last retrieved on 13 April 2014.

‘city’, ‘metropolitan’, ‘borough’, ‘Yorkshire’, and ‘England’, which are useful words defining the concept space of the entity.

8.2. Column annotation revision

The bag-of-words representation of the domain is then used to revise the concept annotations on all NE-columns ( C ). To do so, we compute a domain consensus score dc for each candidate concept from each NE-column, and add this to their overall confidence score (line 7 in Algorithm 2). The domain consensus score is based on the frequency weighted dice overlap between the bag-of-words representations of the concept and the domain. (17) dc ( c j ) = dice ( c j , domain )

Since the sizes of bow ( c j ) and bow ( domain ) are often different orders of magnitude, square root is used to balance the score. Also domain consensus is computed with respect to entities from all cells from any columns, which serves as a way of ensuring inter-column dependence. After revising the confidence scores of candidate concepts, the winning concepts for each column are re-selected (Line 9).

8.3. Cell annotation revision

For any column, if the new winning concept is different from the that generated in the previous iteration, the disambiguation result on that column is revised (Line 10). This follows the procedure of preliminary cell disambiguation (Section 7.3).

These updating processes are repeated until all annotations are stabilized. Specifically, in each iteration function stabilized checks the winning concepts for all NE-columns and the winning entities for all cells in the previous iteration against those in the current iteration. The UPDATE process is called to be stabilized if no difference is detected.

Note that re-computing disambiguation and classification may require retrieving data of new entity candidates from the knowledge base and subsequently constructing their feature representation for disambiguation due to the possible change of c j + at each iteration. However, this design still largely improves the exhaustive strategy because: (1) empirically the UPDATE phase stabilizes fast and in most cases involves merely re-selecting those ‘losing’ candidate entities that were already seen in the LEARNING phase; (2) when new candidates are indeed added it only happens in significantly fewer cells than the entire column that an exhaustive strategy would otherwise have to deal with.

Example 6.

Following Example 5, assuming we have annotated all NE-columns and their cells (also see d₆ in Fig. 2). We begin the UPDATE process by taking the winning entity annotations from columns 1, 3, and 4 in the Table shown in Fig. 6 to create a bag-of-words representation of the domain. Again using the ‘Director’ column, we proceed to compute a domain consensus score for each candidate concept for this column (i.e., ‘Film director’, ‘Film writer’ etc.) and update their confidence scores. The winning concept is re-selected, which we assume is changed to ‘Film director’. This is different from that at the beginning (‘Film writer’). Therefore, we take the new concept and use it to revise cell annotations in the column. We do this for the other two columns and repeat this process until all annotations are no longer changed.

9. Relation enumeration and annotating literal-columns

9.1. Relation enumeration

Relation enumeration firstly begins by interpreting relations between the subject column and any other columns on each row independently. Let T j be the subject column in a table and T j ′ denote any other columns. Given the winning subject entity e i , j + for cell T i , j and T i , j ′ ( j ≠ j ′ ) as another cell on the same row, the candidate set of relations between T i , j and T i , j ′ , denoted by R j , j ′ i , is derived from the triples containing e i , j + as subject, denoted by Ψ i , j = { ⟨ e i , j + , predicate , object ⟩ } . Then let ψ i , j ∈ Ψ i , j be one of the triples, and functions p ( ψ i , j ) , o ( ψ i , j ) return the predicate and object from the triple respectively, the candidate relations R j , j ′ i is the set of unique predicates in Ψ i , j , i.e., { p ( ψ i , j ) | ∀ ψ i , j ∈ Ψ i , j } .

Then a confidence score is computed for each candidate relation r j , j ′ i ∈ R j , j ′ i . To do so, the subset of triples from Ψ i , j containing r j , j ′ i as predicate are selected. Then the object of each triple in this set is matched against the content in T i , j ′ using the frequency weighted dice function (Eq. (8)), and the highest score is assigned to be the confidence score for the candidate relation: (18) cf ( r j , j ′ i ) = max ψ i , j ∈ Ψ i , j , p ( ψ i , j ) = r j , j ′ i dice ( T i , j ′ , o ( ψ i , j ) ) where function dice ( T i , j ′ , o ( ψ i , j ) ) computes an overlap score between the bag-of-words representations of the cell and the object of a triple that contains r j , j ′ i as predicate. The winning relation for the row is denoted by r j , j ′ i + .

After the winning relation is computed for each row between T j and T j ′ , the candidate set of relations for the two columns R ( j , j ′ ) is derived by collecting the winning relations on all rows: (19) R ( j , j ′ ) ← ⋃ i r i , j ′ i +

Then a confidence score is computed for each instance r j , j ′ ∈ R ( j , j ′ ) , and it consists of two parts: a relation instance score re and a relation context score. The relation instance score is computed in the same way as concept instance score: (20) re ( r j , j ′ ) = ∑ i cf ( r j , j ′ i + ) if r j , j ′ i + ≡ r j , j ′ 0 else | { T i } | where i denotes the row index of the table and | { T i } | returns the number of rows in the table.

The relation context score is computed in the same way as entity context score using Eq. (10), and the function used to calculate an overlap score between r j , j ′ and each of its context is the frequency weighted dice function in Eq. (8). This is adapted by replacing e i , j with r j , j ′ and x i , j with x j , j ′ . The bag-of-words representation bow ( r j , j ′ ) is based on l ( r j , j ′ ) which returns the name and URI of the relation. The context of a relation includes column header (which sometimes indicates the relation with the subject column), surrounding paragraphs and semantic markups. Other types of context are less likely to contain mentions of relations.

The final confidence score of a candidate relation adds up its instance and context score with equal weights, and the final binary relation that associates subject column T j with column T j ′ is the candidate with the highest confidence score.

Example 7.

Assuming the entity annotation for cell T 3 , 1 in the table of Fig. 6 is ‘A Difficult Life (fb:/m/02qlhz2)’, which has two triples ⟨fb:/m/02qlhz2, fb:/film/film/directed_by, ‘Dino Risi’⟩ and ⟨fb:/m/02qlhz2, fb:/film/film/starring, ‘Dino Sordi’⟩. To predict the relation between columns T 1 and T 3 on this row, the object values of the two triples are matched against the text value ‘Dino Risi’ in cell T 3 , 3 based on overlap. Then the first triple will receive a score of 1.0 while the second 0.5. Hence the relation between the two columns elected by this row ( r 1 , 3 3 + ) is the predicate ‘fb:/film/film/directed_by’ and cf ( r 1 , 3 3 + ) = 1.0 . Next we repeat this process for the remaining rows to elect a relation for every other row between the two columns, and the set of all these relations become R 3 , 3 . Suppose that r 1 , 3 4 + is also ‘fb:/film/film/directed_by’ and cf ( r 1 , 3 4 + ) = 0.9 . Then to compute the overall confidence score of ‘fb:/film/film/directed_by’ across the two columns, the relation instance score adds up the two values and become 1.9. We then calculate the relation context score and add it to the instance score to derive the final score.

9.2. Labeling literal-columns

Literal-columns are expected to contain attribute data of entities in the subject column. They do not denote entities and therefore, cannot be interpreted using the column interpretation method described above. In previous work [7,21,23–25] they are simply ignored. This work also assigns a column annotation that best describes the attribute data in literal-columns.

Given a literal-column T j ′ that forms a binary relation r j , j ′ with the subject column T j , the annotation for this column is simply l ( r j , j ′ ) , since r j , j ′ typically describes a property of the subject column concept in such cases.

10. Experiment settings

Semantic Table Interpretation can be evaluated by both in-vitro (assessing the annotations directly) and in-vivo (assessing the accuracy of applications built on top of the annotations) experiments. In this work, we use in-vitro experiments because (1) they are the most commonly used evaluation approach and (2) standard datasets are available.

10.1. Knowledge base and datasets

We use Freebase as the knowledge base for Semantic Table Interpretation, as it is currently the largest knowledge base and linked data set in the world. It contains over 3.1 billion facts about over 58 million topics (e.g., entities, concepts), significantly exceeding other popular knowledge bases such as DBpedia and YAGO. Further it has direct mappings to resources from other datasets, making them easier to be used as gold standard. For evaluation, we compiled and annotated four datasets using Freebase: Limaye200, LimayeAll, IMDB and MusicBrainz. To the best of our knowledge, this is the largest dataset for this task and we make them available to encourage comparative studies.12

¹²

Please contact the author on how to obtain, as the dataset is very large. Although Freebase has been closed, this work was however, first submitted in May 2013, at which time the close-down of Freebase was not foreseeable. To enable comparative studies, we also release cached Freebase data for this work. Also the current API on GitHub implements an interface with DBpedia, and a plan is made to migrate relevant software to the Google Knowledge Graph once an appropriate API is available.

10.1.1. LimayeAll and Limaye200

These datasets are the rebuilt versions of the original four datasets used by Limaye et al. [21]. The original datasets consist of over 6,000 tables, 94% collected from Wikipedia and the rest from the general Web. Entities in the tables were annotated with links to Wikipedia articles; columns and binary relations between columns were annotated by concepts and relations in the YAGO knowledge base (2008 version).

These datasets are re-created for a number of reasons. First, Wikipedia has undergone significant changes since the publication of the datasets such that a large proportion of the source webpages – as well as the contained tables – have been changed. Second, we notice that the original ground truth for named entity disambiguation were very sparse and possibly biased. As shown in Appendix C, it is less well-balanced than the re-created dataset and a simple exact name match baseline has achieved significantly higher accuracy than the original reported results in Limaye et al. [21]. Third, this work uses a different knowledge base from YAGO, such that the original ground truth cannot be directly used.

Entity ground truth – LimayeAll We run a process to automatically update the webpages in the original dataset and re-annotate entity cells by mapping the original Wikipedia ground truth to Freebase. Details of this process is described in Appendix B.

Column annotation and relation ground truth – Limaye200 To create the ground truth for evaluating column classification and relation enumeration, a random set of 200 tables are drawn from the LimayeAll dataset. These tables are firstly manually examined to identify subject columns, then annotated following a similar process as Venetis et al. [35]. Specifically, TableMiner⁺ and the baselines (Section 10.3) are run on these tables and the candidate concepts for all table columns and relations between the subject column and other columns in each table are collected and presented to annotators. The annotators mark each label as ‘best’, ‘okay’, or ‘incorrect’. The basic principle is to prefer the most specific concept/relation among all suitable candidates. For example, given a cell ‘Penrith Panthers’, the concept ‘Rugby Club’ is the ‘best’ candidate to label its parent column while ‘Sports Team’ and ‘Organization’ are ‘okay’. The annotators may also insert new labels if none of the candidates are suitable.

10.1.2. IMDB

The IMDB dataset contains over 7,000 tables extracted from a random set of IMDB movie webpages. Each IMDB movie webpage13

¹³

E.g., http://www.imdb.com/title/tt0071562/.

contains a table listing a ‘cast’ column of actors/actresses and a column of corresponding characters played. Cells in the actor/actress column are linked with an IMDB item id, which, when searched in Freebase, returns a unique (if any) mapped Freebase URI. Thus entities in these columns are annotated automatically in such a way. The ‘character’ column is not used since they are not mapped in Freebase. The cast column is also manually labeled with ‘best’ and ‘okay’ concepts in the same way as for Limaye200. No subject column or relations are annotated because only one column is considered in this dataset.

10.1.3. MusicBrainz

The MusicBrainz dataset contains some 1,400 tables extracted from a random set of MusicBrainz record label webpages. Each MusicBrainz record label webpage14

¹⁴

E.g., http://musicbrainz.org/label/9e6b4d7f-4958-4db7-8504-d89e315836af.

contains a table listing the music released by a production company. Each webpage uses pagination to separate very large tables, and only the first page is downloaded. The table typically has 8 columns, of which one lists music release titles (subject column) and one lists music artists. Each release title or artist has a MusicBrainz id, which can be mapped to a Freebase URI in the same way as for the IMDB dataset. Thus entities in these two columns are annotated in such a way. Then the table columns and binary relations between the subject column and others are also annotated manually following the same procedure as for IMDB and Limaye200.

10.1.4. Dataset statistics

Table 3 shows general statistics of the datasets. Figure 7 shows the distribution of rows and columns containing entity annotations in the ground truth, and length of text in cells by number of tokens. Tables in MusicBrainz contain no more than 50 rows because of the pagination on the webpage and only the first page is downloaded. The IMDB entity ground truth has only 1 column in every table; while for MusicBrainz, this is either 1 or 2 columns. Very long cell text is found to be rare in LimayeAll, but slightly more frequent in MusicBrainz due to long names of classic music titles. Cells in IMDB tables are typically person names and usually contains 1 or 2 tokens. Arguably, LimayeAll and Limaye200 are the most diverse datasets, since they cover a significantly larger number of domains and more diverse table structures and schemata, whereas IMDB and MusicBrainz each contains only one table structure and schema.

OPEN IN VIEWER

Table 3

Statistics of the datasets for evaluation. ‘All’ under ‘Labeled columns’ shows the number of both labeled NE- and literal-columns, while ‘NE’ refers to only NE-columns. Likewise ‘All’ under ‘Labeled relations’ shows the number of labeled relations between subject columns and either NE- or literal columns, while ‘NE’ refers to only relations with NE-columns

Dataset	Tables	Subject column	Entities	Labeled columns		Labeled relations
				All	NE	All	NE
Limaye200	200	✓	–	615	415	361	204
LimayeAll	6,310		227,046	–	–	–	–
IMDB	7,416		92,321	7,416	7,416	–	–
MusicBrainz	1,406	✓	93,266	9,842	4,218	7,030	5,624

OPEN IN VIEWER

Fig. 7.

Dataset statistics (min., max. avg. (black diamonds), kth quantile): #r – number of rows; #nec – number of columns containing annotated named entities in ground truth; cl – content cell text length in terms of number of tokens delimited by non-alphanumeric characters.

Table 4 compares against datasets used by other studies. Arguably, TableMiner⁺ is evaluated using the most comprehensive collection of datasets known to date.

OPEN IN VIEWER

Table 4

Comparison against datasets used by state-of-the-art. ‘–’ indicates unknown or not clear

Method	Dataset	Tables	Columns	Entities	Relations
TableMiner+	Limaye200	200	615	–	361
	LimayeAll	6,310	–	227,046	–
	IMDB	7,416	7,416	92,321	–
	MusicBrainz	1,406	9,842	93,266	–
Hignette et al. [14,15]	1 dataset	–	81	–	–
Limaye et al. [21]	4 datasets	6,310	747	142,737	90
Syed et al. [7]	1 dataset	5	21	171	–
Venetis et al. [35]	1 dataset	168	–	–	–
Buche et al. [2]	1 dataset	90	81	–	316
Mulwad et al. [24]	1 dataset	203–490	–	–	–
Zhang [42]	2 datasets	7,446	7,608	94,406	–
Zhang [41]	2 datasets	6,310	615	227,046	–

10.2. Evaluation metrics

Effectiveness – Subject column detection is evaluated by Precision. Then the three annotation tasks of Semantic Table Interpretation are evaluated using the standard Precision, Recall and F1 measures. Since TableMiner⁺ ranks candidates by scores, only the highest ranked prediction by TableMiner⁺ is considered. Each ‘best’ label is awarded a score of 1 while each ‘okay’ label is awarded 0.5. Further, if there are multiple highest-ranked candidates, each candidate considered correct only receives a fraction of its score as score # topranked . For example, if a column containing film titles has two concept candidates with the same highest score: ‘Film’ (best) and ‘Book’ (incorrect), this prediction receives a score of 0.5 instead of 1. This is to penalize the situation where the Semantic Table Interpretation system fails to discriminate false positives from true positives. From a knowledge base population point of view, false positives cause incorrect triples to be populated into knowledge bases and the LOD cloud.

For column classification and relation enumeration, evaluation reports results under both ‘strict’ and ‘tolerant’ mode. To evaluate column classification, the strict mode only considered ‘best’ annotations; while the tolerant mode considers both ‘best’ and ‘okay’ annotations. Evaluating relation enumeration under the strict mode only considers relations between subject column and other columns in a table, and only ‘best’ annotations are included. Under the tolerant mode, in addition to also including ‘okay’ annotations, if TableMiner⁺ predicts correct relations between non-subject columns or the reversed relation between the subject column and other columns, then each prediction is awarded a score of 0.5.

Moreover, since most state-of-the-art methods have focused on only NE-columns, we report results obtained on NE-columns as well as both NE- and literal-columns for column classification and relation enumeration.

The efficiency of TableMiner⁺ is assessed by empirical wall-clock time and savings in terms of candidate entities needed to be considered for disambiguation. As discussed before, retrieving candidate entities and their data, constructing feature space and computing similarities consume the large majority of time. A more reliable way of improving efficiency is thus reducing the size of the candidate space. To reduce network latency we use a caching mechanism in each comparative model and TableMiner⁺ (see Section 10.3). Specifically, when a request to the knowledge base is sent for the first time, we cache the query results locally. Then all subsequent identical requests will only be served by the local cache.

10.3. Comparative models and configurations

TableMiner⁺ is evaluated against four baseline methods and two re-implemented state-of-the-art methods. The implementation of all these methods are released on GitHub.15

¹⁵

https://github.com/ziqizhang/sti.

10.3.1. Baselines

Each baseline starts with the same subject column detection component, but uses different methods for disambiguating entity cells, classifying columns, and annotating relations between subject column and other columns.

Baseline ‘name match’ B _nm firstly disambiguates every cell in an NE-column by retrieving candidate entities from Freebase using the text content in the cell as query, then selecting a single entity: the highest ranked candidate whose name matches exactly the cell text. If no candidates are found to match, the top-ranked candidate is chosen. Freebase adopts a ranking algorithm that reflects both the relevance and popularity of a topic in the knowledge base.

Next, to classify the NE-column with a concept, entities from each cell cast a vote for the concepts they are associated to, and the one receiving the most votes is chosen as the annotation for the column.

Relation enumeration follows a similar procedure. Candidate relations on each row is derived and their scores computed in the same way as TableMiner⁺ (Section 9.1, Eq. (18)). Then each candidate with a score greater than 0 is selected from the row and considered as a candidate relation for the two columns and casts a vote toward the candidate. The best relations for the two columns are those receiving the most votes.

Literal-columns are annotated the same way as TableMiner⁺ (Section 9.2).

Baseline ‘similarity-based’ firstly disambiguates every cell in an NE-column, then derives column annotations based on the winning entity from every cell.

For cell disambiguation, we compute a score for each candidate entity as the sum of a simple context score and the string similarity between the name of the candidate and the cell text. The context score is computed using Eq. (9), where x is the row content only.

For column classification, candidate concepts for an NE-column are firstly gathered based on the winning entities from each cell. The final score of a candidate concept consists of two parts: (1) the number of winning entities associated with the concept normalized by the number of rows in the table, and (2) a string similarity score between the concept’s name and the header text (if exists).

For relation enumeration and the annotation of literal-columns, we use the same procedures from the name match baseline B _nm .

To compute string similarity, we test three metrics and therefore create three similarity baselines: Cosine (B_cos), Dice (B _dice ) coefficient, and Levenshtein (B _lev ).

The key differences between the four baselines and TableMiner⁺ are: (1) TableMiner⁺ uses out-table context while the baselines do not; (2) TableMiner⁺ adopts a bootstrapping, incremental approach with an iterative, recursive optimization process to enforce interdependence between different annotation tasks. The baselines however, use an exhaustive strategy and are based on very simple interdependence (i.e., both relation enumeration and column classification depend on cell disambiguation).

10.3.2. Re-implementation of state-of-the-art

We re-implemented two state-of-the-art methods and adapted them to Freebase as there are no existing software that can be directly used, and also different knowledge bases have been used in the original work. We choose to implement the methods by Limaye et al. [21] and Mulwad et al. [24], as they are able to address all three annotation tasks in Semantic Table Interpretation. Re-implementation of these methods is not a trivial task. First, the use of different knowledge bases implies that certain features used in the original work are unavailable, must be adapted or replaced. Second, each method has used in-house tools for pre-processing or training. Therefore, our re-implementation has focused on the core inference algorithm in the two methods. We advise readers that the re-implementation is not guaranteed to be an identical replication of the original systems. We describe details of re-implementation in Appendix D, and here we summarize key points. Note that both methods can only deal with NE-columns.

Limaye et al. (Limaye2010) model a table as a factor graph and apply joint inference to solve the three annotation tasks simultaneously. A factor encodes the compatibility between a variable (e.g., a cell) and its candidates (e.g., candidate entities), or between variables believed to be interdependent. In the original work, the compatibility is calculated based on a number of features, the weight of which is learned using a supervised model. Our implementation16

¹⁶

We used Mallet GRMM: http://mallet.cs.umass.edu/grmm/.

simply uses equal weights. Further, we discard all relation variables and only build a smaller factor graph of concept and entity variables. This is because empirically, we have noticed that adding relation variables caused drop in the accuracy of column classification (see Appendix D).

Mulwad et al. model a table using a similar factor graph, then apply a light-weight inference algorithm based on semantic message passing. Their method depends on a pre-process that disambiguates entity cells (i.e., the so-called ‘entity ranker’). This process uses a supervised model built on features that are specific to the knowledge bases used in the original work. We create two models each with a different substitute of the ‘entity ranker’. Mulwad2013 uses a simple ranker that linearly combines features equivalent to those used in the original work (but derived from Freebase) to score and rank candidate entities. Mulwad2013 ^tm+ uses TableMiner⁺’s formula of entity confidence score ( cf ( e i , j ) in Section 7.2.1) to score and rank candidate entities.

10.3.3. TableMiner⁺ configuration

The convergence threshold in the I-Inf algorithm is set to 0.0117

¹⁷

This is a rather arbitrary choice that was found to perform reasonably well during development. We did not experiment with different choices extensively.

in both subject column detection and the preliminary column classification phases. The Web search API used for computing the Web search score in subject column detection is the Bing Search API18

¹⁸

http://datamarket.azure.com/dataset/bing/search.

and default parameters are used. TableMiner⁺ uses various context for Semantic Table Interpretation. The weights of context in different annotation tasks are defined in Table 5.

OPEN IN VIEWER

Table 5

Different context weight used in different components

Component	In-table context			Out-table context
	column header	row content	column content	webpage title	table caption/title	paragraphs	semantic markups
Sub. Col. detection §6.2	–	–	–	1.0	1.0	0.5	–
Entity context score §7.2.1	1.0	1.0	0.5	1.0	1.0	0.5	1.0
Concept context score §7.2.1	1.0	–	1.0	1.0	1.0	1.0	1.0
Relation context score §9.1	1.0	–	–	–	–	1.0	1.0

Context is assigned a weight of 1.0 if it is considered ‘very important’ or 0.5 otherwise (subjectively decided). For example, in subject column detection, if header words are found in the webpage title or table captions, they are stronger indicators (hence ‘very important’) of subject column than if found in paragraphs that are distant from tables. For column classification and relation enumeration, different types of context are equally weighted because the bag-of-words representations for candidate concepts and relations are based on their names – semantically very important features but can be very sparse therefore any matches are considered a strong signal.

In the four datasets, semantic markups are only available in IMDB and MusicBrainz as the Microdata format. Any2319

¹⁹

https://any23.apache.org/.

is used to extract these annotations as RDF triples and the objects of triples are concatenated to create features. Annotations within the HTML <table> tags are excluded.

10.3.4. Parallelization and hardware

All models except Limaye2010 do not require parallelization as they are reasonably fast. Each model is able to run on a server with 4 GB memory. Limaye2010 requires similarity computation between every pair of candidate entity and concept for each column, the amount of which grows quadratically with respect to the size of a table. Thus the running of Limaye2010 is parallelized on 50 threads, each allocated with 4 GB memory.

11. Results and discussion

11.1. Subject column detection

Table 6 shows the precision of predicting subject columns in the Limaye200 and MusicBrainz datasets. The unsupervised subject column detection method achieves a precision of near 96% and 93% on the Limaye200 and MusicBrainz datasets respectively, compared to the reportedly 94–96% precision by a supervised model in Venetis et al. [35], and therein 83% by a baseline that chooses the leftmost column that does not contain numeric data.

OPEN IN VIEWER

Table 6

Subject column detection results in Precision

Dataset	Tables	Precision
Limaye200	200	95.5
MusicBrainz	1406	92.7

Figure 8 shows the convergence statistics in computing the Web search score (ws) in the I-Inf algorithm. The number of tables in which the ws score is calculated20

²⁰

In cases that only one NE-column is available in a table, this column is simply selected as the subject column.

is: 145 (73%) in Limaye200, 4,711 (75%) in LimayeAll, and 1,402 (near 100%) in MusicBrainz. Table 7 shows the statistics of the slowest convergence on each dataset.

OPEN IN VIEWER

Fig. 8.

Convergence statistics (max, min, average (black diamond), kth quantiles) for I-Inf in the calculation of the Web search score for subject column detection. itr – number of iterations (rows processed) until convergence; % – fraction of table rows processed.

OPEN IN VIEWER

Table 7

Statistics of the slowest convergence in the calculation of the Web search score for subject column detection

	Limaye200	LimayeAll	MusicBrainz
100% of rows processed in
% of tables	6.9%	5.9%	6.5%
Avg. rows	7.2	6.5	4.6
Rows >20	0	4	0
>50% of rows processed in
% of tables	26.2%	19.8%	12.6%
Avg. rows	6.0	6.0	5.2
Rows >20	0	7	0

Using Limaye200 as an example, Fig. 8 suggests that to compute the ws score, on average, only 4 rows (or less than 35%) are processed, and in 75% of tables no more than 5 rows (or less than 55%) are processed. Table 7 suggests that among all 145 tables that need calculation of ws scores, only 10 tables have all of their rows processed. They have an average of 7.2 rows and none has greater than 20 rows. Then 26.2% of these 145 tables have at least 50% of their rows processed. However, on average they have only 6 rows and none of them have greater than 20 rows. These figures suggest potentially significant improvement in efficiency over an exhaustive approach that computes the ws score using all rows in tables. The figures on the LimayeAll and MusicBrainz datasets suggest even greater savings. Consider that typical Web search APIs are quota-limited and pay-per-use, and it is extremely expensive (if not impossible) to run a local search engine on a reasonable sample of the entire Web. We believe that the I-Inf algorithm delivers substantial benefits in the task of subject column detection.

Manual inspection shows that in most cases the errors fall under several categories. The first is due to duplicate values in subject columns. An extreme example is the disambiguation table discussed before (i.e., ‘List of peaks named Bear Mountain’), in which the subject column contains only a single unique value. The second is caused by long-named entities in subject columns. For example, the subject column in the MusicBrainz tables lists titles of music releases, some of which has a name consisting of more than 10 tokens. This severely penalizes their context match cm and ws scores as it is unlikely to find exact match of their names in table context and search result documents. The third category includes arguable (few) tables that in strict terms, do not necessarily have a subject column. This includes tables listing events, such as lap records of racing car drivers in a particular tournament. In these cases, annotators typically selected the leftmost NE-column.

11.2. Effectiveness

11.2.1. Against baselines

Tables 8, 9 and 10 compare TableMiner⁺ against the four baselines in the cell disambiguation, column classification and relation enumeration tasks respectively. The highest figures are marked in bold. Overall, it is clear that TableMiner⁺ always obtains the best performance in all tasks and on all datasets. It also shows stronger improvement in the classification and relation enumeration tasks.

OPEN IN VIEWER

Table 8

Disambiguation results (F1) on four datasets

	Limaye200	LimayeAll	IMDB	MusicBrainz
B nm	78.3	82.2	92.8	57.0
B lev	78	82.1	93.5	84.83
B cos	79.2	82.7	93.4	84.76
B dice	79.9	82.8	93.5	84.84
TableMiner +	82.3	83.7	97.6	84.87

OPEN IN VIEWER

Table 9

Classification results (F1) on three datasets

			B nm	B lev	B cos	B dice	TableMiner +
Limaye200	NE-columns only	strict	23.9	45.4	43.5	48.9	65.8
		tolerant	48.8	63.8	62.2	66.1	75.0
	All columns	strict	31.4	48.7	46.9	51.3	64.0
		tolerant	51.1	63.3	61.8	65.0	71.5
IMDB	NE-/All columns	strict	22.7	32.3	31.9	32.0	97.0
		tolerant	60.0	64.6	64.4	64.5	97.2
MusicBrainz	NE-columns only	strict	59.1	82.6	83.4	83.9	85.2
		tolerant	61.7	82.6	83.6	83.9	85.9
	All columns	strict	54.6	72.2	72.6	72.9	74.3
		tolerant	55.9	72.2	72.7	72.9	74.7

OPEN IN VIEWER

Table 10

Relation enumeration results (F1) on two datasets

			B nm	B lev	B cos	B dice	TableMiner +
Limaye200	NE-columns only	strict	61.3	61.7	61.8	61.8	72.5
		tolerant	65.8	66.3	66.5	66.4	76.0
	All columns	strict	59.7	61.0	60.6	61.1	66.2
		tolerant	63.0	64.4	64.1	64.4	68.7
MusicBrainz	NE-columns only	strict	63.8	67.2	67.1	67.1	67.9
		tolerant	65.0	68.3	68.2	68.2	69.1
	All columns	strict	78.7	82.0	81.9	81.9	82.6
		tolerant	79.2	82.5	82.4	82.4	83.1

For disambiguation, even the simplistic baseline B _nm obtains surprisingly competitive results on the LimayeAll and IMDB datasets. In fact, on the original datasets by Limaye et al. [21] B _nm obtains a surprisingly high F1 of 92.6, significantly higher than the weighted average21

²¹

Macro-average over all datasets taking into account the size of each dataset.

of 84.1 based on figures reported in Limaye et al. [21]. As discussed earlier, our analysis – shown in Appendix C – suggests that the original datasets are sparse and less balanced.

Its highly competitive performance on the IMDB dataset could be explained by the domain and the method for ranking search results by Freebase. Movie is a highly popular domain representing a fair large proportion of Freebase. Since Freebase Search API promotes popular topics, when a person name is searched it is more likely to obtain movie-related topics as top results than any other domains. Hence by selecting the top result B _nm is very likely to succeed.

While although music is also a highly popular domain, B _nm could not replicate similar performance. Manual inspection shows that a fair proportion of music titles and artists uses very ambiguous names (e.g., ‘Trouble’, a musical release, ‘Pine’, an artist). In contrast, other baselines perform significantly better by considering row content in tables.

Compared to the baselines, TableMiner⁺ consistently obtains the best performance. On the most diverse dataset LimayeAll, it improves F1 by between 0.9 and 1.5 points. On the MusicBrainz dataset, it makes little difference from B _lev , B_cos, and B _dice . By examining the data it is found that the out-table context on MusicBrainz webpages are very sparse. In most cases, the webpage contains only the table. Microdata annotations are also predominantly found inside table structures, which are not used by TableMiner⁺. On the contrary, the IMDB dataset is completely the opposite: the webpages contain much richer out-table context (including pre-defined Microdata annotations), but little in-table context as the tables have only two columns and neither has column headers. TableMiner⁺ achieves significant improvement (between 3.9 and 4.6) over baselines on IMDB. This strongly suggests that out-table context serves as useful clues for disambiguating entities in table cells, particularly when in-table context is absent. Further, the Microdata-annotations extracted from these webpages could have been a strong contributor considering that the only difference in out-table context used on LimayeAll and IMDB is that the latter also uses them as features.

For classification, TableMiner⁺ in most cases outperforms baselines by a very large margin. Experiments on the most diverse dataset Limaye200 see an improvement of between 16.9 and 41.9 under strict mode and 8.9–26.2 under tolerant mode when only NE-columns are considered. When all columns are included, the figures are 12.7–32.6 strict and 6.5–20.4 tolerant. MusicBrainz sees the smallest improvement of the minimum of 1.3 strict and 2.0 (both v.s. B _dice ) when only NE-columns are considered, or 1.4 strict and 1.8 tolerant when all columns are included. This is due to the same reason behind TableMiner⁺’s moderate performance in the disambiguation task on this dataset: the out-table context is very sparse, thus TableMiner⁺ in most cases only uses in-table context. Again the most significant improvement is obtained on the IMDB dataset. With the lack of in-table context, particularly column headers that are considered a crucial feature in annotating table columns, all baselines perform poorly compared against TableMiner⁺. TableMiner⁺ more than tripled their performance under the strict mode and significantly outperforms under the tolerant mode, achieving near-perfect accuracy in both cases.

Also note that the performance by B _nm is generally inferior on any dataset. This is due to its inability to promote a single top ranked candidate concept in most cases, or in other words, multiple winning candidates are penalized by the scoring method. Other baselines improve this by also considering the string similarity between candidate concept’s label and table column headers.

OPEN IN VIEWER

Table 11

Comparison (F1) against the two re-implemented state-of-the-art (NE-columns only). Note that the re-implementation is not guaranteed to be identical to the original works due to reasons such as the use of specific tools, change of knowledge bases and datasets

			Limaye2010	Mulwad2013	Mulwad2013 tm+	TableMiner +
Disambig.	Limaye200	–	64.3	68.3	80.2	82.3
	LimayeAll	–	66.0	70.1	81.9	83.7
	IMDB	–	80.6	76.0	96.0	97.6
	MusicBrainz	–	66.4	73.4	83.0	84.87
Classification	Limaye200	strict	28.4	30.5	37.4	65.8
		tolerant	51.9	52.3	58.9	75.0
	IMDB	strict	1.7	15.1	59.8	97.0
		tolerant	49.3	55.2	78.2	97.2
	MusicBrainz	strict	72.4	65.6	71.0	85.2
		tolerant	72.4	74.2	79.3	85.9
Relation	Limaye200	strict	–	55.9	55.1	72.5
		tolerant	–	60.5	58.5	76.0
	MusicBrainz	strict	–	60.5	49.5	67.9
		tolerant	–	67.6	62.7	69.1

For relation enumeration, on the multi-domain Limaye200 dataset, an improvement of between 10.7–11.2 strict and 9.5–10.2 tolerant is obtained when only relations between NE-columns are considered. Regardless of column types, the figures are 5.1–6.5 strict and 4.3–5.7 tolerant. Improvement on MusicBrainz is smaller: the minimum of 2.8 strict and 0.8 tolerant with NE-columns only, and the minimum of 0.6 strict and 0.7 tolerant if all columns are included. Again this could be attributed to the lack of out-table context in this dataset.

11.2.2. Against state-of-the-art

Table 11 shows that TableMiner⁺ outperforms the re-implemented state-of-the-art models by a large margin in most cases. Surprisingly, models Limaye2010 and Mulwad2013 have underperformed many baselines in most occasions, particularly in the disambiguation task. This may be attributed to two reasons. First, as discussed before, the original work has used knowledge base specific features that are unavailable in Freebase, or supervised processes to optimize features. This has made the adaptation work difficult and although we have made careful attempt to implement alternatives, we cannot guarantee an identical replication of the original methods. Second, we observe that in the cell disambiguation task, both Limaye2010 and Mulwad2013 have only used features that are based on string similarity metrics. Our similarity baselines (B _lev , B_cos, B _dice ) also use string similarity features but add an important type of feature that proves to be very effective: a context score that compares the bag-of-words representation of candidate entities of a cell against the row context of the cell.

By using the disambiguation component of Table-Miner⁺, Mulwad2013^tm+ made significant improvement over Mulwad2013 on the cell disambiguation and column classification tasks. It also outperforms baselines in several occasions, but still obtained lower accuracy than TableMiner⁺.

The poor performance of all three models on the column classification task under strict mode is mainly due to the fact that the algorithms empirically favored general concepts (‘Person’) over more specific ones (‘Movie Directors’). Again this could be caused by the lack of a clean, strict concept hierarchy that could be more reliable reference of concept specificity than the alternative features we have to use in Freebase. However, concept hierarchies are not necessarily available in all knowledge bases. Nevertheless, TableMiner⁺ is able to predict a single best concept candidate in most cases without such knowledge. Additionally, the extremely poor accuracy on the IMDB dataset under the strict mode is largely because all tables in the dataset share the same schema.

We must re-iterate that despite our best effort, the re-implementation is not identical to the original works due to many reasons stated above. Hence following the practice adopted by Mulwad et al. [24], we also compare against state-of-the-art using reported figures in Table 12. As it is shown, TableMiner⁺ has obtained very competitive results.

OPEN IN VIEWER

Table 12

TableMiner⁺ on Limaye200 (classification and relation enumeration) and LimayeAll (disambiguation) and state-of-the-art reported figures. All results are based on NE-columns only. [24] and [35] report results under tolerant mode only, weighted average are used where necessary

	Disamb.	Class.	Relation
TableMiner strict	83.7	65.8	72.5
TableMiner tolerant		75.0	76.0
Limaye et al. [21]	84.1	44.5	58.3
Mulwad et al. [24]	75.9	54.9	83.5
Venetis et al. [35]	–	68.6	54.8

11.2.3. Remark

Overall, we believe these results are very positive. The rich context model adopted by TableMiner⁺ – especially the usage of out-table context – enables TableMiner⁺ to achieve the best performance in all tasks, and significantly outperform both baseline and state-of-the-art methods that ignore out-table contextual features in most cases. In particular, column classification appears to benefit most, suggesting that out-table context provides very useful clues for annotating table columns. The superior performance observed on the IMDB dataset further confirms this, and also shows that existing semantic markups within webpages can be very useful features in this task. Intuitively, when describing table content we tend to focus on the general information rather than specific data in individual table components, which possibly explains the particular contribution by out-table context to the column classification task. Moreover, results on the IMDB dataset also suggest that TableMiner⁺ can be easily adapted to solve tasks in list structures, which are essentially single column tables without headers.

11.3. Efficiency

Firstly, the efficiency of TableMiner⁺ is compared against the baselines B _lev , B_cos and B _dice that represent the exhaustive strategy. The three baselines are almost identical in terms of efficiency since they only differ in the string similarity metric used. Therefore, only B _lev is compared as an example.

Table 13 compares the wall-clock hours of Table-Miner⁺ against B _lev on the four datasets, and shows the proportion of time spent by TableMiner⁺ on data retrieval – including searching for candidate entities and retrieving their data from Freebase or cache. TableMiner⁺ is shown to be faster than B _lev , despite its complicated feature modeling and algorithmic computation.

OPEN IN VIEWER

Table 13

Wall-clock hours observed for TableMiner⁺ as savings against the baseline B lev

	Savings (hours)	Savings (% of  B lev )	% of time on data retrieval
Limaye200	3.7	21.7%	99%
LimayeAll	45.7	15.2%	97%
IMDB	3.9	4.1%	96%
MusicBrainz	34.3	28.6%	97%

OPEN IN VIEWER

Table 14

Candidate entity reduction in disambiguation operations by TableMiner⁺ compared against exhaustive baseline B lev and a would-be exhaustive TableMiner (exh-TableMiner)

	B lev	exh-TableMiner
	Overall	Overall	Constrained Disambiguation phase
Limaye200	48.4%	30.4%	39.2%
LimayeAll	52.2%	32.7%	41.4%
IMDB	10.6%	10.6%	59.4%
MusicBrainz	66.4%	44.3%	50.4%

TableMiner⁺ achieves efficiency improvement by using sample-driven column classification and reducing the number of candidates for cell disambiguation, therefore cutting down both the number of data retrieval and feature construction operations. Specifically, it benefits from two design features. First, the one-sense-per-discourse hypothesis ensures that values repeating on multiple cells in non-NE columns are disambiguated collectively costing only one operation. This avoids both repeated data retrieval and feature construction operations for the same set of entity candidates. Whereas classic methods disambiguate these cells individually, costing extra computation. Second, the bootstrapping approach in TableMiner⁺ reduces the total number of candidate entities by firstly creating preliminary column annotations using a sample instead of the entire column content, then using this outcome to constrain candidate space in entity disambiguation. Table 14 compares the total number of candidate entities processed during disambiguation operations in TableMiner⁺ against (1) the exhaustive baseline B _lev , and (2) a ‘would-be exhaustive TableMiner⁺’ (exh-TableMiner ⁺ ) which exploits one-sense-per-discourse but is forced to disambiguate every unique cell in the column before running column classification (i.e., without using I-Inf to create preliminary column annotations to constrain disambiguation). TableMiner⁺’s improvement is shown as reduction in % against the two reference methods.

Compared against the exhaustive baseline B _lev , TableMiner⁺ reduces the total number of candidate entities to be disambiguated by 10–67%. Note that the smallest improvement on the IMDB dataset is due to (1) the dataset being dominated by very small tables (see Fig. 7 on average less than 15 rows), and as a result, I-Inf in the LEARNING phase does not converge or converges relatively slowly (to be discussed in Appendix E); and (2) one-sense-per-discourse being void since only one column (hence the subject column) is available. Empirically, this translates to the very small improvement in wall-clock time shown in Table 13.

The reduction narrows when compared against exh-TableMiner ⁺ , however it still represents a substantial improvement. If we only consider the new cells to be disambiguated after the preliminary column classification phase, in which case the disambiguation candidate space is constrained by the preliminary column annotations (i.e., ‘constrained disambiguation phase’ in Table 14), TableMiner⁺ improves over exh-TableMiner ⁺ by a significant 39–60%.

OPEN IN VIEWER

Table 15

Number of entity candidates need to be retrieved from Freebase at the UPDATE phase

	Number	‰ of total
Limaye200	177	3.9‰
LimayeAll	7,762	5.1‰
IMDB	418	0.8‰
MusicBrainz	867	1.6‰

Furthermore, as mentioned before, one potential issue that may damage TableMiner⁺’s efficiency is that during the UPDATE phase, new entity candidates can be retrieved and processed, due to the change of winning concepts on a column in each update iteration. In the worst case, the total number of candidates to be retrieved from Freebase equals that in an exhaustive method. However, empirically it is found that this rarely happens. The number of entity candidates to be retrieved from Freebase in the UPDATE phase are shown in Table 15, compared to the total number of new entity candidates retrieved from Freebase by TableMiner⁺ in all phases. Further, Table 16 shows the number of iterations until stabilization is reached in the UPDATE phase. It suggests that the UPDATE phase stabilizes very fast. Compared to the semantic message passing algorithm in Mulwad et al. [24], at high-level, the iterative UPDATE phase is similar to running semantic message passing on a graph containing two types of variable nodes – column headers and content cells – and one type of factor nodes that model compatibility between the variable nodes. This is a much simpler graph than that used by Mulwad et al., which can fail to converge and empirically a threshold must be used to exit the loop.

OPEN IN VIEWER

Table 16

Number of iterations until stabilization at the UPDATE phase. 1 itr – fraction of tables on which the UPDATE phase stabilizes after 1 iteration

	Max.	Avg.	1 itr.
Limaye200	4	1.3	72.8%
LimayeAll	5	1.3	75.8%
IMDB	4	1.2	79.7%
MusicBrainz	4	1.3	73.1%

Secondly, we compare TableMiner⁺ against Limaye2010 and Mulwad2013. To factor out network latency we re-run the three systems using cached Freebase data and compare the wall-clock time. Note that TableMiner⁺ and Mulwad2013 are both run in a single thread while Limaye2010 is run with parallelization using 50 threads. Both Mulwad2013 and Limaye2010 exhaustively process the entire table before running inference algorithms. Table 17 shows that TableMiner⁺ is the most efficient, completing the annotation tasks faster than the other two systems. It is significantly faster than Limaye2010, which spent an enormous amount of time on computing similarity between pairs of entity and concept candidates in each column. The improvement by TableMiner⁺ is rather compelling: had we implemented parallelization for TableMiner⁺, the savings in wall-clock time would be in the orders of magnitude. We believe this is convincing evidence that Semantic Table Interpretation can significantly benefit from efficient algorithms, while parallelization can only be partial solution.

OPEN IN VIEWER

Table 17

Wall-clock hours observed for TableMiner⁺ (1 thread), Mulwad2013 (1 thread), and Limaye2010 (50 threads) when only local cache is used

	Table Miner+	Mulwad 2013	Limaye 2010
LimayeAll	4.6	5.4	76.0
IMDB	2.3	2.5	28.5
MusicBrainz	1.0	1.9	9.0

11.4. The effect of using partial content for interpretation

TableMiner⁺ uses partial content from a table column to perform preliminary column classification, the outcome of which is used to guide preliminary cell disambiguation. The annotations are then revised by the UPDATE process, which allows evidence from the remaining content from the table to feed back into the annotation process. Hence one question that remains to be answered is whether a Semantic Table Interpretation system that is purely based on partial data can be as good as systems that use the entire table content.

To answer this question we carry out additional experiments that are detailed in Appendix E. First, we drop the UPDATE phase from TableMiner⁺ to create a model TM iinf nu ( nu means ‘no update’). Effectively, this means that preliminary column classification in TM iinf nu will create the final column annotations using a sample from each column, and preliminary cell disambiguation will create the final cell annotations based on the column classification results. Next, we create alternative models by replacing the stopping criteria automatically calculated by I-Inf in TM iinf nu with arbitrarily set sample size. For example, we may configure the system to use a maximum of 10 rows from a column in preliminary column classification.

Results have shown that TM iinf nu still consistently outperforms the best performing baseline in almost all occasions. Compared against the alternative models using arbitrarily set sample size, it is able to obtain either the best or very close (with a difference of merely 0.1–0.6 point) performance in accuracy. We believe that these further confirm that: (1) Semantic Table Interpretation can benefit from using various in-table and out-table features; (2) it is possible to achieve higher accuracy using only partial data in the task, improving both effectiveness and efficiency; (3) the I-Inf algorithm is very robust as it is able to automatically determine an optimal sample size for column classification.

12. Conclusion

This work introduced TableMiner⁺, a Semantic Table Interpretation method that annotates tabular data for semantic indexing, search and knowledge base population. We have made several contributions to state-of-the-art. First, TableMiner⁺ uses various context both inside and outside tables as features in Semantic Table Interpretation. This is shown to be particularly useful for improving annotation accuracy. Second, TableMiner⁺ is able to make inference based on partial content sampled from a table. This is shown to deliver significant efficiency improvement against state-of-the-art methods that exhaustively process the entire table. Third, TableMiner⁺ offers a comprehensive solution, solving all annotation tasks of Semantic Table Interpretation and deals with both entity and literal columns. And finally, we release the largest collection of datasets as well as the first publicly available software for the task.

Extensive experiments show that TableMiner⁺ outperforms all baselines and re-implemented (near identical) state-of-the-art methods on any datasets under any settings. On the two most diverse datasets covering multiple domains and different table schemata, it significantly improves over all the other models by up to 42 percentage points. Compared against classic, exhaustive baselines, TableMiner⁺ reduces empirical wall-clock time by up to 29% and in the column classification task alone, but uses only 55% of table content (as opposed to 100% by exhaustive methods) to classify columns in the two most diverse datasets. It is also significantly faster than the re-implemented methods even when network latency is eliminated by using a local copy of the knowledge base.

TableMiner⁺ is however, still limited in a number of ways. First, relation enumeration is yet incomplete, as TableMiner⁺ only handles binary relations between the subject column and other columns. Second, several threshold setting (e.g., I-Inf convergence threshold) and weighting in formulas (e.g., subject column score formula) could be improved by using machine learning techniques to learn optimal configurations from data. Third, TableMiner⁺ is evaluated using Freebase, and in the general domain. Plans are made to evaluate it with other knowledge bases such as DBpedia and WikiData, as well as adapting to domain specific contexts. We will explore these directions in the future work.