Figure 1: Part of the meta model for hyperbooks
Nicola Henze Wolfgang Nejdl
University of Hannover University of Hannover
Lange Laube 3, 30159 Hannover Lange Laube 3, 30159
Hannover
Germany Germany
+49 511 762 9716 +49 511 762 9710
henze@kbs.uni-hannover.de nejdl@kbs.uni-hannover.de
http://www.kbs.uni-hannover.de/~henze http://www.kbs.uni-hannover.de/~nejdl
We have implemented an adaptive hyperbook system (KBS Hyperbook) for an introductory course on computer science (CS1). The adaptation techniques used for this course are based on a goal-driven approach. This allows students/users to choose their own learning goal(s) and get suggestions for suitable projects and information units covering the knowledge required to reach these learning goals. In addition, sequential paths through the hyperbook are generated which provide the user with required knowledge.
The user model underlying our hyperbook system 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 for adapting the content or the link structure of the hyper document. For our KBS hyperbook system we follow a constructivistic pedagogic approach, building on project based learning, group work and discussions [7]. Such an project-based 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 functionality:
In this paper we will describe the implementation of these adaptation requirements within our 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 refer to actual content to be displayed over the WWW as pages of the hyperbook (see [5, 6] for a description of the basic principles and the implementation of the KBS hyperbook system).
Figure 1: Part of the meta model for hyperbooks
All implemented adaption strategies in our hyperbook are based on
knowledge items. Such a knowledge item (
) denotes an elementary
knowledge concept of the application domain. The knowledge items are
used for indexing the contents of information units, project units and
for describing the range of goals. They are similar to the domain
model concepts used in [1].
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.). They are semantically related to other information units (i.e. ``object'' and ``object instantiation'' are related information units). 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. We will not further discuss these semantic relationships in this paper but instead refer to [11]. This navigational structure can be annotated (already known, suggested, too difficult) according to the current knowledge of the reader ( adaptive navigational structure). For this annotation, we use the well known traffic light metaphor (see e.g. [1, 12]).
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 user's 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).
The user can select a set of knowledge items (called a goal), and the system can generate (according to the user's knowledge) an index of projects most useful for achieving the user's learning goal (adaptive project selection), a trail for learning these knowledge items (adapted to the user's 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 user's current knowledge (adaptive goal selection), and then propose corresponding projects, trails or information units.
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 user's current knowledge in the form of a
-vector. This separation of 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. The implementation technique used
for our user model is a Bayesian network
.
This BN contains the knowledge items as network nodes. The
dependencies between s are expressed by conditional probabilities
between the s (a detailed description can be found in a
technical
report
[8]). 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.
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 user's
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 user's goal are sufficiently contained
in this project, and
s necessary for project, that are not part of the user's
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). The second one determines whether the actual knowledge of a user is sufficient for performing the suggested project without too many difficulties (fitness). For example, a user interested in learning simple control structures in Java will have difficulties with a project that uses control structures to build a graphical user interface if she/he has no or only beginner's knowledge about graphical user interfaces.
The hyperbook selects the best project(s) by comparing the weighted sums of these two measures. The weights allow to emphasize either one of the aspects matching and fitness, currently we use a factor of 0.5 for each aspect.
We implemented a matching algorithm that calculates the
project-goal-distance between a project and the actual goal based on
the s contained in the goal and their relevance in the project.
Each contained in the goal is assumed to have a relevance of 100.
The relevance of a for a project is defined by its percentage in
relation to the whole project. The matching algorithm uses the
euclidean metric to calculate the distance between a that belongs
to the user's 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 every of the goal that is not contained in
the project, this distance is set to a maximum value of 100. Thus, for
all 
, we have
The project-goal-distance for a project and a given goal is then calculated as the mean value of all these distances:
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 the system's estimation of the
user's knowledge with respect to this .
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 links between information units are 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.
In this section we will specifically compare our system to other hyperbook-like approaches, to other systems which use similar techniques for indexing and describing relevant information. The technical report [8] contains a more detailed comparison including additional systems.
ELM-ART [12] 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 outcoming pages, but store dependency information in a separate user model (the Bayesian network). Observations about the learning progress of a particular user can be used to update the user model independently from particular pages, the system is able to infer for example that prerequisite knowledge of a knowledge item has already been acquired by a user if the knowledge item itself is understood by the user. The way ELM-ART uses learning units is different to our system as we generate individualized learning units (projects plus trails and information units) for the users.
The technique of indexing every page with concepts learned by reading a page, prerequisite knowledge and, in addition, the prerequisite that makes this page superfluous, is also used by [4]. The authoring tool provided in Interbook [3, 1], which evolved from the ELM-ART tutoring system, uses a hierarchically organized domain model based on texts structured with sections, subsections, etc. Based on this domain model, pages of the electronic textbook are generated. Pop [9] uses a hierarchy for knowledge representation. These approaches of using an explicit domain model are similar to our approach, but we allow generally structured domain models based (e.g. based on the description of a software engineering process (``process'', ``phases'', ``activities'')).
PT [10] uses three levels for a customized hypertext: A domain representation level, stereotypes and an individual model. A meta hypertext is used to cover examples of different sorts (mathematical, text-based, tiny-focussed, larger-complete). The used implementation technique (e.g. the use of preprocessor commands) is very different from our approach and handles page adaption. The use of knowledge components for structuring the domain is very similar to the way we model the conditional dependencies for our BN: more general concepts are splitted into refined concepts which themselves may be splitted into refined concepts, etc.
This paper describes the adaptation functionalities of our CS1 learning environment based on active, project-based learning: adaption of information resources, adaptive navigational structures, adaptive trail generation and adaptive project and goal selection, as well as their implementation. We think that these functionalities are necessary for and enhance the utility of adaptive hypermedia systems in project oriented learning environments.
After adding additional material into the hyperbook during the winter semester for our CS1 course and reimplementing our metadata storage module (which manages all structural, semantical and user information) in Java, we have now (hopefully) consolidated the system and will make it available over the WWW under http://www.kbs.uni-hannover.de/hyperbook/ (which displays both the actual CS1 material as well as all metadata information concerning the structural and semantical models used in the hyperbook).
The next step will be the evaluation of the updating functionalities
made possible by the Bayesian network (which stores our learning
dependencies and is updated by evidences about user learning
achievements with respect to our s) and the added flexibility we
gained by decoupling this part of the user model from the structural
and semantical units in our hyperbook, when we further extend and/or
restructure our CS1 material.
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.
is a
random variable with four values, knowledge() is calculated as
the mean value of the probabilities for those four values.