Constructing a classifier for classifying queries

• US 8,407,214 B2
• Filed: 06/25/2008
• Issued: 03/26/2013
• Est. Priority Date: 06/25/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Xiao, Wang, Ye-Yi
• Primary Examiner(s): Badawi, Sherief
• Application Number:
  US12/145,508
• Publication Number:
  US 20090327260A1
• Time in Patent Office: 1,735 Days
• Field of Search: 707/708, 707/710, 707/726, 707/721, 707/737, 707/741, 707/763, 707/706, 707/767, 707/728, 707/731, 707/749, 707/798, 705/5, 715/234
• US Class Current: 707/726
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

To construct a classifier, a data structure correlating queries to items identified by the queries is received, where the data structure contains initial labeled queries that have been labeled with respect to predetermined classes, and unlabeled queries that have not been labeled with respect to the predetermined classes. The data structure is used to label at least some of the unlabeled queries with respect to the predetermined classes. Queries in the data structure that have been labeled with respect to the predetermined classes are used as training data to train the classifier.

Claims

1. A method of constructing a classifier, comprising:

receiving a click graph correlating queries to items identified by the queries, wherein the click graph contains initial labeled queries that have been labeled with respect to predetermined query-intent classes that represent whether or not corresponding queries are associated with particular intents of users to search for particular information from particular categories of information that a user wishes to perform a search in, and unlabeled queries that have not been labeled with respect to the predetermined query-intent classes, wherein the click graph comprises query nodes representing respective queries that are assigned a positive query-intent class when a query node corresponds to a positive query-intent class, or a negative query intent class when the query node does not correspond to a query-intent class, uniform resource locator (URL) nodes representing respective URLs, and edges between at least some of the query nodes and URL nodes when a user has navigated to a URL node for a given query;

using the click graph to label at least some of the unlabeled queries with respect to the predetermined query-intent classes by inferring the query-intent classes of the unlabeled nodes from class memberships of the labeled query nodes based on similarity of click patterns from query nodes to correlated URL nodes; and

using queries in the click graph that have been labeled with respect to the predetermined query-intent classes as training data to train the classifier.

2. The method of claim 1, wherein the classifier comprises a query intent classifier for classifying whether a query is related to a specific query intent, and wherein if a query is related to a specific query intent the query is submitted to a vertical search engine based on that specific intent.

3. The method of claim 1, further comprising assigning weights to respective edges between queries and URLs, wherein the weights are based on counts of clicks from queries to URLs.

4. The method of claim 3, wherein the edges and weights assigned to the respective edges together define the click patterns.

5. The method of claim 1, wherein using the click graph to label at least some of the unlabeled queries comprises:

iteratively computing values of elements in a collection, wherein the values are representative of likelihoods that the queries in the click graph belong to corresponding predetermined classes, wherein iteratively computing the values of elements comprises repeating computation of the values until a convergence criterion has been reached.

6. The method of claim 5, wherein computing values of the elements in the collection is based on an objective function that balances computing the values based on patterns of correlations between the queries and items in the click graph and computing the values based on the initial labeled queries.

7. The method of claim 1, further comprising:

feeding back an output of the classifier to the step of using the click graph to label at least some of the unlabeled queries with respect to the predetermined classes, wherein feeding back the output of the classifier causes re-labeling of some of previously labeled queries; and

modifying the classifier based on the re-labeled queries.

8. The method of claim 1, wherein at least one of the URL nodes represents a group of related URLs.

9. The method of claim 1, wherein the click graph is automatically built by:

initializing the click graph to initially contain query nodes corresponding to the initial labeled queries but that initially does not contain other query nodes;

adding URL nodes connected to the query nodes present in the click graph;

adding query nodes that are connected to the added URL nodes; and

repeating the adding of the URL nodes and adding of the additional query nodes until at least a predefined number of query nodes has been reached.

10. An article comprising:

at least one computer storage device containing instructions that when executed cause a computer to;

receive an initial set of queries that have been labeled with respect to query intent classes;

receive a collection of data in the form of a click graph that includes correlations between unlabeled queries and items identified by the queries, wherein the click graph has query nodes representing respective queries that are assigned a positive query-intent class that represents that corresponding queries are associated with particular intents of users to search for particular information from particular categories of information that a user wishes to perform a search in when a query node corresponds to a positive query-intent class, or a negative query-intent class when the query node does not correspond to a query-intent class, uniform resource locator (URL) nodes representing respective URLs, and edges between at least some of the query nodes and URL nodes when a user has navigated to a URL node for a given query and wherein the respective edges between queries and URLs have weights assigned to them based on counts of clicks from queries to URLs which are used to define click patterns;

apply a graph-based learning algorithm to enable labeling of at least some of the unlabeled queries with respect to the query intent classes according to labeling in the initial set of queries by inferring the query-intent classes of the unlabeled nodes from class memberships of the labeled query nodes based on similarity of click patterns from query nodes to corresponding URL nodes; and

create training data based on the initial set of labeled queries and the queries labeled by the graph-based learning algorithm to train a query intent classifier.

11. The article of claim 10, wherein applying the graph-based learning algorithm comprises:

generating a click graph in response to the received collection of data;

computing values of elements of a collection to represent likelihoods that the queries in the click graph correspond to the query intent classes.

12. The article of claim 10, wherein the instructions when executed cause the computer to further:

use the trained query intent classifier to apply content-based classification on the queries that have been labeled based on the graph-based learning algorithm;

feed back an output of the content-based classification to the graph-based learning algorithm;

re-apply the graph-based learning algorithm using the output of the content-based classification to cause modification in labeling of some of the queries; and

modify the training data based on the re-applying of the graph-based learning algorithm to cause re-training of the query intent classifier.

13. The article of claim 10, wherein the click graph includes edges representing clicks between the unlabeled queries and uniform resource locators (URLs).

14. The article of claim 10, wherein the instructions when executed cause the computer to further send the query intent classifier to a location for use with a search engine.

15. The article of claim 14, wherein the query intent classifier comprises a classifier to classify a query as a query for information from a particular domain.

16. The article of claim 10, wherein receiving the initial set of queries that have been labeled with respect to query intent classes comprises receiving the initial set of queries that have been labeled with respect to query intent classes by one or more humans.

17. A system for constructing a classifier, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,

receive a click graph that contains query nodes representing respective queries and second nodes representing items identified by the queries, wherein a subset of the query nodes have been initially labeled with respect to predetermined query-intent classes that represent whether or not corresponding queries are associated with particular intents of users to search for particular information from particular categories of information that a user wishes to perform a search in and that are assigned a positive query-intent class when a query node corresponds to a positive query-intent class, or a negative query intent class when the query node does not correspond to a query-intent class, and wherein a remainder of the query nodes initially are not labeled with respect to the predetermined query-intent classes;

compute values representing likelihoods that the queries belong to the predetermined query-intent classes by inferring the query-intent classes of the unlabeled nodes from class memberships of the labeled query nodes based on similarity of user click patterns from query nodes to corresponding URL nodes;

assign labels to at least some of the unlabeled query nodes to label the unlabeled query nodes with respect to the predetermined query-intent classes based on the computed values; and

use the subset of the query nodes and the query nodes labeled based on the computed values as training data to train a classifier.

18. The system of claim 17, wherein the respective edges between queries and URLs have weights assigned to them based on counts of clicks from queries to URLs and wherein the edges and weights assigned to the respective edges together define the click patterns.