ACQUISITION OF SEMANTIC CLASS LEXICONS FOR QUERY TAGGING

• US 20100268725A1
• Filed: 04/20/2009
• Published: 10/21/2010
• Est. Priority Date: 04/20/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hoffmann, Raphael D., Wang, Ye-Yi, Li, Xiao
• Granted Patent: US 9,336,299 B2
• Time in Patent Office: Days
• US Class Current: 707/765
• 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 for updating a query tagging model using one or more stratified lexicons comprising:

creating a list data structure comprising a set of lists, wherein a list comprises one or more phrases;

creating seed distribution data comprising one or more phrases, wherein a phrase comprises a lexicon probability distribution;

creating a sub-graph based upon the list data structure and the seed distribution data;

executing a graph learning technique upon the sub-graph to create an expanded set of phrases, wherein a phrase comprises an updated lexicon probability distribution;

creating one or more stratified lexicons based upon the expanded set of phrases; and

updating a query tagging model using the one or more stratified lexicons as lexicon features.

2. The method of claim 1, the creating a list data structure comprising:

obtaining a set of HTML lists from one or more web resources;

filtering the set of HTML lists based upon a number of phrases occurring within a particular list within a predefined range;

filtering the set of HTML lists based upon a maximum length of phrases occurring within a particular HTML list; and

creating the set of lists from the filtered set of HTML lists.

3. The method of claim 1, the creating seed distribution data comprising:

for particular phrases within the seed distribution data, assigning a probability to one or more lexicons based upon a set of labeled training data, wherein the probability corresponds to the probability the phrase relates to the particular lexicon.

4. The method of claim 1, the creating a sub-graph comprising:

labeling one or more phrases within the list data structure with a corresponding lexicon probability distribution based upon the seed distribution data;

removing one or more lists from the list data structure having a number of phrases labeled with a lexicon probability distribution below a predetermined threshold;

removing one or more phrases from the list data structure occurring within one or more lists at a frequency below a predetermined threshold.

5. The method of claim 1, the executing a graph learning technique comprising, iteratively:

for particular lists within the sub-graph, assigning a list lexicon probability distribution to a particular list based upon lexicon probability distributions of phrases comprised within the list; and

for particular phrases within the sub-graph, assigning an updated lexicon probability distribution to a particular phrase based upon list lexicon probability distributions of lists comprising the phrase.

6. The method of claim 1, the creating one or more stratified lexicons comprising:

grouping a set of phrases within the expanded set of phrases into a stratified lexicon, wherein respective phrases within the set of phrases comprise updated lexicon probabilities within a predefined range; and

associating the stratified lexicon with a corresponding lexicon.

7. The method of claim 1, wherein the query tagging model is a conditional random fields tagging model.

8. The method of claim 1, comprising:

executing the query tagging model upon a query to label one or more terms within the query.

9. The method of claim 8, the executing the query tagging model comprising:

receiving the query comprising one or more terms; and

for respective terms within the query, assigning one or more labels to a term based upon an occurrence of the one or more terms within a stratified lexicon of a corresponding lexicon.

10. A system for updating a query tagging model using one or more stratified lexicons comprising:

a list data structure constructor configured to create a list data structure comprising a set of lists, wherein a list comprises one or more phrases;

a seed distribution constructor configured to create seed distribution data comprising one or more phrases, wherein a phrase comprises a lexicon probability distribution;

a sub-graph constructor configured to create a sub-graph based upon the list data structure and the seed distribution data;

a graph learning component configured to execute a graph learning technique upon the sub-graph to create an expanded set of phrases, wherein a phrase comprises an updated lexicon probability distribution;

a stratified lexicon constructor configured to create one or more stratified lexicons based upon the expanded set of phrases; and

a tagging model updater configured to update a query tagging model using the one or more stratified lexicons as lexicon features.

11. The system of claim 10, the list data structure constructor configured to:

obtain a set of HTML lists from one or more web resources;

filter the set of HTML lists based upon a number of phrases occurring within a particular list within a predefined range;

filter the set of HTML lists based upon a maximum length of phrases occurring within a particular HTML list; and

create the set of lists from the filtered set of HTML lists.

12. The system of claim 10, the seed distribution constructor configured to:

for particular phrases, assign a probability to one or more lexicons based upon a set of labeled training data, wherein the probability corresponds to the probability the phrase relates to the particular lexicon.

13. The system of claim 10, the sub-graph constructor configured to:

label one or more phrases within the list data structure with a corresponding lexicon probability distribution based upon the seed distribution data;

remove one or more lists from the list data structure having a number of phrases labeled with a lexicon probability distribution below a predetermined threshold; and

remove one or more phrases from the list data structure occurring within one or more lists at a frequency below a predetermined threshold.

14. The system of claim 10, the graph learning technique configured to:

for particular lists within the sub-graph, assign a list lexicon probability distribution to a particular list based upon lexicon probability distributions of phrases comprised within the list; and

for particular phrases within the sub-graph, assign an updated lexicon probability distribution to a particular phrase based upon list lexicon probability distributions of lists comprising the phrase.

15. The system of claim 14, wherein the updated lexicon probability distribution comprises one or more updated lexicon probabilities, wherein an updated lexicon probability corresponds to a probability that the particular phrase is associated with a particular lexicon.

16. The system of claim 10, the stratified lexicon constructor configured to:

group a set of phrases within the expanded set of phrases into a stratified lexicon, wherein respective phrases within the set of phrases comprise updated lexicon probabilities within a predefined range; and

associate the stratified lexicon with a corresponding lexicon.

17. The system of claim 10, the tagging model updater configured to:

execute the query tagging model upon a query to label one or more terms within the query.

18. The system of claim 10, wherein the query tagging model is a conditional random fields tagging model.

19. The system of claim 16, the query tagging model configured to:

receive the query comprising one or more terms; and

for respective terms within the query, assign one or more labels to a term based upon an occurrence of the one or more terms within a stratified lexicon of a corresponding lexicon.

20. A system for updating a query tagging model using one or more stratified lexicons comprising:

a list data structure constructor configured to create a list data structure in a graph format based upon a filtered set of HTML lists;

a seed distribution constructor configured to create seed distribution data based upon labeled training data;

a sub-graph constructor configured to create a sub-graph of the list data structure based upon removing one or more lists and one or more phrases based upon the seed distribution data;

a graph learning component configured to execute a graph learning algorithm upon the sub-graph create an expanded set of phrase based upon assigning list lexicon probability distributions to respective lists and updated lexicon probability distributions to respective phrases within the sub-graph;

a stratified lexicon constructor configured to group a set of phrases within the sub-graph into a stratified lexicon, wherein the stratified lexicon is associated with a corresponding lexicon based upon a predefined range; and

a tagging model updater configured to update a query tagging model based upon execution of the query tagging model upon one or more queries.