TRANSFORMING TABLES IN DOCUMENTS INTO KNOWLEDGE GRAPHS USING NATURAL LANGUAGE PROCESSING

Herein from tabular data in a text document, a machine learning text classification pipeline infers natural language syntax and semantics to prepare the tabular data for graph analytics. In an embodiment, a computer infers a respective classification of each column in a table in a text document that contains natural language. Based on the classifications of the columns in the table, the vertices of the knowledge graph are automatically generated. Based on those column classifications and automatic analysis of a particular document portion that does not contain the table, the edges of the knowledge graph are automatically generated. The knowledge graph may be generated and operated as a property graph. Pipeline subsystems herein include column classification, edge type identification, and subject/object detection that provide sufficient semantic enrichment and context sensitivity to faster generate a more accurate knowledge graph than the state of the art.

FIELD OF THE INVENTION

The present invention relates to natural language processing (NLP). Herein, a machine learning (ML) text classifier infers, from tabular data in a text document, natural language semantics to prepare the tabular data for graph analytics.

BACKGROUND

Reading and analyzing information in text documents written in natural language is a technical challenge. Business activity reports and news articles are rich with important information whose value can be increased with analytics. It may be useful to represent information in such documents as knowledge graphs for several reasons. A graph representation is easier to detect patterns by visual inspection. The graph representation allows further automatic processing using graph processing technologies, and allows the creation of a comprehensive graph that contains and links together information from several sources. Currently, this transformation from text documents to knowledge graphs is done by hand as a person must read the text (and any tables in the text) and construct nodes and edges from information they think is relevant. This is a time consuming process.

Especially problematic in natural language processing (NLP) is semantic analysis that depends on context and other correlations. A natural document may contain more than a sequence of paragraphs to be analyzed. The document may instead contain a mix of unstructured (i.e. natural), semi-structured, and structured parts. Document parts of discrepant kinds may be difficult to correlate, which may cause dependency analysis to be incomplete. Such analytic bottlenecks may cause a property graph to be less accurate.

DETAILED DESCRIPTION

General Overview

The present invention relates to natural language processing (NLP). Herein, a machine learning (ML) text classifier infers, from tabular data in a text document, natural language semantics to prepare the tabular data for graph analytics. Here is a new way to transform text documents into knowledge graphs by building a pipeline of state-of-the-art natural language processing techniques. The novel approach herein generates a knowledge graph from natural language documents that contain all the relevant information as tables and text, and this automation facilitates both easier visual inspection of the data and integrates with downstream processing for graph analytics using, for example, graph machine learning or pattern matching algorithms.

Techniques herein may be performed in an ML pipeline that streams or batches documents. Any tables that appear in a natural language document will have property graph components automatically generated. The ML pipeline may contain pretrained and fine-tunable NLP models that can be trained once on a set of text documents annotated with supervision labels. The NLP models learn to transform text documents and tables within documents into knowledge graphs. This ML pipeline may use and/or train a distinct NLP model for each of several subproblems addressed herein. As presented herein, various NLP models may be arranged in serial or parallel.

This approach creates a knowledge graph that represents the information in both the natural language text and the tables in a document. A text to graph pipeline may entail three steps:Named Entity Recognition (NER) to detect the relevant entities in the text which will be represented in the graph as nodes.Relation Extraction (RE) to detect the relations between the entities detected in NER which will be represented in the graph as edges.Coreference Resolution (CR) to consolidate different mentions of the same entity (including pronouns) in the text into a single vertex in the graph.

The named entity recognition and relation extraction models expect and act on inputs that are individual sentences, whereas the coreference resolution model works on the entire document. Increased accuracy and decreased or avoided training time are improvements herein that use pretrained NLP transformer models instead of LSTMs and ELMo embeddings that are not high performance.

To transform a table into a graph, information about entities in the table and their relations are automatically extracted based on learned inferences. In text documents for example, each row of a table may represent one transaction from one party to another. In a generated knowledge graph, each row is represented by a generated edge between two generated vertices. Learned inferences that facilitate creating this edge include the type of the edge, the subject and object of the directed edge, and other properties of the edge such as an amount or quantity and a date. Theses automatic inferences may be contextual due to dependencies between different parts of the document, or due to dependencies inside a particular part.

The inferences may guide automatic detections and decisions. For example, each row in a table may correspond to a distinct directed edge in a graph being generated. Each column in the table may correspond to either the subject, the object, or a property of the edges described in the table. Each table may provide a single edge type. For example, all rows in a table may be detected as purchase orders or those rows may all be detected as debits, etc.

Subsystems herein include column classification, edge type identification, and subject/object detection. The column classification model analyzes a table to determine whether each column is a subject, object, or a property. The edge type identification model uses context information to determine what type of edge occurs in the table. The subject/object detection model parses context information to determine the subject and/or object of the edges in the table, even when not expressly designated in the columns.

Techniques herein exceed the accuracy and speed of the state of the art. In an embodiment, a computer infers a respective classification of each column in a table in a text document that contains natural language. Based on the classifications of the columns in the table, the vertices of the knowledge graph are automatically generated. Based on those column classifications and automatic analysis of a particular document portion that does not contain the table, the edges of the knowledge graph are automatically generated. The knowledge graph may be generated and operated as a property graph.

1.0 Example Computer

FIG.1is a block diagram that depicts an example computer100. In an embodiment, from table120in document110, any of classifications C1-C7by trained machine-learning (ML) inference may be used to discover natural language semantics for formatting contents of table120for graph analytics. Computer100may be one or more of a rack server such as a blade, a personal computer, a mainframe, or a virtual computer.

Computer100or another computer may perform graph analytics on any example graph presented later herein that represents semantic contents of a text document that contains natural language such as document110that may be stored in a file in a filesystem, in a database, or in volatile memory of computer100. Document110may contain a mix of prose, such as portion130, and tabular data such as table120.

1.1 Example Knowledge Graph

NLP herein entails grammatic, syntactic, and semantic analysis of tables and portions of prose in document110to discover (i.e. dynamically detect) relations between entities, and computer100uses those entities and relations to respectively generate vertices and edges in a property graph, including vertices X1-X2and edges E1-E2. A vertex may have few or many edges, but an edge has exactly two vertices (not shown). Due to syntax and semantics explained herein, linguistic classifications of entities include subjects and objects, which are linguistic roles that cause edges to be directed.

Computer100can use a natural language parser to generate interdependent pieces of a parse tree. Semantic analysis of the interdependent pieces facilitates generating a property graph that represents semantic content of a document that does not contain a table. However, the natural language parser cannot parse table120in document110because table120does not contain sentences, which the parser expects.

Table120contains rows (not shown) and columns1-3. The intersection of one row and one column is a cell that contains exactly one value such as value V2. Values V1-V3in column3occur in different respective rows. Each column may have its own format and semantics that are initially unknown to computer100that can discover such schematic details by various NLP techniques presented later herein. For example, computer100may discover that column1contains numbers of accounts that are objects, not subjects. In other words, computer100can infer syntax and semantics for tabular data, either from table120by itself, or from table120in conjunction with portion130.

1.2 Column Classification

One goal of computer100is to infer linguistic classifications C1-C3for respective columns1-3in table120. Computer100may generate one vertex respectively for each value contained in columns based on the respective classifications of the columns as discussed later herein. For example if table120contains ten rows, then each of columns1-3contains ten values. In that case, computer100may generate, based on classification Cl of column1, ten vertices including vertices X1-X2.

Another goal of computer100is to generate an edge for each row in table120, where the edge is directed to connect exactly one vertex that represents a subject and exactly one vertex that instead represents an object. Edge generation is based on various NLP techniques for contents of portion130and based on inferred classifications of column(s). For example if classification Cl indicates that column1contains numbers of accounts that are objects, not subjects, then vertices X1-X2represent objects, not subjects.

Because edges E1-E2should additionally be connected to respective subject vertices (not shown), other column2or3may provide values for generating subject vertices. For example, classification C2may indicate that values in column2represent subjects. Computer100also accommodates scenarios where table120has only one column or where only one column is reliably classified. For example, any of classifications C1-C3that does not exceed a confidence threshold is rejected as inconclusive and is not used for column interpretation. Thus, computer100may sometimes discover only a subject or an object column in table120but not both. In such cases, edges E1-E2cannot be generated based solely on table120, and are instead generated based additionally on syntax and semantics of portion130that accompanies table120.

Instead of being contained in table120, portion130may be adjacent to table120in document110. For example, portion130is prose that may be a variable-sized (i.e. word count) sentence or paragraph that may be directly above (i.e. immediately precedes) table120. Likewise, portion130may be a variable-sized caption directly below (i.e. immediately follows) table120. In another example, portion130contains a fixed count of words that occur immediately before or after table120or both before and after. Document110may contain prose that portion130does not contain, such as in other portions.

As discussed later herein, classification C7may be inferred for portion130of prose, and classification C7may be comparable to classifications C1-C3. In an example not shown, table120has only columns1-2but not column3. If classification C1indicates that column1is an object, not a subject, and classification C2is inconclusive as discussed above, then a classification for column2may be imputed from portion130. For example, classification C7of portion130may be used as the classification of column2instead of inconclusive (e.g. missing) classification C2.

In other words, portion130of prose may provide sufficient linguistic context to supply a missing classification of: a) a column in table120and/or b) a missing and complementary vertex type as a prerequisite for determining an edge type. For example for (b), a table that has only one column cannot supply both a subject and an object as needed to determine a directed edge type. The missing subject or object may be supplied by portion130based on classification C7, even if classification C7has no corresponding column in table120. In an example not shown, table120has only column1but not columns2-3. If classification C1indicates that column1contains account numbers as an object, not a subject, then vertices X1-X2may represent different accounts. In that case, classification C7may indicate that the subject should be extracted from portion130instead of table120.

For example, one identified company may be extracted from portion130of prose, and that one company may be used as a subject to complement object vertices X1-X2as needed to generate edges E1-E2. For example, edges E1-E2may both connect to a same subject vertex that represents that company. Thus, a generated graph may indicate that a single company has deposited money into multiple accounts, which is a graph topology that can be generated from document110only by inferring classification(s) for table120, which is novel, with or without classification(s) for portion130. Classifications C4-C6are discussed later herein.

2.0 First Example Natural Language Processing (NLP) Pipeline

FIG.2Ais a dataflow diagram that depicts an example natural language processing (NLP) pipeline200that has NLP stages connected in series and in parallel. One or more of computer100may implement any or all of the NLP stages of NLP pipeline200.FIG.2Ais discussed with reference toFIG.1.

FIG.2Ais demonstratively provided as a high level overview of an NLP pipeline that is enhanced to generate graph221that represents text document201.FIG.2Aincorporates the mechanisms, stages, and novel specialized NLP pipelines presented later herein.

InFIG.2A, data flows from left to right according to the unnumbered shown arrows. Text document201enters NLP pipeline200that consists primarily of two (i.e. top and bottom) parallel internal pipelines that, like NLP pipeline200, have horizontal dataflow from left to right. Upon entering NLP pipeline200, text document201is (e.g. concurrently) processed by both of top and bottom internal pipelines.

The top internal pipeline has a sequence of NLP stages203,205, and207, and these may or may not be implemented as separate NLP pipelines. The top internal pipeline logically decomposes text document201into natural language sentences. Sentences may be terminated by occurrences of a small predefined set of sentence termination characters such as period, question mark, exclamation point, and semicolon. Each sentence is individually processed by NLP stages203,205, and207. For example, shown sentence n+1 is preceded by shown sentence n. In an embodiment, multiple sentences are concurrently processed by each individual one of NLP stages203,205, and207. For example, sentence splitter203may concurrently process both of sentences n and n+1. Any discussion herein of one current sentence is as a demonstrative convenience that does not prevent concurrent processing of multiple (e.g. all) sentences.

Sentence splitter203tokenizes the current sentence by decomposing the current sentence into occurrences of individual words. Sentence splitter203may detect whitespace characters in the current sentence as separators between words. For example, “It starts fast and ends fast.” is an example sentence that has multiple occurrences of same word “fast” in different positions within the sequence of word occurrences in the example sentence. Sentence splitter203may generate an encoding of the current sentence as a feature vector in which each feature has a one-to-one correspondence to each word occurrence. Thus, each position in the feature vector corresponds to each position in the sequence of word occurrences in the example sentence. Encoding example embeddings of each word occurrence into the feature vector is discussed later herein.

In an embodiment, sentence splitter203performs statistical dependency parsing using a library such as open source spaCy whose parser finds the linguistic dependencies of all noun chunks (e.g. subwords), adjectives, and verbs in prose to infer sentence boundaries even when punctuation marks do not provide clear separation of sentences.

Sentence splitter203emits the generated feature vector as output, which named entity recognition205accepts as input. Named entity recognition205detects names of entities, and an entity name may consist of a sequence of one or more words such as “Joe Lunchbox” that may be an entity that represents a person. An entity is a distinct person, place, or thing, and has a name that is distinct within text document201. In this example, named entities209are recognized in sentence n, and named entities213are recognized in sentence n+1.

Named entity recognition205may replace each occurrence of the word(s) of an entity name with a token (i.e. identifier or learned embedding) that uniquely represents the named entity. Named entity recognition205generates a feature vector, somewhat similar to that generated by sentence splitter203, except that some word(s) are replaced by fewer tokens of recognized entities. The tokens are fewer because multiple words may be replaced by a single (e.g. learned) token that represents those words. Thus, the output of named entity recognition205may be smaller and denser and semantically richer than the less refined output of sentence splitter203. Entity detection is a form of semantic (i.e. not syntactic) analysis, and named entity recognition205provides a semantically enriched representation of the current sentence as an output vector that relation extraction207accepts as input. Named entity recognition205has other embodiments, including later herein named entity recognizer230that has a special way to recognize and classify an entity as a short sequence of adjacent words.

Relation extraction207combines (e.g. learned) syntactic and semantic analysis to detect relations between entities and objects or other entities. Relation extraction207may classify words by syntactic role such as noun and verb or even subject and object or base and modifier (e.g. adjective or adverb). Extracted relations211and215may or may not directly correspond to syntactic dependencies such as respective pieces of a parse tree. Relations215may be inferred without generating a whole parse tree.

Because relations are composable, NLP pipeline200interconnects extracted relations211and215, emitted as output by relation extraction207, to become a cohesive compound data structure shown as graph221that represents the contents of text document201and is subsequently suitable for automated graph analytics.

The bottom internal pipeline has only one NLP stage, which is coreference resolution217that performs (e.g. learned) semantic analysis to detect entity aliases that are alternate names or other words that denote a same entity in different ways. This semantic analysis may detect an antecedent of a pronoun, which may be a highly contextual detection. For example, which entity is the pronoun “it” a coreference (i.e. alias) of may depend on which sentence or phrase contains the current instance of “it”. That is, two instances of “it” (e.g. in two separate sentences) may have different respective antecedents (e.g. nouns) that resolve to different respective entities.

Coreference clusters219are shown as three large circles containing different amounts of small circles. Each large circle represents a cluster that represents a respective entity. Each small circle within a cluster represents a distinct coreference (i.e. alias) of the same entity. Different sentences may have coreferences in a same cluster (for a same entity). For example, “The bicycle is red. It is new, and it is a fast bike!” are example sentences that may contribute four (i.e. “bicycle”, “it”, “it”, “bike”) coreferences to one cluster.

Before final generation of graph221, NLP pipeline200uses generated coreference clusters219to disambiguate words that may otherwise represent an unknown entity or multiple mutually-exclusive possible entities. For example, each coreference in a cluster may be treated as a placeholder that may be replaced in any relation by a token (i.e. identifier or learned embedding) that uniquely represents the entity that the cluster represents. Coreference clusters219may be used to process relations211and215that consist of a few connected vertices as shown.

For a coreference and entity in a same cluster, replacement of the coreference in a first relation with the entity from a second relation may cause the vertex that represents the coreference to be merged with the vertex that represents the entity. That merging of two vertices from different (i.e. unconnected) relations may cause both relations to become connected at the merged vertex that represents the entity. In that way, relations may be composable to combine all of relations211and215to generate topologically complex graph221that may contain many relations, such as linear chains of relations, branches off of a chain, and a star having several branches.

2.1 Example Named Entity Recognizer

FIG.2Bis a dataflow diagram that depicts an example named entity recognizer230that may be an implementation of named entity recognition205ofFIG.2A.FIG.2Bis discussed with reference toFIGS.1and2A.

Words235may be the sequence of natural language words in sentence n ofFIG.2A. Named entity recognizer230: a) accepts words235as input or b) accepts sentence n as input and extracts words235from sentence n.

Named entity recognizer230is an artificial neural network (ANN) that contains a sequence of three neural tiers231-232, and each neural tier may contain its own sequence of neural layers. Flowing data235-238flow into and/or out of a neural tier, and each neural tier may or may not be implemented as a separate neural network. As shown, subwords236are generated as output by roberta tokenizer231and accepted as input by pretrained roberta232. Each of flowing data235-238is a sequence. For example, words235is a sequence of words.

Roberta tokenizer231is pretrained to accept words235as input and infer subwords236as output. For example, the leftmost word of words235is split into two subwords in inferred subwords236as shown. One of words235splits into three subwords as shown. As shown, some words are not split into subwords. For example, nonsense may contain “non” as a subword. A subword may have natural language semantics. Herein, a subword is also referred to as a word fragment.

By factorization, subwords decrease the count of words in a vocabulary (i.e. dictionary). For example, detecting “s” as a subword means that singular and plural forms of a word may share a base subword. In that case, “cat”, “cats”, “dog”, “dogs”, “whale”, “whales” are six words that can be refactored into a vocabulary of only four subwords “cat”, “dog”, “whale”, and “s”.

Pretrained roberta232may implement bidirectional encoder representations from transformers (BERT). A transformer implements neural self-attention to focus on different parts of subwords236as an input sequence (e.g. sentence). This sequence processing captures long-range dependencies between subwords236.

Pretrained roberta232accepts subwords236as input and infers learned subword embeddings237as output. Subword embeddings are contextual. For example, “less” is a subword whose embedding is different depending on which word contains “less”, such as touchless and reckless.

Each embedding in subword embeddings237may have a different amount of subwords. Thus, subword embeddings237contains variable-sized embeddings.

Pooling is a technique used to summarize a variable-sized sequence (i.e. one embedding of subword embeddings237) into a fixed-length vector (i.e. one embedding of word embeddings238). Pooling233accepts subword embeddings237as input and infers learned word embeddings as output. A natural language word is represented by a word embedding that is based on the embeddings of the constituent subwords of the word, but is not contextual. For example, the shown leftmost of subword embeddings237is a pair of two subwords that represent a word. The relative ordering of those two subwords does not affect the inferred word embedding of that word. Pooling233may perform mean pooling (i.e. numeric averaging) of both subwords to infer a word embedding in word embeddings238. Mean pooling ignores the relative ordering of subwords within a word.

2.2 Named Entity Recognizer Training

FIG.2Cis a dataflow diagram that depicts example training of named entity recognizer230ofFIG.2B.FIG.2Cis discussed with reference toFIG.2B.

As explained forFIG.2B, pooling233generates word embeddings238. Softmax classifier241accepts word embeddings238as input and individually processes each word embedding. Each word embedding passes through softmax classifier241that may be a single linear layer feed-forward neural network or a two-layer feed-forward neural network to predict probabilities for that word belonging to each class. Some example classes may include person, organization, and location. In an embodiment, softmax classifier241does not directly predict an entity type for each word, and softmax classifier241instead predicts an entity type for a sequence of a few adjacent words and indicates where one entity ends and another starts, especially if two entities of a same type are adjacent.

Ground truth243is a one-hot label encoding, where the one represents the correct class. Cross-entropy loss is used between word predictions242and ground truth243and backpropagated to fine-tune softmax classifier241and weights in pretrained roberta232. During training, the cross-entropy loss propagates back through all components in the reverse direction of the arrows, fine-tuning every neural tier shown inFIGS.2B-C. Word predictions242are the inferred class, which has the highest inferred probability for a word.

2.3 Example Relation Extractor

FIG.2Dis a dataflow diagram that depicts an example relation extractor250that may be an implementation of relation extraction207ofFIG.2A.FIG.2Dis discussed with reference toFIG.2B.

Although relation extractor250and named entity recognizer230are different subsystems, their internal architectures and dataflows may have some similarities. Words254operate similar to words235as discussed earlier herein. Although not shown inFIG.2D, relation extractor250contains components similar to roberta tokenizer231and subwords236.

Roberta251operates similar to pretrained roberta232as discussed earlier herein. Relation extractor250contains pooling252that is downstream of an unshown pooling that operates similar to pooling233. From roberta251, the unshown pooling accepts subword embeddings that operate similar to subword embeddings237. The unshown pooling emits word embeddings233that operate similar to word embeddings238.

Pooling252generates one embedding of entity embeddings256for each entity. If an entity consists of a single word, the entity embedding is the same as the embedding of that word. If the entity consists of multiple words, then pooling252mean-pools (i.e. averages) the embeddings of each word in the entity to obtain the entity embedding.

Candidate generation253generates relation candidates257by pairing entities because each relation has two entities. Each pair of entities in a sentence is considered as a candidate to have two oppositely-directed relations. With n entities, there are n·(n−1) candidate relations in total. These relation candidates are represented by the concatenation of the entity embeddings of the pair. The directionality is represented by the order of concatenation. When representing the relation A→B, the embeddings of A and B are concatenated in the order A before B. When instead representing the relation B→A, the embeddings of A and B are concatenated in the order B before A.

2.4 Relation Extractor Training

FIG.2Eis a dataflow diagram that depicts example training of relation extractor250.FIG.2Eis discussed with reference toFIGS.2C-D.

Relation candidates257are passed through softmax classifier261that operates similar to softmax classifier241. The classifier outputs relations predictions262for each relation candidate, including the predicted probability of the candidate relation belonging to any of the possible relation types, including the probability of “no relation” between the entities, which means no relation in that direction, although the prediction in the opposite direction might differ.

Ground truth263is one-hot encoded as discussed earlier for ground truth243. Backpropagation of cross-entropy loss for fine tuning occurs similar to as discussed earlier forFIG.2C. Example relation types (i.e. classes) include ownership, transaction, visit, counterparty, and acquaintance. Some relation types may be more specific such as financial transaction, cash transaction, or electronic transaction.

FIG.3is a dataflow diagram that depicts an example natural language processing (NLP) pipeline300that has table2graph303that is an NLP stage or pipeline that analyzes table309in text document301to generate corresponding graph elements319,321,323, and325in property graph305. One or more of computer100may implement any or all of the NLP stages of NLP pipeline300. NLP pipelines200and300are compatible and their NLP stages may be combined or interleaved in a same NLP pipeline.FIG.3is discussed with reference toFIG.1.

NLP pipeline300accepts text document301as input. Table2graph303is an NLP stage that may be arranged in serial or in parallel with other stages (not shown) in NLP pipeline300. Either NLP pipeline300or table2graph303logically decomposes text document301into the following sequence of four parts: a) prose and/or tables that precede portion307of prose in text document301, b) portion307that is a small (e.g. sentence or paragraph as discussed later herein) amount of natural language prose that immediately precedes table309, c) table309, and d) prose and/or tables that follow table309in text document301. In some examples, the ordering of (b)-(c) is reversed. That is, portion307of prose may immediately precede or immediately follow table309.

Table2graph303accepts portion307of prose and table309as input. Table309contains three columns and three rows as shown. The top row of table309is a header that indicates the respective name of each column. Each of the remaining rows are individually analyzed by relation extractor250ofFIG.2Cin table2graph303to generate a respective one of edges321and323that both connect vertices319and325in graph305. For example, relation predictions262ofFIG.2Emay be used to generate edges321and323.

Table2graph303analyzes portion307of prose and table309to generate inferences311as output that NLP pipeline300uses to generate graph305. Inferences311contains inferences313,315, and317, all of which are trainable. Column classifications313contains one linguistic classification inference per column of table309. A predefined small set of linguistic classes may contain an entity class and, for attributes of entities, a property class. For example as shown in column classifications313, all three columns of table309are classified by table2graph303as properties, not entities. Learned column classifying may be based on the name and/or content datatype of a column.

Edge type detection315is a single inference that detects the edge type that is shared by edges321and323that are generated from table309. In some cases, edge type detection315can be inferred solely from column classifications313. In other cases, edge type detection315is also based on portion307of prose. As discussed later herein, edge type detection is a form of learned classification of: table309, a column in table309, and/or portion307of prose. In the shown example, edge type detection315is based on portion307of prose that says “cash deposits . . . cash deposits . . . Currency Transaction” that may cause NLP by table2graph303to infer that edge type detection315is cash transaction. Thus, edge type detection315is an inference that edges321and323should represent cash transactions.

A relation, as discussed earlier herein, may connect two entities and be represented as an edge that connects two vertices. Herein, edges are directed, which means that both entities of a relation have respective linguistic roles such as subject and object. Subject and object317are an inferred subject and an inferred object, which are two separate linguistic inferences that are role classifications. Document elements307and309may contain many entities that table2graph303may infer respective roles for. Of those many entities, several may be classified as a subject, but only one of those subjects is inferred to be the subject for subject and object317. Likewise of many detected objects, only one object is inferred to be the object for subject and object317. For example, multiple entities may be serially or concurrently used to infer classifications, and the earliest inference to finish with subject as the class may be used as the subject for subject and object317. For example, subject and object317may be based on classifications C4-C6of individual words inFIG.1. Entity role inferencing techniques are discussed later forFIG.7.

According to column classifications313, the shown properties of edges321and323have values for date, amount, and branch that are automatically obtained from respective rows and columns of table309during edge generation. According to subject and object317, the shown properties of vertices319and325have values that are automatically obtained from portion307of prose during vertex generation. A one-to-one correspondence of entities to vertices may be used for vertex generation.

4.0 Example Column Transcription and Column Classification

FIG.4Ais a dataflow diagram that depicts an example natural language processing (NLP) pipeline400that has bidirectional encoder representations from transformers (BERT)403that is an NLP pipeline stage that linguistically analyzes table309ofFIG.3in text document301to infer that the date column in table309should be classified as a property as shown or, instead, as a subject or an object, which are linguistic roles (i.e. classes) that facilitate property graph (e.g. final graph305) generation concerns such as topology, granularity, and flow direction. A property may be used as a vertex property or an edge property or neither.

One or more of computer100may implement any or all of the NLP stages of NLP pipeline400. NLP pipelines200,300, and400are compatible and their NLP stages may be combined or interleaved in a same NLP pipeline.FIG.4Ais discussed with reference toFIG.1. BERT403contains a full NLP infrastructure stack that can tokenize text into a sequence of words and analyze the sequence including contextual embedding and machine learning (ML) attention.

BERT403may or may not be based on roberta neural tiers that operate similar to those ofFIG.2B. BERT and roberta operate as encoders that generate embeddings that are not fixed-size embeddings. Instead the BERT or roberta embeddings ofFIGS.2B and4Aare context-sensitive and can vary in length based on the word count of the input sentence. As discussed below, table309contains rows and columns that intersect as cells that store shown values or headers.

As follows, each cell's content is processed as a linguistic word, and cells in one column are concatenated to form a sentence. Herein, each column of table309may be transcribed into a respective sentence for NLP analytics. By this columnar transcription, NLP pipeline400effectively shreds (i.e. vertically slices or projects) table309into columnar sentences that BERT403accepts as input such as new text401. New text401contains a columnar sentence generated by columnar transcription.

NLP pipeline400uses a novel encoding of the values in the date column to generate new (i.e. synthetic) text401that BERT403accepts as input. Depending on embodiment, new text401is a new text document (i.e. not text document301), a new sentence, or a new document that contains only one (i.e. new) sentence.

The horizontal arrow between table309and new text401represents transcription that copies the shown date column from table309into new text401. This transcription effectively projects and rotates the date column a quarter turn counterclockwise into new text401.

This transcription generates a special text encoding of the date column that performs a concatenation of the column name (from the shown header of table309) and all of the values (i.e. dates) in the date column. In new text401, the column name and the values in the column are separated by whitespace (e.g. the shown vertical pipe character and the underscore character) that BERT403treats as separator characters between words. The pipe character may operate as a suffix that indicates “Date” is a column header name.

BERT403contains pooling as discussed earlier herein that generates fixed-size encoded column405that contains a columnar embedding of new text401. Classifier411may be a softmax classifier as discussed earlier herein for stream processing a feed of documents or may be a more computationally intensive classifier (e.g. ML model) for batching. Classifier411is a column classifier that infers that the date column should be classified as property413as shown or, instead, as a subject or an object, which are linguistic roles (i.e. classes). Column classification313is generated from three inferences by classifier411for three columns in table309. Classifier411can infer classifications C1-C3ofFIG.1.

4.1 Example Coreference Resolution

Coreference resolution may concatenate multiple relations into chains, stars, and subgraphs. As discussed later herein, coreference resolution may or may not occur before graph vertex generation to prevent duplicate vertices. As explained earlier forFIG.2A, coreference resolution217performs semantic analysis to detect entity aliases (i.e. alternate names or other words that denote a same entity in different ways). This semantic analysis may detect an antecedent of a pronoun, which may be a highly contextual detection.

FIG.4Bis a dataflow diagram that depicts an example coreference resolver420that may be an implementation of coreference resolution217. Words424may operate similar to words235ofFIG.2B. Word embedding425may operate similar to word embeddings238. Spanbert421may operate somewhat similar to roberta251or BERT403, except that spanbert421does not process individual words. Instead, spanbert421processes small spans of a few adjacent words. Spanbert421works well for named and unnamed entities that are referred to by pairs or triplets or a few adjacent words such as “Mr. Joe Lunchbox” or “that person”.

The initial steps are similar to other BERT or roberta techniques earlier herein, with some important differences. This includes tokenization of the input document into a sequence of words and passing the word sequence through an NLP transformer, in this case spanbert421, to obtain word embeddings. However, because coreference resolution is concerned with inter-sentence contextual dependencies, the entire text document301is processed by spanbert421. For scalability, text document301may be divided into segments of a decided maximum length (e.g.512words) and each segment is independently passed through spanbert421to obtain corresponding embeddings.

To avoid computational complexity, candidate mention generation422generates, and words spans426contains, only spans up to a certain length (e.g.16words), which is sufficient for any postal address. Each of word spans426may contain various counts of words. As discussed earlier herein, pooling423generates candidate mention representations427that contains a fixed-size encoding of each candidate mention. A mention is an express reference to an entity in a sentence. For example, “Mr. Joe Lunchbox” and “that person” are two mentions of a same or different entities.

Word embeddings425, word spans426, and candidate mention representations427are a progression of increasingly meaningful numerical representations. Word embeddings425and word spans426may expressly contain subwords as discussed earlier herein for increased accuracy and density.

FIG.4Cis a dataflow diagram that depicts example operation of coreference resolver420that is already trained according to example neural backpropagation training presented later herein. Inferences are generated by and flow upwards from candidate mention representations427through a sequence of specialized neural networks432,434, and437in coreference resolver420.

On candidate mention representations427, coreference resolver420performs antecedent finding. In grammar, an antecedent is a named mention that confers its meaning to later mentions using the identical name, a synonymous name, or unnamed such as a pronoun, pro-verb, etc. Only one graph vertex should be generated for an antecedent and all of its coreferences.

Coreference resolution entails detecting which candidate spans are actual mentions, and finding the correct antecedents for each of those mentions. Mention scoring neural network432takes as input the span representations of candidate mentions and outputs mention scores433. Each of mention scores433is an inferred probability that a span is a valid mention. Antecedent scoring neural network434takes as input a concatenation of two candidates from candidate mention representations427, and outputs their antecedent scores435. Each of antecedent scores435is an inferred probability that the earlier span is an antecedent of the later span.

To detect whether or not two candidate mentions have a coreference relationship, the sum of the two candidate's individual mention scores and their antecedent score is used, and each sum of those three scores is one of coreference scores436. Softmax437learns the probability distribution of possible antecedents for each mention. A shown additional coreference score is a predefined probability of any mention having no antecedent438, which may or may not incidentally be the highest coreference score.

During training, the predicted distribution from softmax437is compared with the ground truth distribution (not shown) obtained from annotated coreference clusters, where the antecedents of a span are the earlier spans in the same cluster. The loss between these distribution vectors is used for neural fine-tuning, including weights of spanbert421, and neural networks432,434, and437, and the attention vector in pooling423.

Candidate mention representations427occur in a sequence for text document301. Coreference resolver420predicts an antecedent distribution for a mention in that sequence as follows. In this example, the antecedent distribution prediction is for the candidate mention on the right (i.e. latest). To the left of the latest mention are two earlier mentions. A probability distribution from softmax437includes a highest probability for a predicted class (i.e. antecedent), which might be no antecedent438.

5.0 Example Prose Analytics

As explained earlier forFIG.3, edge type detection315is a single inference that detects the edge type that is shared by edges321and323that are generated from table309. In some cases, edge type detection315can be inferred solely from column classifications313. In this example, edge type detection315is also based on portion307of prose. Edge type detection315is an inference that edges321and323should represent cash transactions.

FIG.5Ais a dataflow diagram that depicts an example NLP pipeline500that has BERT503that is an NLP pipeline stage that linguistically analyzes portion307of prose ofFIG.3in text document301to infer edge type detection315that indicates that table309should be classified as containing cash transactions. That means each row of table309contains a separate cash transaction that are respectively represented by edges321and323. Classifier511is a table classifier that operates similar to classifier411as discussed earlier, and fixed-size encoded column505operates similar to fixed-size encoded column405. Classifier511can infer classification C7ofFIG.1.

5.1 Example Graph Generation Process

FIG.5Bis a flow diagram that depicts an example computer process that any NLP pipeline herein may perform to generate a knowledge graph from a text document that contains natural language prose and data table(s). The process ofFIG.5Bmay be based on computer100, and computer100may implement any combination of NLP stages and pipelines herein.FIG.5Bprovides an example of high performance NLP based on techniques herein.

Although the process ofFIG.5Bentails processing one table and one portion of prose in one text document, the process can be repeated in parallel for bulk processing of multiple documents, such as a) parallel processing of multiple tables and portions of prose in a text document in a live stream of text documents or b) parallel processing of multiple text documents or multiple batches of text documents. For example in one text document, multiple tables may each contribute separate sets of generated edges in the knowledge graph being generated.

The single text document that is processed inFIG.5Bmay be text document110,201, or301. The single data table that is processed inFIG.5Bmay be table120or309. The single portion of prose that is processed inFIG.5Bmay be portion130or307of prose. The single knowledge graph that is generated inFIG.5Bmay be graph221or305.

Step522generates new sentence for each column in a data table in a text document. For example as discussed earlier forFIG.4A, each table cell's content may be processed by step522as a linguistic word, and cells in one column are concatenated by step522to form a sentence. For example, each column of table309may be transcribed by step522into a respective sentence for NLP analytics. By this columnar transcription, NLP pipeline400effectively shreds (i.e. vertically slices or projects) table309into columnar sentences that BERT403accepts as input such as new text401. New text401contains a columnar sentence generated by columnar transcription in step522.

Based on each sentence generated by step522, step524infers a respective classification of each column in the table. Step524infers one classification per sentence. As discussed earlier herein forFIG.4A, steps522and524may operate in ML pipeline500, including BERT403that contains pooling that step524uses to generate fixed-size encoded column405that contains a columnar embedding of new text401(i.e. a sentence generated by step522). Classifier411may be a softmax classifier as for stream processing of a live feed of documents or may be a more computationally intensive classifier (e.g. ML model) for batching.

For example, step522and524may process the three columns in table309ofFIG.3, including the shown date column. Classifier411is a column classifier that infers that the date column should be classified by step524as property413as shown or, instead, as a subject or an object, which are linguistic roles (i.e. classes). During step524, column classification313is generated from three inferences by classifier411for three columns in table309.

Based on classifications of columns by step524, step526generates vertices in the knowledge graph being generated. Depending on the embodiment, vertices are generated before or after coreference resolution. That is, final vertices may be generated from merged entities, or duplicate vertices may be generated and merged. Whether merging entails entities or vertices, the merging is based on coreference resolution.

As discussed earlier forFIG.4C, candidate mention representations427appear as unresolved entities in a sequence for text document301. Coreference resolver420predicts an antecedent distribution for a mention in that sequence as follows. A probability distribution from softmax437includes a highest probability for a predicted class (i.e. antecedent), which might be no antecedent438. Based on coreference resolution, step526may merge entities before generating vertices or may merge vertices.

Edge generation may occur before or after coreference resolution and, in either case, does not entail generation and merging of duplicate edges. Based on classifications of columns by step524and based on portion307of prose that does not contain table309, step528generates directed edges in the knowledge graph being generated.

Step528linguistically analyzes portion307of prose ofFIG.3in text document301to infer edge type detection315that indicates that table309should be classified as containing cash transactions. That means each row of table309contains a separate cash transaction that are respectively represented by edges321and323. As discussed earlier forFIG.5A, step528may operate ML pipeline500, including operation of BERT503and classifier511as discussed earlier.

In that way, steps526and528generate vertices and edges to generate the knowledge graph, which may be graph221or305.

6.0 Example Property Graph

FIG.6depicts an example property graph600that contains vertices601,603,605,607,609,611,613, and615that represent distinct entities. For example, vertex603represents shown account12345678. Vertex603is topologically significant according to a count of connected edges or a count of neighbors (i.e. connected vertices). Property graph600is generated and operated similar to final graph305. For example, the many cash transaction relations connected to vertex603may correspond to rows in a table in a document as discussed earlier herein, but that does not mean that rows in a table are limited to redundant edges between only two vertices. Rows of a table may instead be used to generate edges for a star that has one vertex as its center and the edges connect out to various other vertices. Property graph600may be generated and operated as a knowledge graph.

7.0 Example Linguistic Role Classification

As explained earlier herein, a relation may connect two entities and be represented as an edge that connects two vertices. Herein, edges are directed, which means that both entities of a relation have respective linguistic roles such as subject and object. Subject and object317are an inferred subject and an inferred object, which are two separate linguistic inferences that are role classifications. Document elements307and309may contain many entities that table2graph303may infer respective roles for. Of those many entities, several may be classified as a subject, but only one of those subjects is inferred to be the subject for subject and object317as discussed earlier herein. Likewise of many detected objects, only one object is inferred to be the object for subject and object317. Entity role inferencing from prose occurs as follows.

FIG.7is a dataflow diagram that depicts an example NLP pipeline700that has BERT703that is an NLP pipeline stage that linguistically analyzes portion307of prose ofFIG.3in text document301to infer subject and object317. Although the architectures of NLP pipelines500and700are similar and both process portion307of prose, operation of NLP pipeline700differs as follows.

Portion307of prose is tokenized into a sequence of words, including words701,705,709, and713. This sequence of words operates similar to words235as discussed forFIG.2B. For each input word, BERT703infers a fixed-sized word encoding in a sequence of encodings that includes word encodings723,725,727, and729. Classifier711operates similar to other classifiers earlier herein. Classifier711infers a class such as subject, object, or other for each word encoding to generate classifications715,717,719, and721. For example, classifier711may infer classifications C4-C6ofFIG.1. As explained earlier herein, subject and object occur as a pair of entities in a relation and are consistent with the direction of the edge that represents the relation. In an embodiment, classifier711does not directly predict a class for each word, and classifier711instead predicts a class for a sequence of a few adjacent words and indicates where one class instance ends and another starts, especially if two instances of a same class are adjacent.

Hardware Overview

For example,FIG.8is a block diagram that illustrates a computer system800upon which an embodiment of the invention may be implemented. Computer system800includes a bus802or other communication mechanism for communicating information, and a hardware processor804coupled with bus802for processing information. Hardware processor804may be, for example, a general purpose microprocessor.

Computer system800also includes a main memory806, such as a random access memory (RAM) or other dynamic storage device, coupled to bus802for storing information and instructions to be executed by processor804. Main memory806also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor804. Such instructions, when stored in non-transitory storage media accessible to processor804, render computer system800into a special-purpose machine that is customized to perform the operations specified in the instructions.

Computer system800further includes a read only memory (ROM)808or other static storage device coupled to bus802for storing static information and instructions for processor804. A storage device810, such as a magnetic disk, optical disk, or solid-state drive is provided and coupled to bus802for storing information and instructions.

Software Overview

FIG.9is a block diagram of a basic software system900that may be employed for controlling the operation of computing system800. Software system900and its components, including their connections, relationships, and functions, is meant to be exemplary only, and not meant to limit implementations of the example embodiment(s). Other software systems suitable for implementing the example embodiment(s) may have different components, including components with different connections, relationships, and functions.

Software system900is provided for directing the operation of computing system800. Software system900, which may be stored in system memory (RAM)806and on fixed storage (e.g., hard disk or flash memory)810, includes a kernel or operating system (OS)910.

The OS910manages low-level aspects of computer operation, including managing execution of processes, memory allocation, file input and output (I/O), and device I/O. One or more application programs, represented as902A,902B,902C . . .902N, may be “loaded” (e.g., transferred from fixed storage810into memory806) for execution by the system900. The applications or other software intended for use on computer system800may also be stored as a set of downloadable computer-executable instructions, for example, for downloading and installation from an Internet location (e.g., a Web server, an app store, or other online service).

Software system900includes a graphical user interface (GUI)915, for receiving user commands and data in a graphical (e.g., “point-and-click” or “touch gesture”) fashion. These inputs, in turn, may be acted upon by the system900in accordance with instructions from operating system910and/or application(s)902. The GUI915also serves to display the results of operation from the OS910and application(s)902, whereupon the user may supply additional inputs or terminate the session (e.g., log off).

OS910can execute directly on the bare hardware920(e.g., processor(s)804) of computer system800. Alternatively, a hypervisor or virtual machine monitor (VMM)930may be interposed between the bare hardware920and the OS910. In this configuration, VMM930acts as a software “cushion” or virtualization layer between the OS910and the bare hardware920of the computer system800.

VMM930instantiates and runs one or more virtual machine instances (“guest machines”). Each guest machine comprises a “guest” operating system, such as OS910, and one or more applications, such as application(s)902, designed to execute on the guest operating system. The VMM930presents the guest operating systems with a virtual operating platform and manages the execution of the guest operating systems.

In some instances, the VMM930may allow a guest operating system to run as if it is running on the bare hardware920of computer system800directly. In these instances, the same version of the guest operating system configured to execute on the bare hardware920directly may also execute on VMM930without modification or reconfiguration. In other words, VMM930may provide full hardware and CPU virtualization to a guest operating system in some instances.

In other instances, a guest operating system may be specially designed or configured to execute on VMM930for efficiency. In these instances, the guest operating system is “aware” that it executes on a virtual machine monitor. In other words, VMM930may provide para-virtualization to a guest operating system in some instances.

Cloud Computing

Machine Learning Models

A machine learning model is trained using a particular machine learning algorithm. Once trained, input is applied to the machine learning model to make a prediction, which may also be referred to herein as a predicated output or output. Attributes of the input may be referred to as features and the values of the features may be referred to herein as feature values.

A machine learning model includes a model data representation or model artifact. A model artifact comprises parameters values, which may be referred to herein as theta values, and which are applied by a machine learning algorithm to the input to generate a predicted output. Training a machine learning model entails determining the theta values of the model artifact. The structure and organization of the theta values depends on the machine learning algorithm.

In supervised training, training data is used by a supervised training algorithm to train a machine learning model. The training data includes input and a “known” output. In an embodiment, the supervised training algorithm is an iterative procedure. In each iteration, the machine learning algorithm applies the model artifact and the input to generate a predicated output. An error or variance between the predicated output and the known output is calculated using an objective function. In effect, the output of the objective function indicates the accuracy of the machine learning model based on the particular state of the model artifact in the iteration. By applying an optimization algorithm based on the objective function, the theta values of the model artifact are adjusted. An example of an optimization algorithm is gradient descent. The iterations may be repeated until a desired accuracy is achieved or some other criteria is met.

In a software implementation, when a machine learning model is referred to as receiving an input, being executed, and/or generating an output or predication, a computer system process executing a machine learning algorithm applies the model artifact against the input to generate a predicted output. A computer system process executes a machine learning algorithm by executing software configured to cause execution of the algorithm. When a machine learning model is referred to as performing an action, a computer system process executes a machine learning algorithm by executing software configured to cause performance of the action.

Inferencing entails a computer applying the machine learning model to an input such as a feature vector to generate an inference by processing the input and content of the machine learning model in an integrated way. Inferencing is data driven according to data, such as learned coefficients, that the machine learning model contains. Herein, this is referred to as inferencing by the machine learning model that, in practice, is execution by a computer of a machine learning algorithm that processes the machine learning model.

Classes of problems that machine learning (ML) excels at include clustering, classification, regression, anomaly detection, prediction, and dimensionality reduction (i.e. simplification). Examples of machine learning algorithms include decision trees, support vector machines (SVM), Bayesian networks, stochastic algorithms such as genetic algorithms (GA), and connectionist topologies such as artificial neural networks (ANN). Implementations of machine learning may rely on matrices, symbolic models, and hierarchical and/or associative data structures. Parameterized (i.e. configurable) implementations of best of breed machine learning algorithms may be found in open source libraries such as Google's TensorFlow for Python and C++ or Georgia Institute of Technology's MLPack for C++. Shogun is an open source C++ ML library with adapters for several programing languages including C#, Ruby, Lua, Java, MatLab, R, and Python.

Artificial Neural Networks

An artificial neural network (ANN) is a machine learning model that at a high level models a system of neurons interconnected by directed edges. An overview of neural networks is described within the context of a layered feedforward neural network. Other types of neural networks share characteristics of neural networks described below.

In a layered feed forward network, such as a multilayer perceptron (MLP), each layer comprises a group of neurons. A layered neural network comprises an input layer, an output layer, and one or more intermediate layers referred to hidden layers.

Neurons in the input layer and output layer are referred to as input neurons and output neurons, respectively. A neuron in a hidden layer or output layer may be referred to herein as an activation neuron. An activation neuron is associated with an activation function. The input layer does not contain any activation neuron.

From each neuron in the input layer and a hidden layer, there may be one or more directed edges to an activation neuron in the subsequent hidden layer or output layer. Each edge is associated with a weight. An edge from a neuron to an activation neuron represents input from the neuron to the activation neuron, as adjusted by the weight.

For a given input to a neural network, each neuron in the neural network has an activation value. For an input neuron, the activation value is simply an input value for the input. For an activation neuron, the activation value is the output of the respective activation function of the activation neuron.

Each edge from a particular neuron to an activation neuron represents that the activation value of the particular neuron is an input to the activation neuron, that is, an input to the activation function of the activation neuron, as adjusted by the weight of the edge. Thus, an activation neuron in the subsequent layer represents that the particular neuron's activation value is an input to the activation neuron's activation function, as adjusted by the weight of the edge. An activation neuron can have multiple edges directed to the activation neuron, each edge representing that the activation value from the originating neuron, as adjusted by the weight of the edge, is an input to the activation function of the activation neuron.

Each activation neuron is associated with a bias. To generate the activation value of an activation neuron, the activation function of the neuron is applied to the weighted activation values and the bias.

Illustrative Data Structures for Neural Network

The artifact of a neural network may comprise matrices of weights and biases. Training a neural network may iteratively adjust the matrices of weights and biases.

For a layered feedforward network, as well as other types of neural networks, the artifact may comprise one or more matrices of edges W. A matrix W represents edges from a layer L−1 to a layer L. Given the number of neurons in layer L−1 and L is N[L−1] and N[L], respectively, the dimensions of matrix W is N[L−1] columns and N[L] rows.

Biases for a particular layer L may also be stored in matrix B having one column with N[L] rows.

The matrices W and B may be stored as a vector or an array in RAM memory, or comma separated set of values in memory. When an artifact is persisted in persistent storage, the matrices W and B may be stored as comma separated values, in compressed and/serialized form, or other suitable persistent form.

A particular input applied to a neural network comprises a value for each input neuron. The particular input may be stored as vector. Training data comprises multiple inputs, each being referred to as sample in a set of samples. Each sample includes a value for each input neuron. A sample may be stored as a vector of input values, while multiple samples may be stored as a matrix, each row in the matrix being a sample.

When an input is applied to a neural network, activation values are generated for the hidden layers and output layer. For each layer, the activation values for may be stored in one column of a matrix A having a row for every neuron in the layer. In a vectorized approach for training, activation values may be stored in a matrix, having a column for every sample in the training data.

Training a neural network requires storing and processing additional matrices. Optimization algorithms generate matrices of derivative values which are used to adjust matrices of weights W and biases B. Generating derivative values may use and require storing matrices of intermediate values generated when computing activation values for each layer.

The number of neurons and/or edges determines the size of matrices needed to implement a neural network. The smaller the number of neurons and edges in a neural network, the smaller matrices and amount of memory needed to store matrices. In addition, a smaller number of neurons and edges reduces the amount of computation needed to apply or train a neural network. Less neurons means less activation values need be computed, and/or less derivative values need be computed during training.

Properties of matrices used to implement a neural network correspond neurons and edges. A cell in a matrix W represents a particular edge from a neuron in layer L−1 to L. An activation neuron represents an activation function for the layer that includes the activation function. An activation neuron in layer L corresponds to a row of weights in a matrix W for the edges between layer L and L−1 and a column of weights in matrix W for edges between layer L and L+1. During execution of a neural network, a neuron also corresponds to one or more activation values stored in matrix A for the layer and generated by an activation function.

An ANN is amenable to vectorization for data parallelism, which may exploit vector hardware such as single instruction multiple data (SIMD), such as with a graphical processing unit (GPU). Matrix partitioning may achieve horizontal scaling such as with symmetric multiprocessing (SMP) such as with a multicore central processing unit (CPU) and or multiple coprocessors such as GPUs. Feed forward computation within an ANN may occur with one step per neural layer. Activation values in one layer are calculated based on weighted propagations of activation values of the previous layer, such that values are calculated for each subsequent layer in sequence, such as with respective iterations of a for loop. Layering imposes sequencing of calculations that is not parallelizable. Thus, network depth (i.e. amount of layers) may cause computational latency. Deep learning entails endowing a multilayer perceptron (MLP) with many layers. Each layer achieves data abstraction, with complicated (i.e. multidimensional as with several inputs) abstractions needing multiple layers that achieve cascaded processing. Reusable matrix based implementations of an ANN and matrix operations for feed forward processing are readily available and parallelizable in neural network libraries such as Google's TensorFlow for Python and C++, OpenNN for C++, and University of Copenhagen's fast artificial neural network (FANN). These libraries also provide model training algorithms such as backpropagation.

An ANN's output may be more or less correct. For example, an ANN that recognizes letters may mistake an I as an L because those letters have similar features. Correct output may have particular value(s), while actual output may have somewhat different values. The arithmetic or geometric difference between correct and actual outputs may be measured as error according to a loss function, such that zero represents error free (i.e. completely accurate) behavior. For any edge in any layer, the difference between correct and actual outputs is a delta value.

Backpropagation entails distributing the error backward through the layers of the ANN in varying amounts to all of the connection edges within the ANN. Propagation of error causes adjustments to edge weights, which depends on the gradient of the error at each edge. Gradient of an edge is calculated by multiplying the edge's error delta times the activation value of the upstream neuron. When the gradient is negative, the greater the magnitude of error contributed to the network by an edge, the more the edge's weight should be reduced, which is negative reinforcement. When the gradient is positive, then positive reinforcement entails increasing the weight of an edge whose activation reduced the error. An edge weight is adjusted according to a percentage of the edge's gradient. The steeper is the gradient, the bigger is adjustment. Not all edge weights are adjusted by a same amount. As model training continues with additional input samples, the error of the ANN should decline. Training may cease when the error stabilizes (i.e. ceases to reduce) or vanishes beneath a threshold (i.e. approaches zero). Example mathematical formulae and techniques for feedforward multilayer perceptron (MLP), including matrix operations and backpropagation, are taught in related reference “EXACT CALCULATION OF THE HESSIAN MATRIX FOR THE MULTI-LAYER PERCEPTRON,” by Christopher M. Bishop.

Model training may be supervised or unsupervised. For supervised training, the desired (i.e. correct) output is already known for each example in a training set. The training set is configured in advance by (e.g. a human expert) assigning a categorization label to each example. For example, the training set for optical character recognition may have blurry photographs of individual letters, and an expert may label each photo in advance according to which letter is shown. Error calculation and backpropagation occurs as explained above.

Unsupervised model training is more involved because desired outputs need to be discovered during training. Unsupervised training may be easier to adopt because a human expert is not needed to label training examples in advance. Thus, unsupervised training saves human labor. A natural way to achieve unsupervised training is with an autoencoder, which is a kind of ANN. An autoencoder functions as an encoder/decoder (codec) that has two sets of layers. The first set of layers encodes an input example into a condensed code that needs to be learned during model training. The second set of layers decodes the condensed code to regenerate the original input example. Both sets of layers are trained together as one combined ANN. Error is defined as the difference between the original input and the regenerated input as decoded. After sufficient training, the decoder outputs more or less exactly whatever is the original input.

An autoencoder relies on the condensed code as an intermediate format for each input example. It may be counter-intuitive that the intermediate condensed codes do not initially exist and instead emerge only through model training. Unsupervised training may achieve a vocabulary of intermediate encodings based on features and distinctions of unexpected relevance. For example, which examples and which labels are used during supervised training may depend on somewhat unscientific (e.g. anecdotal) or otherwise incomplete understanding of a problem space by a human expert. Whereas, unsupervised training discovers an apt intermediate vocabulary based more or less entirely on statistical tendencies that reliably converge upon optimality with sufficient training due to the internal feedback by regenerated decodings. Techniques for unsupervised training of an autoencoder for anomaly detection based on reconstruction error is taught in non-patent literature (NPL) “VARIATIONAL AUTOENCODER BASED ANOMALY DETECTION USING RECONSTRUCTION PROBABILITY”, Special Lecture on IE. 2015 Dec. 27; 2 (1):1-18 by Jinwon An et al.

Principal Component Analysis

Principal component analysis (PCA) provides dimensionality reduction by leveraging and organizing mathematical correlation techniques such as normalization, covariance, eigenvectors, and eigenvalues. PCA incorporates aspects of feature selection by eliminating redundant features. PCA can be used for prediction. PCA can be used in conjunction with other ML algorithms.

Random Forest

A random forest or random decision forest is an ensemble of learning approaches that construct a collection of randomly generated nodes and decision trees during a training phase. Different decision trees of a forest are constructed to be each randomly restricted to only particular subsets of feature dimensions of the data set, such as with feature bootstrap aggregating (bagging). Therefore, the decision trees gain accuracy as the decision trees grow without being forced to over fit training data as would happen if the decision trees were forced to learn all feature dimensions of the data set. A prediction may be calculated based on a mean (or other integration such as soft max) of the predictions from the different decision trees.