Pre-processing a table in a document for natural language processing

Provided are a computer program product, system, and method for pre-processing a table in a document for natural language processing. A table in a document is parsed to extract column headers, row headers, and data cells, which are processed to determine an initial set of a main element comprising an entity whose value is to be extracted, a conditional element that refines the entity, and a value element comprising a value for the entity. A user selection is received of at least one of the column headers, row headers, and data cells for at least one of the main element, conditional element, and the value element in the initial set to produce a modified set of the main element, conditional element, and value element. The modified set is provided to a natural language processing engine to perform natural language processing of the document including the table, using the modified set.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a computer program product, system, and method for pre-processing a table in a document for natural language processing.

2. Description of the Related Art

A Natural Language Processing (NLP) program processes documents including tables, comprised of columns and rows of data cells, by performing a table flattening pre-process to extract information on the table for the NLP program to use to interpret the document and tables. Table flattening involves parsing the table to extract tokens comprising headers and sub-headers in the table associated with the data cells. Table flattening may involve table segmentation to segment text into rows, columns, and headers and then interpret the text.

The table flattening process may identify three types of elements, including a main element, which defines the primary entity whose value to be extracted, a conditional element, which refines the primary entity, and a value element, which contains the value for the entity. Concatenation rules may then be used to form natural language sentences based on the main, conditional and value elements. Information extracted during the table flattening process is then provided to the NLP program to interpret the document and tables embedded in the document.

There is a need in the art for improved techniques for pre-processing of tables in a document for the NLP program to process.

SUMMARY

Provided are a computer program product, system, and method for pre-processing a table in a document for natural language processing (NLP). A table in a document is parsed to extract column headers, row headers, and data cells. The column headers, row headers, and data cells are processed to determine an initial set of a main element comprising an entity whose value is to be extracted, a conditional element that refines the entity, and a value element comprising a value for the entity from the processed column headers, row headers, and data cells. User selection is received of at least one of the column headers, row headers, and data cells for at least one of the main element, conditional element, and the value element in the initial set to produce a modified set of the main element, conditional element, and value element. The modified set of the main element, conditional element, and the value element are provided to an NLP engine to perform natural language processing of the document including the table, using the modified set of the main element, conditional element, and the value element to interpret the table.

DETAILED DESCRIPTION

When performing natural language processing (NLP) of a document, the NLP program may provide a visualization of annotations output from the NLP processing layer. This visualizations allow users to evaluate the accuracy of detected concepts against the full context from which the concepts were detected in the document. However, one or more pre-processing layers preceding the NLP processing layer of the document can greatly impact the accuracy of the NLP layer output.

Described embodiments provide improved computer technology for NLP pre-processing operations including the table flattening process to provide users information and visualization of the pre-processing table flattening results to allow the user to inspect the results for accuracy and edit classifications of the table elements for subsequent improved processing and understanding by the NLP program. With described embodiments, a table interpreter may process column headers, row headers, and data cells in a table in a document to determine an initial set of a main element comprising an entity whose value is to be extracted, a conditional element that refines the entity, and a value element comprising a value for the entity from the processed column headers, row headers, and data cells. User selection may then be received of at least one of the column headers, row headers, and data cells for at least one of the main element, conditional element, and the value element in the initial set to produce a modified set of the main element, conditional element, and value element. The modified set of the main element, conditional element, and the value element is provided to an NLP engine to perform natural language processing of the document including the table, using the modified set of the main element, conditional element, and the value element to interpret the table.

FIG.1illustrates an embodiment of a computer system100having a processor102to execute program components stored in a memory/storage104. The memory/storage104includes program components executed by the processor102, including a table parser106and a table interpreter108to perform table pre-processing flattening operations, and a natural language processor (NLP) engine110. The table parser106parses a document112including one or more tables114, having rows and columns of data, to produce extracted table items116, including determined row headers, column headers, and data cells, and table item metadata200having metadata on the extracted row headers, column headers, and data cells. A table interpreter108receives the extracted table items116and classifies the table items as an initial set of element classifications300Iincluding a main element, comprising the primary entity whose value is to be extracted as part of natural language understanding of the table, a conditional element, which refines or places a condition on the primary entity, a value element having the value for the primary entity, and lexical connector tokens to connect the elements in a concatenated natural language statement. The table interpreter108may use classification techniques known in the art, such as machine learning technology to classify table items as the main element, conditional element(s), and value element. Machine learning or concatenation rules may be used to determine the lexical connectors for the classified elements in the initial set300I.

The initial set of element classifications300Iand table item metadata200are provided to a graphical user interface (GUI) generator118to generate a table pre-processing GUI120to allow the user to modify the table cells initially determined to be the main element, conditional element, and value element used in interpreting the table to produce a modified set of element classifications and lexical connectors300M. The table flattening GUI generator118further generates a display coordinate mapping400that maps coordinates of the table114, rendered in the table pre-processing GUI120displayed on a user computer display, to coordinates of the table114in the document112. A user, such as a subject matter expert, reviewing the initial classified table element classifications and lexical connectors300I, may use the table pre-processing GUI120to change the table items comprising the table element classifications and lexical connectors to output a user modified set of element classifications and lexical connectors300Mthat are provided to the NLP engine110. The NLP engine110performs natural language processing of the document112and tables114subject to table flattening preprocessing.

With the described embodiments, the table flattening preprocessing allows the user to review the initial set of machine determined element classifications and lexical connectors300Iand determine whether the concatenation rules, classifications, and lexical connectors should be changed to improve the understanding of the meaning of the table114to optimize processing by the NLP engine110.

The document112may comprise a structured document, such as a Microsoft® Word file, Portable Document Format (“PDF)”, Extensible Markup Language (XML) document, a Hypertext Markup Language (HTML) document, as well as an unstructured document, etc. (Microsoft is a trademark of Microsoft Corporation throughout the world).

The memory/storage104may comprise a suitable volatile or non-volatile memory for storing programs to execute and information used by the processor102to execute.

Generally, program modules, such as the program components106,108,110,118may comprise routines, programs, objects, components, logic, data structures, and so on that perform particular tasks or implement particular abstract data types. The program components and hardware devices of the computer system100ofFIG.1may be implemented in one or more computer systems, where if they are implemented in multiple computer systems, then the computer systems may communicate over a network

The programs106,108,110,118may comprise program code loaded into memory and executed by a processor. Alternatively, some or all of the functions may be implemented in hardware devices, such as in Application Specific Integrated Circuits (ASICs) or executed by separate dedicated processors.

In one embodiment, the programs106,108,110may implement a machine learning technique such as decision tree learning, association rule learning, neural network, inductive programming logic, support vector machines, Bayesian network, etc., to perform their specific tasks in the natural language processing pipeline. The programs106,108,110may comprise artificial neural network programs. Each neural network may be trained using backward propagation to adjust weights and biases at nodes in a hidden layer to produce the computed output. In backward propagation used to train a neural network machine learning module, biases at nodes in the hidden layer are adjusted accordingly to produce the desired outcome based on specified confidence levels. Backward propagation may comprise an algorithm for supervised learning of artificial neural networks using gradient descent. Given an artificial neural network and an error function, the method may calculate the gradient of the error function with respect to the neural network's weights and biases.

InFIG.1, arrows are shown between components in the memory/storage104. These arrows represent information flow to and from the program components106,108,110,118and do not represent data structures in the memory104.

FIG.2illustrates an embodiment of table item metadata200ifor one of the table items extracted from the table114, and includes a table item identifier202, comprising a unique identifier of the table item; a table item type204, such as a row header, column header, or data cell; the table item text206; a location208of the table item in the document112, such as page number, horizontal and vertical offsets and coordinates within that page for the start and end of the table item202, such as defining a boundary region from the top left corner of the extracted text to its bottom right corner; location210of table item in the table114, such as row and column numbers within the table114. Table item metadata200imay be generated for each cell in the table114being processed.

FIG.3illustrates an embodiment of element classifications and lexical connectors300Iwhich may comprise an initial set300Igenerated by the table interpreter108or a modified set300Mselected by the user using the table pre-processing GUI120, and includes: a main element302, comprising the primary entity whose value is to be extracted as part of natural language understanding of the table; a main lexical connector304to provide a lexical token to connect the main element302to a conditional element3061, which refines or places a condition on the main element302. If there are multiple conditional elements306n, i.e., n is greater than one, then there would be n−1 lexical connectors, one additional conditional lexical connector308jfor each added conditional element306i. There is a value lexical connector310to connect the final306nor only conditional element3061to the value element312, which contains the value for the entity. If there is only one conditional element3061, i.e., n=1, then there would be no conditional lexical connector and only a value lexical connector310between the sole conditional element3061and the value element312.

Lexical connectors may comprise strings such as “for”, “is”, “and”, etc.

The element classifications and lexical connectors provide300ia concatenation rule for combining main elements comprising values in a row or column for the main element and conditional element(s) comprising values in a row or column that results in the value element312.

FIG.4illustrates an embodiment of an instance of a display screen coordinate mapping400ithat maps display screen coordinates402showing the table114on the user display screen to the document coordinates404of the table114in the document.

FIG.5illustrates an embodiment of operations performed by the table parser106to initiate the table flattening pre-processing of tables114in the document112. Upon receiving (at block500) a document112including a table114, the parser106parses (at block502) the table114to extract table items of column headers, row headers, and data cells in a table114in the document112. For each extracted table item i, the parser106performs the operations at blocks504through510. The parser106determines (at block506) coordinates in the table114in the document112comprising the boundary region including the table item i. The coordinates may include the page number of the table item i within the document112as well as horizontal and vertical offsets and coordinates within that page for the start and end of the table item i. The horizontal and vertical offsets may define a boundary region or bounding box from the top left corner of the extracted table item i to its bottom right corner. The determined coordinates may also include information about the row and column coordinates of the table item i within the containing table114. The parser106generates (at block508) table item i metadata200iindicating table item ID202, table item type204(row, column, data), table item202location in the document208(page and horizontal and vertical offsets in the page), and location210of table item202in the table114, such as row and column location.

The table interpreter108processes (at block512) the extracted table items116, including table item metadata200for the table items, to determine an initial set300Iof element classifications, e.g., main element302, conditional element(s)3061. . .306n, and value element312of the table114, from the extracted column headers, row headers, and data cells, and lexical connectors304,3081. . .308n−1,310between the main element302, conditional element(s)3061. . .306n, and value element312. The determined initial classifications and lexical connectors may then be saved in the initial set of element classifications and lexical connectors300I.

With the embodiment ofFIG.5, the table flattening processes106,108determines an initial set of element classifications and lexical connectors to form concatenation rules to construct natural language sentences describing the information in the cells of the table.

FIG.6illustrates an embodiment of operations performed by the GUI generator118to initiate the review process of the generated initial set300Iof element classifications and concatenation rules to allow editing by a subject matter expert managing the pre-processing and optimization of the NLP engine110. Upon initiating (at block600) the process, the GUI generator118generates (at block602) a table pre-processing GUI120including a representation of the table114with the initial main element, conditional element(s), and value elements highlighted. The GUI generator118renders (at block604) graphical controls in the GUI120, such as drop-down menus, to enable the user to select one of the extracted column headers, row headers, and data cells as the main element302, conditional element(s)3061. . .306n, and value element312different from what the table interpreter108determined. The GUI generator118renders (at block606) graphical controls in the GUI120, such as drop-down menus, to enable the user to select lexical connectors304,3081. . .308n−1,310between the main element302and one of the conditional elements3061, between any pair of conditional elements, and between the last conditional element306nand the value element312, respectively. The GUI generator118may further render (at block608) an add graphical control to enable the user to add an additional conditional element306n+1to the concatenation rules and a lexical connector308n,310for the new conditional element306n+1.

The GUI generator118maps (at block610) display screen coordinates402of the display screen in which the table114is displayed to document coordinates404in the document including the extracted table items to form display screen coordinate mappings400ito map the coordinates in which the table114is rendered on the display screen to coordinates of the table114in the document112. Upon receiving (at block612) a resizing of the GUI120rendered on the display screen changing the dimensions of the displayed table114in the GUI120, control proceeds back to block610to remap the display screen coordinates402to document coordinates404based on the resizing.

The embodiment ofFIG.6renders the table pre-processing GUI120to enable the subject matter expert to modify the initial set300Iof element classifications and lexical connectors to improve the NLP engine110processing of the document112and table114.

In generating the display screen to document112mappings, the GUI generator118translates the screen coordinates to document coordinates, e.g., PDF coordinates. The coordinate mapping may consider the location on-screen of the rendered page, the magnification in effect, the location of the user's click, etc. Straightforward geometrical calculations using these factors may be used to translate the screen coordinates to document112, e.g., PDF coordinates, i.e., the page number and horizontal and vertical offsets within the document112of the coordinates.

FIG.7illustrates an example of a table700, such as table114, including rows and columns. Highlighted table item702comprises the main element302, highlighted column header704comprises a conditional element306, and highlighted data cell706comprises the value element by way of example.

FIG.8aillustrates an example of a table pre-processing GUI800a, such as an embodiment of GUI120, in which the table802ais rendered with columns and headers. A main element drop-down menu804a, a conditional element drop-down menu806a, and value element drop-down menu808aenables the user to select any of the table items as the main element302, conditional element3061(only one is shown), and value element312. Further, the lexical connector controls810a,812aenable the user to select a main lexical connector304and value lexical connector310, respectively. The panel814ashows the result of the selected concatenation rule selected in the drop-down menus804a-812a. The drop-down menus804a-812amay initially be set to the element classifications and lexical connectors in the initial set300Idetermined by the table interpreter108. The add column graphical control816aallows the user to add an additional condition element306iand conditional lexical connector308jto the concatenation rules. InFIG.8a, table elements818a,820a, and822aare set as the main element302, sole conditional element3061, and value element312, respectively, and they are highlighted with a graphic to identify their element classification.

FIG.8billustrates the table pre-processing GUI800b, such as an embodiment of GUI120, after the user has modified the selection of the main element804band conditional element806bpresented in GUI800bto be the table items820band818b, respectively. This changed selection results in a new textual concatenation in panel814b. This new selection modifies the main element302and conditional element3061in the settings3002to produce the modified set300Mof element classifications.

FIG.8cillustrates the table pre-processing GUI800aafter the user has added two additional conditional element drop-down menus using the add column button816c, resulting in three conditional element selection drop-down menus806c1,806c2, and806c3and conditional lexical connector drop-down menus824cand826c. In the example ofFIG.8c, the user has modified the main element804cpresented in GUI800cto be the table items820c. This user selections shown inFIG.8cselects three conditional elements806c1,806c2,806c3to be table items828c,818c, and830cand selects new conditional lexical connectors3081and3082to be824cand826c. This changed selection results in a new textual concatenation in panel814c. These user modifications of the main element302and conditional element806c1,806c2,806c3results in the modified set300Mof classified elements.

FIG.9illustrates an embodiment of operations performed by the GUI generator118to form the modified set300Mof element classifications and lexical connectors300. The GUI generator118receives from the table pre-processing GUI120user modifications of the main element302, conditional element(s)3061. . .306n, value element312, and/or new lexical connector(s)304,308i,310. The GUI generator118then updates (at block902) any of the main element302, conditional element(s)306i, value element312, and/or lexical connectors304,308i,310in the initial set300Ior a previously modified set300Mwith the user modifications to form a new modified set300Mwith the new values entered by the user via the GUI120.

The embodiment ofFIG.9allows a user, such as a subject matter expert, to modify the concatenation rules for the table114by updating the main element, conditional element(s), value element, and/or lexical connectors to provide a more optimized classification of the table items to improve subsequent NLP processing.

FIG.10illustrates an embodiment of operations performed by the GUI generator118to process user selection of table items in the table114via the table pre-processing GUI120. Upon receiving (at block1000) coordinates of user selection of an area in the display screen in the table pre-processing GUI120, the GUI generator118determines (at block1002), from the display screen coordinate mapping400i, document coordinates404in the document112mapping to the determined display screen coordinates402. The table item metadata200kis determined (at block1004) that includes the determined document coordinates404in the document112. The display coordinate mappings4001are then used to determine display screen coordinates402forming a display screen boundary region that maps to the coordinates of the table item208in the determined table item metadata200i. The GUI generator118renders (at block1008) the display screen boundary region that includes the coordinates the user selected and the selected table item as highlighted. The GUI generator118may further update (at block1010) the element classifications and lexical connectors300ito indicate the highlighted table item as main element, conditional element or value element in response to user selection of that designation.

With the embodiment ofFIG.10, the GUI generator118translates, using geometrical calculations, a location of the user's click to document112coordinates, e.g., the page number and horizontal and vertical offsets within the document112of the user's click. The calculated document112coordinates (page number and offsets) of the user's click are used to look up the underlying table item by finding the extracted table item whose bounding box encloses the calculated offsets. In this way, the GUI generator118can locate any table element in the document112that the user clicks on, regardless of whether the text clicked on is (or is not) part of a value that was recognized and extracted from the document. Moreover, when the table item that the user clicks on contributed to a value recognized by the GUI generator118(be it a true positive or a false positive), the GUI generator118locates and renders the value recognized by the NLP engine110because all such values are linked to the extracted text elements that composed the flattened table item string that was sent to the NLP engine110.\

As shown inFIG.11, the computer system/server1102is shown in the form of a general-purpose computing device. The components of computer system/server1102may include, but are not limited to, one or more processors or processing units1104, a system memory1106, and a bus1108that couples various system components including system memory1106to processor1104. Bus1108represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus.

Computer system/server1102typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server1102, and it includes both volatile and non-volatile media, removable and non-removable media.

System memory1106can include computer system readable media in the form of volatile memory, such as random access memory (RAM)1110and/or cache memory1112. Computer system/server1102may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, storage system1113can be provided for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a “hard drive”). Although not shown, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a “floppy disk”), and an optical disk drive for reading from or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM or other optical media can be provided. In such instances, each can be connected to bus1108by one or more data media interfaces. As will be further depicted and described below, memory1106may include at least one program product having a set (e.g., at least one) of program modules that are configured to carry out the functions of embodiments of the invention.

Program/utility1114, having a set (at least one) of program modules1116, may be stored in memory1106by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. The components of the computer1102may be implemented as program modules1116which generally carry out the functions and/or methodologies of embodiments of the invention as described herein. The systems ofFIG.1may be implemented in one or more computer systems1102, where if they are implemented in multiple computer systems1102, then the computer systems may communicate over a network.

Computer system/server1102may also communicate with one or more external devices1118such as a keyboard, a pointing device, a display1120, etc.; one or more devices that enable a user to interact with computer system/server1102; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server1102to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces1122. Still yet, computer system/server1102can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter1124. As depicted, network adapter1124communicates with the other components of computer system/server1102via bus1108. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server1102. Examples, include, but are not limited to, microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.