Making General-Purpose Adaptive Hypermedia Work

Paul De Bra*+, Ad Aerts, Geert-Jan Houben+, Hongjing Wu
Department of Computing Science
Eindhoven University of Technology (TUE)
PO Box 513, Eindhoven
The Netherlands

{debra,wsinatma,houben,hongjing}@win.tue.nl

*Also at the "Centrum voor Wiskunde en Informatica" in Amsterdam.
+Also at the University of Antwerp.


This paper resides at http://wwwis.win.tue.nl/~debra/webnet2000/paper.html.

Abstract: Adaptive hypermedia systems (AHS) have typically been geared towards one specific application or application area, in most cases related to education. The AHA (Adaptive Hypermedia Architecture) system is a Web-based adaptive hypermedia system specifically intended to serve many different purposes. As such AHA must be able to perform adaptation that is based on the user's browsing actions, regardless of the interpretation of browsing as learning. A general-purpose adaptive hypermedia system must be able to handle cycles in adaptation rules and non monotonic user model updates. (An educational system in which a user's knowledge about a hierarchical concept structure can only increase is much simpler.) This paper describes how AHA handles these aspects and indicates how other adaptive hypermedia systems may be turned into more general-purpose tools as well.

Keywords: Web-based adaptive hypermedia, user modeling, adaptation rules.

1. Introduction and Background

Authoring usable hypermedia documents is difficult. On the one hand an author wants to offer a lot of navigational freedom, with short paths to every possible destination. But on the other hand an author wants to avoid overloading the user with too many links, which would make the selection of appropriate destinations difficult. Many adaptive hypermedia applications [B96] tackle this problem by automatically selecting or emphasizing those links that are considered "appropriate", based on a model of the user's state of mind which the system maintains. Educational applications are typical in this respect: the system monitors the user's progress through an electronic textbook and gradually starts to offer more and more complex and detailed information.

Many adaptive hypermedia systems have a simple user model structure. Some features of the user are stored, often called preferences (which are set by the user and not altered by the system) and knowledge about concepts is maintained and updated while the user is browsing. (Actually the knowledge is estimated by the system, based on a record of accesses to information pages and on the results of some multiple-choice tests). Relationships between pages or concepts are also simple: many systems only deal with prerequisite relationships, meaning that one (prerequisite) concept should be studied before another one. These types of systems are well suited for educational applications that share the following properties:

  1. Once the conditions (prerequisites) for a concept are fulfilled they remain fulfilled. (When the user is ready to study a concept, she will always remain ready to study that concept.)
  2. A user's knowledge about a concept can only increase. (The user never forgets what she has learnt.)

Educational adaptive hypermedia systems are based on the notion that the user model consists of concepts with an associated knowledge value. Each time a page (about a concept) is accessed some server-side program (e.g. a Java Servlet) registers this access and updates the knowledge value for the associated concept. In order to turn such a system into a general-purpose one the notion of knowledge about a concept must be generalized to value for a user model attribute. As such a concept need not represent domain knowledge, and the attribute may represent any kind of property, not necessarily knowledge. As such, the applications an adaptive system must deal with may not satisfy the two properties above.

In [DC98] we presented a first version of the AHA system, which allows applications to "violate" the first property: the condition for including or providing access to a piece of information may include negations. Thus, still in educational terminology, learning about a concept may make another concept superfluous and therefore hidden or inaccessible. We call such relationship an inhibitor. (It is the opposite of a prerequisite.) In the first version of AHA applications must satisfy the second property, except that the user can manually alter her user model (through a form). This paper presents the next version of AHA, which supports applications that do not satisfy the second property. In addition, knowledge is no longer represented by a Boolean value (known or not known) but by an integer value between 0 and 100. We give some interesting examples of "general purpose" use of adaptation rules that show adaptive behavior that is very different from that of applications for learning.

The design and development of the general purpose AHA system posed some interesting challenges. In order to accommodate a rich model of an application domain we allow the definition of concept relationships. Changes to the (user model) value for a concept may induce changes to (the value of) other concepts. This has its origin in education as well, where concepts may form a hierarchy. The user may be required to study several small concepts (possibly pages) in order to acquire the knowledge about a larger concept. Updates to the (knowledge) value for the small concepts contribute towards the (knowledge) value for the larger concept. In AHA values can be updated arbitrarily (increased and decreased). Decreasing values is probably most useful in applications where the values have a meaning other than "knowledge". Also, the structure of concept relationships is not required to satisfy constraints such as being acyclic. (A concept knowledge hierarchy would normally be acyclic.) In general, allowing recursive updates to the user model may:

  1. generate unpredictable or even undesired results;
  2. cause infinite loops of updates.

This paper describes how AHA deals with recursive adaptation rules in order to guarantee that the outcome of each user model update is always predictable and desirable. We illustrate this with some typical examples of update rules.

This paper is structured as follows. Section 2 briefly describes the architecture of AHA. Section 3 illustrates why AHA has a recursive update algorithm. Section 4 describes that user model update algorithm, and shows the deterministic (and finite) behavior of that algorithm. Section 5 gives a few non-educational examples expressed in AHA. Section 6 concludes with remarks on possible future extensions of AHA.

2. Overview of AHA

The general structure of AHA is somewhat comparable to many other adaptive hypermedia systems, as described in [B96]. In [DHW99] we defined a reference architecture for adaptive hypermedia systems, called AHAM. According to AHAM an adaptive hypermedia application consists of three parts:

In the (new) AHA system these three parts have the following structure: The above constructs to change the appearance of links, and the conditional inclusion of fragments represent adaptive techniques that are traditionally called [B96]:

Because general-purpose authoring tools for XML data files are currently lacking AHA comes with some scripts to convert HTML pages to the required XML syntax and with a forms-based interface for creating the list of generate rules and requirement rules.

3. The Need for Recursive Updates

All adaptive features depend heavily on the updates to the user model being performed correctly. In the first version of AHA every access to a page could only change the Boolean value for some concepts. Consequently it was not possible to express that 10 pages contributed towards a "composite" concept. As a result the definition of some requirements like prerequisites difficult. If some information in a document depended on the a chapter of 10 pages having been read completely, the first version of AHA required clauses like:

  <relationexpression>
     page1 and page2 and page3 and page4 and page5 and
     page6 and page7 and page8 and page9 and page10
  </relationexpression>
(pageX is allowed shorthand for pageX=100)
In the new AHA one can define each page to generate 10% of "chapter" (apart from generating 100% of itself, which every page concept does). A page for which the entire chapter is prerequisite knowledge then has a requirement:
  <relationexpression>
     chapter=100
  </relationexpression>
Apart from this, it becomes possible to require at least 8 out of the 10 pages to have been read by specifying:
  <relationexpression>
     chapter>=80
  </relationexpression>
(This would require a very long expression in the old AHA system.)
Pages and concepts can also form a deeper hierarchy, like when pages contribute knowledge to a section and sections to a chapter and chapters to a whole book. There are two ways to implement such a hierarchy: recursively or non-recursively. In a non-recursive definition there will be generate rules like
<genitem>
  <name>somepage</name>
  <genlist>sectionXY:+20 chapterX:+5 book:+1</genlist>
</genitem>
The use of integer values may make it impossible to accurately indicate the small contribution a single page makes towards the knowledge of a chapter or whole book. Another problem is that for each page its contribution to the section, chapter and book all have to be indicated. It is easier to only indicate how a page contributes to its section, then indicate (once) how much that section contributes to its chapter, and indicate (once) how much that chapter contributes to the whole book:
<genitem>
  <name>somepage</name>
  <genlist>sectionXY:+20</genlist>
</genitem>
<genitem>
  <name>sectionXYZ</name>
  <genlist>chapterX: +25</genlist>
</genitem>
<genitem>
  <name>chapterXY</name>
  <genlist>book:+20</genlist>
</genitem>
Now, in order for page accesses to contribute towards the (knowledge) value of the whole book, user model updates must be performed recursively by AHA. This is easy to implement, and safe for concept hierarchies (acyclic structures with only positive contributions to knowledge values). However, when designing the user model update algorithm so that it works with arbitrary generate rules the following issues have to be dealt with:
  1. There may be loops in the recursion.
    Example: (An update to) A generates +100% of (that update to) B and B generates -100% of A. When page A is read (for the first time and A is desired), the value of A becomes 100 and the value of B becomes 100. But because B is updated, it generates an update to A: A is decreased by 100. This update to A generates an update to B, etc.
  2. It may be difficult to decide how to handle repeat visits to pages.
    Example: A generates +50% of B. When page A is visited for the first time the value for A becomes 100 and that of B becomes 50. We do not want the value of B to become 100 when A is revisited. On the other hand, if some other request decreases the value of A (and maybe recursively also of B) then a repeat visit to A should update B again.
    Another example is when one set of pages is typically accessed by visitors of some type (say students) and another set of pages is typically accessed by other visitors (say faculty). If repeat visits are registered one can let them augment a "concept" that identifies the visitor type. We will see below how this can be done in AHA.
  3. One page access may induce two updates to a concept. If A generates +50% of B and +50% of C, B generates +60% of D and C generates +40% of D, then a (desirable) first access of A generates an update of +30 to D through B and another update of +20 to D through C. Both updates must be applied (correctly) in order to get a predictable (deterministic) result.

4 The Update Algorithm in AHA

The basic user model update algorithm is a simple recursive application of generate rules. In AHA a (single) generate rule is associated with each concept. So if a concept value is updated (and actually changed by the update), AHA will simply look at the generate rule for that concept to determine which other concept values to update. For each of these concepts the update continues recursively. As shown above this basic algorithm can easily be tricked into producing non-deterministic results or infinite loops. There are three easy ways to avoid loops, without giving up on having a recursive algorithm:

  1. Disallow the definition of sets of generate rules with loops. Loop detection is (conceptually) easy and can be done while the author is entering generate rules.
  2. Allow each concept to be updated only once (per run of the algorithm).
  3. Allow each generate rule to be used only once (per run).

(Actually, each of these rules can be modified to allow some other number of iterations instead of 1.)

Each of these measures has its merits and drawbacks. We want to point these out to illustrate that coming up with an update algorithm that is general purpose is non-trivial.

  1. Circular definitions in generate rules are useful for applications like guided tours, where each step in the tour makes the next page in the tour desirable and all other pages in the tour undesirable. One may wish to have the end of the tour lead back to the beginning, thus creating a loop. Depending on how this loop is implemented (using generate rules) it might result in an infinite loop in a simple straightforward update algorithm.
  2. When we allow only one update to a concept (in each run) then the third example of Section 3 would fail: The update of D through B and C would no longer be possible. If only one of these updates is selected the resulting update to D depends on the choice and is thus unpredictable. (We are not arguing here that incrementing D by 30+20=50 is "the" only and correct solution here. We only argue that non-deterministic behavior is not desirable.)
  3. We can extend the third example of Section 3 so that if we allow each generate rule to be used at most once (or any other fixed number of times per run) it will fail. Assume that A generates +50% of B and +50% of C, B generates +60% of D and C generates +40% of D and D generates 50% of E. We already explained that we want D to be updated by B and C. So D is updated with +30 and +20, but this should result in E being updated with +15 and +10. This requires the generate rule from D to E to be executed twice.
The above examples show that these restrictions are all undesirable in some cases. Therefore, in AHA we have chosen a somewhat less intuitive but certain way to avoid infinite loops while ensuring deterministic behavior. We distinguish four cases:

Consider the following example:

<genitem>
  <name>concept1</name>
  <genlist>concept1:0 concept2:+40 concept3:-30 concept4:50</genlist>
</genitem>
(From the above restrictions we already see that concept1 must be a page concept, because it generates an absolute update.)
If the value of concept1 is augmented by X, the value of concept2 is augmented by 40% of X and the generate rule for concept2 will be (recursively) executed. The value of concept3 is decremented by 30% of X, the value of concept4 is set to 50, but the generate rules for concept3 and concept4 are not executed, and finally the value of concept1 is reset to 0.
Note that in this example X may be a positive or a negative value, and independent of that the update to concept2 may recursively trigger other updates while the update to concept3 never triggers other updates. AHA currently has no events that cause the update algorithm to start with a negative X. (This feature may be added in the future.)

By only (recursively) propagating monotonic updates, and by limiting (clipping) all updates to the range 0..100, the update algorithm is guaranteed to terminate. In worst case all values are initially zero and in each recursive step one abstract concept is augmented by 1. In this case the algorithm can run for 100 times the number of abstract concepts steps and then it stops because all abstract concepts' values are 100. So the algorithm always terminates in O(number of abstract concepts) time. Usually only a few recursive steps are necessary, so the time needed to perform user model updates is negligible compared to that for performing the adaptation on the page content. (AHA uses Java servlets; each page access requires very little computation time, typically less than 0.1 sec on a Pentium class system.)

The restrictions on the four types of updates are necessary to make the update algorithm deterministic. If A updates B and C and B and C would each perform an absolute update to D, with different values, then the result of the update algorithm (on D) depends on the order in which the two absolute updates are performed. However, if the updates to B and C cause recursive steps then they must be monotonic and the restriction on monotonic updates then says that B and C must be abstract concepts. The restriction on absolute updates says that B and C are not allowed to generate an absolute update on D because only page concepts are allowed to generate absolute updates.

5. Examples

A first general purpose example is that of a menu structure like the ones that appear in our Web-based course on Graphical User-Interfaces and in an on-line kiosk system with information for interns. Each menu (or submenu) item corresponds to a page of the course. The menu is shown in a separate frame, like:

To implement a menu structure where clicking on a menu item opens up the submenu (and closes the submenus for other menu items) a set of absolute updates can be used. It is not actually the click that triggers AHA to update the user model, but the access to the page associated with the menu item. (The page is displayed in a separate frame and contains a (one-line) Java function to update the menu frame. Reloading the menu is necessary to allow the server to generate the updated menu.)
<genitem>
  <name>firstmenu</name>
  <genlist>firstmenu:100 secondmenu:0 thirdmenu:0 ...</genlist>
</genitem>
...
(The "firstmenu:100" clause is included for clarity but in fact unnecessary. In AHA "firstmenu:+100" is implied by the access to "firstmenu" and that is enough to guarantee that the value of "firstmenu" becomes 100.)
Each submenu is then conditionally included as follows:
<if expr="firstmenu=100>
  <block>
    <ul>
    <li> first submenu conditionally appears
    <li> ...
    </ul>
  </block>
</if>
A second general purpose example is that of grouping users. If certain pages are typically accessed by students, and other pages by faculty, then one can automatically detect whether the user is a student or faculty member. The Eindhoven University of Technology is currently building an adaptive central university website (with general information). Distinguishing groups of users automatically is one of the intended adaptive features. For a student page one writes:
<genitem>
  <name>studentpage1</name>
  <genlist>studentpage1:0 conceptstudentpage1:+100 student:+2 faculty:-1</genlist>
</genitem>
Each access to "studentpage1" resets the "studentpage1" value so that the update is repeated for each visit to that page. By updating "conceptstudentpage1" a copy of the "studentpage1" concept is obtained that can be used to represent the knowledge of "conceptstudentpage1". When "studentpage1" is accessed for the first time (and is desirable) the value of "studentpage1" first goes from 0 to 100. This causes "conceptstudentpage1" to go from 0 to 100 as well. The self update to "studentpage1" resets the "studentpage1" value to 0. So the small updates to "student" and "faculty" are repeated each time "studentpage1" is accessed, but the value for "conceptstudentpage1" remains at 100 and is thus not updated repeatedly. The update behavior for "conceptstudentpage1" is thus identical to what the update behavior for "studentpage1" would have been if there was no self update to "studentpage1". By augmenting (the value of) "student" and decrementing "faculty" each time a student-related page is accessed one indicates that the confidence that the user is a student and not a faculty member increases. Other pages or fragments can be made dependent on expressions like "student > faculty".

6. Conclusions and Future Work

Web-based adaptive systems need not be geared towards a single application or application area. AHA was originally built to make an on-line (hypermedia) course adaptive. After its redesign it is now being used in different applications, and its adaptation features are used to recognize user groups, to support explorer-type menus, and other aspects that are not necessarily related to the user's knowledge. The examples in Section 3 show how "concepts" and "knowledge values for concepts" can be used (some would say abused) to perform different types of adaptation. Other educational adaptive systems have a user model architecture that is similar to that of AHA: with knowledge values for concepts. By making it possible that accessing a page decreases the "knowledge" for some concept (as well as supporting increases to knowledge) other AHS can also be made more versatile, and used to create adaptive Web-sites for different types of applications.

The possible values that can be associated with a concept (in AHA) are limited to a single integer attribute with values between 0 and 100. While this enables us to define a user model update algorithm that always terminates with a deterministic result it is still limited. In the AHAM model for adaptive hypermedia systems, an arbitrary number of attributes (with arbitrary value domains) can be associated with each concept. The recent additions to AHA allow many (educational and non-educational) applications to be implemented using AHA, but in order to become truly versatile AHA needs to be augmented with facilities to define a user model with arbitrary attributes and value domains for each concept. When this will be done the method in which AHA avoids infinite loops and ensures deterministic behavior of the application of adaptation rules can no longer easily be generalized to such rich user models. Further research is needed to determine how to handle (recursive) user model updates for complex user models.

7. References

[B96]
Brusilovsky, P., Methods and Techniques of Adaptive Hypermedia. User Modeling and User-Adapted Interaction, 6, 1996, 87-129. (Reprinted in Adaptive Hypertext and Hypermedia, Kluwer Academic Publishers, 1998, 1-43.)
[DC98]
De Bra, P., L. Calvi., AHA: a Generic Adaptive Hypermedia System. 2nd Workshop on Adaptive Hypertext and Hypermedia, 1998, 1-10. (URL: http://wwwis.win.tue.nl/ah98/DeBra.html)
[BSW96]
Brusilovsky, P., E. Schwarz and T. Weber. A tool for developing adaptive electronic textbooks on WWW. Proceedings of the WebNet'96 Conference, 1996, 64-69.
[DC98]
De Bra, P., Calvi., L., AHA! An Open Adaptive Hypermedia Architecture, The New Review of Hypermedia, 1998.
[DHW99]
De Bra, P., Houben, G.J., Wu, H., AHAM, A Dexter-based Reference Model for Adaptive Hypermedia, Proceedings of the ACM Conference on Hypertext and Hypermedia, 1999.
[PDS98]
Pilar da Silva, D. Concepts and documents for adaptive educational hypermedia: a model and a prototype. 2nd Workshop on Adaptive Hypertext and Hypermedia, 1998, 33-40. (URL: http://wwwis.win.tue.nl/ah98/Pilar/Pilar.html)