Figure 1: Part of the Meta Model for Hyperbooks
Nicola Henze and Wolfgang Nejdl
University of Hannover
Lange Laube 3, 30159 Hannover, Germany
{henze,nejdl}@kbs.uni-hannover.de
Learning environments that allow for active (constructivist) learning lead to different adaptation requirements than environments based on more conventional teaching strategies. We discuss our approach of building adaptive hyperbooks (adaptive extendible information resources on the internet). The adaptation techniques used in our hyperbooks are based on a goal-driven approach for selecting projects and for generating and presenting prerequisite knowledge necessary for a student project. The user model underlying the hyperbook is a kind of overlay model using a Bayesian Network for estimating user knowledge. We propose a project selection algorithm based on user goals and previous knowledge and a constructive trail mechanism that generates guided tours through the hyperbook containing all prerequisites needed by a particular user to perform a specific project.
One of the main goals of student modeling in educational hypermedia is student guidance [2]. Students/Users have learning goals and previous knowledge which should be reflected by the hyperbook, by adapting the content or the link structure of the hyper document. For our KBS Hyperbook System we follow a constructivistic pedagogic approach, building heavily on project based learning, group work and discussions. Such an active learning environment leads to new requirements for adaptation, in order to adapt the project resources presented in a set of hypermedia documents to the student goals (for a specific project) and the student knowledge. It has to support the student learner by implementing the following adaptation components:
These components are different from the usual techniques used in adaptive hypermedia systems [2], and require different solutions. In this paper we will describe our approach for these adaptation components as well as their implementation. We have implemented an adaptive hyperbook for a CS1 course (introduction to programming using Java), and will use it in our examples.
Problem-oriented and inquiry-oriented learning are two main concepts of constructivist learning environments (see e.g. [10, 5]), as well as other equally important concepts like active construction of understanding, conceptual restructuring, social interactions, reflection and mentoring. In this paper we concentrate on the problem-oriented and inquiry-oriented aspect as well as conceptual structuring, which we reflect in our hyperbook structures. We will not discuss specific pedagogical issues and concepts (for a short discussion of our ideas see e.g. [5]), but will concentrate on the question of how this pedagogical focus changes the structure of the learning materials (the hyperbook) and the requirements for adaptation.
Figure 1: Part of the Meta Model for Hyperbooks
Figure 1 shows part of the high level structure of our hyperbook and simultaneously the different learning strategies in our environment and the resulting link adaptation tasks. The notation we use in this figure is a kind of ER-Modeling notation, which shows concepts as boxes, relations (1:1, 1:n, m:n) as links, and two kinds of adapted relations. The main content of the hyperbook consists of semantic information units and project units. Both of these contain actual content as a WWW page or as a sequence of WWW pages (see [3, 4] for a description of the basic principles and the implementation of the KBS Hyperbook System).
Information units do not correspond to syntactical parts of a book (such as sections or chapters), but semantical parts (such as information units about Java Objects, Iteration Constructs, Parameters, etc.) and fulfill the role of a domain model. Information units are indexed by knowledge items. As information units are already semantic entities, in many cases we have a one to one correspondence between information units and knowledge items. One or more of the knowledge items belonging to a page are the main knowledge items of this page, and for each knowledge item there is exactly one information unit, where it is a main knowledge item. This leads to a kind of knowledge item index, which gives for each knowledge item one main information unit, and some other information units where it occurs too, but not as main knowledge item.
As information units are semantic entities, they are semantically related to other information units (i.e. object and object instantiation). An information unit can also be an instantiation of another information unit (i.e. inheritance is a specific object-oriented concept), or a specialization (i.e. an array is a kind of reference type). These semantic relationships generate the navigational structure between the information units (which is done dynamically by the KBS hyperbook system), so each link between information units corresponds to some kind of semantic relationship between these units. This navigational structure can be annotated (already known, suggested, too difficult) according to the current knowledge of the reader (adaptive navigational structure).
We use a simple traffic light metaphor for annotation: A red ball in front of the link indicates that the corresponding page requires some knowledge the user currently does not have and thus is not recommended for the user (too difficult), while a green ball denotes a recommended link (suggested), which should be understandable by the user. Finally, a grey ball (already known) denotes material which (according to the hyperbook's estimate of the user) is already known to the user.
Project units represent project descriptions, and are indexed by those knowledge items which the student needs to know in order to successfully work on these projects. The relationship between project units and information units can be automatically derived (via the knowledge items) and shows the information units which are relevant for a given project. The links corresponding to this relationship can be adapted as well. This is done by annotating the links according to the users knowledge (already known, suggested, too difficult), leading to an adaptive information resource for a given project. The annotated links are shown as an annotated index (from the project unit to the corresponding information units). The system can also generate a sequential trail (guided tour) through these information units, leaving out already known information units, and ordering the remaining information units, such that difficult information units are suggested at a later stage, when the user knows enough in order to understand them (adaptive trail generation).
Fourth, the user can select a set of knowledge items (called a goal), and the system can generate (according to the users knowledge) an index of projects most useful for achieving the users learning goal (adaptive project selection), a trail for learning these knowledge items (adapted to the users knowledge) or an annotated index of information units for this goal. Finally, the hyperbook system can propose suitable learning goals for the user based on the users current knowledge (adaptive goal selection), and then propose corresponding projects, trails or information units.
The indexing of semantic information units by knowledge items,
as described in the last section, can be considered as a kind of
overlay model. Such a knowledge item
(
) denotes an elementary knowledge concept, the set of knowledge
items describes the knowledge of the application domain. s are the
basic descriptors for the user model. Additionally, we need to model
learning dependencies between s represented by a partial order
between these s, where 1 < 2 denotes the fact, that
1 has to be learned before 2, because understanding 1 is a
prerequisite for understanding 2.
Our user model contains the knowledge items used in the general
hyperbook model, and adds a partial order between these s to
represent learning dependencies. The user model also contains
descriptions of each users current knowledge in the form of a
knowledge vector. This decoupling between hyperbook model and user
model has advantages for authoring the hyperbook, as learning
dependencies between knowledge items are described once in the user
model, and the dependencies between information units of the hyperbook
can be inferred automatically from the -dependencies and the
indexing of the information units by the s.
In order to represent the partial order between the knowledge items,
as well as to facilitate the updating of users knowledge depending on
new information, we have chosen to implement the user model of the KBS
Hyperbook System as a Bayesian network
(BN). This
BN contains the knowledge items as network nodes and provides a
probability for every that corresponds to the system's estimate of
the users knowledge about that . The dependencies between s
are expressed by conditional probabilities between the s. BNs are
useful in user modeling, since they allow to describe the application
domain in a single dependency graph. This graph contains all necessary
prerequisites for a particular knowledge item, models dependencies
among knowledge items and is able to infer for example that
prerequisite knowledge of a has already been acquired by a user if
the itself is understood by the user.
By using a BN, it is possible to use observations about the user's work with the hyperbook and hyperbook projects to update the system's estimate of the users knowledge. For example, if the system's estimate of the users knowledge is too pessimistic, and the user solves an advanced project which the hyperbook had thought to be too difficult for him, the system can use this observation to update its estimate, based on the successful completion of the project unit and the indexing of project units by knowledge items (representing the necessary knowledge to successfully complete this project unit). On the other hand, if we observe an advanced user failing to understand some simple concepts, then the BN can selectively change its estimate of this user with respect to these concepts, without classifying him as a complete beginner, and can suggest specific project units for learning these concepts.
Another advantage of using BNs is the handling of uncertainty in our
observations. We can use every degree of information about the users
knowledge, not only failed / not failed. Currently we use a
vector of four probability values (summing up to 1) describing our
estimate that a user understands a specific knowledge item to the
degrees excellent (expert user), some difficulties (advanced
user), many difficulties (beginner), not ready
(newcomer). This corresponds to using a random variable with four
discrete values. In order to simplify the construction of the
dependency graph, we stratify the s into levels, where the nodes
in each level have a dependency structure expressed by a tree. We
developed a special clustering formalism for this stratified modeling
approach which enables us to generate a directed acyclic graph out of
the dependency graph describing the s and the dependencies among
them (which has advantages for the performance of the inference
algorithms for the BN). The algorithm we use for BN inference is based
on the one in [9]. The current user model for our CS1
Hyperbook ``Introduction into Computer Programming'' contains about
250 nodes.
There are several systems which use the fact, that the user ``reads'' some information, to update the estimate of the users knowledge (e.g. [1]), and also include reading time and/or the sequence of read pages to enhance this estimation. While this is a viable approach, it has the obvious disadvantage, that the fact, that someone is looking at a page may not correspond at all to the knowledge the user has afterwards (maybe the user just took a cup of coffee before going on to the next page). We therefore decided neither to take information about visited pages into account nor the user's path through the hypertext.
Our current system directly asks the user for a feedback on the
different topics ( s) after each project unit. As discussed in the
next section, the user can choose between different answers such as
``topic was easy - I mastered it effortlessly'', ``topic was okay - but
I had some problems, ``topic was hard - I had a few ideas but could
not get the solution and ``no idea about this topic at all''.
Often a user needs information about specific topics but lacks prerequisite knowledge for these topics (e.g. a user wants to work on a project about algorithms but does not understand simple control structures or methods). In such circumstances it does not help to start reading the information unit about algorithms. To support the user in this situation, we compare the user's actual knowledge with the required knowledge needed to understand the requested topic. If the user lacks some requirements we generate a sequence of information units (trail/guided tour) that guides his learning towards his selected topic.
Generation of such a trail is implemented by a depth-first-traversal
algorithm which checks the system's estimate of the user's knowledge
of those s that are prerequisites for the actual goal. The
algorithm checks if all prerequisite knowledge is sufficiently known
by the user - if not, the corresponding information units of the
hyperbook are internally marked. Afterwards a sequence of all those
marked units is generated which leads from the simple to the
complicated topics unto the selected topic. Furthermore, the
hyperbook provides direct access to information resources needed for
the actual task (information goal or project). This information
resource is generated by the same depth-first-traversal algorithm as
mentioned above but contains all found informations units. It
is displayed as a sorted index, each link annotated according to the
user's knowledge using the traffic light metaphor.
To be able to select suitable projects for a user the hyperbook
contains a project library. Each project is indexed by the s,
that have to be understood in order to successfully complete the
project. These s are weighted due to their importance for the
project. As we use a Bayesian Network for modeling the users
knowledge, we do not have to include prerequisite knowledge items,
because they are already taken care of by the dependency structure
expressed by the BN.
A project is useful for a user in his current knowledge state and his situation, if
s comprising the users goal are sufficiently contained
in this project, and
s necessary for project, that are not part of the users
goal, are understood well enough.
These requirements determine the selection criteria for finding an appropriate project for a user that helps the user to achieve his learning goal and reflects his current knowledge state. They are implemented by two algorithms. The first one calculates how good a project matches the goal of a user (project-goal-distance) while the second one calculate the fitness of a user in this project. The hyperbook then chooses the best project by comparing the weighted sums of these two measures.
The matching algorithm (see figure 2)
calculates the project-goal-distance between a project and the actual
goal based on the s and their relevance for the project. It uses
the Euclidean metric to calculate the distance between a that
belongs to the users goal and its relevance for the project. A short
distance means that this is very important for performing the
project while a large value represents the fact that the is not
very relevant for the project. For each of the goal that is not
contained in the project, this distance is set to a maximum value. The
project metric is computed by taking the sum of these distances.
Figure 2: Matching Algorithm of a project to
a user's goal
The second algorithm determines the fitness of a user for a project. To determine this fitness we evaluate the knowledge of the user concerning those parts of the project that do not belong to the user's goal. This enables us to select projects that are based on prerequisites already known by the user, and thus lead him as fast as possible to his goal.
where 
index the project and ID is the
identity function that returns 1, if 
, 0
otherwise, and knowledge(
) is a weighted sum over the four
probability values of the .
If a user wants more guidance during his learning process he can ask the hyperbook for the next learning step. This request is resolved by determining a suitable learning goal depending on his current knowledge. Based on this goal, the hyperbook can propose a suitable project, a set of information units or a trail leading to that goal. To determine the next suitable learning goal, a sequential trail covering the whole hyperbook is calculated. For each item of this trail the system's estimate about the user's knowledge is checked - if the user fails to know some knowledge item, this item is proposed as the next suitable goal.
As discussed previously, the information units are linked based on their semantic relationships. Annotation of these links is very useful if a user wants just wants to browse through the hyperbook. Links are marked as ready_for_reading (green ball in front of a link), not ready_for_reading (red ball) or already_known (grey ball) to help the user select appropriate information units.
An information unit is ready_for_reading if all prerequisites are
known by the user. In terms of our BN this means that an information
unit indexed by a set of s can be read by a user if all children
of these s are sufficiently known. A child of a is
sufficiently known, if it is known, well_known or
excellently_known. For example, a is excellently_known, if the
probability that the user has expert knowledge about it is greater
than the sum of the probabilities for advanced, newcomer and
beginner's knowledge. These definitions are motivated by the
distribution of the probability mass of the four different values for
estimating the user knowledge for a specific knowledge item (expert,
advanced, beginner, newcomer). An information unit is not
ready_for_reading, if at least one of the s expressing required
knowledge for this information unit is not sufficiently known. If the
Bayesian Network of the user model shows that all s belonging to a
page are well_known or excellently_known by a user, this page is
marked as already_known for him. Figure 3 shows an
example page of the hyperbook.
Figure 3: Example page of the Hyperbook
The proposed adaptation component for our hyperbooks is distinct to other approaches in student and user modeling as it uses a Bayesian Network for modeling all relevant knowledge needed for adaption purposes. In addition, it is centered around active learning and thus defines and implements several different adaptation requirements and tasks for generating customized learning units with projects, information resources and sequentialized, individual learning paths through the hyperbook. In the following we will compare our system to other hyperbook-like approaches, to other systems which use similar techniques for indexing and describing relevant information, and to systems that use Bayesian probabilities for maintaining a users knowledge.
ELM-ART [11] and its successors implement episodic user modeling based on a hierarchically organized conceptual network for knowledge representation. Each unit of the network contains the text of the page, information to relate this page to other units and a description about incoming, outgoing and related concepts. Thus the conceptual network contains both information about the application domain and the reading sequence. We use two different models for describing the user and the application domain. Therefore the author does not need to explicitly model incoming and outgoing pages, but stores dependency information in a separate user model (the Bayesian Network), which allows better updating of user knowledge estimation by observations.
The authoring tool provided in Interbook [1], which evolved from the ELM-ART tutoring system, uses a hierarchically organized domain model based on texts structured by sections, subsections, etc. Based on this domain model, pages of the electronic textbook are generated. POP [6] also uses an object hierarchy for knowledge representation. These approaches of using an explicit domain model are similar to ours. However, information units in our system are not only related in a hierarchical way, but can be arbitrary relationships. PT [8] uses three levels for a customized hypertext: A domain representation level, stereotypes and an individual model. A meta structure is used to describe different kinds of examples. The implementation (e.g. the use of preprocessor commands) is very different from our approach and basically performs page adaption.
A comprehensive review of current work using uncertainty management techniques in user modeling is given in [7]. The use of BNs in our hyperbook is distinct from these approaches. We use a single, overall dependency graph for modeling all dependencies between knowledge items. Clearly, this graph is not as fine grained as a graph that is suited for plan recognition or coached problem solving as it serves different purposes. The BN used for our user model has to model dependencies among knowledge units which describe the application domain. Both user model and domain model are required to implement hyperbooks.
The Bayesian student modeling framework presented in this paper contributes to probabilistic user modeling in a number of ways. First, we identified new requirements for learning environments that are based on active, project-based learning. Second, we defined adaptation tasks necessary for such environments such as adaption of information resources, adaptive navigational structures, adaptive trail generation and adaptive project and goal selection. Third, we discussed our implementation of this adaptation tasks in our hyperbook system based on Bayesian Networks. Future work will concentrate on extending the project library implemented in our CS1 hyperbook, use the system to develop an hyperbook for AI (based on our conventional script) and implement automated integrity checking for indexing the information units.
Student Modeling in an Active Learning Environment using Bayesian Networks
This document was generated using the LaTeX2HTML translator Version 96.1-h (September 30, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 um.
The translation was initiated by Nicola Henze on Sat Nov 14 14:49:21 MET 1998
with
associated probabilities and a labeled directed acyclic graph G
encoding conditional probabilities between these random variables. The
vertices of G correspond to the random variables 
and the edges represent conditional dependencies between them. A
conditional dependency links a child variable to a set of parent
variables and is defined by the conditional distributions of the child
variable given the configuration of its parent variables.