Document structure extraction using machine learning

Patent metadata

Field	Value
Publication number	US-11769072-B2
Application number	US-201615231294-A
Country	US
Kind code	B2
Filing date	Aug 8, 2016
Priority date	Aug 8, 2016
Publication date	Sep 26, 2023
Grant date	Sep 26, 2023

Abstract

The structure of an untagged document can be derived using a predictive model that is trained in a supervised learning framework based on a corpus of tagged training documents. Analyzing the training documents results in a plurality of document part feature vectors, each of which correlates a category defining a document part (for example, “title” or “body paragraph”) with one or more feature-value pairs (for example, “font=Arial” or “alignment=centered”). Any suitable machine learning algorithm can be used to train the predictive model based on the document part feature vectors extracted from the training documents. Once the predictive model has been trained, it can receive feature-value pairs corresponding to a portion of an untagged document and make predictions with respect to the how that document part should be categorized. The predictive model can therefore generate tag metadata that defines a structure of the untagged document in an automated fashion.

First claim

What is claimed is:

1. A document structure extraction method comprising:
receiving, by a document structure analytics server, an untagged document that comprises a plurality of document parts, wherein certain of the document parts have a visual appearance that is defined by formatting information included in the untagged document;
receiving, by the document structure analytics server, a command to generate a table of contents for the untagged document;
in response to receiving the command to generate the table of contents, invoking a document tagging process that comprises:
identifying a document type category to which the untagged document belongs;
extracting at least a portion of the formatting information from the untagged document;
for each of two or more of the plurality of document parts, generating one or more feature-value pairs using the extracted formatting information, wherein each of the generated feature-value pairs characterizes the visual appearance of the corresponding document part by associating a particular value with a particular formatting feature;
making a selection of a particular predictive model, from amongst a plurality of predictive models hosted by the document structure analytics server, wherein the selection is made based on the particular predictive model having been trained using a corpus of tagged training documents belonging to the identified document type category to which the untagged document belongs, and wherein each of the predictive models is configured to categorize document parts for documents sharing a common document type categorization for a respective predictive model;
using the particular predictive model to predict a categorization for each of the two or more document parts that form part of the untagged document based on the corresponding one or more feature-value pairs, wherein the particular predictive model applies a machine learning algorithm to make predictions based on a collection of categorized feature-value pairs aggregated from, and characterizing document parts included in, the corpus of tagged training documents belonging to the identified document type category; and
defining tag metadata that associates each of the two or more document parts with the corresponding predicted categorization generated by the particular predictive model;

generating the table of contents based on the defined tag metadata, wherein the table of contents correlates a document part identified as a heading by the particular predictive model with a location of the heading within the untagged document; and
modifying the untagged document to include the generated table of contents.

2. The document structure extraction method of claim 1 , wherein one of the generated feature-value pairs associates a font size formatting feature with a particular font size value.

3. The document structure extraction method of claim 1 , wherein
the untagged document is received from a client computing device; and
the method further comprises applying the tag metadata to the untagged document to produce a tagged document that includes the table of contents, and sending the tagged document that includes the table of contents to the client computing device.

4. The document structure extraction method of claim 1 , wherein one of the generated feature-value pairs associates a font size formatting feature with a particular value that is selected from a group consisting of a largest font in the untagged document, an intermediate-sized font in the untagged document, and a smallest font in the untagged document.

5. The document structure extraction method of claim 1 , wherein one of the generated feature-value pairs associates a font size formatting feature with a particular value that is selected from a group consisting of a font size that is larger than a preceding paragraph, a font size that is smaller than the preceding paragraph, a font size that is larger than a following paragraph, and a font size that is smaller than the following paragraph.

6. The document structure extraction method of claim 1 , wherein the particular value defines the particular formatting feature in relation to a formatting feature for a second document part.

7. The document structure extraction method of claim 1 , wherein
the particular value is selected from a group consisting of left justification, center justification, right justification, and full justification; and
the particular formatting feature is a paragraph alignment formatting feature.

8. The document structure extraction method of claim 1 , the document tagging process further comprising using the particular predictive model to determine a confidence level in the categorization for at least some of the two or more document parts that form part of the untagged document.

9. The document structure extraction method of claim 1 , wherein receiving the untagged document further comprises receiving, from a document viewer executing on a client computing device, the plurality of document parts and the formatting information.

10. The document structure extraction method of claim 1 , wherein receiving the untagged document further comprises receiving, by the document structure analytics server, a plurality of untagged documents from a document management system.

11. The document structure extraction method of claim 1 , further comprising embedding the tag metadata into the untagged document to produce a tagged document that also includes the table of contents.

12. The document structure extraction method of claim 1 , further comprising
embedding the tag metadata into the untagged document to produce a tagged document that also includes the table of contents, and
sending the tagged document to a client computing device.

13. The document structure extraction method of claim 1 , further comprising modifying the untagged document such that the visual appearance of at least some of the two or more document parts is further defined by the predicted categorization generated by the particular predictive model.

14. A non-transitory computer readable medium encoded with instructions that, when executed by one or more processors, cause a document structure analysis process to be invoked, the process comprising:
identifying a plurality of training documents, each of which is associated with a particular document type category;
accessing a particular one of the training documents, the particular training document comprising a plurality of document parts, wherein a particular one of the document parts has (a) a visual appearance defined by formatting information included in the particular training document, and (b) a document part categorization;
generating, for the particular document part, one or more feature-value pairs using the formatting information, wherein each of the generated one or more feature-value pairs characterizes the visual appearance of the particular document part by correlating a particular value with a particular formatting feature, wherein a particular one of the generated feature-value pairs defines a proportion of content comprising the particular training document having a particular visual appearance;
defining a document part feature vector that links the generated one or more feature-value pairs with the document part categorization, wherein the document part feature vector links
a feature-value pair that correlates a document part comprising 90% or more of document content with a body paragraph categorization, and
a feature-value pair that correlates a document part comprising less than 0.1% of document content with a title categorization;

storing the document part

Assignees

• Adobe Inc

Inventors

• Kraley Michael

Classifications

• G06N20/00 Primary

  Machine learning · CPC title

• G06F18/24133

  Distances to prototypes · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title

• G06V30/414

  Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text · CPC title

• G06F40/117

  Tagging; Marking up (details of markup languages G06F40/143); Designating a block; Setting of attributes (style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154) · CPC title