Predicting user interests

• US 9,026,479 B1
• Filed: 02/02/2011
• Issued: 05/05/2015
• Est. Priority Date: 02/02/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baluja, Shumeet, Covell, Michele
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): HANCHAK, WALTER P
• Application Number:
  US13/019,782
• Time in Patent Office: 1,553 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06N 3/00 Computing arrangements based on biological models
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for predicting user interests. In one aspect, a method includes training a prediction model to generate a category prediction of a next query from a set of queries, the category prediction specifying categories to which a next query belongs, the prediction model comprising a plurality of prediction functions that each generate a category prediction of a next query, wherein the prediction functions include two or more of a time-based prediction functions that generate a category prediction based on the category data and a difference of submission times of the queries, a rank-based prediction functions that generate a category prediction based on the category data and a rank order by which the queries were received, and a category-based prediction function that generates a category prediction based on the category data.

Claims

1. A method performed by data processing apparatus, the method comprising:

accessing query log data storing queries and user identifiers, wherein the query log data specify, for each user identifier;

queries associated with the user identifier, each query associated with the user identifier being a query received from one or more user devices associated with the user identifier; and

for each query, a submission time of the query, the submission time related to a time that the query was received by a search system;

training, by a data processing apparatus, a prediction model to generate a category prediction of a next query from a set of queries, the category prediction specifying categories to which the next query is predicted to belong, wherein the prediction model comprises a plurality of prediction functions that each generate a category prediction of the next query, wherein each category prediction is based on the query log data and category data defining, for each query of the set of queries, categories to which the query belongs, and wherein the prediction functions include a combination of;

one or more time-based prediction functions that generate a category prediction of the next query based on the category data and a difference of submission times of the queries of the set of queries, the one or more time-based prediction functions generating a category prediction of the next query by;

adjusting, for each particular query of the set of queries, a category weight for each category to which the particular query belongs based on an amount of time that has passed since the submission time of the particular query; and

generating a category prediction of the next query based on the adjusted category weights for each category and for each particular query;

one or more rank-based prediction functions that generate a category prediction of the next query based on the category data and a rank order by which the queries of the set of queries were received; and

one or more category-based prediction functions that generate a category prediction of the next query based on the category data and that is independent of the submission times of the queries of the set of queries.

2. The method of claim 1, wherein:

each of the one or more time-based prediction functions include time-based prediction parameters;

each of the one or more rank-based prediction functions include rank-based prediction parameters;

each of the one or more category-based prediction functions include category-based prediction parameters; and

training the prediction model comprises iteratively generating category predictions for the prediction model and adjusting the time-based prediction parameters, rank-based prediction parameters and category-based prediction parameters of the prediction functions for each iteration until a termination event occurs.

3. The method of claim 2, wherein training the prediction model comprises, for each iteration subsequent to a first iteration:

adjusting one or more of the prediction parameters of the prediction functions to generate a current set of parameters;

for each user identifier;

selecting a respective set of most recent queries, the set of most recent queries being the queries associated with the user identifier and that have most recent submission times of the queries associated with the user identifier;

receiving, for each query in the set of most recent queries, the category data defining categories to which the query is determined to belong;

generating a category prediction for the prediction model from a proper subset of the set of most recent queries that excludes the query with the most recent submission time;

comparing the category prediction for the prediction model to the categories to which the query with the most recent submission time is determined to belong;

determining, from the comparisons, a current error measure for the current set of parameters that measure an error of the category predictions generated for the prediction model;

comparing the error measure of the current set of parameters to a best error measure of a best set of parameters, the best error measure of the best set of parameters having been generated from a previous iteration and stored; and

storing the current set of parameters and the current error measure as the best set of parameters and the best error measure only if the current error measure is less that the best error measure.

4. The method of claim 3, wherein adjusting one or more of the prediction parameters of the prediction functions to generate a current set of parameters comprises adjusting one or more of the parameters stored as the best set of parameters.

5. The method of claim 4, wherein:

the prediction parameters of the prediction functions include a weight parameter that weights the category prediction of a next query.

6. The method of claim 5, wherein adjusting one or more of the prediction parameters of the prediction functions:

randomly selecting only one of the prediction parameters; and

randomly adjusting the selected prediction parameter.

7. The method of claim 3, wherein the termination event is achieving a maximum number of iterations.

8. The method of claim 3, wherein the termination event is determining an error measure that meets a minimum error threshold.

9. The method of claim 3, wherein:

the query log data specify, for each query, one of a plurality of a domain categories, each domain category being a category of a domain for which a query was submitted from a user device;

selecting a respective set of most recent queries for each user identifier comprises selecting a respective set of most recent queries for each user identifier and each domain category; and

training the prediction model comprises training a plurality of prediction models, wherein each prediction model is associated with a domain category is trained on only the sets of most recent queries for the domain category.

10. The method of claim 9, wherein the domain categories include a maps category, a social network category, or a general content category.

11. The method of claim 3, wherein:

the query log data specify, for each query, one of a plurality of a device categories, each device category being a category of a user device from which a query was submitted, and wherein the device categories include a mobile device category and a desktop device category;

selecting a respective set of most recent queries for each user identifier comprises selecting a respective set of most recent queries for each user identifier and each device category; and

training the prediction model comprises training a plurality of prediction models, wherein each prediction model is associated with a device category is trained on only the sets of most recent queries for the device category.

12. The method of claim 2, wherein training the prediction model comprises training the prediction model using one of a stochastic hill-climbing algorithm, a simulated annealing algorithm, a genetic algorithm, a population-based incremental learning algorithm, or a TABU search algorithm.

18. The method of claim 1, wherein the one or more category-based prediction functions generates a category prediction of the next query based on a number of queries in the set of queries that belong to each of the categories to which the queries of the set of queries belong.

19. The method of claim 1, wherein the one or more category-based prediction functions generates a category prediction of the next query by:

for each particular query of the set of queries, identifying a particular number of the one or more categories to which the particular query belongs;

determining a number of queries in the set of queries that belong to each of the identified categories; and

generating the category prediction of the next query based on the number of queries that belong to each of the identified categories.

20. The method of claim 1, wherein the rank order specifies a ranking of each query of the set of queries with respect to each other query of the set of queries.

13. A method performed by data processing apparatus, the method comprising:

accessing query log data storing queries and user identifiers, wherein the query log data specify, for each user identifier;

queries associated with the user identifier, each query associated with the user identifier being a query received from one or more user devices associated with the user identifier; and

for each query, a submission time of the query, the submission time related to a time that the query was received by a search system;

training, by a data processing apparatus, a prediction model to generate a category prediction of a next query from a set of queries, the category prediction specifying categories to which a next query is predicted to belong, wherein;

the prediction model comprises a combination of two or more of;

a time-based prediction function that generates a category prediction of a next query based on category data and a difference of submission times of the queries of the set of queries, the category data defining, for each query of the set of queries, categories to which the queries query belongs, the time-based prediction function including time-based prediction parameters, the time-based prediction function generating a category prediction of the next query by;

adjusting, for each particular query of the set of queries, a category weight for each category to which the particular query belongs based on an amount of time that has passed since the submission time of the particular query; and

generating a category prediction for the next query based on the adjusted category weight for each category and for each particular query;

a rank-based prediction function that generates a category prediction of the next query based on a rank order by which the queries of the set of queries were received, and includes rank-based prediction parameters; and

a category-based prediction function that generates a category prediction of the next query based on the category data of the queries of the set of queries and that is independent of the submission times of the queries of the set of queries, and includes category-based prediction parameters; and

the training comprises iteratively generating category predictions for the prediction model and respectively adjusting two or more of the time-based prediction parameters, rank-based prediction parameters and category-based prediction parameters of the prediction functions for each iteration until a termination event occurs.

14. The method of claim 13, wherein training the prediction model comprises, for each iteration subsequent to a first iteration:

adjusting one or more of the prediction parameters of the prediction functions to generate a current set of parameters;

for each user identifier;

selecting a respective set of most recent queries, the set of most recent queries being the queries associated with the user identifier and that have most recent submission times of the queries associated with the user identifier;

receiving, for each query in the set of most recent queries, the category data defining categories to which the query is determined to belong;

generating a category prediction for the prediction model from a proper subset of the set of most recent queries that excludes the query with the most recent submission time;

comparing the category prediction for the prediction model to the categories to which the query with the most recent submission time is determined to belong;

determining, from the comparisons, a current error measure for the current set of parameters that measure an error of the category predictions generated for the prediction model;

comparing the error measure of the current set of parameters to a best error measure of a best set of parameters, the best error measure of the best set of parameters having been generated from a previous iteration and stored; and

storing the current set of parameters and the current error measure as the best set of parameters and the best error measure only if the current error measure is less that the best error measure.

15. Software comprising instructions stored in a non-transitory computer readable storage device that upon execution cause a data processing apparatus to perform operations comprising:

accessing query log data storing queries and user identifiers, wherein the query log data specify, for each user identifier;

queries associated with the user identifier, each query associated with the user identifier being a query received from one or more user devices associated with the user identifier; and

for each query, a submission time of the query, the submission time related to a time that the query was received by a search system;

training, by a data processing apparatus, a prediction model to generate a category prediction of a next query from a set of queries, the category prediction specifying categories to which the next query is predicted to belong, wherein the prediction model comprises a plurality of prediction functions that each generate a category prediction of the next query based on the query log data and category data defining, for each query of the set of the set of queries, categories to which the queries query belong, wherein the prediction functions include a combination of;

one or more time-based prediction functions that generate a category prediction of the next query based on the category data and a difference of submission times of the queries, the one or more time-based prediction functions generating a category prediction of the next query by;

adjusting, for each particular query of the set of queries, a category weight for each category to which the particular query belongs based on an amount of time that has passed since the submission time of the particular query; and

generating a category prediction of the next query based on the adjusted category weights for each category and for each particular query;

one or more rank-based prediction functions that generate a category prediction of the next query based on the category data and a rank order by which the queries of the set of queries were received; and

one or more category-based prediction functions that generate a category prediction of the next query based on the category data and that is independent of the submission times of the queries of the set of queries.

16. Software comprising instructions stored in a non-transitory computer readable storage device that upon execution cause a data processing apparatus to perform operations comprising:

accessing query log data storing queries and user identifier, wherein the query log data specify, for each user identifier;

queries associated with the user identifier, each query associated with the user identifier being a query received from one or more user devices associated with the user identifier; and

for each query, a submission time of the query, the submission time related to a time that the query was received by a search system;

training, by a data processing apparatus, a prediction model to generate a category prediction of a next query from a set of queries, the category prediction specifying categories to which a next query is predicted to belong, wherein;

the prediction model comprises a combination of two or more of;

a time-based prediction function that generates a category prediction of a next query based on category data and a difference of submission times of the queries, the category data defining, for each query of the set of queries, categories to which the queries query belongs, the time-based prediction function including time-based prediction parameters, the time-based prediction function generating a category prediction of the next query by;

adjusting, for each particular query of the set of queries, a category weight for each category to which the particular query belongs based on an amount of time that has passed since the submission time of the particular query; and

generating a category prediction for the next query based on the adjusted category weight for each category and for each particular query;

a rank-based prediction function that generates a category prediction of the next query based on a rank order by which the queries of the set of queries were received, and includes rank-based prediction parameters; and

a category-based prediction function that generates a category prediction of the next query based on the category data of the queries of the set of queries and that is independent of the submission times of the queries of the set of queries, and includes category-based prediction parameters; and

the training comprises iteratively generating category predictions for the prediction model and adjusting the time-based prediction parameters, rank-based prediction parameters and category-based prediction parameters of the prediction functions for each iteration until a termination event occurs.

17. A system comprising:

a data processing apparatus; and

a memory device in data communication with the data processing apparatus and storing instructions that cause the data processing apparatus to perform operations comprising;

accessing query log data storing queries and user identifier, wherein the query log data specify, for each user identifier;

queries associated with the user identifier, each query associated with the user identifier being a query received from one or more user devices associated with the user identifier; and

for each query, a submission time of the query, the submission time related to a time that the query was received by a search system;

training, by a data processing apparatus, a prediction model to generate a category prediction of a next query from a set of queries, the category prediction specifying categories to which a next query is predicted to belong, wherein;

the prediction model comprises a combination of two or more of;

a time-based prediction function that generates a category prediction of a next query based on category data and a difference of submission times of the queries, the category data defining, for each query of the set of queries, categories to which the queries query belongs, the time-based prediction function including time-based prediction parameters, the time-based prediction function generating a category prediction of the next query by;

adjusting, for each particular query of the set of queries, a category weight for each category to which the particular query belongs based on an amount of time that has passed since the submission time of the particular query; and

generating a category prediction for the next query based on the adjusted category weight for each category and for each particular query;

a rank-based prediction function that generates a category prediction of the next query based on a rank order by which the queries of the set of queries were received, and includes rank-based prediction parameters; and

a category-based prediction function that generates a category prediction of the next query based on the category data of the queries of the set of queries and that is independent of the submission times of the queries of the set of queries, and includes category-based prediction parameters; and

the training comprises iteratively generating category predictions for the prediction model and adjusting the time-based prediction parameters, rank-based prediction parameters and category-based prediction parameters of the prediction functions for each iteration until a termination event occurs.

21. The system of claim 17, wherein:

each of the one or more time-based prediction functions include time-based prediction parameters;

each of the one or more rank-based prediction functions include rank-based prediction parameters;

each of the one or more category-based prediction functions include category-based prediction parameters; and

training the prediction model comprises iteratively generating category predictions for the prediction model and adjusting the time-based prediction parameters, rank-based prediction parameters and category-based prediction parameters of the prediction functions for each iteration until a termination event occurs.

22. The system of claim 21, wherein training the prediction model comprises, for each iteration subsequent to a first iteration:

adjusting one or more of the prediction parameters of the prediction functions to generate a current set of parameters;

for each user identifier;

selecting a respective set of most recent queries, the set of most recent queries being the queries associated with the user identifier and that have most recent submission times of the queries associated with the user identifier;

receiving, for each query in the set of most recent queries, the category data defining categories to which the query is determined to belong;

generating a category prediction for the prediction model from a proper subset of the set of most recent queries that excludes the query with the most recent submission time;

comparing the category prediction for the prediction model to the categories to which the query with the most recent submission time is determined to belong;

determining, from the comparisons, a current error measure for the current set of parameters that measure an error of the category predictions generated for the prediction model;

comparing the error measure of the current set of parameters to a best error measure of a best set of parameters, the best error measure of the best set of parameters having been generated from a previous iteration and stored; and

storing the current set of parameters and the current error measure as the best set of parameters and the best error measure only if the current error measure is less that the best error measure.