Cooccurrence and constructions

• US 8,147,250 B2
• Filed: 04/02/2008
• Issued: 04/03/2012
• Est. Priority Date: 08/11/2003
• Status: Active Grant

• Current Assignee: Educational Testing Service
• Original Assignee: Educational Testing Service
• Inventors: Deane, Paul
• Primary Examiner(s): MOSSER, KATHLEEN MICHELE
• Application Number:
  US12/061,395
• Publication Number:
  US 20080183463A1
• Time in Patent Office: 1,462 Days
• Field of Search: 434/323, 434/350, 434/353, 704/9, 704/10
• US Class Current: 434/169
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding

Abstract

A method and system for performing automatic text analysis is described. A local ranking for one or more contexts with respect to a word and a global ranking for one or more contexts are generated. The rankings are based on the frequency with which the contexts appear in a corpus. A statistic may be generated using the local and global rankings, such as a log ratio rank statistic equal to the logarithm of the global rank divided by local rank, to measure the similarity of contexts with respect to words with which they combine. A source matrix of word to context values is then created. Singular value decomposition is used to create sub-matrices from the source matrix. Vectors from the sub-matrices corresponding to context(s) and/or word(s) are then selected to determine term-term or context-context similarity or term-context correspondence.

Claims

1. A computer-implemented method for generating an automated evaluation of a corpus by ranking contexts within which a word in said corpus appears, comprising:

for each word in said corpus, determining with a computer a local ranking for each of one or more contexts,

wherein each context comprises a word sequence located in a particular arrangement relative to the word, wherein the particular arrangement comprises a relative ordering of the word sequence and the word,

wherein the local ranking comprises an ordering based on the frequency with which each context appears with the word;

for each context, determining a global ranking;

computing with the computer a statistic for each context based on one or more of the local ranking and the global ranking;

ordering with the computer the one or more contexts based on the computed statistic for each context; and

deriving with the computer said automated evaluation from said ordered one or more ordered contexts.

2. The method of claim 1 wherein the global ranking includes an ordering based on the overall frequency of each context in the corpus.

3. The method of claim 1 wherein the computed statistic comprises a log rank ratio statistic, wherein the log rank ratio statistic for a context with respect to a word equals the logarithm of the global rank for the context divided by the local rank for the context with the word.

4. A computer-implemented method for generating an automated evaluation of a corpus by ranking contexts within which a word in said corpus appears, comprising:

for each word in a corpus, determining with a computer a local ranking for each of one or more contexts,

wherein each context comprises a word sequence located in a particular arrangement relative to the word, wherein the particular arrangement comprises a relative ordering of the word sequence and the word,

wherein the local ranking comprises an ordering based on the frequency with which each context appears with the word;

for each context, determining with the computer a global ranking;

computing with the computer a statistic for each context based on one or more of the local ranking and the global ranking;

producing with the computer a source matrix of words by contexts in which an attribute of each context is used as a value for the context-word combination; and

deriving with the computer said automated evaluation from said source matrix of words by contexts.

5. The method of claim 4 wherein the global ranking includes an ordering based on the overall frequency of each context in the corpus.

6. The method of claim 4 wherein the computed statistic comprises a log rank ratio statistic, wherein the log rank ratio statistic for a context with respect to a word equals the logarithm of the global rank for the context divided by the local rank for the context with the word.

7. The method of claim 4 wherein each value comprises a frequency for the context in the corpus.

8. The method of claim 4, further comprising:

generating a term matrix, a factor-weighting matrix and a content matrix from the source matrix.

9. The method of claim 8, further comprising:

computing term-term similarity based on a term vector for each term from the term matrix and a weight vector for each term from the factor-weighting matrix.

10. The method of claim 8, further comprising:

computing context-context similarity based on a context vector for each context from the content matrix and a weight vector for each context from the factor-weighting matrix.

11. The method of claim 8, further comprising:

computing term-context correspondence based on a term vector for the term from the term matrix, a context vector for the context from the content matrix, and a weight vector from the factor-weighting matrix.

12. A computer apparatus for producing a document evaluation by ranking contexts within which a word in a corpus appears, comprising:

a processing system; and

a memory,

wherein the processing system is configured to execute steps comprising;

for each word in a corpus, determining a local ranking for each of one or more contexts,

wherein each context comprises a word sequence located in a particular arrangement relative to the word, wherein the particular arrangement comprises a relative ordering of the word sequence and the word,

wherein the local ranking comprises an ordering based on the frequency with which each context appears with the word;

determining a global ranking for each context;

computing a statistic for each context based on one or more of the local ranking and the global ranking;

ordering the one or more contexts based on the computed statistic for each context; and

returning the ordered one or more contexts for use in automatically evaluating a written document.

13. The computer apparatus of claim 12 wherein the global ranking includes an ordering based on the overall frequency of each context in the corpus.

14. The computer apparatus of claim 12 wherein the computed statistic comprises a log rank ratio statistic, wherein the log rank ratio statistic for a context with respect to a word equals the logarithm of the global rank for the context divided by the local rank for the context with the word.

15. A computer apparatus for producing a document evaluation by ranking contexts within which a word in a corpus appears, comprising:

a processing system; and

a memory,

wherein the processing system is configured to execute steps comprising;

for each word in a corpus, determining a local ranking for each of one or more contexts,

wherein each context comprises a word sequence located in a particular arrangement relative to the word, wherein the particular arrangement comprises a relative ordering of the word sequence and the word,

wherein the local ranking comprises an ordering based on the frequency with which each context appears with the word;

determining a global ranking for each context;

computing a statistic for each context based on one or more of the local ranking and the global ranking;

producing a source matrix of words by contexts in which an attribute of each context is used as a value for the context-word combination; and

returning the source matrix for use in automatically evaluating a written document.

16. The computer apparatus of claim 15 wherein the global ranking includes an ordering based on the overall frequency of each context in the corpus.

17. The computer apparatus of claim 15 wherein the computed statistic comprises a log rank ratio statistic, wherein the log rank ratio statistic for a context with respect to a word equals the logarithm of the global rank for the context divided by the local rank for the context with the word.

18. The computer apparatus of claim 15 wherein each value comprises a frequency for the context in the corpus.

19. The computer apparatus of claim 15,

wherein the processing system is configured to generate a term matrix, a factor-weighting matrix and a content matrix from the source matrix.

20. The computer apparatus of claim 19,

wherein the processing system is configured to compute term-term similarity based on a term vector for each term from the term matrix and a weight vector for each term from the factor-weighting matrix.

21. The computer apparatus of claim 19,

wherein the processing system is configured to compute context-context similarity based on a context vector for each context from the content matrix and a weight vector for each context from the factor-weighting matrix.

22. The computer apparatus of claim 19,

wherein the processing system is configured to compute term-context correspondence based on a term vector for the term from the term matrix, a context vector for the context from the content matrix, and a weight vector from the factor-weighting matrix.

23. An article of manufacture comprising a non-transitory computer readable medium, the computer readable medium comprising instructions for generating an automated evaluation of a corpus by ranking contexts within which a word in said corpus appears, the instructions when executed causing a computer to carry out steps comprising:

for each word in said corpus, determining a local ranking for each of one or more contexts,

wherein each context comprises a word sequence located in a particular arrangement relative to the word, wherein the particular arrangement comprises a relative ordering of the word sequence and the word,

wherein the local ranking comprises an ordering based on the frequency with which each context appears with the word;

for each context, determining a global ranking;

computing a statistic for each context based on one or more of the local ranking and the global ranking;

ordering the one or more contexts based on the computed statistic for each context; and

deriving said automated evaluation from said ordered one or more ordered contexts.

24. The article of claim 23 wherein the global ranking includes an ordering based on the overall frequency of each context in the corpus.

25. The article of claim 23 wherein the computed statistic comprises a log rank ratio statistic, wherein the log rank ratio statistic for a context with respect to a word equals the logarithm of the global rank for the context divided by the local rank for the context with the word.

26. An article of manufacture comprising a non-transitory computer readable medium, the computer readable medium comprising instructions for generating an automated evaluation of a corpus by ranking contexts within which a word in said corpus appears, the instructions when executed causing a computer to carry out steps comprising:

for each word in a corpus, determining a local ranking for each of one or more contexts,

wherein each context comprises a word sequence located in a particular arrangement relative to the word, wherein the particular arrangement comprises a relative ordering of the word sequence and the word,

wherein the local ranking comprises an ordering based on the frequency with which each context appears with the word;

for each context, determining a global ranking;

computing a statistic for each context based on one or more of the local ranking and the global ranking;

producing a source matrix of words by contexts in which an attribute of each context is used as a value for the context-word combination; and

deriving said automated evaluation from said source matrix of words by contexts.

27. The article of claim 26 wherein the global ranking includes an ordering based on the overall frequency of each context in the corpus.

28. The article of claim 26 wherein the computed statistic comprises a log rank ratio statistic, wherein the log rank ratio statistic for a context with respect to a word equals the logarithm of the global rank for the context divided by the local rank for the context with the word.

29. The article of claim 26 wherein each value comprises a frequency for the context in the corpus.

30. The article of claim 26, the instructions when executed causing the computer to generate a term matrix, a factor-weighting matrix and a content matrix from the source matrix.

31. The article of claim 30, the instructions when executed causing the computer to compute term-term similarity based on a term vector for each term from the term matrix and a weight vector for each term from the factor-weighting matrix.

32. The article of claim 30, the instructions when executed causing the computer to compute context-context similarity based on a context vector for each context from the content matrix and a weight vector for each context from the factor-weighting matrix.

33. The article of claim 30, the instructions when executed causing the computer to compute term-context correspondence based on a term vector for the term from the term matrix, a context vector for the context from the content matrix, and a weight vector from the factor-weighting matrix.