System for classifying a search query

• US 7,603,348 B2
• Filed: 01/26/2007
• Issued: 10/13/2009
• Est. Priority Date: 01/26/2007
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: He, Xiaofei, Jhala, Pradhuman Dasharalhasinh
• Primary Examiner(s): Stevens; Robert
• Application Number:
  US11/698,408
• Publication Number:
  US 20080183685A1
• Time in Patent Office: 991 Days
• Field of Search: 707/5, 707/6, 707/2, 707/3, 707/4, 707/E17.014
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A system is described for classifying a search query. The system may create a machine learning classifier function that may be “trained” by a plurality of categorized queries within a query taxonomy. The system may represent the queries as term vectors and input the term vectors to the machine learning classifier function to generate a value that may correspond to a particular category within the query taxonomy. The system may regularize the machine learning classifier function based on user search click data to improve the classifying accuracy.

Claims

1. A method of classifying a search query with a computer having a processor, the method comprising:

categorizing, by the processor, a plurality of selected search queries;

storing the categorized search queries in a taxonomy database according to category, the taxonomy database being stored in a data storage system coupled with the processor;

storing in a query log database query log data derived from the plurality of categorized search queries submitted to one or more search engines and including user click data, wherein the query log database is stored in the data storage system and is coupled with the processor;

computing, by the processor, a term vector for each of the plurality of selected search queries as a function of a web search, wherein the data storage system is operable to store the term vectors;

creating, by the processor, a classifier function as a function of the computing the term vectors, wherein the data storage system is operable to store the classifier function;

regularizing, by the processor, the classifier function based on the query log data comprising;

constructing a weighted query graph including nodes that represent the plurality of categorized search queries to model semantic relationships therebetween based on the query log data; and

mapping the weighted query graph to a line such that related queries are located close to each other within the weighted query graph; and

classifying, by the processor, an un-categorized search query as a function of the regularized classifier function.

2. The method of claim 1 wherein the plurality of selected search queries comprises a plurality of search queries selected according to at least one of a query frequency, variety, specificity, length, or combinations thereof.

3. The method of claim 1 wherein the categorizing comprises:

manually categorizing the selected search queries in a query taxonomy.

4. The method of claim 1 wherein the computing comprises:

submitting each of the plurality of selected search queries to a search engine;

identifying one or more returned web pages for each of the plurality of selected search queries; and

computing the term vector for each of the plurality of selected search queries as a function of terms extracted from the one or more returned web pages.

5. The method of claim 1 wherein the classifier function comprises a supervised learning algorithm.

6. The method of claim 1 wherein the un-categorized search query comprises a search query submitted to a search engine by a user.

7. The method of claim 1 wherein the classifying comprises:

computing a term vector for the un-categorized search query as a function of a web search; and

classifying the un-categorized search query as a function of the regularized classifier function.

8. The method of claim 1 further comprising:

storing the un-categorized search query in the query taxonomy database as a function of the classifying.

9. The method of claim 1 further comprising creating a dimensional vector space as a function of the term vectors, wherein the classifier function is given by ƒ

(x)=a^Tx where ƒ

(x) and x correspond to target variables and predictor variables of the plurality of selected search queries, respectively, and where a is a term vector corresponding to a number of dimensions of the dimensional vector space.

10. The method of claim 9 further comprising minimizing a regularizer function by setting a as (X₁X₁^T+λ

₁XLX^T+λ

₂I)<sup>−

1</sup>X₁y where I is the identity matrix, X=(x₁, . . . , x_m), X₁=(x₁, . . . , x_m1), y=(y₁, . . . , y_m1) where y_i is a category index number of X_i, and L=D−

W where W represents the similarity between the un-categorized search query and the categorized search queries within the dimensional vector space based on the query log data and D represents a diagonal matrix with entries being the column sum of W.

11. A system for creating a regularized classifier function for classifying a search query comprising:

a taxonomy database operable to store a plurality of categorized search queries wherein the taxonomy database is stored in a data storage system;

a term vector processor coupled with the taxonomy database and operable to create term vectors for each of the plurality of categorized search queries as a function of a web search, wherein the data storage system is operable to store the term vectors and is coupled with the term vector processor;

a classifier function processor coupled with the term vector processor and operable to create a classifier function as a function of the term vectors, wherein the data storage system is operable to store the classifier function and is coupled with the classifier function processor;

a query log database containing query log data derived from the plurality of categorized search queries submitted to one or more search engines and including user click data, wherein the query log database is stored in the data storage system; and

a regularization processor coupled with the classifier function processor and the data storage system, the regularization processor operable to regularize the classifier function by;

constructing a weighted query graph including nodes that represent the plurality of categorized search queries to model semantic relationships therebetween based on the query log data; and

regularizing the machine learning classifier function based on the query log data by mapping the weighted query graph to a line such that related queries are located close to each other within the weighted query graph.

12. The system of claim 11 wherein the taxonomy database comprises a query taxonomy.

13. The system of claim 11 wherein the term vector processor is operable to:

submit each of the plurality of categorized search queries to a search engine;

extract terms located within one or more returned web pages corresponding to each of the plurality of categorized search queries; and

create the term vectors for each of the plurality of categorized search queries as a function of the terms.

14. The system of claim 11 wherein the classifier function processor comprises a machine learning function operable to create the classifier function.

15. The system of claim 11 wherein the query weight graph comprises at least one edge connecting two search queries, and wherein the edge represents a relationship between the two search queries.

16. The system of claim 11 further comprising a vector space processor coupled with the term vector processor and operable to create a dimensional vector space as a function of the term vectors.

17. The system of claim 16 wherein the classifier function is given by ƒ

(x)=a^Tx where ƒ

(x) and x correspond to target variables and predictor variables of the plurality of selected search queries, respectively, and where a is a term vector corresponding to a number of dimensions of the dimensional vector space.

18. The system of claim 17 wherein the classifier function processor classifies an un-categorized search query as a function of the regularized classifier function, and the regularization processor minimizes a regularizer function by setting a as (X₁X₁^T+λ

₁XLX^T+λ

₂I)<sup>−

1</sup>X₁y where I is the identity matrix, X=(x₁, . . . , x_m), X₁=(x₁, . . . , x_m1), y=(y₁, . . . , y_m1) where y_i is a category index number of x_i, and L=D−

W where W represents the similarity between the un-categorized search query and the categorized search queries within the dimensional vector space based on the query log data and D represents a diagonal matrix with entries being the column sum of W.

19. A system for classifying a search query comprising computer programming logic stored in a memory and executable by a processor coupled with the memory, the computer programming logic comprising:

first logic operative to compute term vectors as a function of categorized search queries in a query taxonomy;

second logic coupled with the first logic and operative to generate a vector space as a function of the term vectors;

third logic coupled with the second logic and operative to create a classifier function as a function of the vector space;

fourth logic coupled with the third logic and operative to regularize the classifier function, wherein the fourth logic;

constructs a weighted query graph including nodes that represent the categorized search queries to model semantic relationships therebetween based on query log data derived from submission of the categorized search queries to one or more search engines and including user click data; and

regularizes the classifier function based on the query log data by mapping the weighted query graph to a line such that related queries are located close to each other within the weighted query graph; and

fifth logic coupled with the fourth logic and operative to classify an un-categorized search query as a function of the regularized classifier function.

20. The system of claim 19 wherein the categorized search queries comprise training data operative to train the classifier function.

21. The system of claim 19 wherein the fifth logic is further operative to store the un-categorized search query in a taxonomy database as a function of the classification.