Error correction in tables using a question and answer system

Mechanisms are provided for performing tabular data correction in a document. The mechanisms receive a natural language document comprising a portion of content and analyze the portion of content within the natural language document to identify an erroneous sub-portion comprising an erroneous or missing item of information. The mechanisms generate a semantic signature for the erroneous sub-portion and generate a query based on the semantic signature. The mechanisms apply the query to a knowledge base to identify a candidate sub-portion of content. The mechanisms correct the erroneous sub-portion using the identified candidate sub-portion of content to generate a corrected natural language document.

BACKGROUND

The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for performing error correction in tables using a Question and Answer (QA) system.

Documents include information in many forms. For example, textual information arranged as sentences and paragraphs convey information in a narrative form. However, some types of information are presented in a tabular organization. For example, a document can include tables for presenting financial information, organizational information, and more generally, any data items that are related to one another through some relationship.

Natural language processing (NLP) is a technique that facilitates exchange of information between humans and data processing systems. For example, one branch of NLP pertains to transforming a given content into a human-usable language or form. For example, NLP can accept a document whose content is in a computer-specific language or form, and produce a document whose corresponding content is in a human-readable form.

SUMMARY

In one illustrative embodiment, a method, in a data processing system comprising a processor and a memory, for performing tabular data correction in a document is provided. The method comprises analyzing, by the data processing system, a portion of content within a natural language document to identify an erroneous sub-portion comprising an erroneous or missing item of information. Moreover, the method comprises generating, by the data processing system, a semantic signature for the erroneous sub-portion and generating, by the data processing system, a query based on the semantic signature. In addition, the method comprises applying, by the data processing system, the query to a knowledge base to identify a candidate sub-portion of content. Furthermore, the method comprises correcting, by the data processing system, the erroneous sub-portion using the identified candidate sub-portion of content to generate a corrected natural language document.

DETAILED DESCRIPTION

The illustrative embodiments are directed to correcting erroneous or missing portions of content of a document using a Question and Answer (QA) system and queries generated from the context of the document surrounding the erroneous portion of the content. In some illustrative embodiments, the erroneous or missing portions of content comprise values in cells of table data structures, the context of the document comprises discovered functional dependencies within the table data structures between portions of the table data structures or across one or more different table data structures, and the natural language conversions of cell information into queries are used by a QA system to correct the erroneous or missing portions of content. For purposes of the following discussion, it will be assumed that the illustrative embodiments operated on tables in documents, however it should be appreciated, as noted above, that the mechanisms of the illustrative embodiments may be applied to any portion of content in a document where the portion of content is determined to be likely erroneous or missing and where context information associated with the identified portion of content may be used as a basis for generating one or more queries to be presented to a QA system, as described in greater detail hereafter.

Assuming illustrative embodiments operating on table structures in documents, it should be appreciated that the table data structures may be provided in various formats including as separate table data files or embedded in other data structures, such as documents of a corpus of information, for example. Moreover, various processing operations may be applied to such table data structures by various applications, algorithms, and the like, or may be the impetus for erroneous or missing data values in table data structures. One such processing operation that may be applied is natural language processing (NLP) of a document that contains a table data structure. Another type of operation that is applied to a document which may result in table data structures, or other portions of content, having erroneous or missing data values or content is optical character reading (OCR). Still other types of operations include manual input of table data into an application to generate a table data structure. Any processing operation that may result in, or be applied to, a table data structure may be the focus of the mechanisms of the illustrative embodiments.

For purposes of the following description, it will be assumed that the mechanisms of the illustrative embodiments will be applied to table data structures embedded or otherwise associated with a document in a corpus of information for the purpose of performing natural language processing on the table data structure. However, it should be appreciated that this is only one possible implementation and the mechanisms of the illustrative embodiments are not limited to such. Rather, the scope of the illustrative embodiments of the present invention is intended to encompass any table data structure and any processing operation that may be applied to a corrected table data structure including, but not limited to, table data structures embedded in documents and NLP operations being applied to corrected table data structures.

Using NLP as an example processing operation to be applied to a table data structure, the illustrative embodiments recognize that documents subjected to NLP commonly include tabular data, to wit, content in the form of one or more tabular data structures (tables). A cell of a table is a containing unit within a table, such that the contents of the cell can be uniquely identified by a row and column or other suitable coordinates of the table.

The illustrative embodiments recognize that information presented within the cells of a table often relates to information in other cells of the same table, cells of a different table in the same document, or cells of a different table in a different document. The relationships between the information contained in different cells is important for understanding the meaning of the tabular data, and generally for understanding the meaning of the document as a whole.

The illustrative embodiments recognize that specialized processing or handling is needed in NLP for interpreting the tabular data correctly and completely. Presently available technology for understanding the relationship between cell-values is limited to heuristically guessing a label for a cell using the row or column titles.

Moreover, the illustrative embodiments recognize that tables within electronic documents may contain incorrect or missing information due, for example, to faulty optical character reading (OCR) scan operations, corrupted data, incorrect data entry by human beings, or any other possible source of error. Furthermore, these tables may contain information that is critical for understanding the document in general and thus, it is important to correct the information wherever possible.

The illustrative embodiments used to describe the present invention generally address and solve the above-described problems and other problems related to the limitations of presently available NLP technology with regard to its processing of table information in electronic documents. The illustrative embodiments provide a method, system, and computer program product for discovering relationships in tabular data and for correcting incorrect or missing information in such tabular data based on discovered functional dependencies. Moreover, the illustrative embodiments provide mechanisms for generating queries from the document containing the erroneous or missing content, e.g., data values in cells of a table data structure, and utilizing a Question and Answer (QA) system, such as the Watson™ QA system available from International Business Machines Corporation of Armonk, N.Y., to determine the correct content to replace the erroneous or missing content in the document.

With regard to discovering functional dependencies, the illustrative embodiments recognize that a cell in a table can depend on one or more other cells in the table, cells across different tables in the given document, or cells across different tables in different documents. The dependency of one cell on another is functional in nature, to wit, dependent based on a function. The functions forming the bases of such functional dependencies can be, for example, any combination of mathematical, statistical, logical, or conditional functions that operate on certain cell-values to impart cell-values in certain other cells. As an example, a cell containing a total amount value is functionally dependent upon the cells whose values participate in the total amount value calculation. As another example, a statistical analysis result cell, such as a cell containing a variance value in an experiment, can be functionally dependent on a set of other cells, perhaps in another table, where the outcomes of the various iterations of the experiment are recorded.

These examples are not intended to be limiting on the illustrative embodiments. Functional dependencies are indicative of relationships between the cells of one or more tables, and are highly configurable depending on the data in a table or document, purpose there for, and the meaning of the various cells. Furthermore, a cell can participate in any number of functional dependencies, both as a dependant cell and/or as a depended-on cell. Because information in a cell can relate to information available anywhere in a given document, a functional dependency of a cell can include depending on non-tabular data in a given document as well.

The illustrative embodiments improve the understanding of the information presented in tabular form in a document by enabling an NLP tool to understand relationships of cells of tabular data. The illustrative embodiments provide a way of determining the functional dependencies of cells in a table on other cells, surrounding text of the table, contents in a document, or a combination thereof. Moreover, the illustrative embodiments provide mechanisms for correcting incorrect data in these cells or completing the data in cells where there is missing data based on the detected or discovered functional dependencies. Furthermore, these functional dependencies and other context information extracted from the document, in which the erroneous or missing content is present, may be used to generate queries that can be submitted to a QA system which then applies these queries to a corpus of documents to ascertain the correct content, e.g., data values in an cell of a table, to replace the erroneous or missing content in the document.

Illustrative embodiments described herein improve both precision and recall in natural language processing of a document with tabular data. Typically, attempts to improve precision result in degraded recall performance, and vice versa. The term “precision” refers to a measure of how much of what is understood from a table is correct, over how much is understood from the table. The term “recall” refers to a measure of how much is understood from the table, over how much information there actually is to understand in the table. Through the use of the mechanisms of the illustrative embodiments, both are improved.

The illustrative embodiments are described with respect to certain documents and tabular data only as examples. Such documents, tabular data, or their example attributes are not intended to be limiting to the invention. Furthermore, the illustrative embodiments may be implemented with respect to any type of data, data source, or access to a data source over a data network. Any type of data storage device may provide the data to an illustrative embodiment of the present invention, either locally at a data processing system or over a data network, without departing from the spirit and scope of the illustrative embodiments.

The above aspects and advantages of the illustrative embodiments of the present invention will be described in greater detail hereafter with reference to the accompanying figures. It should be appreciated that the figures are only intended to be illustrative of exemplary embodiments of the present invention. The present invention may encompass aspects, embodiments, and modifications to the depicted exemplary embodiments not explicitly shown in the figures but would be readily apparent to those of ordinary skill in the art in view of the present description of the illustrative embodiments.

Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium is a system, apparatus, or device of an electronic, magnetic, optical, electromagnetic, or semiconductor nature, any suitable combination of the foregoing, or equivalents thereof. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical device having a storage capability, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber based device, a portable compact disc read-only memory (CDROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium is any tangible medium that can contain or store a program for use by, or in connection with, an instruction execution system, apparatus, or device.

In some illustrative embodiments, the computer readable medium is a non-transitory computer readable medium. A non-transitory computer readable medium is any medium that is not a disembodied signal or propagation wave, i.e. pure signal or propagation wave per se. A non-transitory computer readable medium may utilize signals and propagation waves, but is not the signal or propagation wave itself. Thus, for example, various forms of memory devices, and other types of systems, devices, or apparatus, that utilize signals in any way, such as, for example, to maintain their state, may be considered to be non-transitory computer readable media within the scope of the present description.

FIG. 1depicts a pictorial representation of a network of data processing systems in which illustrative embodiments may be implemented. Data processing environment100is a network of computers in which the illustrative embodiments may be implemented. Data processing environment100includes network102. Network102is the medium used to provide communications links between various devices and computers connected together within data processing environment100. Network102may include connections, such as wire, wireless communication links, or fiber optic cables. Server104and server106couple to network102along with storage unit108. Software applications may execute on any computer in data processing environment100.

In addition, clients110,112, and114couple to network102. A data processing system, such as server104or106, or client110,112, or114may contain data and may have software applications or software tools executing thereon.

Only as an example, and without implying any limitation to such architecture,FIG. 1depicts certain components that are usable in an example implementation of an embodiment. For example, Application105in server104is an implementation of an embodiment described herein. Application105operates in conjunction with Natural Language Processing (NLP) engine103. NLP engine103may be, for example, an existing application capable of performing natural language processing on documents, and may be modified or configured to operate in conjunction with application105to perform an operation according to an embodiment described herein. Storage108includes library of hypotheses109according to an embodiment. Client112includes document with tabular data113that is processed according to an embodiment.

Servers104and106, storage unit108, and clients110,112, and114may couple to network102using wired connections, wireless communication protocols, or other suitable data connectivity. Clients110,112, and114may be, for example, personal computers or network computers. In the depicted example, server104may provide data, such as boot files, operating system images, and applications to clients110,112, and114. Clients110,112, and114may be clients to server104in this example. Clients110,112,114, or some combination thereof, may include their own data, boot files, operating system images, and applications. Data processing environment100may include additional servers, clients, and other devices that are not shown.

With reference toFIG. 2, this figure depicts a block diagram of a data processing system in which illustrative embodiments may be implemented. Data processing system200is an example of a computer, such as server104or client112inFIG. 1, or another type of device in which computer usable program code or instructions implementing the processes may be located for the illustrative embodiments.

Memories, such as main memory208, ROM224, or flash memory (not shown), are some examples of computer usable storage devices. Hard disk drive226, CD-ROM230, and other similarly usable devices are some examples of computer usable storage devices including computer usable storage medium.

With reference toFIG. 3, this figure depicts an example of tabular data within which functional dependencies can be identified in accordance with an illustrative embodiment. Table300is an example of tabular data appearing in document113inFIG. 1within which functional dependencies can be determined using application105inFIG. 1, for example.

The horizontal or vertical rule-lines are depicted for bounding a table and cell only as an example without implying a limitation thereto. A table or tabular data can be expressed in any suitable manner, and a cell can be demarcated in any manner within the scope of the illustrative embodiments. For example, indentation, spacing between cell data, different spacing in tabular and non-tabular content, symbols, graphics, a specific view or perspective to illustrate tabular data, or a combination of these and other example manners of expressing tabular data and cells therein are contemplated within the scope of the illustrative embodiments.

Table302is a portion of table300and includes several headers that serve to organize the data in the various cells into headings, categories, or classifications (categories). The headers can be row-headers or column headers. The headers are not limited to the table boundaries or extremities within the scope of the illustrative embodiments. For example, a header can be embedded within a table, between cells, such as in the form of a sub-header, for example, to identify a sub-category of tabular data. Such sub-row or sub-column headers are contemplated within the scope of the illustrative embodiments. In one embodiment, certain header information can be specified separately from the corresponding tabular data, such as in a footnote, appendix, another table, or another location in a given document.

For example, header304identifies a group of columns, which include data for the broad category of “fiscal year ended January 31.” Headers306,308, and310identify sub-categories of the “fiscal year ended January 31” data, namely, by year for three example years.

Row headers312include some clues, both in content and organization, for identifying dependencies between cells. For example, row header314is a “total” and is indented under row headers316and318. Similarly, row header320is another “total” and is indented under row header322. The indentations at row headers314and320are example organizational clues that are useful in understanding the functional relationships between cells in the same row as row headers314and320, and other cells in table302. The word “total” in row headers314and320are another example of the content clues usable for determining functional dependencies of cells in their corresponding rows in a similar manner. That is, content clues may provide clues to functional relationships between cells by having terms, functional definitions, equations, or the like, that are identifiable and indicative of the relationships based on the content of the headers/cells themselves. The organizational clues provide clues based on their hierarchical or other organizational relationships with one another.

These example clues are not intended to be limiting on the illustrative embodiments. Many other clues or the content, organizational, or other types, will be conceivable from this disclosure by those of ordinary skill in the art, and the same are contemplated within the scope of the illustrative embodiments. Hereafter, the organizational, content, or other types of clues will be referred to collectively as “clues” for ease and clarity of the following description of the illustrative embodiments.

As can be appreciated, the same clues help understand the information in different cells differently. For example, consider table352, which is another portion of table300. Header354identifies a group of columns, which include data for the broad category of “Change.” Headers356and358identify sub-categories of the “change” data, in other words, comparisons of two consecutive years, from the three example years of categories306,308, and310.

Row headers312impart different meanings to the cells in their corresponding rows in tables302and352. For example, while the “total” according to row header314implies a dollar amount of income in the corresponding cells in table302, the same row header implies a dollar amount change and a percentage change in the corresponding cells in table352. As in this example table300, in an embodiment, the clues in one location, such as in row headers312, can also operate in conjunction with other clues, data, or content in other places, to enable determining the meaning of certain cells in a given tabular data.

With reference toFIGS. 4A and 4B, these figures depict a block diagram of a manner of discovering relationships in tabular data in accordance with an illustrative embodiment. Table400is the same as table300inFIG. 3. Tables402,452are analogous to tables302and352respectively inFIG. 3. Column headers404,406,408, and410are analogous to headers304,306,308, and310respectively inFIG. 3. Row headers412-422are analogous to row headers312-322respectively inFIG. 3. Similarly, column headers454,456and458of table452are analogous to headers354,356and358respectively inFIG. 3.

As noted with respect toFIG. 3, clues in and around a given tabular data can assist in determining the functional dependencies of a cell. Similarly, markups in a given table can also form additional clues and assist in that determination, reinforce a previous determination, or both. For example, lines424and426are example table markups that act as additional clues in determining functional dependencies of some cells. As noted above, lines or other notations for expressing a table or cell demarcation are only examples, and not intended to be limiting on the illustrative embodiments. Tables and cells can be expressed without the use of express aids, such as lines424and426, within the scope of the illustrative embodiments.

As an example, row header414indicates that cell428contains a total or summation of some values presented elsewhere, perhaps in table402. In other words, a clue in header414helps determine a functional dependency of type “sum” of cell428on some other cells.

Line424reinforces this determination, and helps narrow a range of cells that might be participating in this functional dependency. For example, an embodiment concludes that contents of cell428are a total, or sum, of the cell values appearing above line424up to another delimiter, such as another line, table boundary, or the like.

As another example, row header420indicates that cell430contains a total or summation of some values presented elsewhere, perhaps in table402. In other words, a clue in header420helps either determine or confirm a hypothesis of a functional dependency of type “sum” of cell430on some other cells.

Line426reinforces this determination, and helps narrow a range of cells that might be participating in this functional dependency. For example, an embodiment concludes that contents of cell430are a total, or sum, of the cell values appearing above line426up to another delimiter, such as another line, e.g., line424.

Lines424and426are described as example structural markups or clues only for clarity of the description and not as a limitation on the illustrative embodiments. Another example markup that can similarly assist in determining functional relationships between cells is a semantic clue, such as compatible row and column type. For example, when a row header of a cell indicates a revenue value and the column header of a cell indicates a year, it is likely that the cell in that row and column at least includes a revenue value in that year, and perhaps is related to certain other values in the same column by a sub-total type functional relationship. In this example, a clue relates to a specific cell. Such a cell-specific clue is useful in confirming a functional dependency for that cell, and may or may not be usable for confirming similar functional dependency across the whole column.

As another example, the presence of a common header404hints at a commonality in columns406,408, and410. Separately, an embodiment can conclude that the content of headers406,408and410all have semantic type “Year.” The embodiment determines a hint that these three columns are similar. When the embodiment finds that the same functional dependencies hold in those three columns, the embodiment assesses a confidence level in that finding using the fact that this hint or clue supports the confidence level. A hint as described above is a column-wide hint. A hypothesis that a dependency holds over a number of columns is a column-wide hypothesis. A column-wide hint is useful in supporting a column-wide hypothesis.

An embodiment uses some of the available markups or clues in and around the table to hypothesize a functional dependency. An embodiment further uses other available clues or markups to confirm the hypothesis, thereby improving a confidence level in the hypothesis. Essentially, a hypothesis is a framework of a functional dependency—a hypothetical relationship between hypothetical cells—which when applied to an actual table and constituent cells can be true or false for all cases where applied, or sometimes true and sometimes false.

A hypothesis is confirmed or supported, or in other words, confidence in a hypothesis is above a threshold, if clues or markups support an instance where the functional dependency according to the hypothesis yields a correct result. Confidence in a hypothesis is also increased from one value to another, such as from below a threshold level of confidence to above the threshold level of confidence, if the functional dependency according to the clue can be replicated at other cells or cell-ranges in the given tabular data (i.e., a clue holds true, or supports the hypothesis).

In machine learning terms each clue in a set of all possible supporting clues is called a “feature.” Presence or absence of a feature for an existing hypothesis increase or decrease the confidence level in that hypothesis. A “model” according to an embodiment is a mechanism to compute the confidence score for a hypothesis based on a subset of features that are present (or support) the hypothesis. In one embodiment, the model operates as a rule-based engine. In another embodiment, the model is ‘trainable’ by using a training set of tables for which confidence score is known a priori (i.e., a “labeled set”).

Library of hypotheses432is analogous to library of hypotheses109inFIG. 1. Library of hypotheses432is a collection of hypotheses that an embodiment, such as in application105inFIG. 1, receives for determining functional dependencies in table400. In one embodiment, a user supplies library of hypotheses432. In another embodiment, an application provides library of hypotheses432. In one embodiment, library of hypotheses432is a part of a larger library of hypotheses (not shown), and is selected according to some criteria. An example criterion for selecting the member hypotheses of library of hypotheses432can be domain-specificity. For example, library of hypotheses432may include only those hypotheses that are applicable to the domain of the tabular data being analyzed. Constituent hypotheses in library of hypotheses432can be changed as the tabular data changes.

In example library of hypotheses432as depicted, hypothesis434hypothesizes that some cells are a sum of some other cells in the same column, i.e., are “column sums,” or “col_sum.” Similarly, hypothesis436hypothesizes that some cells are a difference between certain other cells in the same row, i.e., are “row difference,” or “row_diff.” Hypothesis438hypothesizes that some cells are a division of certain other cell in the same row with another cell in the same row or a constant, i.e., are “row division,” or “row_div.”

Hypothesis440hypothesizes that some hypotheses repeat in different columns, i.e., are “column repeat,” or “col_repeat.” For example, “column sum” hypothesis434can repeat in column406, and in columns408and410. Similarly, hypothesis442hypothesizes that some hypotheses repeat in different rows, i.e., are “row repeat,” or “row_repeat.” For example, “row difference” hypothesis436can repeat in row416, and in rows418and414. Applicability of one hypothesis can boost the confidence in applicability of another hypothesis in this manner. In other words, if hypothesis434seems to indicate functional dependency between certain cells, and hypothesis440seems to validate the applicability of hypothesis434across more than one columns, an embodiment exhibits higher than a threshold level of confidence in the functional dependency indicated by hypothesis434.

Graph460shows the various example hypotheses in library of hypotheses432in operation on table400. For example, at element462in graph460, hypothesis col_sum appears to apply to a set of values bound between lines424and the beginning of data in table402, i.e., elements464and466in graph460, and results in the value in cell428. Similarly, at element468, hypothesis col_sum also appears to apply to the cells between lines424and426, one of which is a result of a previous application of the same hypothesis at element462, and the other is element470, and results in the value in cell430. Element472in graph460indicates that the arrangement of elements462,464,466,468, and470repeats according to hypothesis440in columns408and410in table402. Remainder of graph460similarly determines the functional dependencies in table452.

Thus, in the example depicted inFIGS. 4A and 4B, the examples of determined dependencies indicate repeatable patterns and are validated by the supporting computation on the cells involved. Given a suitable threshold level, an embodiment can express a confidence level that exceeds the threshold level. Accordingly, the embodiment outputs a natural language processed form of the cells of table400whereby the cell values are expressed, not only by reference to their denominations or headers, but also by their inter-relationships.

For example, the value in cell428would be expressed not only as “two million, one hundred fifty one thousand, three hundred and forty one dollars of total revenues and non-operating income in 2009” but also as “a total of the income in electric and gas categories of the revenues and non-operating income in the year 2009.” Such natural language processing with the benefit of an embodiment is far more useful and informative than what can be produced from the presently available NLP technology.

With reference toFIG. 5, this figure depicts a block diagram of an application for discovering relationships in tabular data in accordance with an illustrative embodiment. Application502can be used in place of application105inFIG. 1. Application502receives as inputs504and506, one or more documents with tabular data, and a library of hypotheses, respectively. Application502includes functionality508to locate instances of tabular data in input504. Using library of hypotheses506functionality510analyzes the functional dependencies of cell data in an instance of tabular data located by functionality508in input504.

In performing the analysis, functionality510uses functionality512to determine cell-ranges participating in a given functional dependency. Some example ways of determining cell-ranges using clues and markups are described in this disclosure.

Functionality514assesses a confidence level in a functional dependency analyzed by functionality510. Functionality510,512, and514operate on as many cells in as many table instances as needed in a given implementation without limitation. Application502outputs one or more NLP documents516, with table structures and functional dependencies identified therein, optionally including any suitable manner of indicating confidence levels in one or more such functional dependencies.

With reference toFIG. 6, this figure depicts a flowchart of an example process for discovering relationships in tabular data in accordance with an illustrative embodiment. Process600can be implemented in application502inFIG. 5. Process600begins by receiving a set of one or more documents that include tabular data (step602). Process600receives a library of hypotheses (step604). For example, the library of hypotheses can be limited to include only those hypotheses that are applicable to the subject-matter domain of the documents received in step602.

The complexity of finding functional dependencies increases exponentially with the size of table being analyzed and the number of hypotheses in a given library of hypotheses. Thus, an embodiment optimizes the detection of functional dependencies by limiting the number or types of hypotheses in a given library of hypotheses, limiting the cell-ranges to search for functional dependencies, or a combination thereof.

Process600selects a hypothesis from the library of hypotheses (step606). Process600selects a cell-range, such as by using clues, markups, or variations thereof, in some combination of one or more such clues, markups, or variations, across one or more tables or surrounding contents in one or more documents (step608). Process600determines whether the selected hypothesis fits the selected cell-range (step610). For example, as described with respect toFIGS. 4A and 4B, process600may determine whether a cell in question computes as a column sum from a cell-range bound by certain markups above that cell. This example way of determining whether the selected hypothesis fits is not intended to be limiting on the illustrative embodiments. Because the hypothesis being used can be any suitable hypothesis according to the documents being analyzed, any suitable manner of determining whether the hypothesis is satisfied can be used within the scope of process600.

If the selected hypothesis fits the selected cell-range (“Yes” path of step610), process600proceeds to step614. In one embodiment, after determining that a collection of clues support a hypothesis, process600assesses a confidence level in the functional dependency according to the hypothesis (block612). An embodiment implements block612separately from process600, and performs the confidence level assessment separately from process600, such as in a different iteration, pass, or process. An embodiment of block612is described as process700inFIG. 7.

Process600determines whether more tabular data has to be analyzed to determine functional dependencies of cells (step614). If more tabular data has to be analyzed (“Yes” path of step614), process600returns to step606. If no more tabular data is to be analyzed (“No” path of step614), process600outputs one or more NLP documents, with table structures and functional dependencies according to the hypotheses-fit and confidence (step616). Process600ends thereafter. In one embodiment, process600outputs table structures and functional dependencies data according to the hypotheses-fit and confidence, for use in an existing NLP engine, such as NLP engine103inFIG. 1, which produces the NLP document.

At step610, if process600determines that the selected hypothesis does not suitably fit the selected cell-range (“No” path go step610), process600determines whether the cell-range has been exhausted for the selected hypothesis (step618). For example, if the selected hypothesis is a “column sum” and the cell-range above the cell being evaluated has been reduced to zero cells, the cell-range would be exhausted for that hypothesis. Cell-range exhaustion is a hypothesis-dependent concept, and can be determined in any suitable manner according to the hypothesis being considered.

If the cell-range has been exhausted (“Yes” path of step618), process600determines whether more hypotheses remain to be tried for the cell whose function dependency is being analyzed (step620). If one or more hypotheses can be tried (“Yes” path of step620), process600returns to step606. If no more hypotheses are to be tried (“No” path of step620), process600proceeds to step614.

If a cell-range has not been exhausted (“No” path of step618), process600adjusts the cell range, such as by increasing the number of cells in the range, decreasing the number of cells in the range, changing to a different range of cells, or a combination of these and other possible changes (step622). Process600then returns to step610.

With reference toFIG. 7, this figure depicts a flowchart of an example process for assessing a confidence level in accordance with an illustrative embodiment. Process700can be implemented as block612inFIG. 6. One branch of process700begins by selecting a different cell-range according to similar markups or clues (step702). For example, in one embodiment, process700selects comparable cell-ranges in different columns or rows having similarly purposed data. In another embodiment, process700considers (not shown) other semantic clues, structural clues, denominations and type compatibilities among cells, suggestive words or phrases such as “total” or “sub-total”, or a combination of these and other aids to select a different cell-range to verify a fit for the selected hypothesis.

In other words, for a cell-range and a hypothesis that is true for that range an embodiment searches for a set of supporting clues (features). That set of supporting clues may include not only markups or semantic clues, but also other hypotheses that were found true on that cell-range. The embodiment thus finds a collection of supporting evidence for that hypothesis on that cell-range. The embodiment then computes a total confidence score based on the collection of supporting evidence.

Process700determines whether the hypothesis (a primary hypothesis) fits the new cell-range selected in step702(step704). If the hypothesis fits the new cell-range (“Yes” Path of step704), process700increases the confidence level in the functional dependency according to the hypothesis (step706). Process700ends thereafter. If the hypothesis does not fit the new cell-range (“No” path of step704), process700may end or repeat thereafter, leaving the confidence level unchanged, or may decrease the level of confidence (step708). For example, the value of a feature can be positive, zero or negative. For example, if there is no common header across three example columns, the value of the corresponding feature might be zero—that is, neutral. However, if the three columns have different semantic types, that feature will likely be negative thereby actually decreasing the confidence.

Another branch of process700begins by selecting a different hypothesis (a secondary hypothesis) fits the cell-range where another hypothesis (the primary hypothesis already fits), (step703). Process700determines whether the other hypothesis—the secondary hypothesis—fits the cell-range (step705). If the secondary hypothesis fits the cell-range (“Yes” Path of step705), process700increases the confidence level in the functional dependency according to the hypothesis at step706. Process700may end thereafter. If the secondary hypothesis does not fit the cell-range (“No” path of step705), process700may end or repeat thereafter, leaving the confidence level unchanged, or may decrease the level of confidence at step708.

When process700repeats, process700repeats for different cell-ranges and different secondary hypotheses in a similar manner. A repeat iteration evaluates different hypotheses across different ranges and found results. A secondary hypotheses may not apply to a cell-range initially, but, as more dependencies are discovered, the secondary hypotheses (and other higher-order hypotheses)(not shown) may start matching other cell-ranges and supporting other found results. Such matches or support may in-turn trigger testing other hypotheses, and so on (not shown).

During the confidence assessment phase an embodiment attempts to create a collection of various “features” that might increase the confidence level in a functional dependency. An embodiment regards the presence of second-order dependencies, as indicated by a secondary hypothesis fit (misfit), as yet another confidence-increasing (decreasing) feature. Applicability across cell-ranges is depicted in described in the several embodiments only as examples, without implying a limitation thereto. A feature set considered for confidence-level change is not limited only to range-similarity, but may be derived from many other characteristics of tabular data usable as clues, such as including but not limited to various markup clues, layout clues (i.e. common category header), semantic clues (i.e. all headers have the same semantic type (i.e. ‘Year’), and derived discovered dependencies like similar dependency in multiple rows.

Thus, a computer implemented method, system, and computer program product are provided in the illustrative embodiments for discovering relationships in tabular data. An embodiment uses a library of hypotheses to test whether portions of a given tabular data have a particular structure and functional dependency. A hypothesis is tested for one or more cell-ranges to determine whether an outcome of the hypothesis is supported by computations using the selected cell-ranges. A confidence level is associated with the functional dependency within the cell-range according to the hypothesis. The cell-ranges are selected based on a plurality of criteria including variety of clues and markups in the tabular data, content surrounding the tabular data or elsewhere in the given set of documents.

Clues and hypothesis confirmations are described using cell-ranges in some embodiments only as examples and not to imply a limitation thereto. Information, clues, or features, to support selecting a particular hypothesis can come from any portion of a given document, including content other than tabular data in the document, within the scope of the illustrative embodiments.

Some embodiments are described with respect to pre-determined hypotheses or known functions only as examples and not to imply a limitation on the illustrative embodiments. An embodiment can also hypothesize a previously unknown or un-programmed functional dependency, in the form of a learned function. For example, an embodiment may apply some analytical technique on data in a given table and find a statistical data pattern in the tabular data. The embodiment can be configured to account for such findings in the form of a learned function or learned hypothesis within the scope of the illustrative embodiments. The embodiment can then include the learned hypothesis into the collection for further validation or confidence level assessment.

The description of the examples and embodiments described herein are described with respect to clues, hypotheses, documents, tabular data, and NLP in English language is not intended to be limiting on the illustrative embodiments. An embodiment can be implemented in a similar manner using clues, hypotheses, documents, tabular data, and NLP in any language within the scope of the illustrative embodiments.

The above description illustrates the functionality of the present invention, in various embodiments, to identify functional relationships or dependencies between cells in tabular information of one or more documents during natural language processing of the one or more documents. The functional dependencies may be determined from within a single table structure of a single document, from across multiple table structures in a single document, or from across multiple table structures of multiple documents. The discovered functional dependencies may be utilized when performing natural language processing processes, such as may be used for various purposes. One such purpose is to utilize natural language processing as part of a Question and Answer (QA) system, such as the Watson™ QA system available from International Business Machines Corporation of Armonk, N.Y. For example, the discovered functional dependencies may be utilized by such a QA system when performing annotation operations for annotating documents of a corpus for later use in performing question answering operations.

In addition to the above, the illustrative embodiments further provide mechanisms for correcting incorrect information in table structures of documents or supplementing such table structures with information that might be missing from the table structures. That is, as mentioned above, information in table structures of documents may be incorrect or missing due to many different reasons including errors in optical character reading (OCR) operations, data corruption, user error when performing data entry, or the like. However, these table structures may contain information that is critical for understanding the document in general and thus, it is important to correct the information or provide the missing information whenever possible. The illustrative embodiments provide mechanisms for making such corrections, either automatically or with the assistance of a human user, based on the leveraging of redundant information in a corpus of documents and automatically generated queries based on the context surrounding the erroneous or missing table data values, submitted to a QA system. Based on the confidence of the results generated by the QA system, automatic or semi-automatic correction of erroneous or missing data values is performed.

With this additional capability of the illustrative embodiments, given a table structure, in a document, which contains an erroneous or missing value in a cell of the table structure, the illustrative embodiments correct or generate the value in the cell by generating one or more queries from the context surrounding the erroneous or missing value and submitting those one or more queries to a QA system for generating of candidate results which may be used to correct or generate the value in the cell. That is, from the discovered functional dependency structure discovered using the mechanisms previously described, the illustrative embodiments infer a substructure of a portion of the table which contains the incorrect or missing data values as conforming with the larger structure. Then, using this known relationship between individual cells, the illustrative embodiments generate one or more queries based on the known relationship, e.g., relationships between headers of columns/rows in the table data structure, etc. The queries are submitted to a QA system which applies the queries to a corpus of documents which then generates one or more candidate answers based on the queries and one or more corresponding measures of confidence. The measures of confidence may be compared against one or more threshold confidence values to select a candidate answer as a replacement for the erroneous or missing data value in the cell. Moreover, the measure of confidence of the selected candidate answer may be compared against a threshold value to determine if automatic replacement of the cell's data value is to be performed or if a notification is to be sent to a human user for authorization to perform the replacement. Thus, mechanisms are provided for correcting erroneous or missing content of a document, e.g., a data value of a cell in a table structure of a document, based on inferring the correct content from a corpus of documents.

This additional automatic or semi-automatic correction capability of the illustrative embodiments further augments the discovery of functional dependencies as described above by providing mechanisms for identifying erroneous cells in a table structure and then, having identified them, using the discovered functional dependencies and other context information to correct the erroneous cells, where an erroneous cell is a cell that either stores an incorrect data value or has a missing data value. Moreover, in some illustrative embodiments, rather than actually correcting an erroneous or missing data value in a table structure based on the discovered functional dependencies, operations may be invoked to alert a human user of the erroneous or missing data value indicating the nature of the error in the data value, e.g., a cell requiring a date value instead has a floating point value or the data value is simply missing, and suggesting a correct data value for replacing the erroneous or missing data value and providing the user with the option to accept or reject the suggested correct data value. If the user accepts the correct data value, then the table structure may be automatically updated. If the user rejects the correct data value, then the table structure may not be updated and the user may or may not instead specify a different data value to replace the erroneous or missing data value.

In order to identify erroneous cells, various algorithms and heuristics may be employed. For example, in one illustrative embodiment, a block of cells may be predefined, e.g., a certain number of columns and rows in the table structure may be specified, and the block of cells may be analyzed to determine if they have a regular structure, e.g., a repeatable pattern, defined or discovered dependency relationship, or the like. If the block of cells has a regular structure, the block of cells may be further analyzed to determine if one or more of the cells in the block of cells does not match the regular structure. For example, if a block of cells corresponds to a listing of numerical values, and a cell comprises an alphabetical entry, such as a word, string of letters, or the like, then the cell may be determined to be not in conformance with the regular structure of the block of cells. As another example, if a block of cells corresponds to a listing of dates, and a cell in the block comprises a floating point number, then it may be determined that the cell is suspicious of being erroneous because it does not appear to be in conformance with the regular structure of the block of cells.

The identification of cells that are suspicious of being erroneous may make use of various table formatting hints, such as column headers, row headers, cell formulas, and the like, to assist in identifying the regular structure of the block of cells and determining those cells that do not fit with the identified regular structure. Moreover, various artificial intelligence and machine learning methods may be employed to assist in identifying suspicious cells within the table structure. For example, features extracted during natural language processing of a document and the table structure, such as markup language information, layout information, functional clues, and the like, may be used to infer functional dependencies within the table structure. This facilitates training and using machine learning models which can then be used to signal the presence of a functional dependency within a table structure. The presence of erroneous or missing data values within the table structure may be performed by identifying portions of the table structure that break the functional dependencies identified by the machine learning models.

For example, the mechanism described previously for identifying functional dependencies between cells may be used to identify the functional dependency of a cell within a block of cells by looking at the information that is able to be gathered from other cells, headers, the title of the table, and other information about the content and structure of the table. For example, an arithmetic dependency (e.g., sum, product, unit conversion, ratio, etc.) or known enumerations (e.g., days of the week, months of the year, time of day, etc.) may be identified for the cell by looking at the cells around the cell in question, the headers of columns/rows, the title of the table, formulas associated with cells, and the like. If a functional pattern is identified to be true for other column and/or row dependencies in the cell block, except for the row/column containing the cell, or the cell itself, then this cell is likely to be storing an erroneous data value or a missing data value, and thus is a suspicious cell whose data value needs to be corrected or otherwise provided.

The identification of suspicious cells within blocks of cells may be repeated for each block of cells in a table structure. Thus, a single block of cells may have zero or more suspicious cells, and a table structure may have multiple blocks of cells with each block of cells having zero or more suspicious cells identified within them.

Having identified a suspicious cell within a block of cells using the mechanisms described above, the context surrounding the suspicious cell is determined and used as a basis for generating one or more queries to be used with a QA system. In generating the queries, the illustrative embodiments analyze context information, such as column headers, row headers, table titles, hierarchical structures of headers and titles, and the like, along with identified dependency relationships between cells of tables, grammatical rules, and the like, to determine a semantic signature of the cell which is informative of how to convert text or individual table cells into natural language sentences. Based on this information, table narration mechanisms are employed to convert the context surrounding a suspicious cell into a narrated statement with the erroneous or missing data value present in the narrated statement. The narrated statement serves as a semantic signature for the suspicious cell. One example table narration mechanism that may be employed is described in commonly assigned and co-pending U.S. patent application Ser. No. 13/838,130 entitled “Adapting Tabular Data for Narration,” filed Mar. 15, 2013, which is hereby incorporated by reference in its entirety.

Such semantic signatures are of the general type of <cell semantic reference> [fact(s)]. In this format, for a cell having a column header of “2007” and a row header hierarchy of “Revenues and non-operating income”→“electric”, with the cell having a value of $1,899,457, a semantic signature of “Electric Revenue for 2007 is $1,899,457” may be generated where the cell semantic reference is “Electric Revenue for 2007” and the fact is “$1,899,457”.

The semantic signature describes what the suspicious cell represents. Using semantic signatures facilitates answering questions from table data structures. For example, a question of “What is electric revenue for 2007?” may be answered directly by finding a cell with a semantic signature matching the semantic signature in the query and returning its contents.

It should be appreciated that semantic signatures do not need to be unique either inside one table, or across multiple tables, such as may be present in multiple documents of a corpus. For example, electric revenue for the same issuer in 2007 may occur in a number of documents. Many documents, for example, may contain comparative revenue numbers across a number of years. Thus, the “2007” value may appear in a document directed to “2008” revenue comparisons, or the like. This creates a de-facto redundancy in a corpus of documents. The illustrative embodiments exploit this de-facto redundancy to perform error correction in suspicious cells of a table in a document by querying the corpus of documents based on the semantic signature of the suspicious cell to identify redundant information in other documents of the corpus that may offer the correct content for the suspicious cell.

For example, with the mechanisms of the illustrative embodiments, the semantic signature generated for the suspicious cell generated using the table narration mechanism may be converted to a natural language question. The natural language question may then be input to a QA system as an input question upon which the QA system operates to search a corpus of documents for one or more candidate answers to answer the input question. Alternatively, rather than using a natural language question and a QA system, one or more structured requests may be generated and sent to a document database which may then apply the structured requests against the document database to identify results for the structured requests. In general, one may consider these operations the generation of queries that are applied against a knowledge base, e.g., corpus of documents, document database, or the like, in order to generate results in response to the queries. For purposes of the following description, it will be assumed that the knowledge base is a corpus of documents operated on by a QA system based on an input question submitted to the QA system that is generated from the semantic signature of a suspicious portion of content in a document, e.g., a suspicious cell in a table data structure of a document.

For example, if a document processing system determines that a value in a cell corresponding to the semantic signature “Electric Revenue for 2007” is questionable, e.g., because of an OCR error, or the like, the document processing system may submit the question “what is the Electric Revenue for 2007” to a QA system which will generate one or more queries that are applied to an already existing corpus of documents to find information in other documents matching the semantic signature specified in the question. The QA system returns a listing of candidate answers and their corresponding confidence measures as a result of applying the one or more queries to the already existing corpus of documents. The confidence measures may be evaluated to determine if one of the candidate answers has sufficient confidence to be selected as a replacement for the questionable content of the cell. Furthermore, the confidence measure for the selected candidate answer may evaluated to determine if the confidence measure is sufficient to warrant automatic replacement of the questionable content of the cell or if a notification should be sent to a human user to obtain authorization to replace the questionable content. In the latter case, the mechanisms of the illustrative embodiments may generate a notification to the human user which contains one or more suggested corrections for the questionable content of the cell including information about the source of the one or more suggested corrections, e.g. document name, table name within the document, publication information, author information, or any other source information that may be of use by a human user in determining whether to trust the source of the suggested correction.

FIG. 8Ais an example diagram of a portion of a table structure that may be found in a document processed by a natural language processing system, in which an erroneous data value is present within the table structure. In the example shown inFIG. 8, the portion of the tabular data in the document being processed includes a summary of revenues, expenses and changes that includes a plurality of columns for different calendar years 2007-2009 and rows corresponding to different categories of revenues and expenses.

As can be seen fromFIG. 8A, each of the columns follows a repeated pattern of functional dependency with regard to the total operating revenues in row4. The data value in cell B4breaks this repeated pattern of functional dependency in that cell B4contains the erroneous data value “rei/xz” which is not what would be expected if the functional dependency were followed. Thus, cell B4may be identified as an erroneous cell whose data value needs to be corrected. It is also possible to “guess” that the cell B4contains an erroneous data value based on one set of criteria, e.g., that all cells around that cell have numeric values and thus, it is expected that cell B4should have a numeric value, but then to infer the correct data value for the cell B4the mechanisms of the illustrative embodiments must discover that cell B4is part of a functional dependency.

FIG. 8Brepresents another document in a corpus of documents in which cells having a similar semantic signature may be found in accordance with one illustrative embodiment. As shown in a comparison ofFIGS. 8A and 8B, both documents contain table structures having cells with a semantic signature of “Gas revenue for 2007”. The document inFIG. 8Brepresents a document already in a corpus of documents while the document inFIG. 8Arepresents a document that is being processed by a document processing system and in which a suspicious cell is identified, such as in the manner described above. The document inFIG. 8B, i.e. the earlier document, was already adapted and loaded into the knowledge base, e.g., the corpus of documents upon which a QA system operates, with the semantic signature of the revenue block being recognized.

In the example illustrated inFIGS. 8A and 8B, the document processing system needs to find out the true value for the cell “Gas revenue for 2007” in the document being processed, i.e. the document ofFIG. 8A. Using the mechanisms of the illustrative embodiments, relational dependencies, patterns, and the like, are used to identify a suspicious cell in the table of the document being processed (document ofFIG. 8A). Having identified a suspicious cell in the table of the document, table narration is performed on the suspicious cell in order to generate a semantic signature. As mentioned above, in one illustrative embodiment, the mechanisms of co-pending and commonly assigned U.S. patent application Ser. No. 13/838,130 may be used to perform the table narration to generate the semantic signature for the suspicious cell. In other illustrative embodiments, other table narration techniques may be utilized as will become apparent to those of ordinary skill in the art in view of the present description. For example, through analysis of the row and column headers of the table corresponding to the suspicious cell, as well as analysis of the relational dependencies between cells to identify the type of value to be stored in the cell, a narrative for the cell may be determined. In the present example, regardless of which table narration mechanism is used, a semantic signature of “Gas revenue for 2007” may be determined.

The semantic signature of the suspicious cell may be converted to a query through a query generation engine's application of query generation rules that convert statements to queries. For example, the statement “Gas revenue for 2007” coupled with an answer type of numerical, may be converted to a query of the type “What is the gas revenue for 2007” by appending the question “what is” to the semantic signature for the cell. Similarly, for statements coupled to answer types that are of a name type, appending the question “who is” may convert a semantic signature's statement into a query that can be input to a knowledge base for generation of answers. Question generation rules take into account the type of answer that is being sought and other semantic and grammatical rules for the language of the question in order to generate the natural language question for submission to the QA system. Alternatively, the question generation engine may instead formulate structured queries directly, such as by using the Structured Query Language (SQL) or the like, that can be applied to a database of documents rather than generating a natural language question for submission to a QA system.

Assuming an embodiment in which a QA system is utilized, the natural language question is submitted as an input question to the QA system which operates on it as it would any other input question by generating one or more queries from the input question and applying the queries to a corpus of documents. The QA system obtains a listing of candidate answers from the corpus of documents along with a corresponding confidence measure and returns the ranked listing of candidate answers and their confidence measures. In addition, additional source information may be provided along with the candidate answers to indicate the source from which each candidate answer was obtained. Thus, in the depicted example, the input question “What is the gas revenue for 2007” may be submitted as an input question to the QA system, which will analyze the question and generate queries that are applied to a corpus and the resulting ranked listing of candidate answers is returned, e.g., a listing of a first candidate answer with “$254,340” as an answer with a “95%” confidence measure, a second candidate answer with “$360,432” as an answer with “45% confidence”, and the like.

The candidate answers returned by the QA system are analyzed to identify which candidate answer is the most likely correct answer for replacing the erroneous value in the suspicious cell. For example, the highest ranked candidate answer may be selected as a potential replacement for the erroneous value and may be further analyzed to determine if this candidate answer should actually be used as a replacement and whether such replacement can be performed automatically with a threshold amount of certainty, or if a human user needs to provide authorization for the replacement. These determinations may be made by comparing the confidence measure against one or more confidence measure thresholds. For example, the confidence measure of the selected candidate answer may be compared against a first threshold that is indicative of a minimum level of confidence required to be considered a valid potential replacement for an erroneous value in a suspicious cell, e.g., 90% confidence threshold. The confidence measure may then be compared against a second threshold to determine if manual intervention by a human user is required to perform the replacement, e.g., a threshold of 95%. If the confidence measure meets or exceeds both criteria, then the replacement of the erroneous value with the candidate answer may be performed automatically. If the confidence measure meets the first threshold criteria but not the second, then a notification may be sent to a human user suggesting the replacement of the erroneous value with the candidate answer, specifying the measure of confidence, and optionally providing source identification information for consideration by the user. If the user selects to perform the replacement, then the replacement is performed by the system; otherwise if the user selects not to perform the replacement, an error notification may be presented to the user indicating that the document being processed contains an erroneous value that could not be corrected.

If the confidence measure does not meet either threshold criteria, then the selected candidate answer is not used as a replacement for the erroneous value. Other candidate answers in the ranked listing may be processed in a similar manner to determine if any other candidate answers meet the requirements. In addition, in cases where the first threshold criteria is met by a candidate answer but the second threshold criteria is not met, the system may analyze other candidate answers in the ranked list to determine if any other candidate answers in the ranked list meet both threshold criteria, in which case any candidate answers that meet both threshold criteria may be selected as the potential replacement for the erroneous value.

It should be appreciated that the use of two separate thresholds is just one example embodiment and other embodiments may utilize different mechanisms for determining if there is a sufficient level of confidence in a selected candidate answer being a valid replacement for an erroneous value, and determining whether such replacement is to be performed automatically or with human user intervention, without departing from the spirit and scope of the illustrative embodiments. For example, in another illustrative embodiment, a single minimum confidence measure threshold may be used to determine if the selected candidate answer is a valid replacement for the erroneous value, and a determination as to the degree by which the minimum confidence measure threshold is exceeded may be used as a basis for determining if the replacement can be performed automatically or with human user intervention, e.g., if the confidence measure exceeds the minimum confidence measure threshold by more than 10%, then the replacement can be performed automatically. Many other embodiments are possible in view of this description of the illustrative embodiments.

Again, it should be noted that while the illustrative embodiments described herein are directed to the correction of erroneous or missing values in cells of a table, the illustrative embodiments are not limited to such. Rather, any content of a document that is identifiable as suspicious of being erroneous or missing may be a basis for such correction. For example, erroneous or missing words in a sentence may be identified and the context surrounding the erroneous or missing words may be used as a basis for generating a natural language question or structured query that is applied to a knowledge base to determine an appropriate correction for the erroneous or missing word.

Thus, the mechanisms of the illustrative embodiments provide functionality and logic for identifying suspicious portions of content, e.g., cells in a table structure of a document, which have content that may need to be corrected or replaced, or may lack content that should be generated. The mechanisms of the illustrative embodiments obtain context information from the document and use this context information to generate a natural language question or structured query to be submitted to a knowledge base, e.g., corpus of documents via a QA system, database of documents, or the like. The results of processing the question/query on the knowledge base are returned and used as a basis for selecting a replacement content for the erroneous or missing content in the suspicious portion of content. The replacement is then performed either automatically or with human intervention based on a determined level of confidence in the replacement content.

FIG. 9is an example block diagram of an application for correcting erroneous or missing data values in cells based upon discovered functional relationships in tabular data in accordance with an illustrative embodiment. It should be noted that the application902shown inFIG. 9is illustrated as being for an embodiment that operates in conjunction with a QA system930operating on a corpus of documents932. Other illustrative embodiments may include utilizing the application902with other types of knowledge bases, such as a database of documents or the like upon which a structured query may be applied.

The application902shown inFIG. 9may receive input from the application shown and described above with reference toFIG. 5or may be integrated with the application ofFIG. 5depending upon the particular desired embodiment. In either case, the application902ofFIG. 9can be used, along with application502, in place of application105inFIG. 1. Application902receives as input904the natural language processed documents with the table structures and functional dependencies as output by application502(assuming that application902is separate from application502). The table structures are then analyzed by the erroneous data value analysis engine906of the application902to identify erroneous data values based on one or more heuristics, identified functional dependency patterns, or the like, to identify erroneous data values908within the table structures904.

The identification of erroneous data values908are input to the correction engine910. The correction engine910controls the overall operation for correcting erroneous or missing data values908in the input document904using the various components912-916. That is, the correction engine910invokes the question generation engine912to analyze the context of the document surrounding the erroneous or missing data values, including header information from the rows/columns, functional dependencies identified, and the like, to generate a semantic signature for the erroneous or missing data value. The question generation engine912may then convert the semantic signature to a natural language question that may be submitted to the QA system930via the QA system interface914.

The QA system930receives the generated question from the application902via the QA system interface914as an input question for answering by the QA system930. The QA system930performs its operations for processing input questions, as will be described in greater detail hereafter with reference toFIG. 10, to generate one or more queries that are applied against the corpus932of documents. The QA system930, based on results of applying the one or more queries to the corpus932, generates a ranked listing of one or more candidate answers to answer the input question. The candidate answers may be ranked according to confidence measures that are calculated for each of the candidate answers as part of the application of the one or more queries to the corpus932. Each of the candidate answers in the ranked listing may have associated confidence measures and, optionally, source information to identify the source document, publication, author, organization, or other entity that is the source of the document or documents providing the candidate answer.

The ranked listing of candidate answers may be returned by the QA system930to the correction engine910via the QA system interface914. The correction engine910then invokes the results analysis engine916to process the ranked listing of candidate answers to select a candidate answer as a potential replacement, or newly generated value, for the missing or erroneous data value908. A candidate answer may be selected from the ranked listing based on the associated confidence measures, e.g., a candidate answer having a highest confidence measure. The selected candidate answers' confidence measure is then analyzed to determine if it is sufficient to be used as a replacement or new value for the missing or erroneous data value908. In addition, the confidence measure is further analyzed to determine if it is sufficient to warrant automatic correction of the erroneous or missing data value908or if a human user is to be notified and requested to provide manual approval of the correction. As mentioned previously, such determinations may be made by comparing the confidence measures against one or more thresholds.

If it is determined that human intervention is necessary to obtain authorization to perform the replacement of the erroneous or missing data value908, then a notification may be sent to a user at the user's computer940. The notification may include the suggested replacement value, the measure of confidence associated with the suggested replacement value, and optionally source information indicating the source of the suggested replacement value. If the user responds with authorization to perform the replacement, the correction engine910may correct the erroneous or missing data value908. If the user does not respond with authorization to perform the replacement, and error notification may be generated and output to the user so that the user may thereafter perform manual correction of the erroneous or missing data value908via the user computer940. If it is determined that manual intervention by a user is not necessary, the correction engine910may perform the correction of the erroneous or missing data value908automatically without contacting the user via the user computer940. The application902may then output the natural language processed documents920with the corrected data values in the table structures.

It should be appreciated that while the illustrative embodiments have been described above with regard to primarily numerical data values in cells of a table structure, the illustrative embodiments are not limited to such. To the contrary, as touched upon above, the illustrative embodiments may be utilized to identify functional dependencies of non-numeric data values and correct erroneous or missing non-numerical data values in a similar fashion as described above.

As described above, in some illustrative embodiments, the mechanisms of the illustrative embodiments operate in conjunction with a QA system. The QA system implements one or more QA system pipelines for processing input questions and generating candidate answers to the input questions. If multiple QA system pipelines are utilized, each pipeline may be trained and configured for operation with a particular domain of subject matter. In such a case, an initial analysis of the input question may be utilized to identify the domain of the input question so that routing of the question to an appropriate QA system pipeline may be performed.

FIG. 10illustrates a QA system pipeline for processing an input question in accordance with one illustrative embodiment. The QA system pipeline ofFIG. 10may be implemented, for example, as a QA system pipeline of QA system930inFIG. 9. It should be appreciated that the stages of the QA system pipeline shown inFIG. 10may be implemented as one or more software engines, components, or the like, which are configured with logic for implementing the functionality attributed to the particular stage. Each stage may be implemented using one or more of such software engines, components or the like. The software engines, components, etc. may be executed on one or more processors of one or more data processing systems or devices and may utilize or operate on data stored in one or more data storage devices, memories, or the like, on one or more of the data processing systems.

As shown inFIG. 10, the QA system pipeline1000comprises a plurality of stages1010-1080through which the QA system operates to analyze an input question and generate a final response. In an initial question input stage1010, the QA system receives an input question that is presented in a natural language format. That is, a user may input, via a user interface, an input question for which the user wishes to obtain an answer, e.g., “Who are Washington's closest advisors?” In response to receiving the input question, the next stage of the QA system pipeline1000, i.e. the question and topic analysis stage1020, parses the input question using natural language processing (NLP) techniques to extract major features from the input question, classify the major features according to types, e.g., names, dates, or any of a plethora of other defined topics. For example, in the example question above, the term “who” may be associated with a topic for “persons” indicating that the identity of a person is being sought, “Washington” may be identified as a proper name of a person with which the question is associated, “closest” may be identified as a word indicative of proximity or relationship, and “advisors” may be indicative of a noun or other language topic.

The identified major features may then be used during the question decomposition stage1030to decompose the question into one or more queries that may be applied to the corpora of data/information1045in order to generate one or more hypotheses. The queries may be generated in any known or later developed query language, such as the Structure Query Language (SQL), or the like. The queries may be applied to one or more databases storing information about the electronic texts, documents, articles, websites, and the like, that make up the corpus of data/information1045. That is, these various sources themselves, collections of sources, and the like, may each represent different corpus1047within the corpora1045. There may be a different corpus1047defined for different collections of documents based on various criteria depending upon the particular implementation. For example, different corpora may be established for different topics, subject matter categories, sources of information, or the like. As one example, a first corpus may be associated with healthcare documents while a second corpus may be associated with financial documents. Alternatively, one corpus may be documents published by the U.S. Department of Energy while another corpus may be IBM Redbooks documents. Any collection of content having some similar attribute may be considered to be a corpus1047within the corpora1045.

The queries may be applied to one or more databases storing information about the electronic texts, documents, articles, websites, and the like, that make up the corpus of data/information, e.g., the corpus of data932inFIG. 9. The queries being applied to the corpus of data/information at the hypothesis generation stage1040to generate results identifying potential hypotheses for answering the input question which can be evaluated. That is, the application of the queries results in the extraction of portions of the corpus of data/information matching the criteria of the particular query. These portions of the corpus may then be analyzed and used, during the hypothesis generation stage1040, to generate hypotheses for answering the input question. These hypotheses are also referred to herein as “candidate answers” for the input question. For any input question, at this stage1040, there may be hundreds of hypotheses or candidate answers generated that may need to be evaluated.

The QA system pipeline1000, in stage1050, then performs a deep analysis and comparison of the language of the input question and the language of each hypothesis or “candidate answer” as well as performs evidence scoring to evaluate the likelihood that the particular hypothesis is a correct answer for the input question. As mentioned above, this may involve using a plurality of reasoning algorithms, each performing a separate type of analysis of the language of the input question and/or content of the corpus that provides evidence in support of, or not, of the hypothesis. Each reasoning algorithm generates a score based on the analysis it performs which indicates a measure of relevance of the individual portions of the corpus of data/information extracted by application of the queries as well as a measure of the correctness of the corresponding hypothesis, i.e. a measure of confidence in the hypothesis.

In the synthesis stage1060, the large number of relevance scores generated by the various reasoning algorithms may be synthesized into confidence scores for the various hypotheses. This process may involve applying weights to the various scores, where the weights have been determined through training of the statistical model employed by the QA system and/or dynamically updated, as described hereafter. The weighted scores may be processed in accordance with a statistical model generated through training of the QA system that identifies a manner by which these scores may be combined to generate a confidence score or measure for the individual hypotheses or candidate answers. This confidence score or measure summarizes the level of confidence that the QA system has about the evidence that the candidate answer is inferred by the input question, i.e. that the candidate answer is the correct answer for the input question.

The resulting confidence scores or measures are processed by a final confidence merging and ranking stage1070which may compare the confidence scores and measures, compare them against predetermined thresholds, or perform any other analysis on the confidence scores to determine which hypotheses/candidate answers are the most likely to be the answer to the input question. The hypotheses/candidate answers may be ranked according to these comparisons to generate a ranked listing of hypotheses/candidate answers (hereafter simply referred to as “candidate answers”). From the ranked listing of candidate answers, at stage380, a final answer and confidence score, or final set of candidate answers and confidence scores, may be generated and output to the submitter of the original input question. In accordance with the illustrative embodiments, the ranked listing of candidate answers, or the final answer, may be returned to the application902inFIG. 9for processing of the results to identify a replacement value for an erroneous or missing value, or portion of content, in a document being processed.

FIG. 10is a flowchart outlining an example process for correcting erroneous or missing data values in cells based upon discovered functional relationships in tabular data in accordance with one illustrative embodiment. Again,FIG. 10outlines an example process that is for correcting a cell in a table structure of an NLP document, however in other illustrative embodiments, these mechanisms may be used to correct any portion of content in a NLP document and is not limited to cells in tables or numerical values, as previously discussed above.

As shown inFIG. 10, the process starts by receiving a natural language processed document with table structure and functional dependencies identified according to hypotheses and confidence ratings (step1010) as described in the processes outlined inFIGS. 6 and 7above. The table structure is analyzed to determine if there are any erroneous or missing data values in cells of the table structure (step1020). If not, the operation terminates.

Otherwise, if an erroneous or missing data value is found, a semantic signature for the erroneous or missing data value is generated (step1030). A question/query is generated from the semantic signature (step1040) and is submitted to a knowledge base, e.g., QA system, document database, or the like (step1050) search the knowledge base for an answer to the question/query. The results of the application of the question/query to the knowledge base are received (step1060) and the results are used as a basis to replace the missing or erroneous value with a correct value either automatically or manually based on measures of confidence returned in the results (step1070). The operation then terminates.

Thus, the illustrative embodiments provide mechanisms for identifying functional dependencies between portions of table structures in documents being ingested by a natural language processing system. These functional dependencies are further utilized to identify erroneous or missing data values in these portions of table structures, or other portions of content in a document. Moreover, the illustrative embodiments utilize the context surrounding the identified erroneous or missing data values, or portions of content, to generate questions/queries that are submitted to a knowledge base to obtain corrected values or corrected portions of content. Based on measures of confidence associated with the corrected values or corrected portions of content, the erroneous or missing content may be automatically or semi-automatically (with human user manual approval) corrected. As a result, more complete table structures and other document content for natural language processed documents are generated that can be used to perform natural language processing operations, such as question and answer operations in a QA system, such as IBM's Watson™ QA system, or the like.