Systems and Methods for Determining Lexical Associations Among Words in a Corpus

• US 20150347385A1
• Filed: 06/01/2015
• Published: 12/03/2015
• Est. Priority Date: 05/30/2014
• Status: Active Grant

• Current Assignee: Educational Testing Service
• Original Assignee: Educational Testing Service
• Inventors: Flor, Michael, Beigman Klebanov, Beata
• Granted Patent: US 9,519,634 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Systems and methods are provided for identifying one or more target words of a corpus that have a lexical relationship to a plurality of provided cue words. The cue words and statistical lexical information derived from a corpus of documents are analyzed to determine candidate words that have a lexical association with the cue words. The statistical information includes numerical values indicative of probabilities of word pairs appearing together as adjacent words in a well-formed text or appearing together within a paragraph of a well-formed text. For each candidate word, a statistical association score between the candidate word and each of the cue words is determined. An aggregate score for each of the candidate words is determined based on the statistical association scores. One or more of the candidate words are selected to be the one or more target words based on the aggregate scores.

Claims

1. A computer-implemented method of identifying one or more target words of a corpus that have a lexical relationship to a plurality of provided cue words, the method comprising:

receiving a plurality of cue words;

analyzing the cue words and statistical lexical information derived from a corpus of documents with a processing system to determine candidate words that have a lexical association with the cue words, the statistical information including numerical values indicative of probabilities of word pairs appearing together as adjacent words in a well-formed text or appearing together within a paragraph of a well-formed text;

for each candidate word,

determining, using the processing system, a statistical association score between the candidate word and each of the cue words using numerical values included in the statistical information, and

generating, using the processing system, an aggregate score for each of the candidate words based on the statistical association scores; and

selecting one or more of the candidate words to be the one or more target words based on the aggregate scores of the candidate words.

2. The computer-implemented method of claim 1 comprising:

processing each cue word with the processing system to determine one or more inflectional variants of the cue word, wherein the determining of the candidate words that have a lexical association with the cue words further includes analyzing the inflectional variants and the statistical lexical information with the processing system, wherein the statistical lexical information is included in a dataset or database, and wherein the determining of the candidate words includes searching the cue words and the inflectional variants across entries of the dataset or database.

3. The computer-implemented method of claim 1, wherein the numerical value is a frequency count, the frequency count indicating a number of times that a word pair appears together as adjacent words in the corpus or a number of times that a word pair appears together within respective paragraphs of the corpus.

4. The computer-implemented method of claim 3, wherein a statistical association score is determined by processing with the processing system a frequency count.

5. The computer-implemented method of claim 1, wherein the statistical lexical information is included in a dataset or database that comprises:

a plurality of first entries containing bigram data, each first entry including (i) a sequence of two English words, and (ii) an associated numerical value, the numerical value indicating a probability of the sequence appearing in a well-formed text, and

a plurality of second entries containing co-occurrence data, each second entry including (i) first and second English words, and (ii) an associated numerical value, the numerical value indicating a probability of the first and second English words appearing together within a paragraph in a well-formed text.

6. The computer-implemented method of claim 5,

wherein the numerical values of the first entries are first frequency counts, each first frequency count indicating a number of times that the sequence appears in the corpus;

and

wherein the numerical values of the second entries are second frequency counts, each second frequency count indicating a number of times that the first and second English words appear together within respective paragraphs of the corpus.

7. The computer-implemented method of claim 1 comprising:

processing the corpus with the processing system to generate a database or dataset including the statistical lexical information, the processing including;

parsing the corpus with the processing system to identify a plurality of tokens included in the corpus, each token being (i) an individual word, (ii) a punctuation mark, or (iii) a digit-based number of the corpus;

converting with the processing system all tokens comprising digit-based numbers to a uniform token; and

processing the plurality of tokens with the processing system to determine the entries of the database or dataset.

8. The computer-implemented method of claim 1, wherein the generating of the aggregate score comprises summing the statistical association scores between the candidate word and each of the cue words, the sum being the aggregate score.

9. The computer-implemented method of claim 1, wherein the generating of the aggregate score comprises:

for each cue word, generating a ranked list of candidate words, each candidate word of the list (i) being ranked based on its association score with the cue word, and (ii) being associated with a rank value based on its order in the list; and

for each candidate word, multiplying the rank values associated with the candidate word to generate a product, the product being the aggregate score for the candidate word.

10. The computer-implemented method of claim 1, wherein the determining of a statistical association score between a candidate word and a cue word comprises:

determining a Pointwise Mutual Information (PMI) value for the candidate word and the cue word, the PMI value being the statistical association score between the candidate word and the cue word, and the determining of the PMI value comprising;

determining a probability p(A, B) of the candidate word and the cue word (i) appearing together as adjacent words in a well-formed text, or (ii) appearing together within a paragraph of a well-formed text, the probability p(A, B) determined using the statistical information;

determining probabilities p(A) and p(B) of candidate word and the cue word, respectively, appearing in a well-formed text using the statistical information; and

determining the PMI value for the candidate word and the cue word based on

11. The computer-implemented method of claim 1, wherein the determining of a statistical association score between a candidate word and a cue word comprises:

determining a Normalized Pointwise Mutual Information (NPMI) value for the candidate word and the cue word, the NPMI value being the statistical association score between the candidate word and the cue word, and the determining of the NPMI value comprising;

determining a probability p(A, B) of the candidate word and the cue word (i) appearing together as adjacent words in a well-formed text, or (ii) appearing together within a paragraph of a well-formed text, the probability p(A, B) determined using the statistical information;

determining probabilities p(A) and p(B) of candidate word and the cue word, respectively, appearing in a well-formed text using the statistical information; and

determining the NPMI value for the candidate word and the cue word based on

12. The computer-implemented method of claim 1, wherein the determining of a statistical association score between a candidate word and a cue word comprises:

determining a simplified log-likelihood (SLL) value for the candidate word and the cue word, the SLL value being the statistical association score between the candidate word and the cue word, and the determining of the SLL value comprising;

determining a probability p(A, B) of the candidate word and the cue word (i) appearing together as adjacent words in a well-formed text, or (ii) appearing together within a paragraph of a well-formed text, the probability p(A, B) determined using the statistical information;

determining probabilities p(A) and p(B) of the candidate word and the cue word, respectively, appearing in a well-formed text using the statistical information; and

determining the SLL value for the candidate word and the cue word based on

13. The computer-implemented method of claim 1 comprising:

determining if the plurality of cue words includes a stop word; and

based on a determination that the plurality of cue words does not include a stop word, removing candidate words that are stop words.

14. The computer-implemented method of claim 1 comprising:

processing the selected one or more target words with the processing system to determine one or more inflectional variants for each of the one or more target words, wherein the one or more target words and the inflectional variants thereof are returned in response to a query that includes the plurality of cue words.

15. The computer-implemented method of claim 1, wherein one or more of the statistical association scores is a maximum statistical association score between a candidate word and a cue word, the maximum statistical association score being selected from a plurality of determined statistical association scores between the candidate word and the cue word.

16. A system for identifying one or more target words of a corpus that have a lexical relationship to a plurality of provided cue words, the system comprising:

a processing system; and

computer-readable memory in communication with the processing system encoded with instructions for commanding the processing system to execute steps comprising;

receiving a plurality of cue words;

analyzing the cue words and statistical lexical information derived from a corpus of documents to determine candidate words that have a lexical association with the cue words, the statistical information including numerical values indicative of probabilities of word pairs appearing together as adjacent words in a well-formed text or appearing together within a paragraph of a well-formed text;

for each candidate word,

determining a statistical association score between the candidate word and each of the cue words using numerical values included in the statistical information, and

generating an aggregate score for each of the candidate words based on the statistical association scores; and

selecting one or more of the candidate words to be the one or more target words based on the aggregate scores of the candidate words.

17. The system of claim 16, wherein the instructions command the processing system to process each cue word with the processing system to determine one or more inflectional variants of the cue word, wherein the determining of the candidate words that have a lexical association with the cue words further includes analyzing the inflectional variants and the statistical lexical information with the processing system, wherein the statistical lexical information is included in a dataset or database, and wherein the determining of the candidate words includes searching the cue words and the inflectional variants across entries of the dataset or database.

18. The system of claim 16, wherein the numerical value is a frequency count, the frequency count indicating a number of times that a word pair appears together as adjacent words in the corpus or a number of times that a word pair appears together within respective paragraphs of the corpus.

19. A non-transitory computer-readable storage medium for identifying one or more target words of a corpus that have a lexical relationship to a plurality of provided cue words, the computer-readable storage medium comprising computer executable instructions which, when executed, cause a processing system to execute steps comprising:

receiving a plurality of cue words;

analyzing the cue words and statistical lexical information derived from a corpus of documents to determine candidate words that have a lexical association with the cue words, the statistical information including numerical values indicative of probabilities of word pairs appearing together as adjacent words in a well-formed text or appearing together within a paragraph of a well-formed text;

for each candidate word,

determining a statistical association score between the candidate word and each of the cue words using numerical values included in the statistical information, and

generating an aggregate score for each of the candidate words based on the statistical association scores; and

selecting one or more of the candidate words to be the one or more target words based on the aggregate scores of the candidate words.

20. The non-transitory computer-readable storage medium of claim 19, wherein the instructions command the processing system to process each cue word with the processing system to determine one or more inflectional variants of the cue word, wherein the determining of the candidate words that have a lexical association with the cue words further includes analyzing the inflectional variants and the statistical lexical information with the processing system, wherein the statistical lexical information is included in a dataset or database, and wherein the determining of the candidate words includes searching the cue words and the inflectional variants across entries of the dataset or database.

21. The non-transitory computer-readable storage medium of claim 19, wherein the numerical value is a frequency count, the frequency count indicating a number of times that a word pair appears together as adjacent words in the corpus or a number of times that a word pair appears together within respective paragraphs of the corpus.

22. A computer-implemented method of identifying one or more target n-grams of a corpus that have a lexical relationship to a plurality of provided cue words, the method comprising:

receiving a plurality of cue words;

analyzing the cue words and statistical lexical information derived from a corpus of documents with a processing system to determine candidate n-grams that have a lexical association with the cue words, the statistical information including numerical values indicative of probabilities of multiple words appearing together as adjacent words in text of the corpus or appearing together within a paragraph of text in the corpus;

for each candidate n-gram,

determining, using the processing system, a statistical association score between the candidate n-gram and each of the cue words using numerical values of the dataset, and

generating, using the processing system, an aggregate score for each of the candidate n-grams based on the statistical association scores; and

selecting one or more of the candidate n-grams to be the one or more target n-grams based on the aggregate scores of the candidate n-grams.

23. A system comprising a processing system and computer-readable memory in communication with the processing system, the computer-readable memory being encoded with instructions for commanding the processing system to execute the method of claim 22.

24. A non-transitory computer-readable storage medium comprising computer executable instructions which, when executed, cause a processing system to execute the method of claim 22.