Acquisition of semantic class lexicons for query tagging

• US 9,336,299 B2
• Filed: 04/20/2009
• Issued: 05/10/2016
• Est. Priority Date: 04/20/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hoffmann, Raphael Dominik, Wang, Ye-Yi, Li, Xiao
• Primary Examiner(s): Zhen, Wei
• Assistant Examiner(s): HUDA, MOHAMMED NURUL
• Application Number:
  US12/426,370
• Publication Number:
  US 20100268725A1
• Time in Patent Office: 2,577 Days
• Field of Search: 707/4, 707/740, 707/5, 705/2, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A user'"'"'s search experience may be enhanced by providing additional content based upon an understanding of the user'"'"'s intent. Query tagging, the assigning of semantic labels to terms within a query, is one technique that may be utilized to determine the context of a user'"'"'s search query. Accordingly, as provided herein, a query tagging model may be updated using one or more stratified lexicons. A list data structure (e.g., lists of phrases obtained from web pages) and seed distribution data (e.g., pre-labeled probability data) may be used by a graph learning technique to obtain an expanded set of phrases and their respective probabilities of corresponding with particular lexicons (e.g., semantic class lexicons). The expanded set of phrases may be used to group phrases into stratified lexicons. The stratified lexicons may be used as features for updating and/or executing the query tagging model.

Claims

1. A method performed by a computing device, the method comprising:

creating seed distribution data comprising a seed phrase and associated seed probabilities that the seed phrase corresponds to a plurality of different lexicons having associated meanings, the seed probabilities including at least;

a first seed probability assigned to the seed phrase, the first seed probability indicative of a first likelihood that the seed phrase corresponds to a first lexicon associated with a first meaning of the seed phrase, and

a second seed probability assigned to the seed phrase, the second seed probability indicative of a second likelihood that the seed phrase corresponds to a second lexicon associated with a second meaning of the seed phrase, the first seed probability different than the second seed probability, the first lexicon different than the second lexicon; and

identifying, from a plurality of web documents, a set of lists of phrases that include the seed phrase as well as other phrases; and

based at least on the seed probabilities, determining other probabilities that the other phrases correspond to the plurality of different lexicons having the associated meanings.

2. The method of claim 1, further comprising:

performing a first filtering of the set of lists of phrases by removing certain lists from the set based at least upon a number of phrases occurring within respective lists; and

performing a second filtering of the set of lists of phrases by removing further lists from the set based at least upon respective lengths of phrases occurring within respective lists,

wherein the other probabilities are determined after the first filtering and after the second filtering.

3. The method of claim 1, further comprising:

obtaining a set of labeled training data having different semantic labels for the seed phrase, including a first instance of training data labeling the seed phrase with the first meaning and a second instance of training data labeling the seed phrase with the second meaning,

wherein the creating the seed distribution data is performed using the set of labeled training data.

4. The method of claim 1, further comprising:

creating a sub-graph representing appearances of the seed phrase and the other phrases in different lists from the set of lists; and

assigning list probabilities to individual lists in the sub-graph that include the seed phrase based at least on the seed probabilities,

wherein the other probabilities are determined based upon the list probabilities.

5. The method of claim 1, further comprising:

grouping a first set of phrases into a first stratified lexicon and a second set of phrases into a second stratified lexicon, respective first phrases within the first stratified lexicon comprising first lexicon probabilities within a first predefined range and respective second phrases within the second stratified lexicon comprising second lexicon probabilities within a second predefined range of relatively lower lexicon probabilities than the first predefined range.

6. The method of claim 1, further comprising:

updating a query tagging model based at least in part upon the other probabilities that the other phrases correspond to the plurality of different lexicons having the associated semantic classes.

7. The method of claim 6, further comprising:

executing the query tagging model upon a query to label a term within the query.

8. A computing device comprising:

at least one processing unit; and

at least one memory storing instructions which, when executed by the at least one processing unit, cause the at least one processing unit to;

identify a first seed phrase and associated first seed probabilities that the first seed phrase corresponds to a plurality of different semantic meanings;

identify a second seed phrase and associated second seed probabilities that the second seed phrase corresponds to the plurality of different semantic meanings;

identify, from a plurality of web documents, first lists of phrases that include the first seed phrase as well as first other phrases;

identify, from the plurality of web documents, second lists of phrases that include the second seed phrase as well as second other phrases;

based at least on the first seed probabilities, determine first other probabilities that the first other phrases correspond to the plurality of different semantic meanings; and

based at least on the second seed probabilities, determine second other probabilities that the second other phrases correspond to the plurality of different semantic meanings.

9. The computing device of claim 8, wherein the first seed phrase is the word “

orange” and

the first seed probabilities include an individual first seed probability that the word “

orange”

means a type of fruit and another individual first seed probability that the word “

orange”

means a particular color.

10. The computing device of claim 9, wherein the word “

orange”

is assigned a relatively higher probability of meaning the type of fruit than of meaning the particular color.

11. The computing device of claim 10, wherein the second seed phrase is the word “

electronic” and

the second seed probabilities include an individual second seed probability that the word “

electronic”

refers to music and another individual second seed probability that the word “

electronic”

refers to a particular type.

12. The computing device of claim 11, wherein the word “

electronic”

is assigned a relatively higher probability of referring to the particular type than of referring to music.

13. The computing device of claim 8, wherein the web documents comprise HyperText Markup Language (HTML).

14. A computing device comprising:

at least one processing unit; and

at least one memory storing instructions which, when executed by the at least one processing unit, cause the at least one processing unit to;

identify seed probabilities that a seed phrase belongs to different semantic classes, the seed probabilities including at least;

a first seed probability that the seed phrase belongs to a first semantic class, and

a second seed probability that the seed phrase belongs to a second semantic class that is different than the first semantic class;

identify, from a plurality of web documents, phrase lists that include the seed phrase as well as other phrases; and

based at least on the seed probabilities, determine other probabilities that the other phrases included in the phrase lists belong to the different semantic classes, including at least first other probabilities that the other phrases belong to the first semantic class and second other probabilities that the other phrases belong to the second semantic class.

15. The computing device of claim 14, wherein the instructions, when executed by the at least one processing unit, cause the at least one processing unit to:

obtain training data having labeled instances of the seed phrase, including first instances where the seed phrase is labeled as belonging to the first semantic class and second instances where the seed phrase is labeled as belonging to the second semantic class;

determine a first number of times the seed phrase is labeled in the training data as belonging to the first semantic class;

determine a second number of times the seed phrase is labeled in the training data as belonging to the second semantic class;

calculate the first seed probability based at least on the first number of times the seed phrase is labeled in the training data as belonging to the first semantic class; and

calculate the second seed probability based at least on the second number of times the seed phrase is labeled in the training data as belonging to the second semantic class.

16. The computing device of claim 15, wherein the other phrases lack corresponding seed probabilities derived from the training data.

17. The computing device of claim 16, wherein the other phrases do not appear in the training data.

18. The computing device of claim 14, wherein the instructions, when executed by the at least one processing unit, cause the at least one processing unit to:

identify an individual phrase list that includes the seed phrase as well as another seed phrase having other seed probabilities that the another seed phrase corresponds to the different semantic classes; and

determine an individual phrase list probability distribution for the individual phrase list based at least on the seed probabilities and the other seed probabilities, the individual phrase list probability distribution reflecting respective probabilities that individual phrases included in the individual phrase list correspond to the different semantic classes.

19. The computing device of claim 14, wherein the instructions, when executed by the at least one processing unit, cause the at least one processing unit to:

identify an individual phrase that appears in both the individual phrase list and another individual phrase list having another individual phrase list probability distribution reflecting respective probabilities that other phrases included in the another individual phrase list correspond to the different semantic classes; and

determine an individual phrase probability distribution for the individual phrase based at least on the individual phrase list probability distribution and the another individual phrase list probability distribution.

20. The computing device of claim 19, wherein the seed phrase also appears in the another individual phrase list.

21. The computing device of claim 19, wherein the instructions, when executed by the at least one processing unit, cause the at least one processing unit to:

based on the individual phrase probability distribution for the individual phrase, update a query tagging model that tags queries that include the individual phrase according to the different semantic classes.