A Learning Algorithm for Web Page Scoring Systems

1 Introduction

PageRank [Page et al., 1998] is the most popular algorithm to compute the page relevance in a collection of hyper­ linked documents, like the Web. This algorithm exploits the topology of the citation graph in order to determine the au­ thority of each page using the intuitive idea that authorita­ tive documents are linked by many authoritative documents. Thus, the original algorithm computes a ranking which de­ pends only on the graph connectivity without considering the page contents. However, focused versions of PageR­ ank have been proposed in the literature [Haveliwala, 2002; Richardson and Domingos, 2002; Diligenti eta/., 2002] in or­ der to define more selective rankings for topic-specific search engines. These approaches allow a limited degree of adapta­ tion related to the choice of the specific topic. A text classifier is trained using examples of pages on the topic of interest but no further level of learning is considered in the ranking mod­ els. In particular, the classifier is trained independently on the ranking algorithm.

We propose a more general approach in which the learning algorithm is defined directly on the ranking model. In this case there is not a predefined topic, but a supervisor provides examples of pages to be promoted and pages which are con­ sidered as not relevant. Thus, the learning algorithm is able to manage both positive examples (relevant pages) and neg­ ative examples (not relevant pages). The ranking function is based on the Web surfer model [Diligenti eta/., 2002]. The relevance of a page is defined by the probability of the surfer to visit the page when considering the stationary probability distribution of the Markov chain which describes the surfer behavior. Basically the learning algorithm computes the pa­ rameters which define the surfer model in order to reduce the probability of visiting a negative example and to increase the probability of being in a positive example. In order to reduce the number of free parameters, the surfer model is simplified by dividing the pages among a set of categories and assuming that the surfer behavior depends only on the category of the page where it is located. In particular, the set of categories does not need to be predefined but it is determined by a clus­ tering algorithm based on the document contents. Moreover, whereas the focused versions of the PageRank simply direct the Web surfer to the most promising page (i.e. the page whose content is the most similar to the content of a target page), the proposed algorithm can exploit hierarchies of top­ ics, allowing the surfer to follow complex paths, composed by many steps, leading to relevant pages.

The paper is organized as follows. In the next section the web surfer model is reviewed. Then, in section 3 the learning algorithm is described. Section 4 reports some experiments which show the effectiveness of the proposed learning algo­ rithm. Finally, in section 5 the conclusions are drawn.

2 Random Walks on the Web graph

Random walk theory has been widely used to compute the absolute relevance of a page in the Web [Page et al., 1998; Lempel and Moran, 2000]. The Web is represented as a graph G, where each Web page is a node and a link between two nodes represents a hyperlink between the associated pages. A common assumption is that the relevance Xp of page p is represented by the probability of ending up in that page dur­ ing a walk on this graph.

We consider the model of a Web surfer who can perform one out of two atomic actions while visiting the Web graph: jumping to a node of the graph (action J) or following a hyperlink from the current page (action l). In general, the action taken by the surfer will depend on the page contents and the links it contains. We can model the user's behavior by a set of probabilities which depend on the current page:

x(lJq) is the probability of following one hyperlink from page q, and x(JJq) is the probability of jumping from page q. These values must satisfy the normalization constraint, x(JJq) + x(lJq) = 1.

The two actions need to specify their targets. Assum­ ing that surfer behavior is time-invariant, then the targets are specified by the probability x(pJq, J) of jumping from page q to page p, and the probability x(pJq, l) of selecting a hy­ perlink from page q to page p. x(pJq, l) is not null only for the pages p linked directly by page q, i.e. p E ch(q), being ch(q) the set of the children of node q in the graph G. These sets of values must satisfy the probability nor­ malization constraints .L:pEG x(pJq, J) = 1, Vq E G and .L:pEch(q) x(pJq, l) = 1, Vq E G.

The model considers a temporal sequence of actions per­ formed by the surfer and it can be used to compute the proba­ bility that the surfer is located in page pat timet, xp(t). The probability distribution on the pages of the Web is updated by taking into account the actions at time t + 1 using the follow­ ing equation

where pa(p) is the set of the parents of node p. The relevance of a page p, Xp is computed using the stationary distribution of the Markov Chain of equation (1). This is a simplified version of the model proposed in [Diligenti eta/., 2002].

3 Learning the page rank

The random surfer model which is used to compute the page relevance scores depends on the values assigned to the proba­ bilities x(pJq, J), x(JJq), x(pJq, l), and x(lJq). In most of the approaches proposed in the literature, these parameters are predefined or computed from some features describing the page p and/or the page q. For example, in the original PageR­ auk scheme x(lJq) = d, x(JJq) = 1- d, x(pJq, J) = k, and x(pJq, l) = ch(q).

However, in the general case, it would be infeasible to es­ timate the parameters without any assumption to reduce their number. In particular, we assume that the pages are grouped into n clusters according to their content and that the surfer's behavior for any page p is dependent only on the cluster which p belongs to. In our experiments we used classical clustering techniques (e.g. k-means) on the bag-of-words rep­ resentation of the pages [Kobayashi and Takeda, 2000]. By this hypothesis, the parameters of the model are computed as:

where cq is the cluster which page q belongs to, JcPJ is the number of pages in cluster cP, the parameter r( cq -+ cPJl) is the tendency of the surfer to follow a hyperlink from a page in cluster cq to a page in cluster cP, and the parameter x( cP Jcq, J) is the tendency of the surfer to jump from a page of cluster cq to a page of cluster cP. The values r(cq-+ cPJl) are initialized to 1, such that all links are equally likely to be followed. Because of the model assumptions, the stronger is the tendency of the surfer to move to a cluster, the higher are the scores associated to the pages in that cluster.

3.1 The learning set

We assume that a supervisor provides a set pages labeled as relevant and not relevant. These examples are used to define a specific view of the collection of documents contained in a search engine. In particular the supervisor provides:

• a set of pages N+ which should get a high rank;
• a set of pages N- which should get a low rank.

In the first case we refer to "positive" or "good" pages, whereas in the latter case to "negative" or "bad" pages.

Each example page is associated to its Context Graph [Dili­ genti eta/., 2000], representing how the page can be reached from the Web. The graph is organized into layers as shown in figure 1. The example page is the only node in layer 0. Then, each node in layer i > 0 links only nodes in layer i - 1. Thus, a page belongs to layer i if it is at least i links away from the example page. The depth K of the context graph is defined as the number of layers in the graph including level 0. For a given example, the context graph can be built by back­ crawling the Web adding to layer i + 1 the pages which link the pages in layer i, up to a maximum level K. Moreover, all the pages that are linked by at least a page of the graph are also considered.

The learning set consists of the context graphs built from the examples inN+ and N-. CQ is the set of all the pages contained in the learning set; Lt (Lf:) is the union of the pages in the layer k of the context graphs of the positive (neg­ ative) examples.

3.2 Learning the transition parameters

We define the set of transition probabilities T = { x(p E Cj[q E c;,l) i,j = 1, . .. ,n}, which represent the proba­ bilities of the surfer to select a hyper! ink from a page in the cluster c; to a page in the cluster Cj . The rank of the pages in the set N+ is increased, whereas the rank of the pages inN­ is decreased if we increase the probability of the paths leading to pages inN+ and we reduce the probability of paths leading to pages in N - . This effect can be obtained by maximizing the following cost function

where 0 :S a :S 1 is a discount factor which is used to reduce the impact on the cost function of the links too far from the target page.

The probability x(p E Ltlq E Lt+l' T, l) of moving one level in the context graph towards a good page, can be rewrit­ ten as

where x(p E Cj [q E c;, l) reflects the surfer model assump­ tion that the links are selected depending only on the clusters c; andcj. Theprobabilityx(p E Lt[q E Lt+ 1 ,q E c;,p E Cj, l) of following a link to a page in the cluster Cj of layer k from a page in the cluster c; of layer k + 1 of a context graph can be estimated as

where n(A -+ B) is the number of links from the pages in the set A to the pages in the set B.

On the other hand the term x(q E c;[q E Lt+l, l) repre­ sents the probability that the surfer is located in a page of the cluster c;, given that the page belongs to the layer k + 1 of a positive context graph. This probability can be estimated using the scores of the pages in cluster c; and in Lt+l' com­ puted using the current values of the parameters, as

Similar relationships can be derived for the negative set.

The cost function (3) can be optimized by updating the pa­ rameters in T using gradient ascent. The gradient with re­ spect to the transition parameters x(p E Cj [q E c;, l) can be computed using equation (4), yielding

where we neglected that x(q E c;[q E Lt+l,l) and x(q E e; [q E L k+l, l) actually depend on the transition parameters. Since the model parameters r(c; -+ Cj [l) are essentially a not normalized version of the transition parameters x(p E Cj[q E c;, l), we can update them directly as

where T) is the learning rate.

Once the model parameters are updated, a new score dis­ tribution can be computed, thus updating the estimate of the variables x(q E c;[q E Lt+I>l) using equation (6). There­ fore, the function optimizatiOn and the score estimation can be iterated, using an EM style algorithm [Dempster et a!., 1977], till a termination criterion is satisfied.

3.3 Learning the jump parameters

The transition parameters for a jump can be optimized to in­ crease the probability of jumping to a "good" page and not to a "bad" page. This effect is obtained by maximizing the cost function

where P = {x(p E cj[q E c;, J) i,j = 1, ... ,n} is the set

of the jump parameters.

We start observing that,

By assuming that the jump target is independent on the orig­ inating cluster c;, the term x(p E N+[q E c;,p E Cj, J) can be estimated as

Moreover, the value x( q E c; I J) is computed at each iteration as

Similar relationships can be derived for the negative set.

The cost function (9) is maximized by gradient ascent. The gradient can be computed using equation (10) and the equiv­ alent equation for the negative set, yielding

where we neglected the dependence of x ( q E Ci I J) on the pa­ rameters. At each iteration, the parameters are updated using the direction of the gradient as,

being 'f/ the learning rate, and then normalized to meet the probabilistic constraints

The adapted surfer model can re-surf the Web graph yield­ ing a new estimate of equation (12). Thus, the new gradient estimate can be used to update again the parameters, till the stop criterion is satisfied.

3.4 Learning the surfer action bias

The surfer action bias is represented by the value of x(llq E c;) which is the probability of following a link from the cur­ rent page rather than jumping to another page (x(Jiq E Ci) = 1 - x(llq E ci)). In order to favor the action leading to good pages, we maximize the following cost function which rep­ resents a weighted average of the probabilities of ending in the layer k of a positive context graph and not of a negative context graph,

where Q = {x(llq E c;) i = 1, ... , n} is the set of the free parameters, and 0 ::; a ::; 1 is a discount factor to reduce the effect of the outer layers on the cost function.

The probability of moving to a page k steps away from a target is,

The term x(p E Ltlq E Ci, l) represents the probability of ending in the layer k of a positive context graph by following a link from a page of cluster i and can be estimated as

where we assumed that all links out of a page are equally likely to be followed. The term x(p E Ltlq E ci, J) is the probability of jumping to the layer k of a positive context graph from a page of cluster i, and can be computed as

Finally, x(q E ci) can be computed at each iteration as in equation (12). Similar relationships hold for the negative set.

The gradient of the cost function (16) can be computed us­ ing equation (17) and the corresponding relationship for the negative set, yielding

neglecting the dependence of x(q E Ci) on x(llq E ci). The parameters are updated by gradient ascent as

where the learning rate must be chosen small enough in order to preserve the stochastic model of the surfer.

The adapted surfer model can re-surf the Web graph yield­ ing a new estimate of equation (12). Thus, the new gradient estimate can be used to update again the parameters and the procedure is iterated till the stop criterion is satisfied.

4 Experimental results

In the following experiments, the learning algorithm was ap­ plied only to the transition parameters of the random surfer model. The experiments were performed on two datasets, each containing 1.000.000 documents, which were collected by focus crawling the Web on the topics "wine" and "playsta­ tion", respectively. The documents were clustered using a hierarchical version of the k-means algorithm [Fukunaga, 1990]. We considered different numbers of clusters generated by the k-means algorithm. In particular, in two different runs, we clustered the pages from the dataset on topic "playstation" into 16 and 25 sets, whereas the dataset on topic "wine" was clustered into 25 and 100 sets.

Two topic-specific search engines were build creating the inverted lists containing the terms of all the documents. Then, the rank of each page in the dataset was computed using the model described in section 2 by setting its parameters to re­ produce the original PageRartk ranking. We tested the quality of the ranking function by submitting a set of queries to this focused search engine. The documents matching the query were sorted by the scores assigned by the random surfer. By interacting with the search engine, we found pages which were authorities on the specific topic but were (incorrectly) not inserted in the top positions of the result list. Such pages were selected as examples of pages which should get a higher rank (positive examples). On the other hand, we found pages having a high score which were not authorities on the topic. Such pages were selected as negative examples. The learn­ ing algorithm, as described in section 3, was applied to the datasets, using the selected examples. In the experimental setup only a small set of examples (3-15) was typically la­ belled as positive or negative.

4.1 Analysis of the effects oflearning

In a first group of experiments we aimed at demonstrating that the surfer model as learnt by the proposed training algo­ rithm, could not be generated by a simpler (but less powerful) schema as the focused versions of PageRank, proposed in the literature.

In figure 2-(a) 2-(b), we show the values of the transi­ tion parameters for each cluster, resulting from the train­ ing sessions for a surfer on the topic "wine" and "playsta­ tion", respectively. The learnt parameters represent a com­ plex interaction of the resulting surfer with the page clus­ ters. This interaction could not be expressed by a simple schema as, for example, the focused versions of PageRank proposed in the literature [Richardson and Domingos, 2002; Diligenti et al., 2002]. This demonstrates that the model, in order to learn the users' feedback, needed to exploit hierar­ chies of topics to model the complex path leading either to positive or negative examples.

In figure 3-(a) and 3-(b), we show for each cluster, the val­ ues of the probability of the surfer of being located in a page of that cluster. In particular we used the dataset on topic "wine" clustered into 25 and 100 groups, respectively. The probabilities are normalized with respect to the number of pages in the cluster. The learning algorithm is able to increase the likelihood of the random surfer to visit pages belonging to a set of clusters, while decreasing its probability of visiting pages belonging to other clusters.

In figure 4, we report the rank of pages after the learning session with respect of their rank before learning. In particu­ lar, on the x axis the pages are sorted according to their page rank before the learning session. The closer a page to the origin, the more "relevant" the page is. On the y axis it is re­ ported the corresponding page rank after the learning session. The plot shows the generalization capability of the learning algorithm, which is able to change the ranks of a significant percentage of pages, even if a small set of example was pro­ vided.

4.2 Qualitative results

After training the surfer and computing the scores for all pages in the dataset, we compared the rank before and after the training process.

Figure 5 reports the pages which obtained the largest vari­ ation in their rank. The pages that obtained a negative rank variation were either topic-generic authoritative pages (e.g. www.netscape.com, www.yahoo.com) or pages relevant for different topics than "wine" (e.g. "www.forgottensoldier­ .org"). Only the page "www.yahoo.com" was explicitly pro­ vided to the system as a negative example. On the other hand, the pages that obtained a positive rank variation were effec­ tively authoritative pages on the topic "wine" (e.g. "www­ .wine-searcher.com" or "webwinery.com"). Among the most ascending documents, only the page "www.winespectator­ .com" was explicitly provided to the system as a positive ex­ ample, whereas all other pages were pushed up in the rank for the capability of the system to generalize from a small set of training data.

5 Conclusions

In this paper we introduced a novel algorithm to learn the ranking function over a collection of Web pages. The pro­ posed framework allows us to tune a previously computed rank distribution, specifying which pages should get a higher or lower score. Like in the original PageRank, we assume that the score of a page is proportional to the probability that a Web surfer is visiting the page. The learning algorithm adapts the parameters of the surfer in order to increase the probabil­ ity that the surfer is visiting a "good" page, while decreasing the probability that the surfer is visiting a "bad" page. The parameters are estimated from the Context Graphs, which compactly represent the topological context in which a Web page is inserted. The learning algorithm is fast since only close ancestors of example pages are considered in the Con­ text Graphs. Thus, it can be applied to large scale repositories with little overhead (i.e. the ranking function must be com­ puted more many times). Further investigations are needed to compare the accuracy of the learnt ranking functions with respect to the focused versions of the PageRank and to ex­ ploit the complete learning algorithm which considers all the model parameters.