Contextual weighting of words in a word grouping

• US 9,201,876 B1
• Filed: 05/29/2012
• Issued: 12/01/2015
• Est. Priority Date: 05/29/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, Shailesh, Chhaparia, Mahesh, Pathak, Shweta
• Primary Examiner(s): Serrou, Abdelali
• Application Number:
  US13/482,296
• Time in Patent Office: 1,281 Days
• Field of Search: 704 7- 10, 704/252, 704/256.4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 40/00 Handling natural language data speech analysis or synthesis, speech recognition G10L
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

Methods and apparatus related to contextual weighting of words. Methods are provided for determining co-occurrence relationships between words in a corpus of word groupings and for contextually weighting words in a word grouping as a function of which other words are present in the word grouping.

Claims

1. A computer implemented method of determining a co-occurrence relationship between words in a corpus of word groupings, comprising:

identifying a plurality of word pairs from a vocabulary of words;

determining, utilizing one or more processors, a co-occurrence probability for each of the word pairs in a corpus having a plurality of word groupings, each of the co-occurrence probability is based on the probability of co-occurrence of a single of the word pairs in a single of the word groupings;

wherein determining the co-occurrence probability for a word pair of the word pairs comprises determining a weighted count of the word groupings in which the word pair is present, wherein a word grouping of the word groupings in which the word pair is present is from a document, and wherein the weight of the contribution of the word grouping to the weighted count is based on at least two of frequency of occurrence, field weighting, and decorations of both words of the word pair in the document;

determining, utilizing one or more processors, a co-occurrence consistency for each of the word pairs by comparing the co-occurrence probability for each of the word pairs to an incidental occurrence probability for each of the word pairs, the incidental occurrence probability for each of the word pairs being specific to a respective of the word pairs;

creating a co-occurrence consistency matrix with the co-occurrence consistency for each of the word pairs;

receiving, by a search engine, a query submitted to the search engine by a user, the query including a word grouping having a plurality of word grouping words;

identifying, by the search engine and based on the co-occurrence consistency matrix, the co-occurrence consistency for each of a plurality of the word pairs in the word grouping words;

performing, by the search engine, a link analysis on the word grouping words utilizing the identified co-occurrence consistencies for the plurality of the word pairs in the word grouping words as weighting factors in the link analysis;

assigning, by the search engine, a contextual weight to each of a plurality of the word grouping words based on the link analysis; and

providing, by the search engine and based on the assigned contextual weights, results to the query submitted to the search engine by the user.

2. The method of claim 1, further comprising omitting certain of the word pairs from the co-occurrence consistency matrix having the co-occurrence consistency that is below a co-occurrence consistency threshold value.

3. The method of claim 1, further comprising creating a co-occurrence count matrix with the weighted count for the word pair and with counts for other of the word pairs.

4. The method of claim 3, wherein the counts for the other of the word pairs are weighted counts.

5. The method of claim 3, further comprising omitting, from the co-occurrence count matrix, certain of the word pairs having a respective of the counts that is below a co-occurrence count threshold value.

6. The method of claim 5, further comprising omitting certain of the word pairs from the co-occurrence consistency matrix having the co-occurrence consistency that is below a co-occurrence consistency threshold value.

7. The method of claim 1, wherein the step of determining the co-occurrence consistency for each of the words pairs includes comparing the co-occurrence probability of each of the word pairs to marginal probabilities of the words of each of the word pairs.

8. The method of claim 7, wherein the step of determining the co-occurrence probability for the word pair includes determining a co-occurrence total for all of the word pairs and dividing the weighted count by the co-occurrence total.

9. The method of claim 1, wherein the word groupings include at least one of tags for images, tags for videos, ad keywords, words from queries, words from documents, and words from social networking posts.

10. A system including memory and one or more processors operable to execute instructions stored in the memory, comprising instructions to:

identify a plurality of word pairs from a vocabulary of words;

determine a co-occurrence probability for each of the word pairs in a corpus having a plurality of word groupings, each of the co-occurrence probability is based on the probability of co-occurrence of a single of the word pairs in a single of the word groupings;

determine a co-occurrence consistency for each of the words pairs by comparing the co-occurrence probability for each of the word pairs to an incidental occurrence probability for each of the word pairs, the incidental occurrence probability for each of the word pairs being specific to a respective of the word pairs;

wherein the instructions to determine the co-occurrence probability for a word pair of the word pairs comprise instructions to determine a weighted count of the word groupings in which the word pair is present, wherein a word grouping of the word groupings in which the word pair is present is from a document, and wherein the weight of the contribution of the word grouping to the weighted count is based on at least two of frequency of occurrence, field weighting, and decorations of both words of the word pair in the document;

create a co-occurrence consistency matrix with the co-occurrence consistency for each of the word pairs;

receive, by a search engine of the system, a query submitted to the search engine by a user, the query including a word grouping having a plurality of word grouping words;

identify, by the search engine and based on the co-occurrence consistency matrix, the co-occurrence consistency for each of a plurality of the word pairs in the word grouping words;

perform, by the search engine, a link analysis on the word grouping words utilizing the identified co-occurrence consistencies for the plurality of the word pairs in the word grouping words as weighting factors in the link analysis;

assign, by the search engine, a contextual weight to each of a plurality of the word grouping words based on the link analysis; and

provide, by the search engine and based on the assigned contextual weights, results to the query submitted to the search engine by the user.

11. The system of claim 10, wherein the instructions further comprise instructions to omit certain of the word pairs from the co-occurrence consistency matrix having the co-occurrence consistency that is below a co-occurrence consistency threshold value.