METHODS AND SYSTEMS TO TRAIN MODELS TO EXTRACT AND INTEGRATE INFORMATION FROM DATA SOURCES

• US 20100145902A1
• Filed: 05/15/2009
• Published: 06/10/2010
• Est. Priority Date: 12/09/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: McDonald, Glenn, Molnar, Ray, Benthall, Margaret, BOYAN, Justin
• Granted Patent: US 8,805,861 B2
• Time in Patent Office: Days
• US Class Current: 706/54
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

Methods and systems to model and acquire data from a variety of data and information sources, to integrate the data into a structured database, and to manage the continuing reintegration of updated data from those sources over time. For any given domain, a variety of individual information and data sources that contain information relevant to the schema can be identified. Data elements associated with a schema may be identified in a training source, such as by user tagging. A formal grammar may be induced appropriate to the schema and layout of the training source. A Hidden Markov Model (HMM) corresponding to the grammar may learn where in the sources the elements can be found. The system can automatically mutate its schema into a grammar matching the structure of the source documents. By following an inverse transformation sequence, data that is parsed by the mutated grammar can be fit back into the original grammar structure, matching the original data schema defined through domain modeling. Features disclosed herein may be implemented with respect to web-scraping and data acquisition, and to represent data in support of data-editing and data-merging tasks. A schema may be defined with respect to a graph-based domain model.

Claims

1. A computer program product including a computer readable medium having computer program logic stored therein, the computer program logic comprising:

logic to cause a processor to analyze user-input tag data, including computer readable tags and associated tokens, corresponding to at least a portion of a first set of one or more documents, and based on the analysis, to assign tags to non-user-tagged tokens within one or more of a second portion of the first set of documents, or a second set of one or more documents;

wherein each token includes one or more computer readable elements of a corresponding document; and

wherein the computer readable tags include one or more of,

data tags to associate corresponding tokens with an entity-type of a graph-structured domain model, and

navigation tags to associate corresponding tokens with one or more document navigation actions.

2. The computer program product of claim 1, wherein the computer readable tags further include:

data tags to associate corresponding tokens with a relationship between a first entity-type and a second entity-type in the graph-structured domain model.

3. The computer program product of claim 1, wherein the navigation tags include one or more of:

a next-page link tag to associate corresponding tokens with a navigation action from a current document to another document that contains data formatted similarly to the current document;

a detail-link tag to associate corresponding tokens with a navigation action from a current document to another document that contains data formatted differently than the current document; and

a submit-form tag to associate corresponding tokens with a navigation action to another document in response to a submission of a form.

4. The computer program product of claim 1, wherein the computer program logic includes logic to cause the processor to train a scoring function to score a processor-identified sequence of computer readable tags and a corresponding sequence of processor-identified tokens, and to compute the score as a weighted sum of features of the sequence of tokens, wherein the scoring function includes at least two of:

logic to cause the processor to determine whether a portion of a document, including a current token and extending forward, matches an expression;

logic to cause the processor to determine whether a portion of the document, including the current token and extending backward, matches an expression;

logic to cause the processor to determine whether a portion of the document, including the current token and extending forward, matches a value that exists in a field of a database;

logic to cause the processor to determine whether a portion of the document, including the current token and extending backward, matches a value that exists in a field of the database; and

logic to cause the processor to determine whether the current document is enclosed within one or more of a hyper-text mark-up language (HTML) tag and a HTML style.

5. The computer program product of claim 4, wherein the logic to train the scoring function includes:

logic to cause the processor to evaluate each of a plurality of states of a Hidden Markov Model (HMM), including to weigh and evaluate a plurality of document features at each of the states, wherein each state is associated with a corresponding one of the computer readable tags.

6. The computer program product of claim 5, wherein the computer program logic further includes:

logic to cause the processor to train a first HMM with respect to document features and tag data associated with the first set of one or more documents; and

logic to cause the processor to train a second HMM in response to a change in the tag data, including to initialize a weight of a feature in the second HMM to a weight of the corresponding feature in the first HMM when a corresponding tag state exists in the first and second HMMs.

7. The computer program product of claim 4, wherein the computer program logic further includes:

logic to cause the processor to train the scoring function to correlate tagged tokens of a partially tagged document with the corresponding tags, and to suggest one or more of the tags to apply to one or more untagged tokens of the partially tagged document based on the correlation.

8. The computer program product of claim 7, wherein the computer program logic further includes:

logic to cause the processor to force the tagged tokens of the partially tagged document to align with corresponding states of a Hidden Markov Model (HMM), wherein each state is associated with a corresponding one of the computer readable tags;

logic to cause the processor to identify a highest scoring path through the HMM for the entire document when the tagged tokens are in forced alignment with the corresponding states of the HMM; and

logic to cause the processor to suggest the one or more additional tags to apply to the one or more untagged tokens of the partially tagged document based on tag states corresponding to the highest scoring path.

9. The computer program product of claim 8, wherein the computer program logic includes logic to cause the processor to train the HMM with respect to the partially tagged document and a plurality of other documents within the first set of one or more documents.

10. The computer program product of claim 4, wherein the computer program logic further includes:

logic to cause the processor to iteratively train the scoring function to assign tags to tokens of the first set of one or more source documents in accordance with the user-input tag data;

logic to cause the processor to tally mismatches between tags assigned by the scoring function and the user-input tags, at each token of the first set of one or more documents, during the training iterations; and

logic to cause the processor to generate a notification of a possible user mistagging when one or more of a number and a percentage of mismatches associated with a token during the training iterations exceeds a threshold.

11. The computer program product of claim 5, wherein the computer program logic further includes:

logic to cause the processor to compute statistics associated with a score of a parsed document, including one or more of a per-token score at each state of the HMM and a per-token overall score;

logic to cause the processor to compute statistics associated with token regions corresponding to a tag, wherein the statistics include one or more of a number of parsed tokens and a percentage of one or more of punctuation characters, hypertext mark-up language tags, numbers, and words relative to the number of parsed tokens; and

typicality logic to cause the processor to determine a typicality measurement associated with statistics of a parsed document relative to statistics of one or more parsed reference documents.

12. The computer program product of claim 11, wherein the typicality logic includes logic to cause the processor to infer a multidimensional probability distribution over the parse statistics of the one or more parsed reference documents, and to evaluate a probability of the parse statistics of the parsed document.

13. The computer program product of claim 11, wherein the computer program logic further includes logic to cause the processor to prioritize a set of untagged documents with respect to corresponding typicality measurements.

14. The computer program product of claim 11, wherein the computer program logic further includes logic to cause the processor to identify an untagged document as atypical with respect to the one or more parsed reference documents when a corresponding typicality measurement is below a threshold.

15. The computer program product of claim 14, further including logic to cause the processor to identify a source of documents as having changed when a threshold number of newly retrieved documents from the source are identified as atypical.

16. The computer program product of claim 15, further including logic to cause the processor to perform one or more of automatically repair and suggest repairs to tags of a stylistically changed source document, including to use a tagging output of a secondary Hidden Markov Model trained on content-specific features of the first set of one or more source documents, omitting layout-specific features of the first set of one or more source documents.

17. The computer program product of claim 14, further including logic to cause the processor to identify a new source of documents as substantially similar to an existing source of documents when less than a threshold number of new source documents from the new source are identified as atypical.

18. The computer program product of claim 17, wherein the computer program logic includes logic to cause the processor to parse the new source documents and to determine corresponding typicality measurements using one or more scoring functions that include content-specific features of the documents and that omit layout-specific features of the documents, including a hypertext mark-up language enclosure feature.

19. The computer program product of claim 3, wherein:

the user-input tag data includes user-specified submit form tag data corresponding to a plurality of form elements of the first set of one or more documents;

the plurality of form elements includes one or more of a data input field, a radio button, a checkbox, and a drop-down menu;

the user-specified submit form tag data includes one or more of,

a plurality of user-specified values for each of a plurality of form fields and an indication that a cross-product of the plurality of values be entered into the corresponding form fields,

a plurality of user-specified values for each of a plurality of form fields, and an indication that a portion of a cross-product of the plurality of values be entered into the corresponding form fields,

a user-specified database query to be used at runtime to produce a combination of values to enter into a plurality of form fields, and

a user-indication that values are to be provided at run time; and

the computer program logic includes logic to cause the processor to populate form fields of the second set of documents with corresponding sets of the user-specified values and to submit the corresponding forms at runtime.

20. The computer program product of claim 1, further including:

logic to cause the processor to associate each of a plurality of buckets with a corresponding domain model schema based at least in part on navigation tag data; and

classification logic to cause the processor to predict which of the plurality of buckets a document corresponds to from the navigation tags to be followed to navigate to the document.

21. The computer program product of claim 1, further including:

logic to cause the processor to associate each of a plurality of buckets with a corresponding domain model schema based at least in part on navigation tag data; and

classification logic to cause the processor to predict which of the plurality of buckets a document within the second set of one or more documents corresponds to based on features of the document, wherein the features include one or more of;

a set of one or more hypertext mark-up language (HTML) document object model (DOM) paths contained in the document,

statistics associated with text under each of the DOM paths, and

slash-delimited substrings of a universal resource locator of the document.

22. A system, comprising:

means for analyzing user-input tag data, including computer readable tags and associated tokens, corresponding to at least a portion of a first set of one or more documents; and

means for assigning the computer readable tags to tokens within one or more of a second portion of the first set of one or more documents and a second set of one or more documents based on the analysis;

wherein each token includes one or more computer readable elements of a corresponding document; and

wherein the computer readable tags include one or more of,

data tags to associate corresponding tokens with an entity-type of a graph-structured domain model, and

navigation tags to associate corresponding tokens with one or more document navigation actions.

23. A method, comprising:

analyzing user-input tag data, including computer readable tags and associated tokens, corresponding to at least a portion of a first set of one or more documents; and

assigning the computer readable tags to tokens within one or more of a second portion of the first set of one or more documents and a second set of one or more documents based on the analysis;

wherein each token includes one or more computer readable elements of a corresponding document;

wherein the computer readable tags include one or more of,

data tags to associate corresponding tokens with an entity-type of a graph-structured domain model, and

navigation tags to associate corresponding tokens with one or more document navigation actions; and

wherein the analyzing is performed within a suitably programmed computer system.

24. A computer program product including a computer readable medium having computer program logic stored therein, the computer program logic comprising:

logic to cause a processor to implement a graph-structured domain model schema having a plurality of entity types, a plurality of permissible directional relationship arcs amongst the entity types, and cardinalities associated with the relationship arcs; and

logic to cause the processor to interpret the graph-structured domain model schema as a domain grammar over sequences of tags, wherein each tag corresponds to one of an entity-type and a path between entity types in the domain model schema.

25. The computer program product of claim 24, wherein the computer program logic further includes:

logic to cause the processor to heuristically identify a sequence of grammar transformations, (G→

G′

)_i, that transforms the domain grammar to a page grammar that parses one or more user-input sequences of tags.

26. The computer program product of claim 25, wherein each of the grammar transformations (G→

G′

)_i is invertible, and wherein each corresponding inverse transformation (G′

→

G)_i is configured to undo an effect of the corresponding transformation (G→

G′

)_i with respect to grammar, and to structurally transform corresponding tagged data that is parseable in accordance with grammar G′

into data that is parseable in accordance with grammar G.

27. The computer program product of claim 26, further including:

logic to cause the processor to apply, in a reverse order, the inverse of each of the grammar transformations of the heuristically identified sequence of grammar transformations from the domain grammar to the page grammar, including to transform the page grammar to the domain grammar and to transform tagged data parsed by the page grammar into tagged data that conforms to the domain grammar and to the graph-structured domain model schema.

28. A system, comprising:

means for implementing a graph-structured domain model schema having a plurality of entity types, a plurality of permissible directional relationship arcs amongst the entity types, and cardinalities associated with the relationship arcs; and

means for interpreting the graph-structured domain model schema as a domain grammar over sequences of tags, wherein each tag corresponds to one of an entity-type and a path between entity types in the domain model schema.

29. A method, comprising:

implementing a graph-structured domain model schema having a plurality of entity types, a plurality of permissible directional relationship arcs amongst the entity types, and cardinalities associated with the relationship arcs; and

interpreting the graph-structured domain model schema as a domain grammar over sequences of tags, wherein each tag corresponds to one of an entity-type and a path between entity types in the domain model schema;

wherein the implementing and the interpreting are performed within a suitably programmed computer system.

30. A computer program product including a computer readable medium having computer program logic stored therein, the computer program logic comprising:

logic to cause a processor to enforce a graph-structured domain model schema with respect to a database, including to define named relations between entities of different entity types and to associate one of a plurality of cardinality rules with each named relation, wherein the plurality of cardinality rules include a singular cardinality constraint, a multiple cardinality constraint that allows values to accumulate over time, and a multiple cardinality constraint that does not allow values to accumulate over time.

31. The computer program product of claim 30, wherein the computer program logic further includes:

compare logic to cause the processor to determine whether first and second similarly named entities correspond to a common entity based at least in part on a cardinality constraint associated with a named relation from the first named entity to a first list of one or more other named entities, and the named relation from the second entity type to a second list of one or more other named entities.

32. The computer program product of claim 31, wherein the compare logic includes:

logic to cause the processor to determine that the first and second named entities correspond to different entities when the named relationship has a singular cardinality constraint and the first and second lists differ from one another;

logic to cause the processor to determine that the first and second named entities correspond to different entities when the named relationship has a multiple cardinality constraint that does not allow list values to accumulate, and the first and second lists differ from one another; and

logic to cause the processor to determine that the first and second named entities correspond to a common entity when the named relationship has a multiple cardinality constraint that allows list values to accumulate.

33. The computer program product of claim 31, wherein the compare logic includes logic to cause the processor to determine whether the first and second named entities correspond to a common entity based on a combination of a cardinality constraint and one or more of:

domain, system, and service policies;

domain-specific and data-specific rules; and

data object-specific and relationship-specific rules.

34. The computer program product of claim 31, wherein the computer program logic further includes:

merge logic to cause the processor to merge the first and second named entities into a logical single entity for subsequent database queries when the first and second named entities correspond to a common entity.

35. The computer program product of claim 34, wherein the merge logic includes logic to cause the processor to combine the first and second lists and to associate the single entity with the combined list through the named relation when the processor determines that the first and second entities correspond to a common entity.

36. The computer program product of claim 30, wherein the computer program logic further includes:

logic to cause the processor to receive a named entity, including one or more corresponding relations, from one or more sources and to incorporate the received named entity in the database;

logic to cause the processor to revise one or more features of the named entity in response to user-input;

logic to cause the processor to maintain an original state of the named entity and to maintain the user-initiated revision to the named entity in the database subsequent to the user-initiated revision;

logic to cause the processor to re-receive the named entity, including the one or more corresponding relations, from the one or more sources subsequent to the user-initiated revision, and to determine that the re-received named entity is redundant to the original state of the named entity.

37. The computer program product of claim 36, wherein the computer program logic includes:

multi-layer graph representation logic to cause the processor to maintain the original state of the named entity, including the one or more corresponding relations, in a first graph layer, to maintain the user-initiated revision to the named entity in a second graph layer, and to relate the first and second graph layers with aliasing objects and corresponding relations to other objects.

38. The computer program product of claim 37, wherein the multi-layer graph representation logic includes one or more of:

create node logic to cause the processor to create named entities and corresponding relations in the database;

trash logic to cause the processor to identify a named entity as deleted while maintaining a copy of the named entity in the database;

purge logic to cause the processor to permanently remove a named entity from the database;

purge batch logic to cause the processor to permanently remove all named entities associated with a batch of related data acquisition operations from the database;

merge logic to cause the processor to combine two or more named entities in the database;

unmerge logic to cause the processor to separate a previously merged entity into its constituent entities, including to segregate relationships associated with the merged entity amongst the corresponding constituent entities as if the constituent entities had not been merged.

edit literal logic to cause the processor to edit a label of a named entity in the database;

add property value logic to cause the processor to add a relation between two named entities in the database; and

delete property value logic to cause the processor to remove a relation between two named entities in the database.

39. A system, comprising:

means for enforcing a graph-structured domain model schema with respect to a database, including means for defining named relations between entities of different entity types and means for associating one of a plurality of cardinality rules with each named relation, wherein the plurality of cardinality rules include a singular cardinality constraint, a multiple cardinality constraint that allows values to accumulate over time, and a multiple cardinality constraint that does not allow values to accumulate over time.

40. A method, comprising:

enforcing a graph-structured domain model schema with respect to a database, including defining named relations between entities of different entity types and associating one of a plurality of cardinality rules with each named relation, wherein the plurality of cardinality rules include a singular cardinality constraint, a multiple cardinality constraint that allows values to accumulate over time, and a multiple cardinality constraint that does not allow values to accumulate over time;

wherein the enforcing is performed within a suitably programmed computer system.

41. A computer program product including a computer readable medium having computer program logic stored therein, the computer program logic comprising:

logic to cause a processor to acquire a data object, including one or more corresponding properties, from an information source;

logic to cause the processor to incorporate the data object into a database of data objects;

logic to cause the processor to revise one or more features associated with the data object in response to user-input, and to preserve an original state of the data object in the database; and

logic to cause the processor to re-acquire the data object, including the one or more corresponding properties, from one or more of the information source and another information source, and to determine that the re-acquired data object is redundant to the original state of the data object.

42. The computer program product of claim 41, wherein the computer program logic includes:

multi-layer graph representation logic to cause the processor to preserve the original state of the data object, including the one or more corresponding properties, in a first graph layer, to maintain the user-initiated revision to the data object in a second graph layer, and to relate the first and second graph layers with aliasing objects and corresponding relations to other objects.

43. The computer program product of claim 42, wherein the multi-layer graph representation logic includes one or more of:

create node logic to cause the processor to create nodes to represent data objects and corresponding relations in the database;

trash logic to cause the processor to identify a node as deleted while maintaining a copy of the node in the database;

purge logic to cause the processor to permanently remove a node from the database;

purge batch logic to cause the processor to permanently remove all nodes associated with a batch of related data acquisition operations from the database;

merge logic to cause the processor to combine two or more nodes in the database;

unmerge logic to cause the processor to undo a merge operation;

edit literal logic to cause the processor to edit a label of a node in the database;

add prop value logic to cause the processor to add a relation between two nodes in the database; and

delete prop value logic to cause the processor to remove a relation between two nodes in the database.

44. A system, comprising:

means for acquiring a data object, including one or more corresponding properties, from an information source;

means for incorporating the data object into a database of data objects;

means for revising one or more features associated with the data object in response to user-input, and for preserving an original state of the data object in the database; and

means for re-acquiring the data object, including the one or more corresponding properties, from one or more of the information source and another information source, and for determining that the re-acquired data object is redundant to the original state of the data object.

45. A method, comprising:

acquiring a data object, including one or more corresponding properties, from an information source;

incorporating the data object into a database of data objects;

revising one or more features associated with the data object in response to user-input, and preserving an original state of the data object in the database; and

re-acquiring the data object, including the one or more corresponding properties, from one or more of the information source and another information source, and for determining that the re-acquired data object is redundant to the original state of the data object;

wherein the acquiring, the incorporating, the revising, and the re-acquiring are performed within a suitably programmed computer system.

46. A computer program product including a computer readable medium having computer program logic stored therein, the computer program logic comprising:

graphical user interface logic to cause a processor to receive user-input graph-based domain model schema definitions and example entity type values, and to display the user-input example values within textual descriptions of cardinality rules of the domain model definitions.

47. A system, comprising:

means for receiving user-input graph-based domain model schema definitions and example entity type values; and

means for displaying the user-input example values within textual descriptions of cardinality rules of the domain model definitions.

48. A method, comprising:

receiving user-input graph-based domain model schema definitions and example entity type values; and

displaying the user-input example values within textual descriptions of cardinality rules of the domain model definitions;

wherein the receiving and the displaying are performed within a suitably programmed computer system.

49. A computer program product including a computer readable medium having computer program logic stored therein, the computer program logic comprising:

Viterbi logic to cause a processor to determine a sequence of best-predecessor states, of length equal to a number of tokens in a token sequence being parsed, for each of a plurality of states of a computational process; and

encoding logic to cause the processor to store each of the sequences of best-predecessor states in a run-length-encoded list.

50. A system, comprising:

means for determining a sequence of best-predecessor states, of length equal to a number of tokens in a token sequence being parsed, for each of a plurality of states of a computational process; and

means for storing each of the sequences of best-predecessor states in a run-length-encoded list.

51. A method, comprising:

determining a sequence of best-predecessor states, of length equal to a number of tokens in a token sequence being parsed, for each of a plurality of states of a computational process; and

storing each of the sequences of best-predecessor states in a run-length-encoded list;

wherein the determining and the storing are performed within a suitably programmed computer system.