Learning & Self Organization

Tomasz Imielinski & Robert C. Berwick

It is critical that the WWW's hyperlink-based information structure dynamically learn usage patterns so that:

Frequently requested information becomes easily accessible: high-demand links are cached or pushed to the top, requiring few link traversals, possibly at the expense of rarely-demanded information.
Services migrate where they are most needed: servers dynamically replicate close to the areas of highest request. This calls for dynamic replication, migration, and caching schemes. Using self-adaptation, the WWW will be better able to automatically tailor itself to individual user needs, as well as handle a larger traffic volume.

Note that the WWW "structure" is understood here in two different senses: (1) as a graph with links as edges, where links themselves can be dynamically defined in response to the usage patterns; and (2) as a mapping between services and servers that provides these graph structure. Hence a service can dynamically migrate to a server as result of a growing request volume. Both scenarios of "dynamic restructuring" can lead to optimization: optimization of expected number of link traversals in order to reach a page and optimization of network traffic and overall latency (response time per page).

We recommend that NSF support progressive evolution to an "adaptive" WWW in two ways:

First, by adopting when possible available adaptive/learning add-on technologies to web page accessors/servers (see below); Second, by initiating tests of the adaptive approach, in conjunction with user modeling efforts.We now address both kind of self-organization - request and service based - in more detail.

Recommendation 1: Request Reoganization and Learning

In the same way that Huffman coding assigns the shortest codes to the most frequently used symbols, a good hyperlink based interface should assign "shortest paths" to the most frequently accessed pages. Dynamic reorganization schemes are needed that use known request-per-page statistical distributions to reorganize the hyperlink interface; these algorithms can minimize the expected number of link traversals per user's query.

Techniques used for building "good" or suboptimal classification trees such as C4.5 can be used here. Individual links can "die" if there is very little or no usage. Similarly, "macrolinks" can be created and even automatically replace frequently traversed paths. In this way the WWW server can "evolve" with changing access patterns with or without human intervention. A "good" server should characterize itself by a low expected access path length.

The client's interface should also reflect the particular client's profile. It is important that the user's list of preferred pages or "hotlist" is not just a flat collection but is itself a hyperlink-based structure. But how to provide a hierarchy on the top of a flat collection of pages? This is similar to a classification problem or even to the clustering problem in unsupervised learning. It would be very helpful if "suggested" classification trees could be provided to the user, who then would choose the one that suits them best. Note that some existing Home Pages already include user-interactive classification-tree algorithms that could be easily adapted to test this idea. We therefore suggest that NSF possibly adopt one of these methods perhaps in a separate experimental "adaptive" Home Page, that researchers could test. A larger-scale experiment with such a system is also possible. Creating such "user's-eye" WWW views as a kind of user's "miniweb" is an important research area, related to the key problem of good user modeling.

Recommendation 2: Service Reorganization and Learning

Research in dynamic replication, migration and caching can be utilized in deciding how WWW servers should replicate their services. The best schemes would allow service replication closest to high service demand areas. Pages could migrate between different servers in response to the changing demand patterns. Typically, global increase in a page's read activity will result in bringing this page closer to the center of "reading activity". If writing and updating is allowed as well, it will constitute a "counterforce" against a growing number of replicas (the update cost is higher). Dynamic replication methods has been developed and studied for data allocation in multiprocessor architectures - some of these same techniques can be directly utilized in the WWW setting.

Internet is a unique environment - there is no other distributed system of such scale, that at the same time has already accumulated such substantial usage statistics. It is critical to use these data dynamically in order to adaptively configure services to minimize access time and network traffic.

Furthermore, the WWW's rich information resources are currently accessible only to a relatively small subgroup, yet all should have equal access. The reasons for current limitations are straightforward: WWW's current interaction mode demands a computer terminal with sufficient available bandwidth, hence reasonable response time. Broadening the Web's constituency demands a wider range of user interfaces. Technologically, this will be surely possible, since in the future we should be able to support a much wider spectrum of client devices, including battery powered palmtops with narrowband wireless connection, and units with voice transcription or even vibration-mode output. In fact, the future WWW client need not be a computer user at all, but merely someone using a fax, phone, or television.

In order to support a varying spectrum of information modalities, we have to extend authoring tools and technologies such as HTML to define different page presentation styles, much as "font styles" and "style sheets" are defined today. In the best case, such an extended modality authoring system could automatically adapt to the end user's preferences.

Recommendation 3: Adaptive Links

Since Web users may vary from broadband/fixed network-based to mobile and wireless connected, we need to provide different views of the same information depending on the "resources of the user". For example, a JPEG image of a page may take too much time and energy for a mobile client to download. Perhaps a grayscale outline (or "greeked" representation, as publishers call it) or even a textual description of the same page would be more appropriate. In general, a HTML link should be parameterized by the client's resources such as bandwidth of the connection, energy source (steady or battery power), buffer size, and the like. The actual link which is involved will be dynamically determined by the server on the basis of current "amount" of client's resources. This will put heavier burdens on information service designers, who will have to provide alternative "views" of the same information. Each page's presentation will have attached "resource prerequisites" that are necessary for satisfactory access.

It is a simple extension of this idea to provide for modality-challenged individuals. As a simple first step, modality-tagged preferences can be flagged for hearing/sight-impaired users as part of their default preferences; this ranges from simple extensions such as automatically encoding volume/font size preferences to a public-access "reader" utilities comparable to current commercial text-to-speech systems. Not all cross-modality conversions are equally simple; note that being able to "describe" full images via natural language is an area of current research, unlikely to be generally possibly in the near-term. This means that for the present, off-line tagging of image-based text is likely to remain in the domain of HTML authoring and document meta-information generation. We suggest that NSF explore this range of possibilities via an augmentation similar to TDD facilities that are supplied in other contexts.

Recommendation 4: Different Presentation Modalities

We argue that frequently requested information pages should be periodically multicasted rather than provided "on demand." For example, the airline schedule for flights departing within the next hour should be periodically broadcasted to wireless users in a particular airport area due to the anticipated high demand for such information. The same information will be provided only "on demand" further from the airport. This periodic multicast may be called a "publishing" mode as opposed to the Web's currently standard "on demand" client-server paradigm. Note that "publishing" mode does not require uplink transmissions from the client. Thus, it is the only possible way to access information for users with "one way" communication abilities such as "one way" pagers. For instance a popular service such as Motorola's Embarc periodically broadcasts information such as financial news to users equipped with PDA's (HP 100LX) and extended with special one way pagers.

In the wireless infrastructure, different cells, managed by so called Mobile Support Stations (MSS), will have autonomy regarding the presentation of each page of information. The same page may be published in one cell and provided on demand in a different cell. This will require an ability to "handoff" from the client who will cross the border between two cells, when their "hot list" of pages may have a different delivery mode.

The ability to specify the mode of page presentation should be a part of a future authoring environment. The author of such a page (or perhaps its "local distributor" in case we deal with the wireless environment) should also have an option to specify other parameters. For example, if a page is to be periodically published, how often should it be published? Under what conditions? Similarly, modality conversions can be specified.

Table of Contents

Next Chapter