Proceedings of the workshop "Adaptive Systems and User Modeling on the World Wide Web",
Sixth International Conference on User Modeling, Chia Laguna, Sardinia, 2-5 June 1997

Work in progress: User modeling in WWW with prerequisite graph model

Ossi Nykänen
Tampere University of Technology (TUT)
Digital Media Institute (DMI)
Department of Mathematics
Hypermedia Laboratory
P.O.Box 692
tel. 358 3 365 3544 fax 358 3 365 3549

Abstract. This paper presents an overview of a prerequisite graph model for modeling users working with mathematical deductive hyperspaces. Prerequisite graph model sets up a frame for representing the knowledge state of the user and diagnoses user's knowledge state within a formula of interaction. Some basic concepts and properties of the model are discussed.

Key words: student modeling, navigation support, adaptive hypermedia.

1. Introduction

It is a difficult task to introduce user model capable of presenting user's abilities on a general application area. There are two fundamentally hard problems to be solved [Ragnemalm, 96]. The structure for representing user's knowledge state and method for diagnosing user's knowledge has to be well chosen. This is clearly a non-trivial task, since user modeling has basically the same tasks and obstacles in the way as the study of artificial intelligence in general.

A good user model should be compact and yet general enough to function within wide application areas. Besides the ability of representing user's knowledge state, user model should also provide tools and functions for working sensibly with information provided. User model should be heavily parametrized and usable with reasonable implementation efforts.

This paper describes a prerequisite graph model for modeling users working with specially constructed hyperspace. Prerequisite graph model is a part of the Hypermedia-Based Learning Environment-project (HBLE) at the hypermedia laboratory at the TUT. The aim of HBLE is to study and develop WWW applications, techniques and material for university-level courses on mathematics especially. Another important aspect of the project is studying conditions and implications of presenting courses on web. On final stage HBLE produces tools and pilot material for creating, studying and administrating university courses with WWW. HBLE is based on the existing work of the hypermedia laboratory at TUT (see, e.g., [Pohjolainen et al, 96] and Matriisilaskenta 1 at <>).

Since student model in our case is not used only for adapting user's view on hyperspace but also for studying student behavior and use of content material, it's quite obvious that the model used should be at least partially transparent. This approach combined with usage requirements stated implies also that student model should be moderately easy to implement and understand. In particular, the need for specialized highly complex student model is not self-evident. It is often more important to provide a model that is usable and suitable for multiple application domains. These requirements suggests the use of overlay model ideology in design (see, e.g., [Brusilovsky, 96]).

In it's basic form prerequisite graph model offers the general functionality needed for appropriate user model for the task. It sets up a frame for representing the knowledge state of the user and diagnoses user's knowledge state within a formula of interaction. Prerequisite graph model sets up a measure for investigating the contextual knowledge of the user and thereby offers direct navigation support. The student-machine interaction in prerequisite graph model is adjusted to match selected application area with tailored interaction modules.

Since author's work is related to the HBLE project, prerequisite graph model is presented from the viewpoint of simple student modeling.

2. Prerequisite graph model

Prerequisite graph model aims to help students studying university courses to navigate in (carefully constructed) course content hyperspace, to follow preprogrammed learning strategies and support student's goal-oriented efforts. Goal-oriented navigational support may be achieved, e.g., by providing hyperspace topics suitable for student's known abilities and interests. The model may also be efficiently used when constructing personalized views in hyperspace.

The basic form of the prerequisite graph model is simple. The model consists of four components: conveniently partitioned hyperspace, a prerequisite graph, a comprehension measure and an interaction formula. It should be noted that partitioning hyperspace and constructing prerequisite graph should be considered as an iterative process that needs thoroughly developed application tools.

2.1. Partitioning hyperspace

The method for partitioning hyperspace, e.g., university course of mathematics, into small meaningful cells suitable for prerequisite graph model, is a straightforward but a non-trivial task. Course content is divided into cells, the smallest knowledge items identified by the student model. From the student's point of view, a cell stands for a single small topic to be studied. Cells may refer to e.g. abstract documents consisting of theory, examples and exercises.

Cells are indexed and labeled according to the information they refer to. Each cell is assigned a topic knowledge measure, a scalar representing the measured knowledge state of the student of the topic. Topic knowledge measures assemble student's topic knowledge vector representing student's knowledge state over whole hyperspace.

2.2. Prerequisite graph

Prerequisite graph defines the overall structure of partitioned hyperspace from the learner's point of view. Hyperspace cells are ordered in a form of a simple semantic network presented as a directed graph. The only semantic taken into consideration is a prerequisite relation, that is, vertex A is said to be prerequisite to vertex B if there exists a path from A to B. In other words, prerequisite graph states what topics should be known before studying further. Arcs of the graph may be weighted in order to compensate the relative "size" of individual topics.

Defining the hyperspace prerequisite semantics makes the guidance and analysis of goal-oriented studying possible. Prerequisite graph is equipped with a comprehension measure, countable scalar value based on the structure of the graph on selected target cells. Comprehension measure allows analyzing user's contextual state of knowledge at large entities. With a comprehension measure, automated guidance system is able to pinpoint students' strong and weak areas of knowledge and thereby help students to focus their efforts on related areas.

Prerequisite relation is the absolute minimum definition of semantics needed for intelligent adaptation. Other types of semantics (is a, part of, implies etc.) may be added to help navigation and guidance, naturally.

2.3. Updating student model

Updating student model is based on interactive exercises. In practice each cell of the hyperspace is assigned with exercises of different levels of difficulty. Student's knowledge state is evaluated according to measurable actions conducted.

A general formula of interaction is defined in order to formalize the student-computer interaction. Formula of interaction characterizes how student's knowledge state is revised. The actual interaction is handled with interaction modules working within the formula of interaction. Interaction modules are adaptive applications specialized in running different types of generic controlled exercises, e.g., simple fill-in questionings and multipart mathematical problems with numerical solutions.

The development of student model is non-monotonous. Student's knowledge state is estimated according to the exercises tried. Properly solved exercises increase the estimate of student's knowledge state within the difficulty and correctness of solved exercises while multiple poorly solved exercises clearly below student's own abilities decrease it.

Since measuring student's knowledge in some specific topic is carried out in a form of exercises, the whole process of learning is based on goals and contexts. Global goals are defined by students themselves or by given course plans. Adaptive interaction formula implies in particular that in the end prerequisite graph becomes highly personal in value. Student is hence free to work individually with truly personalized views in hyperspace in a marketplace learning style focusing efforts mainly in interesting application areas.

2.4. Navigational aids

Together student-sensitive prerequisite graphs and topic comprehension measure form the backbone of navigation tools of the prerequisite graph model. While providing topics suitable for users to study next, model supports also content and link adaptive browsing, finds shortest exercise paths to goals and stands as a global frame for measuring content difficulty on selected application areas.

Additionally, prerequisite graph may also be utilized as a concept map, showing the comprehension connections dealing with prerequisites of various topics. Supplying students complete concept maps, however, is usually not considered as a good policy in teaching.


The theoretical basis of the approach introduced emerges from the hypothesis that the information presented in the application domain may be represented at least in some extent with simple associative network. The assumption is that information presented can be arranged in form of a directed graph. This, however, is not always patently true and should not be regarded as a general guideline.

The intelligent capabilities of prerequisite graph model in navigation support are based on weighted graph analysis only. The model is inadequate in presenting or inferring anything outside this scope. The model is thereby unable of, e.g., answering questions of subject matter. This should not be seen as a drawback, however. It is merely a matter of choice of design. An arbitrary system can reason and behave in such ways that seem intelligent even if the system possess no exact low level representation of the defined application area. In this case, the intelligence of the designed system or method lies in the power of reasoning about navigation aspects.

The prerequisite graph model is suitable for modeling users who work with mathematical sciences, especially in deductive domains. Prerequisite graph may naturally be flattened to resemble a textbook-style linear structure but then most of the expressive powers of the model, as well as it's ability of navigation support, would be lost.

3. Implementation

Prerequisite graph model states no real requirements for programming technique or for platform in terms of student model implementation. The late development of WWW, however, suggests strongly Java and C++ for the appropriate implementation languages. For instance, it seems most beneficial to realize interaction modules as Java applets, since applets naturally fit in the design scheme of WWW educational tools.

In the HBLE project modeling components of the student are implemented with client-server philosophy in mind. The needed software packet for user modeling may be used with standard WWW browser. Browser is used to realize familiar user interfaces on hyperspace and provides the frame for basic interaction. Students work with the learning environment via WWW server. At the beginning of each session student logs in the server providing educational material and starts working. Every function the student does engages scripts in the server side that update the student model, adapt student's view in the hyperspace, and record events for scientific research.

4. Conclusions

Real benefits of using prerequisite graph models in educational hypermedia will not be evident beyond doubt until real student model environments of that kind are implemented. And even then, e.g., the tasks of partitioning hyperspace in chunks suitable for the model or performing a reliable user analysis may prove too difficult or slow to achieve in practice. Creating functional user models requires empirical studies in the end.

Prerequisite graph model offers, however, convenient and intuitively plausible tools and concepts to study and develop hypermedia for education. Student tracking, navigational aids and general modules of interaction will prove to be helpful concepts at least when designing transparent user models for deductive sciences such as mathematics. It should also be noted, that since prerequisite graph model is aimed to function as a general frame of interaction and learning, completing the model in the future is desirable. This is accomplished by adjusting the internal representation or content knowledge of the student model and improving the interaction methods used.


The research is supported by the Academy of Finland, the Finnish Ministry of Education and Tampere University of Technology. Special thanks to professor Seppo Pohjolainen and to my colleagues for their helpful comments.


[Brusilovsky, 1996]
Brusilovsky P.: 1996, 'Methods and Techniques of Adaptive Hypermedia'. User Modeling and User-Adapted Interaction 6, 87-129.

[Pohjolainen et al., 1996]
Pohjolainen, S., Multisilta, J. and Antchev, K.: 1996, 'Matrix algebra with hypermedia'. Education and Information Technologies 1, 123-141.

[Ragnemalm, 1996]
Ragnemalm, E. L.: 1996, 'Student Diagnosis in Practice; Bridging a Gap'. User Modeling and User-Adapted Interaction 5, 93-116.