Adaptive Web Sites: an AI Challenge

1 Introduction

The World Wide Web is becoming a key medium for in­ formation dissemination, entertainment, and communi­ cation. Examples include personal home pages, on-line malls, university course information, and much more. Many web sites quickly sprout intricate collections of pages and hyperlinks as they begin to mirror the com­ plexity of the information they convey.

*This research was funded in part by Office of Naval Re­ search grant 92-J-1946, by ARPA/ Rome Labs grant F3060295-1-0024, by a gift from Rockwell International Palo Alto Research, and by National Science Foundation grant IRI9357772.

Designing a rich web site so that it readily yields its information can be tricky. Unlike the oyster that con­ tains a single pearl, a web site often contains myriad facts, images, and hyperlinks. Many different visitors approach a popular web site - each with his or her own goals and concerns. Consider, for example, the web site for a typical computer science department. The site contains an amalgam of research project descriptions, course information, lists of graduating students, point­ ers to industrial affiliates, and much more. Each nugget of information is of value to someone who would like to access it readily. One might think that a well organized hierarchy would solve this problem, but we've all had the experience of banging our heads against a web site and crying out "it's got to be here somewhere ... ".

The problem of good web design is compounded by several factors beyond the fact that different visitors have distinct goals. First, the same visitor may seek different information at different times. Second, many sites outgrow their original design, accumulating links and pages in unlikely places. Third, a site may be de­ signed for a particular kind of use, but be used in many different ways in practice; the designer's a priori expec­ tations may be violated. Too often web site designs are fossils cast in HTML, while web navigation is dynamic, time-dependent, and idiosyncratic. We challenge the AI community to address this problem by creating adap­ tive web sites: web sites that automatically improve their organization and presentation by learning from user access patterns.

In essence, web design is a problem in user interface design. However, in contrast with vendors of shrink­ wrapped software, few web site designers can afford to subject their web sites to formal usability testing in spe­ cial labs. Fortunately, web users interact directly with a server maintained by the inventors of the service or authors of the content being served. As a result, data on their behavior is recorded in web server logs (see Figure 1). Because this raw data is overwhelming for an over­ worked webmaster to process regularly, web server logs are ripe targets for automated analysis.

Our challenge then is this: how can we build a web site which improves itself over time in response to user inter­ actions with the site? This challenge poses a number of

24hrlab-214.sfsu.edu-- (21/Nov/1996:00:01 :05 -0800] "GET /homefjonesfcollectors.html HTTP/1.0" 200 13119 24hrlab-214.sfsu.edu-- [21/Nov/1996:00:01:06 -0800] "GET /home/jones/madewithmac.gif HTTP/1.0" 200 855 24hrlab-214. sfsu.edu-- [21/Nov/1996:00:01:06 -0800] "GET /home/jones/gustop2.gif HTTP/1.0" 200 25460 x67-122.ejack.umn.edu-- [21/Nov/1996:00:01:08 -0800] "GET /home/rich/aircrafts.html HTTP/1.0" 404 617 x67-122.ejack.umn.edu-- [21/Nov/1996:00:01:08 -0800] "GET /general/info. gif HTTP/1.0" 200 331 203.147.0.10-- (21/Nov/1996:00:01:09 -0800] "GET /home/smith/kitty.html HTTP/1.0" 200 5160 24hrlab-214.sfsu.edu-- [21/Nov/1996:00:01:10 -0800] "GET /homefjonesfthumbnails/awing-bo.gif HTTP/1.0" 200 5117

difficult, but not impossible, questions:

• What kinds of generalizations can we draw from user access patterns and what kinds of changes could we make? Suppose we maintain a web site containing information about various au­ tomobiles, organized by manufacturer. We observe that visitors who look at the Ford Windstar minivan page also tend to look at the Dodge Caravan and Mazda MPV minivan pages. We might therefore create a new page for minivans, which cuts across the existing manufacturer-based organization and provides a new view of the site.
• How do we design a site for adaptivity? We might specifically design parts of the site to be changeable. For example, we might present our users with a "tour guide" (as in [Armstrong et al., 1995]) and have changes to the site be presented as the agent's suggestions. Alternatively, we might annotate our HTML with directives stating where and how changes can be made. Or we may provide semantic information about the entire site, allowing the agent to reason about the relationships between everything, perhaps representing the entire site as a database (see [Fernandez et al., 1997]).
• How do we effectively collaborate with a hu­ man webmaster to suggest and justify poten­ tial adaptations? Suppose the human webmaster is still responsible for the final product. Instead of changing web pages directly, our system might ac­ cumulate observations and suggested changes and present them to the webmaster, clearly explaining its observations and justifying the changes it recom­ mends.
• How do we move beyond one-shot learning algorithms to web sites that continually im­ prove with experience? Over time, our adaptive web site will accumulate a great deal of data about its users and should be able to use its rich history to continually evolve and improve.

Our department maintains a web site for its introductory computer science course. This site contains schedules, announcements, assignments, and other information im­ portant to the hundreds of students who take the course every quarter. Enough information is available that im­ portant documents can be hard to find or entirely lost in the clutter. Imagine, however, if the site were able to determine what was important and make that informa­ tion easiest to find. Important pages would be available from the site's front page. Important links would appear at the top of the page or be highlighted. Timely infor­ mation would be emphasized, and obsolete information would be quietly moved out of the way.

There are several factors that make this challenge both appropriate and timely for the AI community. First, the growing popularity and complexity of the web un­ derscores the importance of the challenge. Second, vir­ tually all existing web sites are not adaptive, yet data to support the learning process is readily available in web server logs. Clearly, here is an opportunity for AI! Finally, a number of disconnected projects in ma­ chine learning [Armstrong et al., 1995], data mining, knowledge representation, plan recognition [Kautz, 1987; Pollack, 1990], and user modeling [Fink et al., 1996] have begun to explore aspects of the problem. Framing the problem explicitly in this paper could help bring these disparate approaches together.

We pose our challenge as a particular task to be ac­ complished by any means available. Many advances in artificial intelligence, both practical and theoretical, have come about in response to such task-oriented ap­ proaches. The quest to build a better chess-playing com­ puter, for example, has led to many advances in search techniques (e.g., [Anantharaman et al., 1990]). The au­ tonomous land vehicle project at CMU [Thorpe, 1990] has resulted in not only a highway-cruising vehicle but also breakthroughs in vision, robotics, and neural net­ works. The quest to build autonomous software agents has similarly led to both practical and theoretical ad­ vances. For example, the Internet Softbot project has yielded both deployed softbots and advances in plan­ ning, knowledge representation, and machine learning [Etzioni, 1996].

We believe that the goal of creating self-improving web sites is a similar task: one whose accomplishment will require breakthroughs in different areas of AI. In this paper we discuss possible approaches to this task and how to evaluate the community's progress. In section 2, we present two basic approaches to creating an adaptive web site. We illustrate both with ongoing research and examples. In section 3, we discuss how to evaluate re­ search on this challenge, discussing practical alternatives as well as open questions. Throughout, we pose Chal­ lenge questions intended to suggest research directions and illustrate where the open questions lie.

2 Approaches to adaptive web sites

Sites may be adaptive in two basic ways. First, the site may focus on customization: modifying web pages in real time to suit the needs of individual users. Second, the site may focus on optimization: altering the site itself to make navigation easier for all . We illustrate these two basic approaches with examples drawn from current AI research. Whether we modify our web pages online or of­ fline, we must use information about user access patterns and the structure of our site. Much of this information is available in access logs and in the site's HTML, but this may not be sufficient; we also discuss how to support adaptivity with meta-information - information about page content. Finally, we examine other issues that arise in designing adaptive web sites.

2.1 Customization

Customization is adjusting the site's presentation for an individual user. Customization allows fine-grained im­ provement , since the interface may be completely tai­ lored to each individual user. One way for a site to respond to particular visitors is to allow manual cus­ tomization: allowing users to specify display options that are remembered during the entire visit and from one visit to the next. The Microsoft Network (at http:/ jwww.msn.com), for example, allows users to cre­ ate home pages with customized news and information displays. Every time an individual visits her MSN home page, she sees the latest pickings from the site presented according to her customizations.

Path prediction, on the other hand, customizes auto­ matically by attempting to guess where the user wants to go and taking her there more quickly. A path prediction system must answer at least the following questions.

• What are we predicting? We may try to predict the user's next step. For example, if we can predict what link on a page a particular user will follow, we might highlight the link or bring it to the top of the page. Alternatively, we may try to predict the user's eventual goal; if we can determine what page at the site a visitor is looking for, we can present it to her immediately.
• On what basis do we make predictions? We might use only a particular individual's actions to predict where she will go next. On the other hand, we might generalize from multiple users to gather data more quickly.
• What kinds of modifications do we make on the basis of our predictions? We may do as little as highlighting selected links (by making them

bold or putting graphics around them, for example) or as much as synthesizing a brand new page that we think the user wants to see.

The WebWatcher [Armstrong et al., 1995] (see http:/ jwww.cs.cmu.edu/ "'webwatcher/) learns to pre­ dict what links users will follow on a particular page as a function of their specified interests. Web Watcher observes many users over time and attempts to learn, given a user's current page and stated interests, where she will go next . A link that Web Watcher believes you are likely to follow will be highlighted graphically and duplicated at the top of the page. Visitors to a site are asked, in broad terms, what they are looking for. Be­ fore they depart, they are asked if they found what they wanted. Web Watcher uses the paths of people who indi­ cated success as examples of successful navigations. If, for example, many people who were looking for "personal home pages" follow the "people" link, then Web Watcher will tend to highlight that link for future visitors with the same goal.

Instead of predicting a user's next action based on the actions of many, we might try to predict the user's ul­ timate goal based on what she has done so far . Goal recognition [Kautz, 1987; Pollack, 1990] is the problem of identifying, from a series of actions, what an agent is trying to accomplish. Lesh and Etzioni [Lesh and Et­ zioni, 1995] pose this problem in a domain-independent framework and investigate it empirically in the Unix do­ main: by watching over a user's shoulder, can we figure out what she is trying to accomplish (and offer to accom­ plish it for her)? They model user actions as planning operators. Assuming users behave somewhat rationally, they use these actions' precondition/postcondition rep­ resentation to reason from what a user has done to what she must be trying to do. In the web domain, we observe a visitor's navigation through our site and try to deter­ mine what page she is seeking. If we can do this quickly and accurately, we can then offer the desired page im­ mediately.

Challenge: Can we formalize user navigation of the web as a planning process that is amenable to goal recognition? Do user actions on the web carry enough evidence of their purpose?

The AVANT! Project [Fink et al., 1996] (see http:/ jzeus.gmd.de/ projectsjavanti.html) focuses on dynamic customization based on users' needs and tastes. As with the Web Watcher, AVANT! relies partly on users providing information about themselves when they en­ ter the site. Based on what it knows about the user, AVANT! attempts to predict both the user's eventual goal and her likely next step. AVANT! will prominently present links leading directly to pages it thinks a user will want to see. Additionally, AVANT! will highlight links that accord with the user's interests. AVANT! is illustrated on a hypothetical Louvre Museum web site. For example, when a disabled tourist comes to the site, links regarding disabled access and tourist information are emphasized. AVANT! relies on users providing some information about themselves in an initial dialogue; the site then uses this information to guide its customization throughout the user's exploration of the site. AVANT! also attempts to guess where the user might go based on what she has looked at so far. For example, if our dis­ abled tourist looks at a number of paintings at the site, AVANT! will emphasize paintings links as it continues to serve pages. As with the Web Watcher, we might ask if we can avoid AVANTI's requirement that users explicitly provide information.

2.2 Optimization

Whereas customization focuses on individuals, optimiza­ tion tries to improve the site as a whole. Instead of mak­ ing changes for each user, the site learns from all users to make the site easier to use. This approach allows even new users, about whom we know nothing, to benefit from the improvements.

We may view a web site's design as a particular point in the vast space of possible designs. Improving the site, then, corresponds to searching in this space for a "bet­ ter" design. Assuming we have a way of measuring "bet­ ter" , we may view this as a classical AI search problem. One possible quality metric would be to measure the amount of effort a visitor needs to exert on average in order to find what she is looking for at our site. Effort is defined as a function of the number of links traversed and the difficulty of finding those links. For example, a site whose most popular local page is buried five links away from the front page could be improved by mak­ ing that page accessible from a readily obvious link on the front page. We can navigate through this space by performing transformations on the site - adding or re­ moving links, rearranging links, creating new web pages, etc. If we guarantee that each transformation improves the quality of the site, we are performing a hillclimbing search.

Challenge: How large is this search space and what is an appropriate search strategy? Can we re­ structure the space to avoid searching large portions of it?

In [Perkowitz and Etzioni, 1997] we sketch the design of a system with a repertoire of transformations that aim to improve a site's organization; transformations include rearranging and highlighting links as well as synthesizing new pages. Our system learns from common patterns in the user access logs and decides how to transform the site to exploit those patterns and make the site easier to navigate. For example, the web site for our depart­ ment's introductory computer science course contains a web page for each homework assignment given during the course. After each assignment's due date, a solution set for that assignment is made available. Our system would observe that after an assignment's due date many visitors look at the solut"ion set; in fact, the most recent solution set is one of the most popular pages at the site. This observation would lead the system to promote the solution set by giving it a prominent link on the front page. Promotion - making the link to a page more prominent - is a simple but effective transformation. We have implemented a form of promotion on an ex­ isting web site and have found that approximately 10% of our 10,000-15,000 daily page accesses are through au­ tomatically generated links; roughly 25% of all visitors click through at least one such link. Of course, we note that promoting a link may be a self-fulfilling prophecy - making a page more prominent may increase its pop­ ularity, artificially inflating the site's apparent success at adaptation.

A more ambitious transformation is clustering- syn­ thesizing a brand new web page that contains links to a set of related objects. From available data, the system must infer that a set of pages at the site are related and group them together. This inference might be based on content (e.g., when a number of pages cover the same topic) or on user navigation patterns (e.g., when visitors to one page are particularly likely to visit certain oth­ ers). As final exams approach, students tend to look at multiple solutions sets on each visit. Even though the solution pages are not linked together directly, visitors navigate from one to another (via intervening pages) on their own. This pattern suggests that the solution sets form a meaningful group in our visitors' heads, which does not appear on our web site - solution sets are only linked to from their respective assignment pages. Our system would create a new page with a link to each so­ lution set and make this new page available to visitors to the site. We are currently implementing clustering transformations based on user navigation data.

2.3 Meta-information

A web site's ability to adapt can be hampered by the lim­ ited knowledge about its content and structure provided by HTML. For example, suppose that a page contains a list of links. Is it appropriate to add a new link at the top of the list? The answer depends on the con­ tents of the list - an adaptive site should not add a link to a course's home page to a list of links to faculty home pages; furthermore, if the list is in alphabetical order then a new item can only be added at the appro­ priate point. Clearly, a site's ability to adapt could be enhanced by providing it with meta-information: infor­ mation about its content, structure, and organization. In this section, we discuss means of providing an adap­ tive site with this sort of information.

One way to provide meta-information is to represent the site's content in a formal framework with precisely defined semantics such as a database or a semantic net­ work. This approach is pioneered by the STRUDEL web-site management system [Fernandez et al., 1997] which attempts to separate the information available at a web site from its graphical presentation. Instead of ma­ nipulating web sites at the level of pages and links, web sites may be specified using STRUDEL's view-definition language. In addition, web sites may be created and updated by issuing STRUDEL queries. For example, a corporation might create home pages for its employees by merging data from its "manager" and "employee" databases. A page would be created for every person in either database. Furthermore, each manager's page would have links to her employees, and vice-versa.

This approach would facilitate adaptivity because STRUDEL would enable a site to reason about its logi­ cal description and detect cases where adaptations would violate the existing logic. Furthermore, an adaptive site could easily transform itself by issuing STRUDEL queries; STRUDEL provides the mechanisms to auto­ matically update the site appropriately. The drawback of the STRUDEL approach is that it requires the site's entire content to be encoded in a set of databases or in wrappers that map web pages and other information sources into STRUDEL. The cost of constructing such wrappers for existing web sites, and particularly for rel­ atively unstructured sites, appears to be high.

A lighter-weight approach is to annotate an existing web site with meta-content tags. In this approach, a formal description of the content coexists with HTML documents. We may choose how much of the site to an­ notate and how complex our annotations will be. Yet, meta-content annotation still facilitates reasoning about the connections between parts of the site and still pro­ vides guidance as to where and how to make changes.

One approach of th~s type is Apple's Meta-Content Format (see http:/ /mcf.research.apple.com). MCF is an attempt to establish a standard for meta-content an­ notation for the web. When a user visits an MCF­ enhanced site with an MCF-enabled browser, she can choose to navigate the site in a three-dimensional rep­ resentation of the site's structure, as determined from the site's MCF annotation. SHOE [Luke et al., 1997] (at http:/ jwww.cs.umd.edujprojects/plus/SHOE/), takes a different tack. SHOE is a language for adding simple ontologies to web pages. SHOE adds basic ontological declarations to HTML; a page can refer to a particular ontology and declare classifications for itself and rela­ tions to other pages. In their example, a man's home page is annotated with information about him, such as the fact that he is a person, his name, his occupation, and his wife's identity (she has her own home page). SHOE is designed to facilitate the exploration of agents and the workings of search tools, but ontological anno­ tation could also support adaptation.

While lighter-weight than STRUDEL, meta-content tagging also has clear disadvantages. First , because the meta-content annotation is separated from the actual content, it has to be updated manually as the content changes. Second, since the meta-content is attached to existing HTML, it provides no direct support for auto­ matic adaptation; Any adaptation must still modify the original HTML.

Each of the approaches described so far require a fair amount of effort to build and maintain the con­ tent descriptions. If we wish only to facilitate adapta­ tion, this effort may be overkill. An alternative that we are actively investigating is to use an extremely lightweight annotation system designed specifically for adaptivity. These annotations would be in the form of directives to the adaptive system telling it where it may (or may not) make changes and what kinds of changes it might make. For example, we might add a list tag to HTML to allow us to describe the elements in a list and how they are ordered. A list might be de­ clared as <list order="unordered">, which tells the system it may reorder the list in any way it chooses. Or a list might be declared <list order="popularity">, in which case the system will draw upon data from access logs to determine how to present the list. A list declared <list order="alphabetical"> or <list order="chronological"> can be modified by additions or deletions so long as its original ordering constraint is preserved.

We present tags of this sort as part of an "Adaptive HTML" language called A-HTML in [Perkowitz and Et­ zioni, 1997]. Our intention is to extend HTML to a higher level of abstraction, allowing a web designer to describe objects in terms of their time-relevance, organi­ zation, and interrelationships. Note that this approach does not require the global establishment of an A-HTML standard; the adaptive site uses a server capable of inter­ preting A-HTML and translating it into standard HTML at runtime. Only the resulting HTML is served in re­ sponse to page requests.

2.4 Open Questions

The quest for a self-improving web site raises a num­ ber of related questions. An adaptive site will be active twenty-four hours a day, seven days a week. The site will constantly be ingesting and analyzing data, adjusting its concepts and models, and updating its own structure and presentation. Over time, this constant cycle will reflect many hours of experience and refinement. In the past , AI research has focused on single trials and short-lived entities: systems that run their experiments and shut down, to start again the next day with a blank slate. Although such an approach may be applied to the adap­ tive site challenge, the most intelligent site will surely be one that continually accumulates knowledge about pages, users, content, and itself.

User interface design is difficult enough for human be­ ings to perform well . Yet an adaptive web site will have to take into account all the artistry of good design in its self-improvements. We can limit the scope of the sys­ tem's ability to change itself, thus ensuring that it cannot do too much harm, but this means we also limit its scope for improvement . On the other hand, giving the system free rein for radical transformation might mean giving it free rein for radical screwup.

Challenge: How do we formalize the concept of good design? How do we limit the potential for harm without overly limiting the potential for good?

We might instead put the AI system in the role of ad­ visor to a human master. Instead of making changes un­ der cover of night, our AI system must now intelligently present suggestions to a human being, complete with explanation and justification. Such a solution frees us from the problem of changing details without changing design but presents us with a new interface challenge.

Challenge: How does our adaptive web site com­ municate its suggestions to a webmaster?

3 Evaluation

Although the problem of measuring the quality of a web site design is thorny, we have identified several prelimi­ nary approaches. Progress on the design of adaptive web sites will include more sophisticated methods of evaluat­ ing a site's usability. We propose a basic metric for how usable a site is: how much effort must a user exert on average in order to find what she wants? As discussed in section 2.2, effort can be defined as a function of the number of links traversed and the difficulty of finding the links on their pages. The standard daily access log may be used to approximately measure user effort.

However, standard log data is not sufficient to know everything about visitor navigation. For example, stan­ dard logs do not distinguish between individuals con­ necting from the same location or record which link a user followed. However, software is available to provide more complete information. WebThreads, for example (see http:/ fwww.webthreads.com), allows a site to track an individual user's progress, including both pages vis­ ited and links followed. Along with analysis of our site's structure, data from a system like WebThreads is suffi­ cient for us to measure user effort.

Analysis of our user logs provides much information about how users interact with the site. In addition, we may use controlled tests with subjects. Such tests have the advantage of allowing us to observe users as they interact with the site - we get much more information than is encoded in user access logs. As subjects perform tasks such as finding information, downloading software, or locating documents, we may gather data such as:

• Whether the subject succeeded at the task (or real­ ized it was not solvable).
• How long the subject took to solve the goal.
• How much exploration was required.

Careful observation of test subjects would complement the limited access data we get on all of the site's regular visitors. Of course, we can also rely on intermediate measures such as encouraging users to fill out feedback forms and send e-mail messages.

4 Conclusion

This paper posed the challenge of using AI techniques to radically transform web sites from today's inert collec­ tions ofHTML pages and hyperlinks to intelligent, evolv­ ing entities. Adaptive web sites can make popular pages more accessible, highlight interesting links, connect re­ lated pages, and cluster similar documents together. An adaptive web site can perform these self-improvements autonomously or advise a site's webmaster, summariz­ ing access information and making suggestions. The im­ provements can happen in real-time as a visitor is nav­ igating the site, or offiine based on observations culled from many visitors.

This paper juxtaposed a number of disconnected projects from knowledge representation, machine learn­ ing, and user modeling that are investigating aspects of the problem. We believe that posing the challenge ex­ plicitly, in this paper, will help to cross-fertilize existing efforts and alert new researchers to the problem. Success in the next two years will have a broad and highly visible impact on the web and the AI community.