Click chain model
AssigneeMicrosoft Corporation
InventorsChao Liu, Fan Guo, Yi-Min Wang
Life of this patent
Estimating the term…
Abstract
Techniques are described for generating a statistical model from observed click chains. The model can be used to compute a probability that a document is relevant to a given search query. With the model, a probability of a user examining a given document in a given search result conditionally depends on: a probability that a preceding document in the given search result is examined by a user viewing the given search result; a probability that the preceding document is clicked on by a user viewing the given search result, which conditionally depends directly on the probability that the preceding document is examined and on a probability of relevance of the preceding document.
Claims21
A computer-implemented method of computing relevancies of documents to queries submitted to a search engine software server hosted on one or more server computers that are configured to receive the queries via a network from client computers, the one or more server computers also being configured to return via the network to the client computers search results configured to be displayed on the client computers, a search result comprising a listing of documents in an order according to relevance to a corresponding query as determined by the search engine, the method comprising:
- accessing a click chain log comprising click chains each indicating which documents at which respective order positions of a corresponding particular search result were clicked or not clicked by a user that viewed the particular search result;
- using the click chain log to train a click chain model (CCM) inference engine, where the CCM inference engine models the click chains such that, for a given search result for a given query, a probability of a user examining a given document in the given search result conditionally depends directly on:
- a probability that a document preceding the given document in the given search result is examined by a user viewing the given search result;
- a probability that the preceding document is clicked on by a user viewing the given search result, which conditionally depends directly on both the probability that the preceding document is examined and on a probability of the preceding document being perceived as relevant to the user with respect to the given query;
- the probability of the preceding document being perceived as relevant by the user with respect to the given query;
- and
- receiving a new query from a client at the search engine, using the CCM inference engine to contribute to computation of relevancies of matching documents to the new query, and returning to the client a search result where the matching documents are ranked according to the relevancies, whereby the matching documents are ranked at least in part according to the CCM inference engine.
One or more computer-readable storage media storing information configured to enable a computing device to perform a process of computing probabilities that respective documents are relevant to a query submitted to a search engine that receives queries from client computers, the search engine returning to the client computers search results for the queries, a search result comprising a listing of documents ordered according to relevance to a corresponding query as computed by the search engine, the process comprising:
- modeling click chains in an inference engine as conditional probabilities including a first probability that a user examines a first document in a search result for a query, a second probability that a user clicks on a second document in the search result for the query, and a third probability of the second document being relevant to the query, wherein the second probability is conditionally dependent on the third probability and the first probability is conditionally dependent on the third probability;
- ranking results of queries from client computers by using the inference engine;
- and
- returning the ranked results to the client computers.
A computing device comprising computer-readable storage media storing information configured to enable the computing device to perform a process of computing probabilities that respective documents are relevant to a query submitted to a search engine that receive queries from client computers, the search engine returning to the client computers search results for the queries, a search result comprising a listing of documents ordered according to relevance to a corresponding query as computed by the search engine, the process comprising:
- training an inference engine with a set of observed click chains, the inference engine modeling user click behavior as a probabilistic dependence graph comprising nodes that represent random events and edges representing conditional dependencies between the random events, the graph comprising:
- a first node representing a probability that a user examines a first document in a search result for a query, a second node representing a probability that a user clicks on a second document in the search result for the query, a third node representing a probability of relevance of the second document to the query, a first edge between the second and third node representing a conditional dependency of the second node on the third node, a second edge between the first and third node representing a conditional dependency of the first node on the third node, and a third edge between the second and third node representing a conditional dependency of the third node on the second node;
- and
- using the inference engine to compute relevancies of documents to queries.
Dependencies are inferred from the claim text.