Web Watcher: A Tour Guide for the World Wide Web

1 Introduction

Browsing the World Wide Web is much like visiting a museum. In a museum the visitor has general areas of interest and wants to see relevant artifacts. But visi­ tors find it difficult to locate relevant material given that they do not initially know the contents of the museum. In many cases their initial interests are poorly defined, becoming clear only after they begin to explore. In a museum the user might rely on a tour guide who is fa­ miliar with the museum and how people interact with it. The visitor could describe his or her initial inter­ ests to the tour guide, who could then accompany the user, point out items of interest, and suggest which di­ rections to turn next. During the tour the visitor could communicate with the guide, express interest in certain artifacts, ask and answer questions as they explore, and refine their interests.

People browsing collections of Web pages often be­ have like museum goers. For example, a visitor to

Tom Mitchell

Carnegie Mellon University School of Computer Science 5000 Forbes A venue Pittsburgh, PA 15213, USA

CMU's Computer Science Web home page might have a general interest in "experimental research on intel­ ligent agents." However, with no specific knowledge about the contents of the collection, the user may find it difficult to locate relevant information. Until they be­ come aware that CMU conducts significant research on robotics, for example, they may not think to mention "learning robots" when describing their general interest in intelligent agents.

Here, we report research into software agents that act as tour guides for the Web. In its most general form, the metaphor of Web agent" as tour guide is very broad, suggesting systems that carry on general natural lan­ guage dialogs with their users, possess detailed knowl­ edge about the semantic content of the Web pages they cover, and learn with experience. Here we describe a first experiment with a more restricted, but operational, tour guide. In particular, we describe Web Watcher [Arm­ strong et al., 1995], a system that accompanies the user as he or she browses the Web. Like a museum tour guide, WebWatcher interactively suggests where to go next. The user can communicate with the system and give feedback. WebWatcher acts as a learning appren­ tice [Mitchell et al., 1994], observing and learning from its users' actions. Over time WebWatcher learns to ac­ quire greater expertise for the parts of the World Wide Web that it has visited in the past, and for the types of topics in which previous visitors have had an interest.

WebWatcher differs in several key respects from keyword-based search engines such as Lycos and Al­ tavista. First, such search engines require that the user describe their interest in terms of specific words that match those in the target Web page. In contrast, WebWatcher can learn that a term such as "machine learning" matches a hyperlink such as "neural networks" or "A vrim Blum," even though these phrases share no words in common. Furthermore, current search engines do not take into account that documents are designed as hypertext. In many cases only a sequence of pages and the knowledge about how they relate to each other can satisfy the user's information need.

In the following we present the design of Web Watcher, as well as experimental results obtained from over 5000 tours given by WebWatcher to various visitors on the Web. We describe how WebWatcher learns to improve the quality of its advice, and present experimental results comparing different learning methods. Finally, we sum­ marize the lessons and perspectives gained from these first experiments with a tour guide agent for the Web.

2 Trace of Web Watcher

WebWatcher was in operation from August, 1995, to February, 1997. A typical WebWatcher tour proceeded a.s follows . We enter the CMU School of Computer Sci­ ence Web at the front door page. On this page an in­ stance of Web Watcher can be invoked by clicking on the hyperlink "The Web Watcher Tour Guide". Clicking on this hyperlink leads us to a page where we are asked for a short description of our current interest. In this example, we enter the phrase "intelligent agents" as our interest. Web Watcher now returns us to the initial page, prepared to guide our tour (figure 1). We are no longer browsing alone, but will be accompanied by WebWatcher on any sequence of hyper links we follow from this point forward .

We can tell that WebWatcher accompanies us from the additions it makes to the original page. A page aug­ mented with WebWatcher's additions is shown in figure 1. Among others they include:

• A list of Web Watche1· Commands is inserted above the original page. The user can invoke these com-
• mands to communicate with WebWatcher as he browses from page to page.
• Selected hyperlinks from the original page have now been highlighted by WebWatcher, to suggest di­ rections relevant to our browsing interests. Web­ Watcher highlights these hyperlinks by inserting eyeball icons (~~) around the hyperlink, as shown in the "projects" link in figure 1 (recall in this ex­ ample the user expressed an interest in "intelligent agents"). The advice Web Watcher provides in this fashion is based on knowledge learned from previous tours.

If we follow WebWatcher's suggestion in figure 1, we reach a page containing a long list of research project pages. WebWatcher again inserts the command list on top of the page and suggests three hyperlinks it judges relevant to our interest in "intelligent agents."

In general, the user may click on any hyperlink, recom­ mended or not. Each time the user selects a hyperlink, Web Watcher accompanies the user to the next page, and logs this hyperlink selection as a training example for learning to improve future advice.

In addition to highlighting hyperlinks WebWatcher also provides other forms of assistance. In particular, it provides a keyword search using a variant of the Lycos search engine applied to the set of pages previously vis­ ited by WebWatcher. It also provides a user command "Show me similar pages" in the command list, which causes WebWatcher to display a list of pages which are similar based on a metric derived from hypertext struc­ ture [Joachims et al., 1995]. Clicking on the command "how many followed each link?" asks WebWatcher to display for each hyperlink the number of previous visi­ tors who took that link. The command "Email me if this page changes" tells Web Watcher to periodically monitor the current page and send the user email if it changes.

WebWatcher accompanies the user along any hyper­ link anywhere on the World Wide Web. To end the tour, the user clicks on one of two options in the command list : "Exit: Goal reached" or "Exit: Goal not found ." This exit provides the user with a way of giving final feedback to WebWatcher.

3 Accompanying the User

WebWatcher is implemented as a server on a separate workstation on the network and acts much like a proxy. Before returning a page to the user it makes three mod­ ifications:

1. The Web Watcher command list is added to the top of the page.
2. Each hyperlink URL in the original page is replaced by a new URL that points back to the Web Watcher server.
3. If Web Watcher finds that any of the hyperlinks on this page are strongly recommended by its search control knowledge, then it highlights the most promising links in order to suggest them to the user.

While it waits for the user's next step, it prefetches any Web pages it has just recommended to the user to minimize network delays. Figure 2 depicts one cycle of user interaction. When the user clicks on a new hyper­ link, WebWatcher updates the log for this search, re­ trieves the page (unless it has already been prefetched) , performs similar substitutions , and returns the copy to the user. This process continues until the user elects to dismiss the agent.

4 Learning in Web Watcher

What is the form of the knowledge required by Web­ Watcher? In general, its task is to suggest an appropri­ ate link given an interest and Web page. In other words, it requires knowledge of the following target function:

The value of LinkQuality is interpreted as the prob­ ability that a user will select Link given the current Page and Int erest. In the following we present three approaches to learning this target function from expe­ rience. The first approach uses previously given tours as a source of information to augment the internal rep­ resentation of each selected hyperlink. The second ap­ proach is based on reinforcement learning. The idea is to find tours through the Web so that the amount of relevant information encountered over the trajectory is maximized. The third approach is the combined method that includes both of the first two approaches.

4.1 Learning from Previous Tours

In the first approach, learning is accomplished by anno­ tating each hyperlink with the interests of the users who took this hyperlink on previous tours . Thus, whenever a user follows a hyperlink the description of this hyperlink is augmented by adding the keywords the user typed in at the beginning of the tour. The initial description of a hyperlink is the underlined text. Figure 3 illustrates the keywords accumulated by hyperlinks, and the way in which these are used to influence subsequent advice.

To suggest hyperlinks during a tour Web Watcher com­ pares the current user 's interest with the descriptions of all hyperlinks on the current page. WebWatcher sug­ gests those hyperlinks which have a description suffi­ ciently similar to the user's interest.

The metric used to compute similarity between a user 's stated interest and a hyperlink description is based on a technique from information retrieval [Salton, 1991]. Interests and hyperlink descriptions are represented by very high-dimensional feature vectors, each dimension representing a particular word in the English language. The elements (called word-weights) of a vector are cal­ culated using the TFIDF heuristic [Salton, 1991] . Based on this vector representation similarity is calculated as the cosine between vectors.

The algorithm WebWatcher uses to suggest hyper­ links considers all hyperlinks on the current page. For each hyperlink, the list of associated keywords (includ­ ing the original underlined words) is used to calculate its similarity to the current user 's interest . The value of LinkQuality for each hyperlink is estimated to be the average similarity of the k (usually 5) highest ranked key­ word sets associated with the hyperlink. A hyperlink is suggested if its value for LinkQuality is above a thresh­ old . The maximum number of hyperlinks suggested on a page is three.

4.2 Learning from Hypertext Structure

The previous section describes a learning method that augments a given hyperlink with the stated interests of earlier users who selected it. In this section we describe a second learning method that augments a given hyper­ link using words encountered in pages downstream of it. This approach is based on reinforcement . learning. The objective is to find paths through the Web which maxi­ mize the amount of relevant information encountered.

Reinforcement Learning

Reinforcement learning allows agents to learn control strategies that select optimal actions in certain settings. Consider an agent navigating from state to state by per­ forming actions. At each state 8 the agent receives a certain reward R( 8). The goodness of an action a can be expressed in terms of an evaluation function Q(8, a), defined for all possible state-action pairs. The value of Q(8, a) is the discounted sum offuture rewards that will be obtained if the agent performs action a in state 8 and subsequently chooses optimal actions. If the agent can learn this function, then it will know how to act in any state. More precisely,

where 8t is the state the agent is in at timet, and where 1 is a discount factor 0 :::; 1 < 1 that determines how severely to discount the value of rewards received further into the future. Under certain conditions, the Q func­ tion can be iteratively approximated by updating the estimate for Q(8, a) repeatedly as follows (see [Watkins, 1989]):

8 1 is the state resulting from performing action a in state 8. Once Q(8, a) is known, the optimal control strategy for the agent is to repeatedly pick the action a that max­ imizes Q(8, a) for its current state 8.

Figure 4 gives an example. Boxes represent possible states of the agent. The edges represent actions that bring the agent from one state to another. The edges are annotated with values of the function Q(8, a). In the rightmost state the agent receives a reward of 1. The reward is 0 in all other states. If the agent always follows the action with the highest Q value, it will get to the reward state in the smallest number of steps and thus maximize the discounted reward it receives.

Reinforcement Learning and Hypertext

Imagine a Web agent looking for pages on which the word "intelligent" occurs. For this agent, states correspond to Web pages, and actions correspond to hyperlinks. In this case, we define the reward Rintelligent( 8) for a particular page 8 to be the TFIDF value of "intelligent" for 8. The agent will then learn a Qintelligent(8, a) function whose value for page 8 and hyperlink a is the sum of discounted TFIDF values of "intelligent" over the optimal tour be­ ginning with a. It can then use this Q function to choose the best link at each step in the tour.

WebWatcher uses a separate reward function Rw(8) and learns a distinct Q w ( 8, a) function for every word w . At runtime the system recommends hyperlinks for which the sum of the Qw(8, a) for the words in the user's interest description is highest. An additional reward is given if the interest matches the underlined text of the hyperlink.

Because Web Watcher cannot expect that users will al­ ways stick to pages it has already seen, a core question in implementing this approach is how to learn a general approximation for each of the Q-functions Q w ( 8, a) that applies even to unseen states (pages) and actions (hyper­ links). We chose a distance-weighted 3-nearest neighbor function approximator [Mitchell, 1997] for this purpose, because of the many features needed to describe pages and hyperlinks, and because of certain theoretical ad­ vantages [Gordon, 1995]. Each hyperlink a is described by the TFIDF vector representation of the underlined anchor text, each page 8 analogously by its title. We de­ fine the similarity between the hyperlink a1 on page 81 and the hyperlink a2 on page 82 to be the distance be­ tween a1 and a2, plus (heuristically) twice the distance between 81 and 82 . The distance between two vectors is defined to be the cosine of the angle between the vectors , in keeping with the standard similarity measure used in information retrieval.

4.3 Experimental Setup

The experiments presented in this section were con­ ducted using 1777 of the 5822 traces starting at the SCS­ FrontDoor page WebWatcher collected between August 2, 1995, and March 4, 1996. We used only those tours where the user typed in an interest and where the tour was at least four steps long. Five different test-training splits were used with the pages and hyperlinks from 70% of the traces used for training.

In addition to the reinforcement learning approach RL and the learning method ANNOTATE from section 4.1, the results for four other methods are presented. RAN­ DOM suggests hyperlinks at random from the current page. POPULARITY suggests those hyperlinks which have been followed most frequently in the past, ignoring information about the current user's interest. MATCH suggests hyperlinks according to the TFIDF-cosine sim­ ilarity between their underlined text and the user's in­ terest. Finally, the COMBINE method combines the predictions of RL, POPULARITY, ANNOTATE, and MATCH using logistic regression. 10% of the available training data is used for regression.

4.4 Experimental Results

The results in figure 5 provide a comparison of the learn­ ing methods. For each example in the test set each learner was allowed to choose three hyperlinks from the corresponding page. Accuracy measures the percentage of examples for which the user followed one of these cho­ sen hyperlinks. We required each learning algorithm to make a prediction regardless of how confident it was.

The method Web Watcher used while accessible to the public was Annotate. The accuracy of 42.2% in the of­ fline experiment here approximately matches the frac­ tion of times (43.9%) users followed WebWatcher's ad­ vice during actual use of the system.

Reinforcement learning performs significantly better than the other basic methods. Nevertheless the com­ bination of all methods achieves the highest accuracy, outperforming each of the individual methods. Our con­ jecture is that this is due to the diversity of the methods and sources of information that are combined. Popu­ larity uses frequency information derived from user be­ havior on a particular page, Match uses the underlined text in hyperlinks, Annotate uses the interest descrip­ tions from previous user traces, and RL makes use of hypertext structure that is downstream of the hyperlink in question.

4.5 Comparison with Human Experts

To get a better feel for the nature of the task of sug­ gesting hyperlinks and to evaluate Web Watcher's perfor­ mance, we conducted an experiment in which we asked humans to perform Web Watcher's task. To make the ex­ periment more tractable we focused on one page, namely an earlier version of the SCS-Front-Door page shown in figure 1. From the 408 training examples available for this page we took 8 random subsets of 15 examples and presented these to eight people who were already well­ informed about this page and its locale. For each ex­ ample, they were given the stated interest of the user, then asked to suggest the 3 hyperlinks the user was most likely to follow out of the 18 hyperlinks on this page.

As figure 6 summarizes, humans achieved an accuracy of 47.5% in predicting which hyperlink the user would follow. The learning method Annotate achieved an ac­ curacy of 42.9% under the same conditions. The 22.4%

for random prediction again provides a baseline. These results suggest that predicting which hyperlink the user is going to follow is a fairly difficult task in a general set­ ting. In comparison to human performance the learning approach does reasonably well.

5 Related Work

Letizia [Lieberman, 1995] is similar to WebWatcher in the sense that the system accompanies the user while browsing. One difference is that Letizia is located on a single user's machine and learns only his or her current interest. By doing lookahead search Letizia can recom­ mend nearby pages.

Syskill and Webert [Pazzani et al., 1996] offers a more restricted way of browsing than Web Watcher and Letizia. Starting from a manually constructed index page for a particular topic, the user can rate hyperlinks off this page. The system uses the ratings to learn a user specific topic profile that can be used to suggest unex­ plored hyperlinks on the page. Syskill and Webert can also use search engines like LYCOS to retrieve pages by turning the topic profile into a query.

Lim [Balabanovic and Shoham, 1995] works in an of­ fline setting. A general model of one user's interest is learned by asking the user to rate pages. Lira uses the model to browse the Web offline and returns a set of pages that match the user's interest.

6 Summary and FUture Research

WebWatcher provides one case study of a tour guide agent for the World Wide Web. By "tour guide agent" we mean any agent that accompanies users from page to page, providing assistance based on a partial under­ standing of that user 's interests and of the content of the Web pages. During its 18 months of operation, Web­ Watcher served thousands of people browsing CMU's School of Computer Science Web pages. The system has the following properties:

• WebWatcher provides several types of assistance, but most importantly highlights interesting hyper­ links as it accompanies the user.
• WebWatcher learns from experience. We found a multi-strategy approach to be the most effective learning method.
• WebWatcher runs as a centralized server so that it can assist any Web user running any type of Web browser as well as combine training data from thou­ sands of different users.

Our experience with WebWatcher led us to believe that self-improving tour guide agents will play an important role on the Web in the future . WebWatcher demon­ strates that it is possible for such an agent to provide helpful advice to many users, and that it is possible to automatically learn from the thousands of users with whom it interacts. Given that popular Web sites are typically visited by many thousands of users, and that the content of the Web changes frequently, it appears that machine learning will play a crucial role in future tour guide agents.

Our experience with Web Watcher has also shown that despite its ability to help some users, its highlighted hy­ perlinks match those followed by users in only 48% of all cases. Interestingly, when we assigned expert hu­ mans the same task, they could do no better. Examining many specific tours given by WebWatcher, we find the following partial explanation for this level of accuracy. Users tend to have a fairly short attention span and are distracted from their stated interest. Furthermore there is great diversity in the interests of users browsing CMU's SCS Front Door so that even after thousands of tours it is not uncommon for the next user to express an interest that WebWatcher has not yet encountered. Together, these two factors suggest that Web Watcher might achieve higher accuracy if the Web locale it had to cover had a narrower, more focused scope.

More generally, our experience with Web Watcher sug­ gests a number of topics for future research:

• Personalized WebWatcher . Whereas WebWatcher learns to specialize to a specific Web locale, one could instead develop tour guide agents that learn to specialize to a particular user. Such an agent could learn a model of the longer-term interests of users by observing which pages they do and do not visit. We have recently begun experiments with such a personalized WebWatcher [Mladenic, 1996] .
• Combining user-specific · and Web locale-specific learning. At the same time WebWatcher learns a model of one particular user, it could retain its capability to annotate hyperlinks based on tours given to many users. In this context, one could ex­ plore a variety of methods for combining the benefits of single-user modeling and learning simultaneously from/about multiple users.
• Richer dialogs with users. One major shortcoming of the current Web Watcher is that it allows the user only to express a few keywords, and only at the beginning of the tour. A more flexible approach would involve an ongoing dialog with the user , much more like that a museum visitor might have with a human guide.
• New machine learning algorithms for classifying hyperlinks . . The learning methods used by Web­ Watcher succeed in improving its performance over time. However, a large space of possible learning
• methods for this problem remains unexplored, i.e. the combination of linguistic analysis with the sta­ tistical techniques described here.
• Intelligent distributed hyperlinks. Web Watcher learns by associating new information with hyper­ links based on its experience. Note this learning could be performed in a much more distributed fash­ ion, with each hyperlink separately building up its own model of itself and making recommendations to the user.

Acknowledgements

This research is supported by a Rotary International fel­ lowship grant, an NSF graduate fellowship , and by Arpa under grant number F33615-93-1-1330.