Ranking advertisements with pseudo-relevance feedback and translation models

Abstract

Methods, computer products, and systems for selecting advertisements in response to an internet query are provided. The method provides for receiving an internet query that includes query terms, retrieving and then ranking a first set of advertisements in response to the internet query using a query likelihood model. The method then selects sampling terms using pseudo-relevance feedback and translation models, the internet query, and the first set of ad materials obtained using the query likelihood model. The sampling terms are chosen from a distribution of terms from the terms in the first set of ad materials, and the pseudo-relevance feedback model is used to select a term in the distribution of terms based on a probability. The use of translation models enhances the topicality of the results because the distribution words selected are related to the terms in the original query as indicated by their translation probabilities.

What is claimed is: 
     
         1 . A method to select advertisements in response to an internet query, the method comprising:
 receiving an internet query (Q), the internet query including query terms (q);   retrieving information related to the received internet query including information about a set of internet documents;   ranking the set of internet documents by a probability that the query was generated by a sampling of terms from each of the set of internet documents;   selecting a top ranked number (N) of the ranked set of internet documents;   constructing a model of the selected top ranked number (N) of the ranked set of internet documents;   selecting content terms from the model;   ranking a first set of ad materials (S) in response to the model, S including a plurality of ad materials (s); and   outputting advertisements based on the first set of ad materials for display in a portion of an internet browser.   
     
     
         2 . The method as recited in  claim 1 , further comprising,
 generating an expanded query including the internet query and the selected content terms from the model,   retrieving a second set of ad materials using the expanded query,   ranking the second set of ad materials, and   outputting advertisements based on the second set of ad materials.   
     
     
         3 . The method as recited in  claim 2 , wherein ranking the second set of ad materials includes ranking the second set of ad materials according to a likelihood the second set of ad materials generated the expanded query. 
     
     
         4 . The method as recited in  claim 1 , wherein ranking the set of internet documents by the probability that the query was generated by the sampling from each of the set of internet documents includes smoothing the ranking of the set of internet documents to give a non-zero probability to any unseen query terms. 
     
     
         5 . The method as recited in  claim 1 , wherein selecting the content terms from the model includes,
 selecting a translation table,   using the selected translation table to estimate a probability of a query term given a term from a vocabulary directly, and   choosing a number of content terms with a highest estimated probability.   
     
     
         6 . The method as recited in  claim 5 , wherein estimating the probability of the query term given the term from the vocabulary directly further includes,
 calculating the probability p(q|w) based on the translation probability t(q|w),   calculating a probability of the internet query Q given the term w (p(Q|w)) as a product for all q of all the probabilities p(q|w), including making p(q|w) equal to the probability t(q|w),   calculating a probability of the term w (p(w)) as the sum for all s in S of probabilities of w given the ad materials s (p(w|s)) times a probability of the ad materials s (p(s)), and   calculating the probability p(w|Q) as proportional to the probability p(w) times the probability p(Q|w).   
     
     
         7 . The method as recited in  claim 6 ,
 wherein selecting content terms further includes calculating a probability of query term q given ad materials s (p(q|s)) as equal to the number of times q occurs in the ad materials s divided by a number of terms in the ad materials s,   wherein calculating the probability p(q|w) further includes making p(q|w) equal to the sum for all s of the probability t(q|w) times the probability p(q|s) times the probability p(w|s) times the probability p(s) divided by the probability p(w).   
     
     
         8 . The method as recited in  claim 1 , wherein the second set of ad materials is selected from a group consisting of,
 a content match ad for the internet query, and   a sponsored search ad for the internet query.   
     
     
         9 . The method as recited in  claim 1 , wherein the ranking the set of internet documents by the probability that the query was generated by the sampling of terms from each of the set of internet documents includes ranking the set of internet documents by the probability that the query was generated by a random sampling of terms from each of the set of internet documents. 
     
     
         10 . A non-transitory computer readable medium having program instructions for selecting advertisements in response to an internet query, comprising:
 program instructions for receiving an internet query (Q), the internet query including query terms (q);   program instructions for retrieving information related to the received internet query including information about a set of internet documents;   program instructions for ranking the set of internet documents by a probability that the query was generated by a sampling of terms from each of the set of internet documents;   program instructions for selecting a top ranked number (N) of the ranked set of internet documents;   program instructions for constructing a model of the selected top ranked number (N) of the ranked set of internet documents;   program instructions for selecting content terms from the model;   program instructions for ranking a first set of ad materials (S) in response to the model, S including a plurality of ad materials (s); and   program instructions for outputting advertisements based on the first set of ad materials for display in a portion of an internet browser.   
     
     
         11 . The non-transitory computer readable medium having program instructions as recited in  claim 10 , further comprising,
 program instructions for generating an expanded query including the internet query and the selected content terms from the model,   program instructions for retrieving a second set of ad materials using the expanded query,   program instructions for ranking the second set of ad materials, and   program instructions for outputting advertisements based on the second set of ad materials.   
     
     
         12 . The non-transitory computer readable medium having program instructions as recited in  claim 11 , wherein ranking the second set of ad materials includes ranking the second set of ad materials according to a likelihood the second set of ad materials generated the expanded query. 
     
     
         13 . The non-transitory computer readable medium having program instructions as recited in  claim 10 , wherein ranking the set of internet documents by the probability that the query was generated by the sampling from each of the set of internet documents includes smoothing the ranking of the set of internet documents to give a non-zero probability to any unseen query terms. 
     
     
         14 . The non-transitory computer readable medium having program instructions as recited in  claim 10 , wherein the program instructions for selecting the content terms from the model includes,
 program instructions for selecting a translation table,   program instructions for using the selected translation table to estimate a probability of a query term given a term from a vocabulary directly, and   program instructions for choosing a number of content terms with a highest estimated probability.   
     
     
         15 . The non-transitory computer readable medium having program instructions as recited in  claim 14 , wherein the program instructions for estimating the probability of the query term given the term from the vocabulary directly further includes,
 program instructions for calculating the probability p(q|w) based on the translation probability t(q|w),   program instructions for calculating a probability of the internet query Q given the term w (p(Q|w)) as a product for all q of all the probabilities p(q|w), including making p(q|w) equal to the probability t(q|w),   program instructions for calculating a probability of the term w (p(w)) as the sum for all s in S of probabilities of w given the ad materials s (p(w|s)) times a probability of the ad materials s (p(s)), and   program instructions for calculating the probability p(w|Q) as proportional to the probability p(w) times the probability p(Q|w).   
     
     
         16 . The non-transitory computer readable medium having program instructions as recited in  claim 15 ,
 wherein program instructions for selecting content terms further includes program instructions for calculating a probability of query term q given ad materials s (p(q|s)) as equal to the number of times q occurs in the ad materials s divided by a number of terms in the ad materials s,   wherein program instructions for calculating the probability p(q|w) further includes program instructions for making p(q|w) equal to the sum for all s of the probability t(q|w) times the probability p(q|s) times the probability p(w|s) times the probability p(s) divided by the probability p(w).   
     
     
         17 . The non-transitory computer readable medium having program instructions as recited in  claim 11 , wherein the second set of ad materials is selected from a group consisting of,
 a content match ad for the internet query, and   a sponsored search ad for the internet query.   
     
     
         18 . The non-transitory computer readable medium having program instructions as recited in  claim 11 , wherein the program instructions for ranking the set of internet documents by the probability that the query was generated by the sampling of terms from each of the set of internet documents includes program instructions for ranking the set of internet documents by the probability that the query was generated by a random sampling of terms from each of the set of internet documents. 
     
     
         19 . A method of outputting advertisements in response to an internet query, the method comprising:
 receiving an internet query, the internet query including query terms;   retrieving information related to the received internet query including information about a set of internet documents;   ranking the set of internet documents by a probability that the query was generated by a random sampling from each of the set of internet documents including smoothing the ranking of the set of internet documents to give a non-zero probability to any unseen query terms;   selecting a top ranked number (N) of the ranked set of internet documents;   constructing a model of the selected top ranked number (N) of the ranked set of internet documents;   selecting content terms from the model;   ranking a first set of ad materials (S) in response to the model, S including a plurality of ad materials (s);   generating an expanded query including the internet query and the selected content terms from the model;   retrieving a second set of ad materials using the expanded query;   ranking the second set of ad materials according to a probability the second set of ad materials generated the expanded query; and   outputting advertisements based on the second set of ad materials.