Mining User Dwell Time for Personalized Web Search Re-Ranking

1 Introduction and RelatedWork

In web search, personalized ranking can significantly improve user experiences, which has thus attracted a great deal of interest in both academia and industry. A personalized ranking method or algorithm needs to estimate individual users' interests over search result documents according to some types of user feedback. However, acquiring explicit user feedback to determine the relevance of a search result document to a web search query is not practical if not infeasible. In comparison, implicit user feedbacks, such as browsing and click history, and user dwell times over a document are more practical, which are most suitable for developing personalized web search algorithms and services, due to their uninstrusiveness in the user search process and the abundance of data available using the approach. In this paper, we propose a personalized webpage re-ranking algorithm through exploring a user's dwell times in his/her previous readings over individual documents. Based on them we then infer concept word level user dwell times for personalized search result re-ranking for the user.

1 This manuscript has been authored by UT-Battelle, LLC, under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes.

The closest related work to this paper is the personalized webpage ranking algorithm proposed in [Xu et al., 2008b], which measures a user's reading interest based on user attention time, i.e., user dwell time. However, their method represents user dwell times only at the level of individual documents, which could result in significant computational overheads when the number of documents a user has previously read is large. The lack of representation of user dwell times at a finer granularity also affects their algorithm's accuracy. In this paper, we address both issues by inferring concept word level user dwell times from originally captured document level user dwell times. Liu et al. [2002] built a personalized web search system by mapping user queries to multiple categories. Teevan et al. [2005] constructed a user interest model for personalized search from various types of search-related information, e.g., user submitted queries, browsed webpages, and personal emails. Sugiyama et al. [2004] understood user interest according to each user's personal needs in his/her previously searches. Kelly and Belkin [2004] studied the relationship between user interests and user dwell time, focusing on understanding task effects of treating display time as implicit feedback. Speretta and Gauch [2005] located multiword phrases to enhance the bag-of-words representation of a document for predicting a user's personal interest from the user's previous webpage access patterns. Dou et al. [2007] utilized five different personalized search approaches to perform searches over 12-day MSN query logs, and concluded that personalized searches cannot always outperform common web searches. They further pointed out that click entropy provides a good criterion for whether a query should be personalized. Unlike their algorithm, which mines browsing history for personalized web searches, our approach analyzes a user's past reading and search activities in terms of user dwell times for personalized re-ranking.

2 Mining User Dwell Time for Personalized Re-Ranking

2.1 Acquiring User Dwell Time

We implemented the customized web browser suggested in [Xu et al., 2008b] for acquiring user dwell time. In the upcoming sections, we will not distinguish between documents and webpages as they are treated the same in our method.

2.2 Representing a Document as a Collection of Concept Words

In our method, we represent each document Di previously read by a user uk, as a collection of concept words. We use this representation because we mine user dwell times at the concept word level in our method. Compared with [Xu et al., 2008b]'s approach, which represents user dwell times at the level of an entire document, our concept word level user dwell time representation makes the training samples more reusable. Given a document Di, we first extract its main content text using an HTML filter. In this step, we carry out several preprocessing substeps to remove non-content information such as tags, advertisements, website navigation bars, and redirection links from the webpage text using the method proposed in [Ntoulas et al., 2006]. For the remaining words, we check whether there is a corresponding definition page for the word in Wikipedia. If such a definition page exists, we recognize the word as a concept word. In this way, we can extract all the concept words contained in a document as well as each word's occurrence number. (The connection between concepts and Wikipedia articles has been intensively studied and well established in prior studies, e.g., [Gabrilovich and Markovitch, 2007].) Formally, we can represent Di as a collection of concept words, i.e., CV (Di) ≜ {(Cj, nj)|j = 1, 2, · · · , z(Di)}, where Cj is a concept word in Di, which occurs nj times, and z(Di) is the total number of concept words in Di.

2.3 Modeling Document Level User Dwell Time and Concept Word Level User Dwell Time

A Reduced Case

To quantitatively model the relationship between document level user dwell time and concept word level user dwell time, we first consider an extremely simplified case where the whole document consists of only one concept word, which may occur multiple times. Without loss of generality, we assume the concept word is Ci and the number of its occurrence in the document is ni. According to the cognitive neuroscience phenomenon of semantic satiation [Satiation, 2011], human brain has a fatigue mechanism where the more times a stimulus is repeatedly received by our brain in a short span of time, the less aroused our brain becomes. After a large number of exposures to the same stimulus, our brain may eventually become irresponsive to the stimulation for a certain period of time, where the period length depends on the frequency and each duration of the repeatedly exerted stimulus. Based on this study result from the cognitive science community, we introduce the following modified logistic sigmoid function to approximately model this saturation effect of our brain due to brain fatigue:

where ϑ(Ci, uk, 1) and ϑ(Ci, uk, ni) respectively represent the dwell times of the user uk due to the exposure of the concept word Ci for the first time and for the first ni times when reading a document. α1, α2 are modulating parameters that control the numerical characteristics of our modeled brain fatigue mechanism, whose determination will be discussed later.

The Full Case

Now we consider the general case where a document consists of multiple concept words of which some may occur multiple times. For a given document D, we assume it carries the concepts C1,C2, · · · ,Cz(D). We also denote the number of occurrences of the concept word Cj in D as nj. We order all the concept words according to the respective occurrence numbers of these words in a descending order, i.e., n1 ⩾ n2 ⩾ · · · ⩾ nz(D). In our modeling of the relationship between document level user dwell time and concept word level user dwell time, we introduce some auxiliary versions of the original document D where occurrences of certain concept words are removed. Let D̂i be the auxiliary version of the original document D where only occurrences of the first i concept words C1,C2, · · · ,Ci are retained. By this definition, D̂ z(D) is the original document D itself since the full set of concept words is retained; D̂1 is the auxiliary version of the original article D that only consists of occurrence of the first concept word C1, which is the simplified case examined above.

Let φ(uk,D̂i ) be the dwell time of the user uk over the auxiliary document version D̂i . We assume the dwell time of the user uk over the auxiliary document version D̂i , denoted as φ(uk,D̂i ), is the dwell time of the user uk over the document version D̂i-1 , φ(uk,D̂i-1 ), plus the dwell time of the user uk due to the exposure of the concept word Ci after seeing D̂i-1 , denoted as ϕ(Ci, uk, D̂i-1 ). This relationship can be formulated as follows:

When estimating the term ϕ(Ci, uk,D̂i-1 ), we also consider an inhibition effect-the more related Ci is to a user's previously encountered concept words C1, C2, · · · ,Ci-1, the less excited a user, or more precisely the user's brain, will be when encountering the concept word Ci. We therefore modify the single concept word user dwell time modeling equation (1) defined in the above to take into consideration such an inhibition effect. The form of our model is:

In (3), s(Ci,Cj) ∈ [0, 1] is the pairwise concept word semantic relatedness between the concept word pair Ci and Cj, which is calculated according to [Gabrilovich and Markovitch, 2007]. s(Ci,Cj) = 0 if Ci and Cj are completely irrelevant; s(Ci,Cj) = 1 if Ci and Cj are identical. nj is the number of times Cj occurs in the document version D̂i-1 .

2.4 Inferring Concept Word Level User Dwell Time

Problem Formulation

Let Dk = {D1, D2, · · · } be the full set of documents the user uk has read previously, and the user's dwell time over each document has been captured. We denote user uk's captured dwell time over the document Di as t(uk,Di) where Di ∈ Dk. Let |Dk| be the cardinality of the set Dk. Let Ck = {C1, C2, · · · } be the full set of concept words that occur in user uk's previous read document set Dk. According to our modeled relationship between document level user dwell time and concept word level user dwell time introduced in Sec. 2.3, we have the following relationships:

The variables involved in (4) include user uk's concept word level dwell time ϑ(Ci, uk, 1) for all Ci ∈ Ck (see (1)) as well as the parameters α1, α2. We will look at how to configure α1, α2 at the end of Sec. 2.5. For the time being, we assume α1, α2 are pre-fixed.

Due to noises in our data capturing procedure, we understand that the user dwell time data we acquire will likely exhibit internal contradiction, making the strict satisfaction of (4) often impossible. Therefore, instead of attempting to find an ideal solution, which may not exist, we aim at finding a most satisfying solution for (4). For this purpose, we convert (4) into the following target function:

where ω(Di) is an observation recency factor, which specifies how long ago the user dwell time sample t(uk,Di) was collected. The more aged a sample is, the less reliable and weighted the sample shall be considered as it is well understood that users' interests change over time. In our current implementation, we empirically choose ω(Di) to be ω(Di) ≜ 1 exp(# of days passed since t(uk,Di) was collected) . Overall, by finding a solution that minimizes Ξ(uk), we can find a most satisfying solution for (4).

It is also noted that each concept word Ci that occurs in a user's past reading activities will introduce a variable ϑ(Ci, uk, 1) into (4). Depending on the number of concept words ever appearing in a user's past readings, the total number of unknowns involved in (4) could be quite large, which poses another challenge for solving (4). Lastly, (4) could be under-constrained as well. To address the above challenges in resolving (4), we introduce a constraint based approach.

A Constraint based Approach for Inferring Concept Word Level User Dwell Time

We introduce the following constraint to represent the internal relationships between a user's dwell time over closely related concept words. Our assumption is: concept words that are more related should possess more similar concept word level user dwell times for the same user. To mathematically represent the above assumption, we first measure the difference between a pair of concept words, Ci and Cj , in terms of their user dwell time and semantic relatedness respectively. For the former, we use the relative difference between the two concept words' user dwell times as the measurement, which is denoted as: δ(uk,Ci,Cj) ≜ |ϑ(Ci,uk,1)-ϑ(Cj,uk,1)| max{ϑ(Ci ,uk,1),ϑ(Cj ,uk ,1)} . For the latter, recall that we use s(Ci,Cj) to define the pairwise relatedness between a pair of concept words Ci and Cj (see Sec. 2.3). Based on the two measurement terms, we can further measure the satisfaction of our above assumption through examining every concept word triple Ci, Cj , Cl. For the this purpose, we introduce the auxiliary function Ψ(Ci, Cj , Cl, uk) for measuring the satisfaction of our aforementioned assumption by the three concept words Ci, Cj , Cl, which is defined as follows:

(δ(uk , Ci , Cl ) - δ(uk, Cj , Cl ))(s(Cj , Cl ) - s(Ci , Cl))

To understand (7), let's examine the following case: the pair of concept words Ci and Cj are semantically more closely related than the pair of concept words Cj and Cl; while the difference in user dwell time of the concept word pair Ci and Cj is smaller than the dwell time difference of the concept word pair Cj and Cl. This is a case that aligns with our assumption; under this circumstance (δ(uk,Ci,Cj) - δ(uk,Cj,Cl)) is negative and (s(Cj,Cl) - s(Ci,Cj)) is negative. Therefore, Ψ1 (Ci,Cj,Cl, uk ) is positive. Following the same reasoning, we can easily examine the other three cases and verify the general property that a positive Ψ1 (Ci,Cj,Cl, uk ) value indicates a satisfying instance of our assumption while a negative Ψ1 (Ci,Cj,Cl, uk ) value indicates a violating instance of our assumption. In addition, it is worth noticing that in all the situations, the larger the magnitudes of (δ(uk, Ci, Cj ) - δ(uk, Cj , Cl)) and (s(Ci, Cj )-s(Cj , Cl)) are, meaning the more significant the qualitative relationships regarding semantic relatedness and user dwell time difference over the two concept word pairs are, the more our assumption would be satisfied. Such a property is quantitatively embodied in the multiplication operation in (7). All in all, we can see that Ψ1 (Ci,Cj,Cl, uk ) calculates how well our assumption is satisfied by the pairwise relationship between the concept word pair Ci and Cj versus the concept word pair Cj and Cl. In the same way, we can verify that Ψ2 (Ci,Cj,Cl, uk ) and Ψ3 (Ci,Cj,Cl, uk ) respectively calculate how well our assumption is satisfied by the pairwise relationships demonstrated between the other two concept word pair comparison cases. Finally, we can see that Ψ(Ci,Cj,Cl, uk), defined in (6), measures the overall satisfaction of our assumption by the group of three concept words Ci , Cj , Cl .

Based on the notation of Ψ(Ci,Cj,Cl, uk), we can now define the constraint for our concept word level user dwell time inference task as follows:

The goal is to maximize Ψ(uk) through finding an optimal assignment over the concept word level user dwell time ϑ(Ci, uk, 1) estimate where Ci ∈ Ck.

Finally, based on the constraint Ψ(uk) formulated above, we can redefine the objective function of our optimization problem as follows:

where the goal is to minimize Υ(uk) through finding an optimal assignment over the concept word level user dwell time estimate ϑ(Ci, uk, 1) for all Ci ∈ Ck.

2.5 Optimizing Target Function

Initialization

For each document Di ∈ Dk that the user uk has read in the past whose document level user dwell time is t(uk,Di), we extract all the concept words that appear in Di: C1,C2, · · · , Cz(Di) whose corresponding occurrence numbers in Di are n1, n2, · · · , nz(Di) respectively (see Sec. 2.2). We then distribute the user dwell time t(uk,Di) spent over the entire document Di onto the concept words C1, C2, · · · ,Cz(Di) proportionally according to the respective concept word density in Di, i.e.:

By accumulating user dwell times assigned to a concept word from processing all the document level dwell times of the user in this way, we can derive an initial estimation over concept word level user dwell time, i.e.:

Searching for Optimal Solutions

In the following step, we search for better solutions that can optimize the target function Υ(uk) through a multidimensional gradient descent based procedure. Recall that earlier in Sec. 2.3, we mentioned in our model of concept word level user dwell time (1), there are free parameters α1, α2. In our experiments, we search for optimal value assignment over the parameters based on all the user data we collected. That is, we congregate the user dwell time data captured from all the users participated in our experiments and perform a top level search over our optimization procedure introduced above to minimize the target function Υ(uk). The identified values for the parameters are α1 = 0.33, α2 = 1.16. We use the values as the default value assignment over α1, α2 for any user of our system. It is also possible to perform a personalized optimization process that only uses a specific user uk's captured user dwell time data to search for an optimal value assignment over α1, α2 for the user. We envision this top level optimization procedure will take place when the user's PC has a long period of idling cycles, e.g., during the wee hours.

2.6 Predicting User Dwell Time for New Documents for Personalized Re-Ranking

Given our estimated concept word level user dwell time, for each document Dx new to the user uk, we can predict the user's potential dwell time on the document. In our prediction, we first represent the document Dx as a collection of concept words via the document representation procedure discussed earlier in Sec. 2.2. And then we can simply apply (2) to derive the predicted user dwell time φ(uk,Dx) on the new document Dx.

Given the respective predicted dwell times for user uk over all the search result documents in a search session, we can now re-rank the search result set. We notice however that re-ranking search results only based on a user's reading interest is not sufficient as other factors should also be accounted for, such as the relatedness of a webpage to the query, the reputation of the webpage's source site, and the link structure around the webpage. Fortunately, these issues have been considered by mainstream commercial search engines. In this work, we utilize rankings produced by the Google web search engine to observe these factors indirectly. Also, like any learning based methods, our new algorithm suffers from the cold-start problem, i.e., if there are not enough webpages browsed by a user in the past, our method would not be able to produce reliable prediction on the user's dwell time over new documents due to lack of training data. Thanks to the hybrid re-ranking mechanism that leverages a commercial search engine's ranking results, we can also overcome the cold-start problem.

3 Experiments

In our experiment, to apply our algorithm to re-rank web search results, each time when a web search query is submitted by a user, we first use the Google search engine to acquire the top 300 search result webpages. And then we predict the potential user interest over these 300 webpages using the hybrid version of our method which has incorporated the original Google ranking result. These webpages are then recommended to the user in descending order of the overall predicted user interest. Inspired by [Xu et al., 2008a], we compute an overall predicted user interest Γ(uk, Di) for user uk over webpage Di as follows:

where Di is one of the top 300 webpages fetched by the Google search engine. Recall φ(uk,Di) denotes user uk's predicted dwell time over the document Di. The parameter λ ranging from 0 to 1 is a user adjustable value that tunes the balance between our learning based results and the commercial ranking produced by Google. In our experiments, we set λ as λ = exp(- nk 100 ) where nk is the number of the articles the user uk has read in the past whose dwell times are known to our algorithm. TRi denotes the rank of the document Di produced by Google among these 300 webpages of search results. The parameter γ specifies how sharply this drop-off is, whose value in our experiment is empirically set to 0.2.

To explore the effectiveness of our algorithm for personalized webpage ranking, we conducted a series of web search experiments using different query words. For each web search session in our experiment, we applied our algorithm to generate a personalized webpage re-ranking over the search results returned by Google. We adopted the normalized discounted cumulative gain (NDCG) to measure ranking quality. To conduct this measurement, we asked each user to assign an integer label between 0 and 4 to every webpage among the top Ntop search result pages, where Ntop denotes the number of search result items in the first page of a search result list, which is fixed to be 20 in all our experiments. These labels indicate the user's personal judgement on the corresponding search result's relevance to the query, where a label value of 4 indicates a strongly relevant document; 0 means an entirely irrelevant result. According to these user provided groundtruth labels on search result relatedness to a query, we can compute the NDCG score to measure the ranking quality. We also compared the performance of our personalized webpage re-ranking algorithmwith that of the original ranking produced by Google, as well as the ranking produced by a recent user-oriented webpage ranking algorithm [Xu et al., 2008b].

In our experiments, we invited sixteen participants from the graduate school of our university to use our personalized webpage ranking system in their daily life and work for three weeks. These participants are all engineering majored students with rich Internet search experiences. During these three weeks, they were encouraged to search information from the Internet as much as possible, and our system would collect the dwell times of individual users on each search result document. In the third week, each user was asked to perform web search using some given query words. After finishing a web search session using an assigned query word, a user would then be asked to label the top Ntop search results' respective relevance to the query according to his/her personal judgement and preferences, as discussed above. Such data collected in the third week were used as groundtruth data for individual users in our experiments. For the training data, we prepared two settings for the experiments. In the first setting, we only used a participant's dwell time collected in the first week of our experiment as the training data; in the second setting, we used the participant's dwell time collected in the first two weeks of our experiment period as the training data. No dwell time data collected during the third week was used for training purpose in either setting. We call the first experiment setting "running our algorithm with limited user dwell time data" and the second experiment setting "running our algorithm with increased user dwell time data." In the following, we report experiment results from both environments respectively.

Running our algorithm with limited user dwell time data.

Figure 1 reports example query words and NDCG scores of their respective search result rankings produced by our algorithm when running our algorithm with limited user dwell time data. For comparison purpose, we also report NDCG scores of rankings over the same sets of search results generated by personalized Google search, i.e., running the Google search function with web search history option turned on.

Running our algorithm with increased user dwell time data.

We repeated our experiments described above, but using the user dwell time data collected from the first two weeks' user web search experiences, to explore the impact of increased amount of user dwell time data on the performance of our algorithm for personalized re-ranking. Table 1 reports our experiment results. This table also reports NDCG scores of search result rankings produced by three popular commercial web search engines-Google, Yahoo and Bing. For comparison purpose, we also report NDCG scores of rankings produced by a recent personalized webpage ranking algorithm [Xu et al., 2008b], which also utilized user dwell time information for personalized webpage ranking. In their paper, they call the user dwell time on a document the attention time of the user over the document. Hence we refer to their algorithm by the abbreviation "AT08" in the following. Both our algorithm and the "AT08" algorithm have access to the user dwell time data collected in the first two weeks of the user's web search activities as the algorithm's training data. Figure 2 visually compares statistic distribution of NDCG scores of these methods using boxplots. The comparison results clearly show the advantage of our algorithm for generating personalized webpage rankings that best reflect a user's ideally expected webpage rankings. We also ran two simplified versions of our algorithm, one without imposing the constraint term Ψ(uk) in (11) when inferring concept word level user dwell time, and the other one without performing the iterative optimal solution search procedure when optimizing our target function in Sec. 2.5. The same set of fifteen example queries were used in these two sets of comparison experiments. We report the comparison results in the same figure, according to which we can clearly see the effectiveness of the two design features of our algorithm.

4 Conclusion

In this paper, we propose a new personalized webpage ranking algorithm through mining dwell times of a user. We introduce a quantitative model to derive concept word level user dwell times from the observed document level user dwell times. Once we have inferred a user's interest over the set of concept words the user has encountered in previous readings, we can then predict the user's potential dwell time over a new document. Such predicted user dwell time allows us to carry out personalized webpage re-ranking. To explore the effectiveness of our algorithm, we measured the performance of our algorithm under two conditions-one with a relatively limited amount of user dwell time data and the other with a doubled amount. Both evaluation cases put our algorithm for generating personalized webpage rankings to satisfy a user's personal preference ahead of those by Google, Yahoo!, and Bing, as well as a recent personalized webpage ranking algorithm.

Acknowledgement

Songhua Xu performed this research as a Eugene P. Wigner Fellow and staff member at the Oak Ridge National Laboratory, managed by UT-Battelle, LLC, for the U.S. Department of Energy under Contract DE-AC05-00OR22725.