Patent Publication Number: US-8126894-B2

Title: Click chain model

Description:
BACKGROUND 
     Some search engines log which documents are clicked for particular queries. These query click logs are a rich source of information in the search business, because they reflect users&#39; preference over the documents presented by a search engine. In addition to being first-party judgments, click logs are useful because they easily outweigh human judges&#39; third-party judgments in terms of both query coverage and quantity. One way to leverage query click logs is to infer the user-perceived relevance of each document with respect to the query that elicited the document. However, while valuable for many applications, inference of document relevance from user clicks is a difficult problem to solve. There may be numerous ad hoc approaches to deriving document relevance, e.g., the more clicks a document receives the more relevant it is, but the effectiveness of such ad hoc approaches is limited because of the lack of theoretical foundations, unpredictable performance in reality, and maintenance difficulties. What is needed is a principled approach to inferring document relevance from user click logs. 
     Techniques related to click chain modeling are described below. 
     SUMMARY 
     The following summary is included only to introduce some concepts discussed in the Detailed Description below. This summary is not comprehensive and is not intended to delineate the scope of the claimed subject matter, which is set forth by the claims presented at the end. 
     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 both the probability that the preceding document is examined and on the probability of the preceding document being perceived as relevant by the user for the given query. 
     Many of the attendant features will be explained below with reference to the following detailed description considered in connection with the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein like reference numerals are used to designate like parts in the accompanying description. 
         FIG. 1  shows a system for modeling a click log for a search engine. 
         FIG. 2  shows a general process for modeling click logs to obtain relevancies. 
         FIG. 3  shows input and output for an inference engine. 
         FIG. 4  shows search user behavior captured for a click chain model. 
         FIG. 5  shows a graphical model representation of a click chain model (CCM). 
         FIG. 6  shows probability distribution functions. 
         FIG. 7  shows evolution of a normalized posterior of an example document. 
         FIG. 8  shows how the normalized posteriors for 5 documents evolve from start to different iterations. 
     
    
    
     DETAILED DESCRIPTION 
     Overview 
     Embodiments described herein relate to a graphical model and an inference algorithm based on the graphical model. Together they will be referred to as a Click Chain Model (CCM). The CCM mathematically models web users&#39; click behaviors. 
       FIG. 1  shows a system for modeling a click log  100  for search engine  102 . The search engine  102  may be any variety of known search engines which generally index a set of documents, receive queries for the documents, and rank matching documents by computing relevancies of the documents to the queries. A web server (not shown) may work in conjunction with the search engine  102 . 
     The click log  100  has click entries, each having a particular query (e.g., the search terms of the query) and an ordering, by relevance, of which documents were found by a search engine  102  to be relevant to its query. A click entry also indicates which of its documents were clicked by a user viewing the documents in a search result for the query. In the example of  FIG. 1 , a query of “Baltimore Orioles” returned 8 specific URLs (url 15 , . . . , url 174 ) and a user who viewed the documents after submitting the query was recorded to have clicked on 3 documents; url 121 , url 430 , and url 357 . The click log  100  may be generated by a logging module  104  observing session activity directed to the search engine  102  and logging queries and subsequent clicks. The queries may be transmitted from various clients  106 , for example web browsers or other applications for accessing the search engine  102 . The queries, as well as clicks on result documents, are transmitted over a network  108  between the clients  106  and a network interface  110  of a server computer  112 . The server computer  112  and search engine  102  may in practice be distributed across multiple server computers. A client  106  may display a search result  114  on a display  116 . As will be described in detail below, an inference engine uses the click log  100  to generate a statistical model of the click log  100  which can be used to compute relevancies of documents to queries. The relevancies can be used by the search engine  102 . Relevancies output by the inference engine  118  may be used for other purposes, for example for online advertising. 
       FIG. 2  shows a general process for modeling click logs to obtain relevancies. Initially, a statistical inference engine is trained  130  using a click chain log. The click chain log indicates which documents at which respective order positions of a corresponding particular search result were clicked or not clicked by a user who viewed the particular search result. The inference engine is modeled  132  as a conditional dependency graph. For a given search result for a given query, a probability of a user examining a given document in the given search result is modeled  134  as conditionally depending on probabilities of other variables, for example: 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 both the probability that the preceding document is examined and on the probability of the preceding document being perceived as relevant by the user with respect to the given query. The trained inference engine may then be used to compute  136  relevancies of documents. To further understand the inferences, looking ahead to graph  158  in  FIG. 5 , note that whether a document is viewed or not, or clicked or not, E i , C i , and S i  will still exist in the model. The clicked or not-clicked status decides whether C i =1 or 0, and P(E i =1) is inferred from the CCM, as E i  and S i  are hidden (i.e., unobserved) variables. 
       FIG. 3  shows input and output for an inference engine  152 . A CCM inference engine receives a click chain log  150 . For any given query q submitted to the inference engine, the inference engine in effect generates probability distribution functions  154  of relevance of q to various URLs (documents). 
     Mathematical Context 
     As mentioned previously, the CCM described herein mathematically models web users&#39; click behaviors. Given a set of documents {d}, each document d i  is assigned three random variables E i , C i  and R i , which respectively denote whether d i  is examined, whether it is clicked, and how relevant d i  is with respect to the query that elicits d i . Given user click logs, C i &#39;s are observed, and a probability of d i  being perceived as relevant by the user with respect to the query may be inferred by calculating the posterior for each R i , i.e., P(R i |D), where D represents the click data. Once P(R i |D) is derived, a number of applications may be improved. For example, by taking the distribution mean and variance of D as the user-perceived relevance of d i  (and confidence), documents may be re-ranked for improved search quality, etc. 
     The CCM described herein may benefit from a simplified model that enables derivation of a closed form (i.e., exact inference) of P(R i |D)). Previous click chain approaches have used approximate algorithms (e.g., Expectation Propagation and Variational Message Passing) to infer relevance. Approximate algorithms may not guarantee convergence to the true posterior. Approximate algorithms are usually slow and therefore do not scale well. Furthermore, approximate algorithms are generally not suited for incremental updates (i.e., updating with incremental additions of data). 
     In contrast to approximate algorithms, an exact inference obtains the true posterior distribution because it gives the closed form of P(R i |D). Therefore, the inference CCM described herein should be precise. Consider U click chains of maximum length M, where there are N total distinct documents in the U click chains. Each CCM is query-dependent, so N≈cM&lt;&lt;UM, where c is a constant. Assuming a conservative case of M=10 and N=100, then consider the following. A CCM stores a (2M+2)×N integer matrix, so a CCM for each query takes 8K memory. If there are 1 million queries, all the CCMs can be stored in the memory of a regular desktop (˜8 gigabits). Furthermore, in view of the closed form, during training process, the query click log can be scanned to memory once and increment the corresponding count in at most two cells for each click chain. The training time may be in linear proportion to the number of click chains (training data) available. Also, when new click chain data is to be incorporated, the model may be updated simply by incrementing the corresponding count in the same way as model training. Finally, the training and model update can be easily distributed to multiple machines; since it involves only incremental updating. Consequently, a MapReduce (described elsewhere) infrastructure may be avoided. 
     Problem Definition 
     This section sets forth a formal definition of the problem of inferring document relevance from query click logs. When a search user submits a query q to a particular search engine, a list of ranked documents D={d 1 , d 2 , . . . , d M } is returned. Based on the assumption that the first search engine result page (SERP) usually includes the top-10 documents (i.e., URLs), it is may be assumed that M=10. After examining the results D, the user may choose to click any document among D. A resulting click log entry may be generated and logged. The click log entry may be of the form C={c 1 , c 2 , . . . , c m }, where c i  is set to 1 if d i  is clicked, and 0 otherwise (i.e., if the i-th document is clicked, the i-th c is set to 1). Given a set of U click log entries from U users for the same SERP D, the problem of inferring document relevance may be stated as: what is the relevance of each d i  (i=1, 2, . . . ,M) with respect to the query q? 
     The above formulation of the problem is somewhat simplified and does not take into account cases where, as a search engine evolves, the SERP D may differ over time for the same query q. As will be seen after the following discussion of the basic CCM, which focuses on inference from multiple click log entries on the same SERP, the CCM can be extended to handle cases with different SERPs. 
     Basic CCM 
     User Behavioral Model 
       FIG. 4  shows search user behavior captured for a click chain model. The CCM leverages captured behavior of search users. Such behavior may be modeled in the following way. Assuming that a SERP displays summaries of the returned documents for a query, first, a web search user examines  140  the SERP in a top-down fashion, starting with the first document. Supposing the user is at the i-th position, i.e., examining the summary or abstract of d i , if  142  the user chooses not to click d i  (no click through) the user is said to have a probability of α 1  to see more results  144  (i.e., examine d i+1 ). However, if  142  the user clicks d i  and views  146  the landing page, then whether  148  the user will come back to the search results  150  and examine d i+1  now depends on how relevant d i  is. Suppose the user will examine d i+1  with probabilities of α 2  and α 3  if d i  is completely irrelevant and relevant, respectively. By default, we set α 1 =0.6, α 2 =0.8, and α 3 =0.3. Note that the exact values of α 1 , α 2 , and α 3  may depend on the particular data used. They may be derived from the data based on the maximum likelihood principle, for example. However, the values provided herein may be used as reasonable defaults for those who would avoid deriving the value from data. In general, it is desirable to have α 3 ≦α 1 ≦α 2 , because people are more likely to stop upon finding a relevant result (hence α 3  is the smallest), and because people who click a document but find it irrelevant are more likely to click the next document than those people who decide not to click the current document (hence α 1 ≦α 2 ). 
       FIG. 5  shows a graphical model  158  representation of the CCM. Random variable S i    160  (ranging from 0 to 1) denotes the relevance of doc d i , and Bernoulli variables E iu    162  and C iu    164  indicate whether the d i  is examined and clicked by user u, respectively. The following explanation will omit subscript u for clarity where there is no ambiguity. All the C i  variables  164  are observed from the click log, while the other variables (E i  and S i ) are hidden variables whose posterior distribution are ultimately to be inferred. While  FIG. 5  shows the dependencies, the set of conditional distributions are specified as follows: 
     No examination no click: P(C i =1|E i =0)=0; 
     Click or not depends on relevance: P(C 1 =1|E 1 =1, S i )=S i ; 
     Sequential examination: P(E i+1 =1|E i =0)=0; 
     Continue examination without click: P(E i+1 =1|E i =1, C i =0)=α 1 ; and 
     Continue examination with click: P(E i+1 =1|E i =1, C i =1, S i )=α 2 (1−S i )+α 3 S i . 
     To complete the model specification, the following priors are placed on P(E i ) and S i &#39;s:
 
 P ( E   1 =1)=1   (1),
 
 p ( S   i )=   [0,1] ( S   i )  i= 1, 2,   (2).
 
Equation 1 implies that every user will examine the first doc in the SERP, and Equation 2 reflects placement of a uniform prior on each S i where   is the indicator function.
 
     It should be noted that in the model specification, a limit was not put on the length of the chain structure. Instead the chain is allowed to go to infinity, while the probability of examining and clicking a page diminishes exponentially with its rank. 
     How to perform page relevance inference and parameter estimation for infinite chain length is described further below. If a finite chain length M is needed for practical reasons, it is possible to let variable E M+1 =0—which renders E j =C j =0(j&gt;M)—and adjust the inference formulae accordingly. 
     In the following subsection, the exact inference algorithm on CCM is elaborated, and its efficiency and scalability is theoretically proven. 
     Exact Inference on CCM 
     A central problem of model inference on a CCM is how to compute the posterior of the S i &#39;s, namely, P(S i |C 1:U ), given the observed click log entries C 1:U  from U users. Through a direct application of Bayes&#39; Theorem, the following equation may be derived:
 
 p ( S   i   |C   1:U )∝ p ( S   i )Π u=1   U    P ( C   |S   i )   (3)
 
where independence between click log entries is assumed. Because the prior p(S i ) is already known, P(C u |S i ) or P(C|S i ) need only be computed when the superscript is safely dropped. Unfortunately, computing P(C|S i ) for the graphical structure shown in  FIG. 5  in general may not be analytically trackable as it might involve taking the sum (or integral, for continuous variables) over the other hidden variables. Therefore, approximate algorithms have been previously applied.
 
     The inventors alone have observed several properties of the conditional probability of CCM, which may help to understand the feasibility of using a sum or integral approach. 
     1. If C j =1 for some j, then ∀i≦j, E i =1. 
     2. If E j =0 for some j, then ∀i≧j, E i =0, C i =0. 
     3. If E i =1, C i =0, then P(E i+1 |E i , C i , S i )=α i   E     i+1    (1−α 1 ) 1−E     i+1    does not depend on S i . 
     Property 1 is that all the documents up to the last clicked one (if any) are examined, in which case, for each document before the last click position, the Markov blanket of its relevance variable S contains at most three variables. Property 2 is that if a page is not examined, the search session terminates and there is no further examination or click. As a result, the complexity of summing over n E i &#39;s is linear to n, rather than exponential in the general case (because each E i =0 eliminates half of the possibility). Property 3 is a corollary from the definition of conditional probabilities P(E i+1 |E i , C i , S i ). This property allows reordering of E&#39;s and S&#39;s to simplify computation. 
     By virtue of the three properties and using the conditional probabilities specified in the “User Behavioral Model” section above, the unnormalized posterior P(C|S i ) may be presented in closed form in the following theorem. 
     
       
         
           
               
             
               
                 TABLE 1 
               
             
            
               
                   
               
               
                 Un-normalized Posterior of P(C|S i ) 
               
            
           
           
               
               
               
               
            
               
                 l exists 
                 Case 
                 Conditions 
                 Un-normalized Posterior 
               
               
                   
               
               
                 Yes 
                 1 
                 i &lt; l, C i  = 0 
                 1 − S i   
               
               
                   
                 2 
                 i &lt; l, C i  = 1 
                 S i (1 − (1 − α 3  / α 2 )S i ) 
               
               
                   
               
               
                   
                 3 
                 i = l 
                 
                   
                     
                       
                         
                           S 
                           i 
                         
                         ⁡ 
                         
                           ( 
                           
                             1 
                             + 
                             
                               
                                 
                                   
                                     α 
                                     2 
                                   
                                   - 
                                   
                                     α 
                                     3 
                                   
                                 
                                 
                                   2 
                                   - 
                                   
                                     α 
                                     1 
                                   
                                   - 
                                   
                                     α 
                                     2 
                                   
                                 
                               
                               ⁢ 
                               
                                 S 
                                 i 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                   
               
               
                   
                 4 
                 i &gt; l 
                 
                   
                     
                       
                         1 
                         - 
                         
                           
                             2 
                             
                               1 
                               + 
                               
                                 
                                   
                                     6 
                                     - 
                                     
                                       3 
                                       ⁢ 
                                       
                                         α 
                                         1 
                                       
                                     
                                     - 
                                     
                                       α 
                                       2 
                                     
                                     - 
                                     
                                       2 
                                       ⁢ 
                                       
                                         α 
                                         3 
                                       
                                     
                                   
                                   
                                     
                                       ( 
                                       
                                         1 
                                         - 
                                         
                                           α 
                                           1 
                                         
                                       
                                       ) 
                                     
                                     ⁢ 
                                     
                                       ( 
                                       
                                         
                                           α 
                                           2 
                                         
                                         + 
                                         
                                           2 
                                           ⁢ 
                                           
                                             α 
                                             3 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     ( 
                                     
                                       2 
                                       
                                         α 
                                         1 
                                       
                                     
                                     ) 
                                   
                                   
                                     
                                       ( 
                                       
                                         i 
                                         - 
                                         l 
                                       
                                       ) 
                                     
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ⁢ 
                           
                             S 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                   
               
               
                 No 
                 5 
                 i = 1 
                 1 − S i   
               
               
                   
               
               
                   
                 6 
                 i = 1 
                 
                   
                     
                       
                         1 
                         - 
                         
                           
                             2 
                             
                               1 
                               + 
                               
                                 
                                   ( 
                                   
                                     2 
                                     / 
                                     
                                       α 
                                       1 
                                     
                                   
                                   ) 
                                 
                                 
                                   i 
                                   - 
                                   1 
                                 
                               
                             
                           
                           ⁢ 
                           
                             S 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                   
               
            
           
         
       
     
     Theorem 1 (Un-normalized Posterior). The un-normalized posterior P(C|S i ) under priors in Equations 1 and 2 can be broken down to 6 cases as shown in Table 1, depending on the observed value of C i  and the distance between i and the last click position if any. 
     Proof of Theorem 1 will now follow for each of the 6 cases in Table 1. With respect to each case, Property 1 informs that it is helpful to identify the last click position I=arg max j  {C j =1}, so that all the E i =0 (i≦I). Each of the 6 cases are now discussed. 
     Case 1, i&lt;I, C i =0: By property 1, E i =1, E i+1 =1. Moreover, P(E i+1 =1|E i =1, C=0, S i )=α 1  does not depend on S i . Since any constant with respect to S i  can be ignored, therefore
 
 P ( C′|S   i ) ∝  P ( C   i =0| E   i =1,  S   i ) P ( E   i+1 =1| E   i =1,  C   i =0,  S   i )=(1− S   i )α 1  ∝ 1− s   i    (4).
 
     Case 2, i&lt;I, C i =1: By property 1, E i =1, E i+1 =1, the Markov blanket of S i  consists of C i , E i  and E i+1 . 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               C 
                               ❘ 
                               
                                 S 
                                 i 
                               
                             
                             ) 
                           
                         
                         ∝ 
                           
                         ⁢ 
                         
                           
                             P 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     C 
                                     i 
                                   
                                   = 
                                   
                                     
                                       1 
                                       ❘ 
                                       
                                         E 
                                         i 
                                       
                                     
                                     = 
                                     1 
                                   
                                 
                                 , 
                                 
                                   S 
                                   i 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             P 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     E 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   = 
                                   
                                     
                                       1 
                                       ❘ 
                                       
                                         E 
                                         i 
                                       
                                     
                                     = 
                                     1 
                                   
                                 
                                 , 
                                 
                                   
                                     C 
                                     i 
                                   
                                   = 
                                   1 
                                 
                                 , 
                                 
                                   S 
                                   i 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             
                               S 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     α 
                                     2 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       1 
                                       - 
                                       
                                         S 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     α 
                                     3 
                                   
                                   ⁢ 
                                   
                                     S 
                                     i 
                                   
                                 
                               
                               ) 
                             
                           
                           · 
                         
                       
                     
                   
                   
                     
                       
                         ∝ 
                           
                         ⁢ 
                         
                           
                             S 
                             i 
                           
                           ⁡ 
                           
                             ( 
                             
                               1 
                               - 
                               
                                 
                                   ( 
                                   
                                     1 
                                     - 
                                     
                                       
                                         α 
                                         3 
                                       
                                       / 
                                       
                                         α 
                                         2 
                                       
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   S 
                                   i 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     Case 3, i=I: By Property 1, the Markov blanket of S i  does not contain any variable before position i, and also it is known that C i =1, E i =1 and ∀j&gt;i, C j =0. The sum/integration is taken over all the E, S variables and can be performed as follows: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               C 
                               ❘ 
                               
                                 S 
                                 i 
                               
                             
                             ) 
                           
                         
                         ∝ 
                           
                         ⁢ 
                         
                           
                             P 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     C 
                                     i 
                                   
                                   ❘ 
                                   
                                     E 
                                     i 
                                   
                                 
                                 , 
                                 
                                   S 
                                   i 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             p 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     C 
                                     
                                       &gt; 
                                       i 
                                     
                                   
                                   ❘ 
                                   
                                     C 
                                     i 
                                   
                                 
                                 , 
                                 
                                   E 
                                   i 
                                 
                                 , 
                                 
                                   S 
                                   i 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             P 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     C 
                                     i 
                                   
                                   = 
                                   
                                     
                                       1 
                                       ❘ 
                                       
                                         E 
                                         i 
                                       
                                     
                                     = 
                                     1 
                                   
                                 
                                 , 
                                 
                                   S 
                                   i 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 
                                   E 
                                   j 
                                 
                                 &gt; 
                                 i 
                               
                               
                                   
                               
                             
                             ⁢ 
                             
                               
                                 ∫ 
                                 
                                   S 
                                   
                                     j 
                                     &gt; 
                                     i 
                                   
                                 
                                 
                                     
                                 
                               
                               ⁢ 
                               
                                 
                                   ∏ 
                                   
                                     j 
                                     &gt; 
                                     i 
                                   
                                   
                                       
                                   
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   P 
                                   ( 
                                   
                                     
                                       
                                         E 
                                         j 
                                       
                                       ❘ 
                                       
                                         E 
                                         
                                           j 
                                           - 
                                           1 
                                         
                                       
                                     
                                     , 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                               
                             ⁢ 
                             
                               
                                 C 
                                 
                                   j 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 S 
                                 
                                   j 
                                   - 
                                   1 
                                 
                               
                             
                             ) 
                           
                           · 
                           
                             p 
                             ⁡ 
                             
                               ( 
                               
                                 S 
                                 j 
                               
                               ) 
                             
                           
                         
                         ⁢ 
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               
                                 
                                   C 
                                   j 
                                 
                                 ❘ 
                                 
                                   E 
                                   j 
                                 
                               
                               , 
                               
                                 S 
                                 j 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             S 
                             i 
                           
                           · 
                           
                             { 
                             
                               
                                 
                                   P 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           E 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         = 
                                         
                                           
                                             0 
                                             ❘ 
                                             
                                               E 
                                               i 
                                             
                                           
                                           = 
                                           1 
                                         
                                       
                                       , 
                                       
                                         
                                           C 
                                           i 
                                         
                                         = 
                                         1 
                                       
                                       , 
                                       
                                         S 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                                 · 
                                 1 
                               
                               + 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             P 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     E 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   = 
                                   
                                     
                                       1 
                                       ❘ 
                                       
                                         E 
                                         i 
                                       
                                     
                                     = 
                                     1 
                                   
                                 
                                 , 
                                 
                                   
                                     C 
                                     i 
                                   
                                   = 
                                   1 
                                 
                                 , 
                                 
                                   S 
                                   i 
                                 
                               
                               ) 
                             
                           
                           · 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 ∫ 
                                 0 
                                 1 
                               
                               ⁢ 
                               
                                 
                                   p 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       S 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   P 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           C 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         = 
                                         
                                           
                                             0 
                                             ❘ 
                                             
                                               E 
                                               
                                                 i 
                                                 + 
                                                 1 
                                               
                                             
                                           
                                           = 
                                           1 
                                         
                                       
                                       , 
                                       
                                         S 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   ⅆ 
                                   
                                     S 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           · 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           { 
                           
                             
                               
                                 P 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       
                                         E 
                                         
                                           i 
                                           + 
                                           2 
                                         
                                       
                                       = 
                                       
                                         
                                           0 
                                           ❘ 
                                           
                                             E 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                         
                                         = 
                                         1 
                                       
                                     
                                     , 
                                     
                                       
                                         C 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       = 
                                       0 
                                     
                                   
                                   ) 
                                 
                               
                               · 
                               1 
                             
                             + 
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             P 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     E 
                                     
                                       i 
                                       + 
                                       2 
                                     
                                   
                                   = 
                                   
                                     
                                       1 
                                       ❘ 
                                       
                                         E 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                     
                                     = 
                                     1 
                                   
                                 
                                 , 
                                 
                                   
                                     C 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   = 
                                   0 
                                 
                               
                               ) 
                             
                           
                           · 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 ∫ 
                                 0 
                                 1 
                               
                               ⁢ 
                               
                                 
                                   p 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       S 
                                       
                                         i 
                                         + 
                                         2 
                                       
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   P 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           C 
                                           
                                             i 
                                             + 
                                             2 
                                           
                                         
                                         = 
                                         
                                           
                                             0 
                                             ❘ 
                                             
                                               E 
                                               
                                                 i 
                                                 + 
                                                 2 
                                               
                                             
                                           
                                           = 
                                           1 
                                         
                                       
                                       , 
                                       
                                         S 
                                         
                                           i 
                                           + 
                                           2 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   ⅆ 
                                   
                                     S 
                                     
                                       i 
                                       + 
                                       2 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           · 
                         
                       
                     
                   
                   
                     
                       
                         
                             
                           ⁢ 
                           
                             { 
                             … 
                             } 
                           
                           } 
                         
                         } 
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             S 
                             i 
                           
                           ( 
                           
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   
                                     α 
                                     2 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       1 
                                       - 
                                       
                                         S 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     α 
                                     3 
                                   
                                   ⁢ 
                                   
                                     S 
                                     i 
                                   
                                 
                               
                               ) 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     
                                       α 
                                       2 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       
                                         1 
                                         - 
                                         
                                           S 
                                           i 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       α 
                                       3 
                                     
                                     ⁢ 
                                     
                                       S 
                                       i 
                                     
                                   
                                 
                                 ) 
                               
                               · 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             1 
                             2 
                           
                           · 
                           
                             ( 
                             
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     α 
                                     1 
                                   
                                 
                                 ) 
                               
                               + 
                               
                                 
                                   α 
                                   1 
                                 
                                 · 
                                 
                                   1 
                                   2 
                                 
                                 · 
                                 
                                   ( 
                                   … 
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             S 
                             i 
                           
                           ( 
                           
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   
                                     α 
                                     2 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       1 
                                       - 
                                       
                                         S 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     α 
                                     3 
                                   
                                   ⁢ 
                                   
                                     S 
                                     i 
                                   
                                 
                               
                               ) 
                             
                             + 
                             
                               ( 
                               
                                 
                                   
                                     α 
                                     2 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       1 
                                       - 
                                       
                                         S 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     α 
                                     3 
                                   
                                   ⁢ 
                                   
                                     S 
                                     i 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             1 
                             2 
                           
                           · 
                           
                             
                               1 
                               - 
                               
                                 α 
                                 1 
                               
                             
                             
                               1 
                               - 
                               
                                 
                                   α 
                                   1 
                                 
                                 / 
                                 2 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                         ∝ 
                           
                         ⁢ 
                         
                           
                             S 
                             i 
                           
                           ⁡ 
                           
                             ( 
                             
                               1 
                               + 
                               
                                 
                                   
                                     
                                       α 
                                       2 
                                     
                                     - 
                                     
                                       α 
                                       3 
                                     
                                   
                                   
                                     2 
                                     - 
                                     
                                       α 
                                       1 
                                     
                                     - 
                                     
                                       α 
                                       2 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   S 
                                   i 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     Case 4, i&gt;I: Now the result will be a function of k=i−I—(the offset of the page from the last click position). The approach to sum over S and E variables is similar to Case 3, but with integration of the outmost S i  and keep a S i  inside without the integration. S will be used to replace S i  in the following equation for easier reading: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             P 
                             
                               
                                 
                                   C 
                                   l 
                                 
                                 = 
                                 1 
                               
                               , 
                               
                                 
                                   i 
                                   - 
                                   l 
                                 
                                 = 
                                 k 
                               
                             
                           
                           ⁡ 
                           
                             ( 
                             
                               C 
                               ❘ 
                               
                                 S 
                                 i 
                               
                             
                             ) 
                           
                         
                         ∝ 
                           
                         ⁢ 
                         
                           { 
                           
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 ∫ 
                                                 0 
                                                 1 
                                               
                                               ⁢ 
                                               
                                                 S 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         
                                                           
                                                             α 
                                                             2 
                                                           
                                                           ⁡ 
                                                           
                                                             ( 
                                                             
                                                             1 
                                                             - 
                                                             S 
                                                             
                                                             ) 
                                                           
                                                         
                                                         - 
                                                         
                                                           α 
                                                           3 
                                                         
                                                       
                                                       ) 
                                                     
                                                     ⁢ 
                                                     S 
                                                   
                                                   ) 
                                                 
                                               
                                             
                                             + 
                                             
                                               
                                                 ( 
                                                 
                                                   
                                                     
                                                       α 
                                                       2 
                                                     
                                                     ⁡ 
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         S 
                                                       
                                                       ) 
                                                     
                                                   
                                                   + 
                                                   
                                                     α 
                                                     3 
                                                   
                                                 
                                                 ) 
                                               
                                               ⁢ 
                                               S 
                                             
                                           
                                           ) 
                                         
                                         · 
                                         
                                           ( 
                                           
                                             1 
                                             - 
                                             
                                               S 
                                               i 
                                             
                                           
                                           ) 
                                         
                                         · 
                                         
                                           
                                             1 
                                             - 
                                             
                                               α 
                                               1 
                                             
                                           
                                           
                                             1 
                                             - 
                                             
                                               
                                                 α 
                                                 1 
                                               
                                               / 
                                               2 
                                             
                                           
                                         
                                       
                                       ) 
                                     
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       ⅆ 
                                       S 
                                     
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     k 
                                   
                                   = 
                                   1 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 ∫ 
                                                 0 
                                                 1 
                                               
                                               ⁢ 
                                               
                                                 S 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         
                                                           
                                                             α 
                                                             2 
                                                           
                                                           ⁡ 
                                                           
                                                             ( 
                                                             
                                                             1 
                                                             - 
                                                             S 
                                                             
                                                             ) 
                                                           
                                                         
                                                         - 
                                                         
                                                           α 
                                                           3 
                                                         
                                                       
                                                       ) 
                                                     
                                                     ⁢ 
                                                     S 
                                                   
                                                   ) 
                                                 
                                               
                                             
                                             + 
                                             
                                               
                                                 ( 
                                                 
                                                   
                                                     
                                                       α 
                                                       2 
                                                     
                                                     ⁡ 
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         S 
                                                       
                                                       ) 
                                                     
                                                   
                                                   + 
                                                   
                                                     α 
                                                     3 
                                                   
                                                 
                                                 ) 
                                               
                                               ⁢ 
                                               S 
                                             
                                           
                                           ) 
                                         
                                         · 
                                         
                                           ( 
                                           
                                             
                                               
                                                 
                                                   1 
                                                   - 
                                                   
                                                     α 
                                                     1 
                                                   
                                                 
                                                 2 
                                               
                                               ⁢ 
                                               
                                                 
                                                   ∑ 
                                                   
                                                     j 
                                                     = 
                                                     0 
                                                   
                                                   
                                                     k 
                                                     - 
                                                     2 
                                                   
                                                 
                                                 ⁢ 
                                                 
                                                   
                                                     ( 
                                                     
                                                       
                                                         α 
                                                         1 
                                                       
                                                       / 
                                                       2 
                                                     
                                                     ) 
                                                   
                                                   j 
                                                 
                                               
                                             
                                             + 
                                             
                                               
                                                 
                                                   ( 
                                                   
                                                     
                                                       α 
                                                       1 
                                                     
                                                     / 
                                                     2 
                                                   
                                                   ) 
                                                 
                                                 
                                                   k 
                                                   - 
                                                   1 
                                                 
                                               
                                               ⁢ 
                                               
                                                 ( 
                                                 
                                                   1 
                                                   - 
                                                   
                                                     S 
                                                     i 
                                                   
                                                 
                                                 ) 
                                               
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               
                                                 
                                                   1 
                                                   - 
                                                   
                                                     α 
                                                     1 
                                                   
                                                 
                                                 
                                                   1 
                                                   - 
                                                   
                                                     
                                                       α 
                                                       1 
                                                     
                                                     / 
                                                     2 
                                                   
                                                 
                                               
                                             
                                           
                                           ) 
                                         
                                       
                                       ) 
                                     
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       ⅆ 
                                       S 
                                     
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     k 
                                   
                                   &gt; 
                                   1 
                                 
                               
                             
                           
                           ⁢ 
                           
                               
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             
                               = 
                                 
                               ⁢ 
                               
                                 
                                   
                                     ∫ 
                                     0 
                                     1 
                                   
                                   ⁢ 
                                   
                                     S 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           ( 
                                           
                                             1 
                                             - 
                                             
                                               
                                                 α 
                                                 2 
                                               
                                               ⁡ 
                                               
                                                 ( 
                                                 
                                                   1 
                                                   - 
                                                   S 
                                                 
                                                 ) 
                                               
                                             
                                             - 
                                             
                                               α 
                                               3 
                                             
                                           
                                           ) 
                                         
                                         ⁢ 
                                         S 
                                       
                                       ) 
                                     
                                   
                                 
                                 + 
                                 
                                   
                                     ( 
                                     
                                       
                                         
                                           α 
                                           2 
                                         
                                         ⁡ 
                                         
                                           ( 
                                           
                                             1 
                                             - 
                                             S 
                                           
                                           ) 
                                         
                                       
                                       + 
                                       
                                         α 
                                         3 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   S 
                                 
                               
                             
                             ) 
                           
                           · 
                           
                               
                           
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     α 
                                     1 
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   1 
                                   + 
                                   
                                     
                                       ( 
                                       
                                         
                                           α 
                                           1 
                                         
                                         / 
                                         2 
                                       
                                       ) 
                                     
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                   - 
                                   
                                     2 
                                     ⁢ 
                                     
                                       
                                         ( 
                                         
                                           
                                             α 
                                             1 
                                           
                                           / 
                                           2 
                                         
                                         ) 
                                       
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                     ⁢ 
                                     
                                       S 
                                       i 
                                     
                                   
                                 
                               
                             
                             
                               2 
                               - 
                               
                                 α 
                                 1 
                               
                             
                           
                         
                         ⁢ 
                         
                             
                         
                       
                     
                   
                   
                     
                       
                         ∝ 
                           
                         ⁢ 
                         
                           1 
                           - 
                           
                               
                           
                           ⁢ 
                           
                             
                               2 
                               
                                 1 
                                 + 
                                 
                                   
                                     
                                       6 
                                       - 
                                       
                                         3 
                                         ⁢ 
                                         
                                           α 
                                           1 
                                         
                                       
                                       - 
                                       
                                         α 
                                         2 
                                       
                                       - 
                                       
                                         2 
                                         ⁢ 
                                         
                                           α 
                                           3 
                                         
                                       
                                     
                                     
                                       
                                         ( 
                                         
                                           1 
                                           - 
                                           
                                             α 
                                             1 
                                           
                                         
                                         ) 
                                       
                                       ⁢ 
                                       
                                         ( 
                                         
                                           
                                             α 
                                             2 
                                           
                                           + 
                                           
                                             2 
                                             ⁢ 
                                             
                                               α 
                                               3 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       ( 
                                       
                                         2 
                                         / 
                                         
                                           α 
                                           1 
                                         
                                       
                                       ) 
                                     
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                             ⁢ 
                             
                               S 
                               i 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ( 
                               
                                 k 
                                 ≥ 
                                 1 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     Case 5, i=1 (No click): The difference between i=1 and i&gt;1 is that E 1 =1 is known, therefore P(E 2 |E 1 =1, C 1 =0) does not depend on S 1 , and
 
 P ( C|S   i )∝  P ( C   i =0| E   i =1,  S   i )=1− S   i    (8)
 
     Case 6, i=1: This is similar to Case 4, but the derivation is simpler and α 2 , α 3  are no longer in the formula: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             P 
                             
                               
                                 
                                   C 
                                   l 
                                 
                                 = 
                                 0 
                               
                               , 
                               
                                 
                                   i 
                                   - 
                                   l 
                                 
                                 = 
                                 k 
                               
                             
                           
                           ⁡ 
                           
                             ( 
                             
                               C 
                               ❘ 
                               
                                 S 
                                 i 
                               
                             
                             ) 
                           
                         
                         ⁢ 
                           
                         ∝ 
                         
                           
                             ∫ 
                             0 
                             1 
                           
                           ⁢ 
                           
                             
                               ( 
                               
                                 1 
                                 - 
                                 S 
                               
                               ) 
                             
                             ⁢ 
                             
                               ⅆ 
                               
                                 S 
                                 ( 
                                 
                                   
                                     
                                       ( 
                                       
                                         1 
                                         - 
                                         
                                           α 
                                           1 
                                         
                                       
                                       ) 
                                     
                                     · 
                                     
                                       
                                         ∑ 
                                         
                                           j 
                                           = 
                                           0 
                                         
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                       ⁢ 
                                       
                                         
                                           ( 
                                           
                                             
                                               α 
                                               1 
                                             
                                             / 
                                             2 
                                           
                                           ) 
                                         
                                         j 
                                       
                                     
                                   
                                   + 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                                
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   α 
                                   1 
                                 
                                 / 
                                 2 
                               
                               ) 
                             
                             
                               k 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               α 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   S 
                                   i 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               1 
                               - 
                               
                                 α 
                                 1 
                               
                             
                             
                               1 
                               - 
                               
                                 
                                   α 
                                   1 
                                 
                                 / 
                                 2 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           ∝ 
                           
                             
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     α 
                                     1 
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 
                                   1 
                                   - 
                                   
                                     
                                       ( 
                                       
                                         
                                           α 
                                           1 
                                         
                                         / 
                                         2 
                                       
                                       ) 
                                     
                                     k 
                                   
                                 
                                 
                                   1 
                                   - 
                                   
                                     
                                       α 
                                       1 
                                     
                                     / 
                                     2 
                                   
                                 
                               
                             
                             + 
                             
                               2 
                               ⁢ 
                               
                                 
                                   ( 
                                   
                                     
                                       α 
                                       1 
                                     
                                     / 
                                     2 
                                   
                                   ) 
                                 
                                 k 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     S 
                                     i 
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 
                                   1 
                                   - 
                                   
                                     α 
                                     1 
                                   
                                 
                                 
                                   1 
                                   - 
                                   
                                     
                                       α 
                                       1 
                                     
                                     / 
                                     2 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           ∝ 
                           
                             1 
                             - 
                             
                               
                                 2 
                                 
                                   1 
                                   + 
                                   
                                     
                                       ( 
                                       
                                         2 
                                         / 
                                         
                                           α 
                                           1 
                                         
                                       
                                       ) 
                                     
                                     k 
                                   
                                 
                               
                               ⁢ 
                               
                                 S 
                                 i 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   k 
                                   ≥ 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     Theorem 1 presents the closed form of the un-normalized posterior P(C|S i ), and interestingly, each of the cases can be written in the form of S i   C     i    (1−βS i ) where β is a case-dependent coefficient and may depend on the distance (i−I) as well. With this theorem, it is straightforward to extend to P(C 1:U |S i ), and finally use it to compute the un-normalized P(S i |C 1:U ) using Equation 3. 
     Once the un-normalized P(S i |C 1:U ) is computed, it is straightforward to normalize it, and to calculate a certain statistical measure as an indicator of the document d i  being perceived as relevant to the user with respect to the query q. For example, the mean of P(S i |C 1:U ) can be taken as the relevance indicator, and its inverse standard deviation (precision) can be taken as confidence. 
     Theorem 1 also makes it clear as to how to update the posterior once a new click log entry C U+1  comes. First check if there is any click in this entry: if yes, for each position i, determine which of the first 4 cases applies and get the corresponding term T by checking the relationship between i and I, and the value of C i  if i&lt;I. Then, multiply the already-computed posterior P(S i |C 1:U ) with T, normalize the product, and compute the mean and variance as the indicator of U+1 users&#39; perceived relevance. To further illustrate the process of posterior update, consider an example in the following subsection. The example will also help understand which documents are promoted or demoted given a click chain. 
     
       
         
           
               
             
               
                 TABLE 2 
               
             
            
               
                   
               
               
                 Illustrative Example 
               
            
           
           
               
               
               
            
               
                   
                 Impression 
                 Click Chain 
               
               
                   
                   
               
            
           
           
               
               
               
               
            
               
                   
                 I 1   
                 d 1 , d 2 , d 3 , d 4 , d 5   
                 XOXOO 
               
               
                   
                 I 2   
                 d 1 , d 3 , d 2 , d 4 , d 5   
                 OXOOO 
               
               
                   
                 I 3   
                 d 1 , d 3 , d 2 , d 4 , d 5   
                 OOOOO 
               
               
                   
                   
               
            
           
         
       
     
     Consider an example to illustrate the computability of CCM. Let M=5 and assume the three SERP impressions shown in Table 2, where ‘o’ and ‘x’ stand for ‘skip’ and ‘click’, respectively. Notice that d 3  moves to the second place in I 2 . This, in the first place, simulates the instability of SERPs and, in the second place, considers what happens when CCM is deployed: the ranking of the top-M documents could change across time. 
     With the default parameter setting α 1 =0.6, α 2 =0.8, α 3 =0.3, Table 1 is materialized as shown in Table 3. With M=5, there are at most four terms needed for cases 4 and 6. These terms reveal how the CCM promotes and demotes the relevance of each document based on whether it is clicked or not and its relative position to others. 
     
       
         
           
               
             
               
                 TABLE 3 
               
             
            
               
                   
               
               
                 Instantiated Un-normalized Posterior of P(C|S i ) 
               
            
           
           
               
               
               
               
            
               
                 l exists 
                 Case 
                 Conditions 
                 Un-normalized Posterior 
               
               
                   
               
               
                 Yes 
                 1 
                 i &lt; l, C i  = 0 
                 1 − S i   
               
               
                   
                 2 
                 i &lt; l, C i  = 1 
                 S i (1 − .63S i ) 
               
               
                   
                 3 
                 i = l 
                 S i  (1 + .83S i ) 
               
               
                   
                 4 
                 i &gt; l 
                 1 − .33S i , 1 − .11S i , 1 − .04S i , 1 − .01S i   
               
               
                 No 
                 5 
                 i = 1 
                 1 − S i   
               
               
                   
                 6 
                 i &gt; 1 
                 1 − .46S i , 1 − .17S i , 1 − .05S i , 1 − .02S i   
               
               
                   
               
            
           
         
       
     
     Note that non-clicked documents are demoted: (1−βS) (β&gt;0) means demotion because it suppresses more for larger S once it is multiplied to the existing posterior. A larger β results in a more severe penalty. Based on the previous point, skipped documents before the last click position are penalized the most. The first document for whole-page-no-click is also most penalized because the P(E 1 =1)=1 is adopted as the prior. Furthermore, documents after the last click position are penalized less and less, because each of them has a decreasing probability of being examined, and since there is no click, the negative effect on relevance is weaker and weaker. As can be seen, the update becomes roughly (1−0.01S), four positions after the last click. Case 6 is similar to Case 4. Finally, consider  FIG. 6 .  FIG. 6  shows a probability distribution function (PDF) for Case 2  200  (non-last-clicked document) and a PDF for Case 3  202  (last-clicked document). As can be seen, clicked documents are promoted (Case 2), and the last-clicked document is promoted the most (Case 3). 
     Understanding which documents the CCM promotes and demotes can help in fine tuning of the model and adapting it to practice. For example, if practice suggests that skipped documents before last click position are penalized too much, or the last clicked document is promoted too much, the CCM can be adjusted by introducing corresponding priors. 
     How the posterior of d 3  is updated with each impression and click chain is now discussed.  FIG. 7  shows how the normalized posterior of d 3  evolves at start  220 , after I 1    222 , after I 2 ,  224  and after I 3    226 .  FIG. 8  shows how the normalized posteriors for d 1 , d 2 , d 4 , and d 5  evolve from start  240 , to I 1    242 , to I 2    244 , and to I 3    246 . Without any click data, the probability for d 3  to be relevant is uniform, which is the uninformative prior of  FIG. 8 , PDF (m) (the “Start” graph of d 5 ). In I 1 , it is known that d 3  is the last clicked position, and falls into Case 3, so its un-normalized posterior becomes s(1+0.83s), as shown in  FIG. 8 , PDF (n) (the “After I 1 ” graph of d 5 ). This reveals that d 3  is more likely to be relevant (μ3=0.6964 instead of 0.5000). But, since a single click chain cannot be completely affirmative, its standard deviation σ3=0.2252 reveals this point. Similarly, in I 2 , d 3  is again the last clicked document, so its un-normalized posterior is s2(1+0.83s)2 with its normalized distribution plotted in  FIG. 8 , PDF (o). Finally, in I 3 , which has no clicks, d 3  falls into Case 6 because it is not the first document, and hence gets the (1−0.46s) term. So the posterior of d 3  after three click chains becomes s 2 (1+0.83s) 2 (1−0.46s), as plotted in  FIG. 8 , PDF (p). The mean (0.7643) and standard deviation (0.1848) of d 3  can be then taken as indicators of d 3 &#39;s relevance. 
     Following the same route, it is possible to figure out the posterior for other documents. Table 4 lists the posterior updating process for each document 
                     TABLE 4                  un-normalized posterior                                 Posterior   Initial   After I 1     After I 2     After I 3                 P(S 1 )   1   s(1 − .63s)   s(1 − .63s)(1 − s)   s(1 − .63s)(1 − s) 2         P(S 2 )   1   (1 − s)   (1 − s)(1 − .33s)   (1 − s)(1 − .33s)(1 −                       .17s)       P(S 3 )   1   s(1 + .83s)   s 2 (1 + .83s) 2     s 2 (1 + .83s) 2 (1 −                       .46s)       P(S 4 )   1   (1 − .33s)   (1 − .33s)(1 − .11s)   (1 − .33s)(1 −                       .11s)(1 − .05s)       P(S 5 )   1   (1 − .11s)   (1 − .11s)(1 − .04s)   (1 − .11s)(1 −                       .04s)(1 − .02s)                    
after each impression. Take d 1  for an example. It is Case 2 in I 1  (hence promoted), and Case 1 in I 2  (hence demoted), and Case 5 in I 3  (demoted again), ending up with the posterior s(1−0.63s)(1−s) 2 . The update process is plotted in  FIG. 8 . If μ-σ is used as the quantifier of relevance, the re-ranking would be d 3 , d 5 , d 1 , d 4 , d 2 . This is reasonable in that d 3  is promoted because it is the last clicked doc in I 1  and I 2  and d 2  is demoted because it is never clicked given the premium real estate. Although putting d 5  to the second place may not seem to make sense, this is actually a reasonable mechanism to test users&#39; taste (or possibly increase diversity): if d 5  is not clicked much, it will soon drop off. Any concern about the ranking instability can be eased because in practice the standard deviation will be used to control when to commit the re-ranking (e.g., only documents with σ≦  are re-ranked), and usually given large data, the ranking should be stable unless users&#39; interests really change, which invokes click pattern changes, and hence the re-ranking. In sum, the CCM tracks users&#39; click preferences, and adjusts ranking accordingly.
 
     Extensions to the CCM 
     The section above elaborates on the basic Click Chain Model, which assumes that the U click log entries are with respect to the same SERP, which often may not hold true in practice—for example, search engines are often updated and the selection and ranking of documents that match a given query may change as the search engine is updated. In this subsection, how to extend the basic CCM for some practical considerations is explained. 
     In practice, the SERP, even the first search result, can change from impression to impression across time, which seems to completely wrap out the CCM. But the basic CCM readily extends to practical SERPs, where previously unseen documents can climb into the top-M documents and previously seen documents can appear in different orders in different SERPs. 
     The capability of the CCM to handle such cases relies on the interpretation of S i : throughout the discussion above in the “BASIC CCM” section, nowhere was it mentioned that S i  is attached with the position i, but instead, S i  is associated with the document d i . Therefore, S i  denotes the relevance of d i , and travels with d i  if d i  moves around within or out of the top-M. In this way, the CCM can handle a variety of real-world click logs. Namely, given a click log entry, for each position i, find corresponding term based on Table 1, and multiply the term to the already-computed posterior of the document that appears in the i-th position in the click log entry. First, if the document is previously unseen, its (un-normalized) posterior is simply the term. Secondly, the derivation above in the “BASIC CCM” section is based on the priors described by Equations 1 and 2, but neither equation is essential to the CCM. For example, the prior P(E i =1)=1 can be waived if the first result is not always examined by users in certain applications. Or, different non-uniform priors can be imposed on S i &#39;s if needed. Finally, the CCM can be built for a set of semantically similar queries, instead of for each individual query. The idea is to equalize a set of queries, merge their click log entries and equalize documents if needed, and learn a CCM. This may make the CCM more robust and reduce the risk of data sparsity for rare tail queries. Note, however, that this approach could be sensitive to the quality of identifying equivalent queries and documents. 
     Experimental Results 
     Some experiments have been performed to probe the value of the CCM described herein. Consider specifically the problem of ClickBoost, i.e., how to re-rank the top documents based on user clicks. ClickBoost is described elsewhere. A common belief is that re-ranking in descending order of the number of clicks received by each document would be a good or even optimal approach (referred to herein as the “NumClick” approach), but experimentation shows that it is actually not true, and CCM-based re-ranking (ranking in descending order of the inferred document relevance) significantly outperforms the NumClick approach. Specifically, all the click chains of 10,118 unique queries were obtained (with query frequencies between 100 and 400) from a production click chain log. For each query, the first three quarter click chains were used to fit the model and evaluate the quality of the re-ranking by replaying the remaining one quarter click chains. Quality was measured by pSkip (described elsewhere). 
     Results showed that among the 10,118 queries, CCM won on 7,124 queries while the naive approach won on 143 queries, and the rest are ties (2,851 queries), which shows that CCM is significantly better than the NumClick approach, as indicated by a statistical test and as shown by these numbers. 
     Even in comparison with re-ranking based on pSkip (described elsewhere) and using pSkip as the quality measure—which disadvantages the CCM—the CCM still outperforms pSkip-based re-ranking. The CCM won on 3,760, and pSkip-ranking won 1,821, and the remaining 4,537 were ties, showing a statistically significant advantage. 
     The demonstrated benefit of CCM for the practical ClickBoost problem suggests applicability of the CCM to other practical problems that use relevance of documents to queries, or other terms. 
     CONCLUSION 
     Described above are approaches for using a CCM to infer relevancies of documents as perceived by users with respect to queries. By virtue of the CCM&#39;s solid theoretical foundation and promising computational properties, the CCM is efficient and scales easily to many real-world data processing problems, as discussed next. 
     The CCM may be used for automated fine tuning of a search engine. Top-part ranking can be automatically adjusted based on inferred user-perceived relevance from user clicks. The CCM may be used for adaptive search. When the meaning of a query changes across time, user click patterns also change, and based on inferred relevance, an adaptive search engine can be developed. The CCM may also improve search diversity. When a query has multiple meanings, users with different information needs will cast preference on different documents. Inferred relevance may bring up the most relevant documents for different information needs. The CCM may also help as a “judge of the judges”. Inferred first-party relevance judgment could be contrasted/reconciled with Human Relevance System (HRS) for improved quality. The CCM may be used to retrain a search ranker. Instead of training a search ranker based on third-party judgment (from HRS), a search ranker could be re-trained based on the inferred relevance, which reflects first-party judgments. The CCM may also be used for computing search quality metrics. Because a major component of user satisfaction is search relevance, the inferred relevance can be used to compose a search quality metric, which correlates with end users&#39; satisfaction. Search user modeling may also be performed using the CCM. Based on an assumption that users with the same/similar perception of a document&#39;s relevance are likely similar in nature, various downstream applications based on user modelings may be accomplished through inferred relevance. There are applications in Ad business as well; e.g., as a “judge of the judges”, for computing ad quality metrics, etc. 
     Embodiments and features discussed above can be realized in the form of information stored in volatile or non-volatile computer or device readable storage media. This is deemed to include at least media such as optical storage (e.g., CD-ROM), magnetic media, flash ROM, etc. The stored information can be in the form of machine executable instructions (e.g., compiled executable binary code), source code, bytecode, or any other information that can be used to enable or configure computing devices to perform the various embodiments discussed above. This is also deemed to include at least volatile memory such as RAM and/or virtual memory storing information such as CPU instructions during execution of a program carrying out an embodiment, as well as non-volatile media storing information that allows a program or executable to be loaded and executed. The embodiments and features can be performed on any type of computing device, including portable devices, workstations, servers, mobile wireless devices, and so on.