IP Library Granted Patent US 11,727,062
Granted Patent B1
US 11,727,062 · App. 17/349,444 · Granted Aug 15, 2023

Systems and methods for generating vector space embeddings from a multi-format document

Inventors: Paul Vincent Gaskell (Romsey, GB); Thomas Roland Barillot (London, GB)
Assignee: BlackRock, Inc.
G06F16/9024G06F40/103G06F40/131G06F40/279G06F40/30G06N3/00G06V30/414G06V30/416
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,727,062
App. No.
17/349,444
Granted
Aug 15, 2023
Kind
B1
Abstract

Embodiments described herein provide a mechanism that encodes a text document into a geometric graph, where the nodes of the graph represent bits of text from the document and the edges of the graph represent relationships among the bits of text as laid out on a page of the document. Each node of the graph is encoded into a vector representation that contains information of the node and the local sub-graph (including the node and all edges branching out from the node). In this way, the vector representations of the document contain information of the inner-relationship between words, sentences and paragraphs of the document, instead of just mapping the text in the document as a string of input tokens to a vector representation.

Claims (84)

1. A method of spatially encoding a natural language document for performing one or more natural language processing (NLP) downstream tasks, the method comprising:

receiving, via a data interface, an input document comprising a first structural object having a first data structure and a second structural object having a second data structure different from the first data structure;

identifying a first set of text spans from the first structural object and a second set of text spans from the second structural object;

generating a document graph containing a plurality of nodes from the first set of text spans and the second set of text spans, wherein each node represents a text span from the first set of text spans or the second set of text spans;

generating, based on spatial information of the text document, a plurality of edges for the document graph, wherein each edge connecting two nodes in the document graph represents a spatial relationship in a context of the text document between two text spans that correspond to the two nodes;

generating, starting from each respective node in the document graph, a respective subgraph containing the respective node and all edges branching out from the respective node;

encoding, by a graph neural network, each respective subgraph corresponding to each node in the document graph, into a respective subgraph vector that represents semantic information about the respective subgraph by:

mapping, via linear projection, a center node of the respective subgraph to a respective hidden layer state representation,

generating a respective attention output between the respective hidden layer state representation corresponding to the respective subgraph and another hidden layer state representation mapped from another subgraph corresponding to another node in the document graph,

generating a set of hidden layer state representations and a set of attention outputs corresponding to neighboring nodes of the center node, and

computing the respective subgraph vector by taking a weighted average of the set of attention outputs weighted by the set of hidden layer state representations; and

generating, by a decoder, a decoding output representing a NLP task result based on subgraph vectors corresponding to all nodes in the document graph.

2. The method of claim 1 , wherein the first set of text spans are identified at a word level or a phrase level from the first structural object.

3. The method of claim 1 , further comprising:

iterating the plurality of nodes in the document graph; and

generating, based on the iterating, the set of subgraph vectors.

4. The method of claim 1 , wherein the plurality of edges contains at least one edge that connects a first node representing a first text span from the first set of text spans and a second text span from the second set of text spans, and

wherein the at least one edge is determined based on a spatial relationship between the first text span and the second text span.

5. The method of claim 1 , wherein the respective subgraph comprises the respective node and a set of nodes that the respective node is connected to by the all edges branching out from the respective node.

6. The method of claim 1 , wherein the respective subgraph comprises more than one hop of branches from the respective node.

7. The method of claim 1 , wherein the respective subgraph vector is generated by:

traversing each node in the respective subgraph according to a pre-defined order; and

encoding, by the graph neural network, text spans obtained from the traversal of nodes in the pre-defined order to the respective subgraph vector.

8. The method of claim 1 , wherein the first structural object or the second structural object includes any combination of:

a paragraph of textual description;

an equation;

a chemical formula;

a table;

a group of bullet points;

a list;

a data chart;

a figure having one or more text spans; and

a subtitle.

9. A system for spatially encoding a natural language document for performing one or more natural language processing (NLP) downstream tasks, the system comprising:

a hardware network interface that receives an input document comprising a first structural object having a first data structure and a second structural object having a second data structure different from the first data structure;

a memory that stores a plurality of processor-executable instructions; and

a processor that reads and executes the plurality of processor-executable instructions to:

identify a first set of text spans from the first structural object and a second set of text spans from the second structural object;

generate a document graph containing a plurality of node from the first set of text spans and the second set of text spans, wherein each node represents a text span from the first set of text spans or the second set of text spans;

generate, based on spatial information of the text document, a plurality of edges for the document graph, wherein each edge connecting two nodes in the document graph represents a spatial relationship in a context of the text document between two text spans that correspond to the two nodes;

generate, starting from each respective node in the document graph, a respective subgraph containing the respective node and all edges branching out from the respective one node;

encode, by a graph neural network, each respective subgraph corresponding to each node in the document graph, into a respective subgraph vector that represents semantic information between text spans by:

mapping, via linear projection, a center node of the respective subgraph to a respective hidden layer state representation,

generating a respective attention output between the respective hidden layer state representation corresponding to the respective subgraph and another hidden layer state representation mapped from another subgraph corresponding to another node in the document graph,

generating a set of hidden layer state representations and a set of attention outputs corresponding to neighboring nodes of the center node, and

computing the respective subgraph vector by taking a weighted average of the set of attention outputs weighted by the set of hidden layer state representations; and

generate, by a decoder, a decoding output representing a NLP task result based on subgraph vectors corresponding to all nodes in the document graph.

10. The system of claim 9 , wherein the first set of text spans are identified at a word level or a phrase level from the first structural object.

11. The system of claim 9 , wherein the processor further reads and executes the plurality of processor-executable instructions to:

iterate the plurality of nodes in the document graph; and

generate the set of subgraph vectors based on the iterating.

12. The system of claim 9 , wherein the plurality of edges contains at least one edge that connects a first node representing a first text span from the first set of text spans and a second text span from the second set of text spans, and

wherein the at least one edge is determined based on a spatial relationship between the first text span and the second text span.

13. The system of claim 9 , wherein the respective subgraph comprises the respective node and a set of nodes that the respective node is connected to by the all edges branching out from the respective node.

14. The system of claim 9 , wherein the respective subgraph vector is generated by:

traversing each node in the respective subgraph according to a pre-defined order; and

encoding, by the graph neural network, text spans obtained from the traversal of nodes in the pre-defined order to the respective subgraph vector.

15. The system of claim 9 , wherein the first structural object or the second structural object includes any combination of:

a paragraph of textual description;

an equation;

a chemical formula;

a table;

a group of bullet points;

a list;

a data chart;

a figure having one or more text spans; and

a subtitle.

16. A non-transitory processor-readable medium storing a plurality of processor-executable instructions for spatially encoding a natural language document for performing one or more natural language processing (NLP) downstream tasks, the processor-executable instructions being executed by a processor to:

receive, via a data interface, the input document comprising a first structural object having a first data structure and a second structural object having a second data structure different from the first data structure;

identify a first set of text spans from the first structural object and a second set of text spans from the second structural object;

generate a document graph containing a plurality of node from the first set of text spans and the second set of text spans, wherein each node represents a text span from the first set of text spans or the second set of text spans;

generate, based on spatial information of the text document, a plurality of edges for the document graph, wherein each edge connecting two nodes in the document graph represents a spatial relationship in a context of the text document between two text spans that correspond to the two nodes;

generate, starting from each respective node in the document graph, a respective subgraph containing the respective node and all edges branching out from the respective node;

encode, by a graph neural network, each respective subgraph corresponding to each node in the document graph, into a respective subgraph vector that represents semantic information between text spans by:

mapping, via linear projection, a center node of the respective subgraph to a respective hidden layer state representation,

generating a respective attention output between the respective hidden layer state representation corresponding to the respective subgraph and another hidden layer state representation mapped from another subgraph corresponding to another node in the document graph,

generating a set of hidden layer state representations and a set of attention outputs corresponding to neighboring nodes of the center node, and

computing the respective subgraph vector by taking a weighted average of the set of attention outputs weighted by the set of hidden layer state representations; and

generating, by a decoder, a decoding output representing a NLP task result based on subgraph vectors corresponding to all nodes in the document graph.

17. The medium of claim 16 , wherein the plurality of edges contains at least one edge that connects a first node representing a first text span from the first set of text spans and a second text span from the second set of text spans, and

wherein the at least one edge is determined based on a logical relationship between the first text span and the second text span.

18. The medium of claim 16 , wherein the respective subgraph vector is generated by:

traversing each node in the respective subgraph according to a pre-defined order; and

encoding, by the graph neural network, text spans obtained from the traversal of nodes in the pre-defined order to the respective subgraph vector.

Assignments (2)
MERGER AND CHANGE OF NAME Recorded Oct 4, 2024
From: BLACKROCK, INC.; BANANA MERGER SUB, INC.
To: BLACKROCK FINANCE, INC.
Reel/Frame 069113/0616 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 25, 2021
From: GASKELL, PAUL VINCENT; BARILLOT, THOMAS ROLAND
To: BLACKROCK, INC.
Reel/Frame 057290/0664 →
Cited By (3)
US 12,481,707 US 12,665,071 US 12,670,505