Accessing documents using predictive word sequences

• US 9,069,842 B2
• Filed: 09/28/2010
• Issued: 06/30/2015
• Est. Priority Date: 09/28/2010
• Status: Active Grant

• Current Assignee: Mitre Corporation
• Original Assignee: Mitre Corporation
• Inventors: MELBY, Paul Christian
• Primary Examiner(s): Vital, Pierre
• Assistant Examiner(s): LODHI, ANDALIB FT
• Application Number:
  US12/892,637
• Publication Number:
  US 20120078883A1
• Time in Patent Office: 1,736 Days
• Field of Search: 707/722, 707/750, 707/769, 707/776
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

Methods and systems for accessing documents in document collections using predictive word sequences are disclosed. A method for accessing documents using predictive word sequences include creating a candidate list of word sequences where respective ones of the word sequences comprise one or more elements derived from the document corpus; expanding the candidate list by adding one or more new word sequences, where each new pattern is created by combining one or more elements derived from the document corpus with one of the word sequences currently in the candidate list; determining a predictive power with respect to the subject for respective ones of entries of the candidate list, where the entries include the word sequences and the new word sequences; pruning from the candidate list ones of said entries with the determined predictive power less than a predetermined threshold; and accessing documents from the document corpus based on the pruned candidate list. The expanding of the candidate list can include creating each new pattern as a gapped sequence, where the gapped sequence comprises one of the word sequences and one of said elements separated by zero or more words. Corresponding system and computer readable media embodiments are also disclosed.

Claims

1. A method for accessing documents related to a subject from a document corpus, comprising:

categorizing documents from the document corpus based on one or more subjects;

creating a candidate list of word sequences, wherein respective ones of the word sequences comprise one or more elements derived from the document corpus;

expanding the candidate list by adding one or more new word patterns, wherein each new pattern comprises a gapped sequence created by combining one or more elements derived from the document corpus with one of said word sequences;

determining a predictive power with respect to the subject for respective ones of entries of the candidate list, wherein the entries comprise said word sequences and said new word patterns;

pruning from the candidate list ones of said entries with the determined predictive power less than a predetermined threshold, wherein the predictive power comprises a measure of information gain, and wherein the pruning further comprises pruning from the candidate list ones of said entries with a frequency of occurrence less than a predetermined frequency threshold;

accessing documents from the document corpus based on the pruned candidate list;

updating the categorization of documents based on the accessing; and

iteratively performing the expanding, the determining the predictive power, and the pruning, for increasing entry lengths until at least one of the entries is of a predetermined length.

2. The method of claim 1, wherein the gapped sequence comprises one of the word sequences and one of said elements separated by zero or more words.

3. The method of claim 2, wherein a maximum length of the gapped sequence is predetermined.

4. The method of claim 2, wherein the creating said each new pattern as a gapped sequence includes:

creating a first new pattern by pre-pending one of the word sequences with a first element from the document corpus; and

creating a second new pattern by appending one of the word sequences with the first element.

5. The method of claim 2, wherein the gapped sequence comprises one of the word sequences and a word from the document corpus separated by zero or more words.

6. The method of claim 1, further comprising:

iteratively performing the expanding, the determining the predictive power, and the pruning, until at least one of the entries is of a maximum length.

7. The method of claim 1, further comprising:

iteratively performing the expanding, the determining the predictive power, and the pruning, until at least one of the entries is of a predetermined length.

8. The method of claim 1, further comprising:

creating an initial list of elements including words or phrases.

9. The method of claim 8, wherein the creating the initial list comprises:

determining a set of phrases including words or phrases from the document corpus; and

adding each of said phrases as one of said elements in the initial list.

10. The method of claim 9, wherein the set of phrases comprises substantially all unique words contained in the document corpus.

11. The method of claim 9, wherein the creating the initial list further comprises:

adding, to the initial list, one or more of synonyms, stopwords or stemmed words for respective ones of said phrases.

12. The method of claim 9, wherein the creating the initial list further comprises:

pruning, from the initial list, phrases having a frequency of occurrence in the document corpus which is less than a predetermined frequency threshold.

13. The method of claim 1, further comprising:

accessing the document corpus;

determining positive labeled documents with respect to the subject in the document corpus; and

calculating, for respective one of said word sequences, the predictive power based upon a presence of the respective entry in the positive labeled documents.

14. The method of claim 1, wherein the creating the candidate list comprises:

determining the predictive power of respective ones of the word sequences; and

pruning from the candidate list ones of said word sequences with the determined predictive power less than a predetermined threshold.

15. The method of claim 1, further comprising:

pruning, from the candidate list, said entries having a frequency of occurrence in the document corpus which is less than a predetermined frequency threshold.

16. The method of claim 1, the accessing further comprising:

removing, from the pruned candidate list, said entries having a precision less than a predetermined precision threshold.

17. The method of claim 1, the accessing comprising:

sorting the pruned candidate list based on a precision-weighted F-measure;

iteratively adding the entries of the sorted candidate list to a search list until the recall of the search list exceeds a predetermined target recall; and

accessing documents from the document corpus based upon the search list.

18. The method of claim 1, wherein the pruning further comprises pruning from the candidate list ones of said entries with a frequency of occurrence less than a predetermined frequency threshold, and the method further comprising:

iteratively performing the expanding, the determining the predictive power, and the pruning, for increasing entry lengths until at least one of the entries is of a predetermined length.

19. A system for accessing documents related to a subject from a document corpus, comprising:

at least one processor;

at least one memory coupled to the processor and configured to store a candidate list of word sequences; and

a word sequence determining and document accessing module implemented on the at least one processor, including;

a document classifier configured to categorize documents from the document corpus based on one or more subjects;

a word sequence generator configured to;

create a candidate list of word sequences, wherein respective ones of the word sequences comprise one or more elements derived from the document corpus;

expand the candidate list by adding one or more new word patterns, wherein each new pattern comprises a gapped sequence created by combining one or more elements derived from the document corpus with one of said word sequences;

determine a predictive power with respect to the subject for respective ones of entries of the candidate list, wherein the entries comprise said word sequences and said new word patterns;

prune from the candidate list ones of said entries with the determined predictive power less than a predetermined threshold, wherein the predictive power comprises a measure of information gain, and wherein the pruning further comprises pruning from the candidate list ones of said entries with a frequency of occurrence less than a predetermined frequency threshold; and

iteratively performing the expanding, the determining the predictive power, and the pruning, for increasing entry lengths until at least one of the entries is of a predetermined length,

wherein the document classifier is further configured to;

access the document corpus based on the pruned candidate list; and

update the categorization of documents based on the accessing.

20. The system of claim 19, wherein the

document classifier is further configured to:

determine positive labeled documents with respect to the subject in the document corpus; and

calculate, for respective one of said word sequences, the predictive power based upon a presence of the respective entry in the positive labeled documents; and

wherein the word sequence determining and document accessing module further comprises a report locator configured to find documents in the document corpus using the candidate list.

21. A computer readable media storing instructions, wherein said instructions when executed are adapted to access documents related to a subject from a document corpus with a method comprising:

categorizing documents from the document corpus based on one or more subjects;

creating a candidate list of word sequences, wherein respective ones of the word sequences comprise one or more elements derived from the document corpus;

expanding the candidate list by adding one or more new word patterns, wherein each new pattern comprises a gapped sequence created by combining one or more elements derived from the document corpus with one of said word sequences;

determining a predictive power with respect to the subject for respective ones of entries of the candidate list, wherein the entries comprise said word sequences and said new word patterns;

pruning from the candidate list ones of said entries with the determined predictive power less than a predetermined threshold, wherein the predictive power comprises a measure of information gain, and wherein the pruning further comprises pruning from the candidate list ones of said entries with a frequency of occurrence less than a predetermined frequency threshold;

accessing documents from the document corpus based on the pruned candidate list;

updating the categorization of documents based on the accessing; and

iteratively performing the expanding, the determining the predictive power, and the pruning, for increasing entry lengths until at least one of the entries is of a predetermined length.