Method and apparatus for the automated construction of models of activities from textual descriptions of the activities

• US 20080294398A1
• Filed: 05/25/2007
• Published: 11/27/2008
• Est. Priority Date: 05/25/2007
• Status: Abandoned Application

• Current Assignee: Justsystems Evans Research Incorporated
• Original Assignee: Justsystems Evans Research Incorporated
• Inventors: Evans, David A., Qu, Yan, Goldin, Ilya M.
• Application Number:
  US11/807,007
• Publication Number:
  US 20080294398A1
• Time in Patent Office: Days
• US Class Current: 703/6
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A method of automatically constructing a model of an activity from an unsupervised examination of a plurality of textual documents describing the activity is comprised of: extracting prototypical steps from the plurality of textual documents; sequencing the extracted steps; aligning the sequenced steps; and constructing the model based on the aligned steps. The model may take the form of a step vs. position matrix which identifies the prototypical steps that make up the activity and provides the probability of each step occupying each position within the activity. The model thus constitutes common sense knowledge that encodes the stereotypical steps of an activity and the stereotypical sequencing of the steps.

Claims

1. A method of operating on a plurality of textual documents discussing an activity, comprising:

extracting prototypical steps of an activity from said plurality of textual documents;

sequencing the extracted steps;

aligning the sequenced steps; and

storing the aligned steps.

2. The method of claim 1 wherein said extracting comprises:

partitioning each of a plurality of textual documents into candidate prototypical steps;

clustering said candidate prototypical steps; and

selecting clusters that cover more than one document.

4. The method of claim 2 additionally comprising labeling said steps within each of said selected clusters.

5. The method of claim 4 wherein said labeling comprises labeling said steps within each of said selected clusters with either a label containing the most frequently used words in each of said selected clusters or an arbitrary label.

6. The method of claim 1 additionally comprising collecting a plurality of textual documents.

7. The method of claim 6 wherein said collecting comprises:

retrieving a first plurality of documents;

building a classifier from said retrieved documents;

retrieving a second plurality of documents;

applying said classifier to said second plurality of documents; and

adding certain of said second plurality of documents to a corpus of textual documents based on said applying.

8. The method of claim 1 additionally comprising constructing a model of the activity based on said stored, aligned steps.

9. The method of claim 8 wherein said constructing a model comprises constructing a step vs. position matrix where each cell in the matrix represents a probability of observing a certain step at a particular location.

3. The method of claim 3 wherein said candidate prototypical steps are selected from the group consisting of words, phrases, sentences, or other semantic units.

10. A method of constructing a model of an activity by operating on a plurality of textual documents discussing the activity, comprising:

extracting prototypical steps of the activity from said plurality of textual documents;

sequencing the extracted steps;

aligning the sequenced steps so as to define a global step alignment;

constructing a model based on said aligned steps; and

saving said model.

11. The method of claim 10 wherein said model is a step vs. position matrix where each cell in the matrix represents a probability of observing a certain step at a particular location in the global alignment of steps.

12. The method of claim 10 wherein said extracting comprises:

partitioning each of a plurality of textual documents into candidate prototypical steps;

clustering said candidate prototypical steps; and

selecting clusters that cover more than one document and that are of a predetermined size.

13. The method of claim 12 wherein said candidate prototypical steps are selected from the group consisting of words, phrases, sentences, or other semantic units.

14. The method of claim 12 additionally comprising labeling said steps within each of said selected clusters.

15. The method of claim 14 wherein said labeling comprises labeling said steps within each of said selected clusters with either a label containing the most frequently used words in each of said selected clusters or an arbitrary label.

16. The method of claim 10 additionally comprising collecting a plurality of textual documents.

17. The method of claim 16 wherein said collecting comprises:

retrieving a first plurality of documents;

building a classifier from said retrieved documents;

retrieving a second plurality of documents;

applying said classifier to said second plurality of documents; and

adding certain of said second plurality of documents to a corpus of textual documents based on said applying.

18. A computer readable medium carrying a model of an activity wherein said model comprises data identifying each step in an activity and a plurality of probabilities for each step representing the likelihoods of that step occupying locations in the global alignment of steps.

19. A computer readable medium carrying a set of instructions which, when executed, perform a method of operating on a plurality of textual documents discussing an activity, comprising:

extracting prototypical steps of an activity from said plurality of textual documents;

sequencing the extracted steps;

aligning the sequenced steps; and

storing the aligned steps.

20. A computer readable medium carrying a set of instructions which, when executed, perform a method of constructing a model of an activity by operating on a plurality of textual documents discussing the activity, comprising:

extracting prototypical steps of the activity from said plurality of textual documents;

sequencing the extracted steps;

aligning the sequenced steps so as to define a global step alignment;

constructing a model based on said aligned steps; and

saving said model.