This paper describes a novel approach to automate extraction of useful information from tables and to record the knowledge procured in a structured data repository. The approach is based on modeling a behavior of an expert, who collects tabular data and maps them to a predefined relational schema. Experimental results demonstrate that the proposed approach predicts expert decisions with high accuracy and thus significantly minimizes the time required of an expert for data aggregation.
Tables are widely used in scientific, financial and other analytical documents to concisely communicate information to human readers. A table usually contains information about objects of the same type. These objects can be easily perceived by the reader through content and relations between different table elements (cells, rows, etc.), because he/she is experienced in table reading and is able to take in both semantic and structural information. Sometimes two tables with exactly the same structure are interpreted completely different just because of slight difference in the external context or because the content of some cells differs.
However, it is hard to automate table analysis and information is extracted mainly by hand by interested parties. A common scenario used by experts is manual cell by cell extraction of data from a table into a relational database, and then using OLAP or other techniques to generate reports and perform analytics over these data. Efforts required for manual extraction are considerable, while the time of experts is always costly.
There is no end-to-end solution for automatic
information extraction from arbitrary tables. And as it
appears to us, construction of a fully automatic
instrument is hardly feasible. It might be possible to
parse automatically the structure of any table, but
semantic interpretation of tabular data requires the
knowledge of a domain expert. Embley et al. [
We present a semi-automatic approach that tracks actions of a domain expert, when he/she begins to process a table (map cell data to a relational scheme), derives regularities/patterns of expert behavior, and applies them to the rest of the table in order to predict further mappings.
This paper is organized as follows: In Section 2 we give an overview of related works. Section 3 discusses the table format used in our work. Section 4 describes the general architecture of our prototype, while Section 5 describes it in details. Section 6 presents our experimental evaluation. We conclude in Section 7.
Silva et. al [
Zanibbi et. al [
Embley et al. [
More recent work of Embley and
Krishnamoorthy [
Vasudevan et. al [
Gatterbauer et al. [
Looking at semi-automatic tools, Google Refine1 should be noted. It is "a power tool for working with messy data, cleaning it up, transforming it from one format into another, extending it with web services, and linking it to databases like Freebase". However, Google Refine is mostly for data cleansing and is not capable of performing information extraction and interpretation. It also cannot track user decisions and anticipate them.
Similarly, Microsoft Excel2 can perform such transformations using formulas and macros, but it demands user to define these formulas explicitly.
Praedea3 is another semi-automatic tool that uses predefined text-mining models (chosen by user) for extracting required data from unstructured documents and mapping them to database or XML scheme. It is not capable to process a table in case there is no suitable predefined model for it. 1 http://code.google.com/p/google-refine 2 http://office.microsoft.com/en-us/excel/
Thus, except for the highly specialized programs
like VeriClick and commercial tools like Google Refine
or MS Excel, we are not aware of any research on
interactive information extraction from tables; and the
authors of VeriClick confirm this observation [
Like other basic notions, 'table' has a lot of different definitions.
Peterman et al. [
Tijerino et al. [
In this work we consider a table to be a set of cells with some text content. In other words, it is the only property of a table that is used explicitly; other properties like repetitive structure or the same datatype in a column or a row are considered by our method implicitly.
Our prototype takes HTML tables as an input; therefore we use terminology from HTML in order to describe cell properties; for example, colspan as a relative width of a table cell. However, our method does not depend on any specific properties of HTML format.
We use classical spreadsheet addressing for cells. For example, A2 of Table 1 is an empty cell in the first column and the second row with rowspan equal 2.
Assume that a user processes a table step-by-step. During each step the user selects multiple cells from the table and maps them to a record in a relational database. Let us define user feedback as information about mappings from a single user step. See Table 2 for an example of the initial user feedback provided by him/her while processing Table 1.
The prototype takes as input an HTML table and enriches it by the predefined Natural Language Processing pipeline; currently we add only information about Named Entity types.
Enriched table is further processed by the main part of the prototype - Table processor on the diagram. It generates output, which has the same format as the user feedback, i.e. information about mappings that assumed to be obtained by the user. This output is reviewed by the user and he/she returns feedback. The prototype stores information from the user feedback into the Target database and uses this feedback in order to generate the next output. History means a local storage of the previous feedbacks, including ones from other tables that were already processed by the user. Information about previous actions is also used by the prototype for the output generation.
Our approach is based on two observations: (a) each table is a layout structure for storing similar objects; and (b) closely located tables (e.g. from the same document or Web-site) usually share similar structure and context. A user processes similar objects from the same table sequentially by repeating similar actions; and this repetition allows the system to learn and anticipate the forthcoming actions. The key idea of the approach is to consider the shift from one user step to the next one. More precisely, a shift consists of row and column offsets (possibly zero) for each cell represented in a pair of sequential user feedbacks. Since any table contains several objects of the same type and structure, we try to recognize it by tracking sequential user steps.
Table 3 shows an example of a shift from the first feedback (underlined words) to the second one (bolded words). Note that some cells remain fixed, e.g. B2.
Shift approach is used in different ways depending on the number of the available user feedbacks. In section 5.1 we describe a regular phase of our algorithm: when at least two user feedbacks are available and we can explicitly compute shifts. Section 5.2 presents the phase when we have only one user feedback and have to guess a correct shift. Section 5.3 considers the phase when user starts to process a table and we have to predict his/her actions based on the previously processed tables.
After two user steps we can construct a shift by computing row and column offsets explicitly for every cell. For example, after two steps of processing Table 1 the following shift is constructed: the first two cells are shifted down by one cell and the third cell stays at the same position.
The constructed shift is further applied to cells of the last user step in order to get new cells and create a new row in a relational database with the same relation/attribute information and new values taken from new cells.
As it was shown in the example above, sometimes the value returned by the user is not just a text content of the cell, but its derivative: compare “FY 2009” in Table 1 with just “2009” in the feedback, Table 2. Solution of this problem is based on the observation that shifted cells share similar structure of their content. We store the way of producing the value from the cell in form of a regular expression. More precisely, we have prepared a set of patterns, which should be tested to match cell content against the value returned by the user within his/her feedback. Currently there are two types of patterns: (a) taking a substring of original cell content, and (b) replacing a substring of original cell content with another predefined string. Patterns of both types contain corresponding regular expressions to be applied to cell content.
.*::::0 (.*)\s(.*)::::1::::2 (\d+)::::1 thousand::::000::::ReplaceAll
Patterns of the first type also contain matching group numbers to be taken into account; patterns of the second type contain a replacement string and a key word ReplaceAll in order to distinguish this type. See Table 4 for the examples of cell value patterns. Sequence of colons (::::) serves as a delimiter.
These patterns work as follows. Assume, have a cell with content “FY 2009” and the corresponding feedback value is “2009”. We try to apply the first pattern (.*) to cell content, which means that we simply take the whole content as is. The result does not match with the feedback value. Then we try the next pattern ((.*)\s(.*)::::1::::2). The result matches with the feedback value and we store this pattern for the corresponding cells of the shift.
If there are more than two steps produced by the user, then we construct candidate shifts for all paired combinations of user feedbacks, assess them, and choose the best shift in order to apply it to cells of the last user feedback. For example, if there are 3 feedbacks, we construct 3 candidate shifts: 1-to-2, 1-to3, and 2-to-3; all 3 candidate shifts are assessed independently, and the best shift is then applied to the last, 3rd feedback.
Shift assessment is performed by computing linear combination of the following 4 features:
Average shift length: normalized sum of lengths of cells offsets. For the example shift, there are 2 offsets having length 2 and 1 offset having length 0, so the feature value is 2/3.
Motivation: people tend to process the table sequentially, taking closest cells if possible. In other words, shorter shifts are preferable by users.
We also tried different weights for different directions, e.g. bigger weight for the right offset than for the down one, because top-down processing seem to be more common, but experiments show that different weights do not introduce any positive effect.
most common cells offsets. For the shift in the example, there are 2 types of offsets: 2 down-by-1 offsets and 1 remain-fixed offset, so the feature value is 2/3 again.
Motivation: a shift usually contains similar offsets of cells, e.g. all 4 cells are shifted down by 1 more often, then when 2 cells are shifted down by 1 and other 2 cells are shifted down by 2 or right by any number.
Average text similarity: normalized value of string similarity metrics computed over corresponding (shifted) cells contents.
Motivation: when we shift one cell to another, both of them must contain values of the same attribute, and different values of the same attributes are usually similar text strings.
To compute such similarity we tried several string
metrics taken from SimMetrics4, the best results have
been obtained using Levenstein distance [
Named entity type consistency: predefined value for 3 cases depending on named entity types of cells contents: 1. Named entity types are equal – value is 1; 2. Named entity types are unequal – value is 0; 3. Named entity types are both undefined – value is 0.5;
Motivation is the same as in the previous feature,
but here we utilize information about named entity
types in order to check attribute consistency. We use a
conditional random field (CRF) model with a
combination of different popular features applied in
supervised named entity recognition [
Coefficients for the linear combination are chosen experimentally to maximize the accuracy: we test all possible values from 0 to 1 with step 0.2 so that their sum equals to 1. We found the best accuracy to be obtained with 0, 0.4, 0.2, 0.4 correspondingly; the further granulation does not change the result.
Given one user feedback we need a shift to apply it to this user feedback as it is done in Regular phase. There are two ways: take a most appropriate shift from the previously processed tables or construct a shift from 4 SimMetrics is a Similarity Metric Library provided by UK Sheffield University http://sourceforge.net/projects/simmetrics/ scratch. To find the most appropriate shift we check all stored shifts for applicability, and then assess similarity of all applicable shifts modified in accordance with the current table. To assess the modified shift we use the linear combination as in section 5.1, but coefficients are re-estimated (0.2, 0, 0.6, 0.2).
This way is very similar to No user feedback phase, see Section 5.3 for details. In short words, modification means that we replace contents of cells in the shift by the contents of the corresponding cells of the current table. For example, if there is a stored shift (from some previously processed table) with just one cell offset – C4-to-C5 with contents “USA”-to-“Russia” – then we modify the shift so that now contents of the cell offset is “20”-to-“60”: we take contents of C4 and C5 cells of Table 1. Note that if the shift contains cell offset like B1-to-B2 with ordinary colspan and rowspan (all equal to 1), then such the shift is inapplicable for the Table 1, because B1 and B2 cells of this table have different colspans.
If there is no suitable shift, i.e. similarity of the best shift does not reach a predefined threshold, then we construct a new one. For this purpose, we iterate over combinations of all possible offsets of row and column for each cell. To limit combinatorial explosion we do not consider offsets above predefined thresholds: 5 for rows and 3 for columns. Each offset combination is actually a shift that can be assessed as it is described above; coefficients are left the same.
When no user feedback is available for the current table, we can use information about previously processed tables. We store all user feedbacks during table processing for the case if some of them have a structure (set of cell positions) appropriate for a new table. To choose the most appropriate user feedback we first check all of them for applicability, i.e. current table must have cells in all cell positions of the user feedback, and these cells must have the same characteristics — particularly, colspan and rowspan. Then all applicable user feedbacks are assessed by constructing and assessing special "fake" shifts from the stored feedback to the feedback obtained by applying the stored feedback structure to current table. Assume we have a feedback shown in Table 5 from the already processed Table 6 and we just begin to process Table 1.
Then we take a structure of the stored feedback, that is actually a cell position and a cell pattern, and apply it to the considered Table 1, see Table 7.
After that we construct a shift from the stored feedback (Table 5) to the obtained feedback (Table 7) and assess it in the way described in section 3.1 with reestimated coefficients (0.2, 0, 0.4, 0.4). Such assessment allows us to choose the most similar table among all already processed ones.
Note that the stored feedback from the 3rd row, but not 4th, is not applicable to Table 1, because A3 cells have different rowspans.
We compiled a set of 30 tables containing financial reports and a set of more than 150 corresponding user feedbacks5. We use the following test metrics: accuracy, precision and recall. Accuracy shows the fraction of outputs that fully match the user feedback: if at least one value in the tool output is wrong, the whole answer is considered to be wrong. Precision and recall characterize the number of correct cell mappings. Obviously, precision and recall can be much higher than accuracy, because many answers are partially correct.
Table 8 shows the results for the regular phase; the 2nd and the 3rd rows show efficiency of shift constructing module and shift choosing module respectively. We consider the shift constructor to work correctly if there is a right output (maybe not the chosen one); for the shift chooser we count only those outputs when there is a correct shift constructed and thereby the shift chooser had a chance to choose it.
Table 9 shows the results for the first 2 phases. Easy to see that these results depend on feedbacks from previously processed tables, because each user feedback is stored during the processing and affects the following outputs. However, the order of tables inside the 5 Dataset's URL : http://modis.ispras.ru/datasets/td.zip document may be valuable; therefore, we shuffle order of blocks containing tables from the same document.
It is worth mentioning that the results of the first two phases also depend on stored shifts (feedbacks, for the first phase) and at the begging of the work, without any stored shift, we face the problem of cold start. That is why we add tests with prepared set of 5 simple stored feedbacks and shifts from other tables.
In addition, we also run tests when all feedbacks and shifts from the same 30 test tables are stored and used for the testing. Of course, it is not an absolutely fair test, because there are stored feedbacks and shifts with strictly the same text content, but these tests may help to understand if the mistakes are caused by the problem of missing stored shifts or the incorrect choice of the stored shift to be applied.
Some mistakes in the regular phase could be explained by the following: sometimes a user goes from the top to the bottom of the left part of the table (e.g. takes all values from the first and the second columns) and then he/she repeats the similar actions for the right part (takes all values from the first and the third columns). Our tool cannot predict a correct shift at the moment when the user switches to the right part, that is why results for shift constructor are low.
In this paper, we focused on the task of semi-automatic data extraction from tables and mapping them to relational scheme; we introduce novel approach that tracks user decisions to predict forthcoming ones; we evaluated it on our test data.
Shift approach provides general scheme for semiautomatic table processing, but many problems are out of scope of this research. One of them is extraction of value from table cell. In most cases it is sufficient to take text substrings (see cell B2 in Table 1), but sometimes certain table cell is actually a set of different attribute values that should be processed by more complex methods. For instance, a price list of a hardware store often contains cells like the following:
HP "Pavilion dm4-2102er" QJ453EA (Core i5 2430M-2.40GHz, 6144MB, HD6470M, WebCam)
Another direction of further research is related to target scheme: currently we copy information about relation and attribute for shifted cells, but methods that are more sophisticated can consider semantics of both table content and relational scheme.