Peter Brusilovsky
email: peterb@mail.sis.pitt.edu

Christoph Peylo
email: christoph.peylo@sla.de

Adaptive and Intelligent Web-based Educational Systems

. AIWBES attempt to be more adaptive by building a model of the goals, preferences and knowledge of each individual student and using this model throughout the interaction with the student in order to adapt to the needs of that student. They also attempt to be more intelligent by incorporating and performing some activities traditionally executed by a human teacher -such as coaching students or diagnosing their misconceptions. The first pioneer intelligent and adaptive Web-based educational systems were developed in 1995

systems we stress that these systems attempt to be different for different students and groups of students by taking into account information accumulated in the individual or group student models. Speaking about intelligent systems we stress that these systems apply techniques from the field of Artificial Intelligence (AI) to provide broader and better support for the users of Web-based educational systems. While the majority of systems mentioned in this introduction can be classified as both intelligent and adaptive, a solid number of systems fall in exactly one of these categories (Figure 1). For example, many intelligent diagnosis systems including German Tutor [START_REF] Heift | Web delivery of adaptive and interactive language tutoring[END_REF] and SQL-Tutor [START_REF] Mitrovic | An Intelligent SQL Tutor on the Web[END_REF] are non-adaptive, i.e., they will provide the same diagnosis in response to the same solution to a problem regardless of the student's past experience with the system. From another side, a number of adaptive hypermedia and adaptive information filtering systems such as AHA [START_REF] De Bra | AHA! An open Adaptive Hypermedia Architecture[END_REF] or WebCOBALT [START_REF] Mitsuhara | An adaptive Web-based learning system with a free-hyperlink environment[END_REF] use efficient, but very simple techniques that can hardly be considered as "intelligent". The reason to focus on both intelligent and adaptive systems in this issue is that that the intersection is still large, the borders between "intelligent" and "non-intelligent" are not clear-cut, and both groups are certainly of interest for AI in Education (AI-Ed) community.

Intelligent ES Adaptive ES

Fig. 1. Relationship between adaptive and intelligent educational systems

Existing AIWBES are very diverse. They offer various kinds of support for both students and teachers involved in the process of Web-enhanced education. To help in understanding this variety of systems and ideas, the author's earlier review of adaptive hypermedia [START_REF] Brusilovsky | Methods and techniques of adaptive hypermedia[END_REF] suggested focusing on adaptive and intelligent technologies. By adaptive and intelligent technologies we mean essentially different ways to add adaptive or intelligent functionality to an educational system. A technology usually can be further dissected into finer-grain techniques and methods, which correspond to different variations of this functionality and different ways of its implementation [START_REF] Brusilovsky | Methods and techniques of adaptive hypermedia[END_REF].

An earlier review [START_REF] Brusilovsky | Adaptive and Intelligent Technologies for Web-based Education[END_REF] identified five major technologies used in AIWBES (Figure 2). These technologies have immediate roots in two research fields that were well established before the Internet age -Adaptive Hypermedia and Intelligent Tutoring Systems (ITS). Since their application in the Web context was relatively straightforward, these technologies were the first to appear in AIWBES and can be considered as "classic" AIWBES technologies. According to their origin, the review [START_REF] Brusilovsky | Adaptive and Intelligent Technologies for Web-based Education[END_REF] grouped the five classic technologies into Adaptive Hypermedia technologies and Intelligent Tutoring technologies (Figure 2). The review also identified and grouped into "Web-inspired" AIWBES technologies some new technologies that appeared on the Web more recently and had almost no direct roots in pre-internet educational systems. The lack of examples of Web-inspired technologies at the time of writing the review [START_REF] Brusilovsky | Adaptive and Intelligent Technologies for Web-based Education[END_REF] did not allow further classification of these technologies.

In this introductory article we follow the review [START_REF] Brusilovsky | Adaptive and Intelligent Technologies for Web-based Education[END_REF] in grouping together similar AIWBES technologies and identifying the roots of these technologies. We leave the set of classic Adaptive Hypermedia and Intelligent Tutoring technologies intact but subdivide the original group of Web-inspired technologies into three groups: Adaptive Information Filtering, Intelligent Class Monitoring, and Intelligent Collaboration Support. The five resulting groups of technologies and their fields of origin are shown in Figure 3. Table 1 provides a good overview of these five groups listing technologies and sample systems for each of the groups. It also helps the reader understand the role of the papers presented in this special issue (shown in bold in Table 1) in the overall context of work on AIWBES. The remaining part of this section describes briefly the technologies group by group while also introducing the papers of this special issue. Major Intelligent Tutoring technologies are: curriculum sequencing, intelligent solution analysis, and problem solving support. All these technologies have been well explored in the field of ITS. The goal of curriculum sequencing technology is to provide the student with the most suitable individually planned sequence of topics to learn and learning tasks (examples, questions, problems, etc.) to work with. It helps the student find an "optimal path" through the learning material. In the context of Web-based education (WBE), curriculum sequencing technology becomes very important due to its ability to guide the student through the hyperspace of available information. Curriculum sequencing was one of the first to be implemented in such early AIWBES as ELM-ART (Brusilovsky, et al., 1996a) and CALAT [START_REF] Nakabayashi | An intelligent tutoring system on the WWW supporting interactive simulation environments with a multimedia viewer control mechanism[END_REF]. Among the systems featured in the special issue ELM-ART [START_REF] Weber | ELM-ART: An adaptive versatile system for Web-based instruction[END_REF] and KBS-Hyperbook [START_REF] Henze | Adaptation in open corpus hypermedia[END_REF] provide two good examples of curriculum sequencing. In ELM-ART sequencing is implemented in the form of a recommended link and an adaptive "next" button. In KBS-Hyperbook it is implemented as a suggested learning path. Intelligent solution analysis deals with students' solutions of educational problems (which can range from a simple question to a complex programming problem). Unlike non-intelligent checkers which can only tell whether the solution is correct or not, intelligent analyzers can tell what is wrong or incomplete and which missing or incorrect pieces of knowledge may be responsible for the error. Intelligent analyzers can provide the student with extensive error feedback and update the student model. Due to its low interactivity and natural match to Web form-submission interface, this technology was also one of the first to be implemented on the Web in such early AIWBES as ELM-ART (Brusilovsky, et al., 1996a) and WITS [START_REF] Okazaki | An Implementation of an intelligent tutoring system (ITS) on the World-Wide Web (WWW)[END_REF]. The systems SQL-Tutor [START_REF] Mitrovic | An Intelligent SQL Tutor on the Web[END_REF], German Tutor [START_REF] Heift | Web delivery of adaptive and interactive language tutoring[END_REF] and the most recent version of ELM-ART [START_REF] Weber | ELM-ART: An adaptive versatile system for Web-based instruction[END_REF] presented in this special issue demonstrate several ways of implementing intelligent solution analysis on the WWW.

The goal of interactive problem solving support is to provide the student with intelligent help on each step of problem solving -from giving a hint to executing the next step for the student. Interactive problem solving support technology is not as popular in Web-based systems as in standalone intelligent tutoring systems -mainly due to implementation problems. As was demonstrated by pioneer systems, pure server-side implementations such as PAT-Online [START_REF] Ritter | Pat Online: A Model-tracing tutor on the World-wide Web[END_REF] can not actively watch the student's actions and can only provide help by request. Pure client-side implementations such as ADIS [START_REF] Warendorf | ADIS -An animated data structure intelligent tutoring system or Putting an interactive tutor on the WWW[END_REF] have a complexity limit.

The proper functionality and level of complexity to implement interactive problem solving support require client-server implementation such as AlgeBrain [START_REF] Alpert | Deploying Intelligent Tutors on the Web: An Architecture and an Example[END_REF], but such systems are harder to develop. Among the systems featured in this special issue, ActiveMath [START_REF] Melis | ActiveMath: A web-based learning environment[END_REF] implements interactive problem solving support in its Omega proof planer. In addition to that, ELM-ART [START_REF] Weber | ELM-ART: An adaptive versatile system for Web-based instruction[END_REF] provides a unique example of example-based problem solving support -a different low-interactive support technology that became quite promising in Web context. Adaptive presentation and adaptive navigation support are two major technologies explored by adaptive hypertext and hypermedia systems. The goal of adaptive presentation technology is to adapt the content presented in each hypermedia node (page) to student goals, knowledge, and other information stored in the student model. In a system with adaptive presentation, the pages are not static but adaptively generated or assembled for each user. ActiveMath [START_REF] Melis | ActiveMath: A web-based learning environment[END_REF] featured in this special issue provides one of the most advanced existing examples of adaptive presentation. In addition, ELM-ART [START_REF] Weber | ELM-ART: An adaptive versatile system for Web-based instruction[END_REF] demonstrates a special form of adaptive presentation -adaptive warnings about the educational status of the current page.

MetaLinks [START_REF] Murray | MetaLinks: Authoring and affordances for conceptual and narrative flow in adaptive hyperbooks[END_REF] demonstrates the use of adaptive presentation for "narrative smoothing".

The goal of adaptive navigation support technology is to assist the student in hyperspace orientation and navigation by changing the appearance of visible links. For example, an adaptive hypermedia system can adaptively sort, annotate, or partly hide the links of the current page to make it easier to choose where to go next. Adaptive navigation support shares the same goal with curriculum sequencing -to help students find an "optimal path" through the learning material. At the same time, adaptive navigation support is less directive and more "cooperative" than traditional sequencing: it guides students while leaving them the choice of the next knowledge item to be learned and next problem to be solved. In the WWW context where hypermedia is a basic organizational paradigm, adaptive navigation support becomes both natural and efficient. It was among the three earliest AIWBES technologies, explored in such systems as ELM-ART (Brusilovsky, et al., 1996a), InterBook [START_REF] Brusilovsky | A tool for developing hypermedia-based ITS on WWW[END_REF], and De Bra's adaptive hypertext course [START_REF] De Bra | Teaching Hypertext and Hypermedia through the Web[END_REF] and became arguably the most popular technology in AIWBES. Half of the systems presented in this special issue use this technology. KBS-Hyperbook [START_REF] Henze | Adaptation in open corpus hypermedia[END_REF], ActiveMath [START_REF] Melis | ActiveMath: A web-based learning environment[END_REF], and ELM-ART [START_REF] Weber | ELM-ART: An adaptive versatile system for Web-based instruction[END_REF] demonstrate several variants of adaptive link annotation. MLTutor [START_REF] Smith | MLTutor: An Application of Machine Learning Algorithms for an Adaptive Web-based Information System[END_REF] uses link sorting and generation.

Adaptive information filtering (AIF) is a classic technology from the field of Information Retrieval. Its goal is finding a few items that are relevant to user interests in a large pool of (textbased) documents. On the Web this technology has been used in both search and browsing context. It has been applied to adapt the results of Web search using filtering and ordering and to recommend the most relevant documents in the pool using link generation. While the engines used by AIF systems are very different from adaptive hypermedia engines, at the interface level Web-based AIF most often use adaptive navigation support techniques. There are two essentially different kinds of AIF engines that can be considered as two different AIF technologiescontent-based filtering and collaborative filtering. The former relies on document content while the latter ignores the content completely attempting instead to match the users who are interested in the same documents. Modern AIF extensively uses machine learning techniques, especially for content-based filtering. Being very popular in the field of information systems, AIF has not been used in educational context in the past. The amount of learning content was relatively small and the need to guide the user to most relevant material was well supported by adaptive sequencing and adaptive hypermedia. However, the Web with its abundance of non-indexed "open corpus" educational resources has made AIF very attractive for educationalists. MLTutor [START_REF] Smith | MLTutor: An Application of Machine Learning Algorithms for an Adaptive Web-based Information System[END_REF] featured in this special issue presents one of the first interesting examples of applying content-based AIF to education. An educational example of collaborative AIF can be found in WebCOBALT [START_REF] Mitsuhara | An adaptive Web-based learning system with a free-hyperlink environment[END_REF].

Intelligent collaborative learning is an interesting group of technologies developed at the crossroads of two fields originally quite distant from each other: computer supported collaborative learning (CSCL) and ITS. The recent stream of work on using AI techniques to support collaborative learning has resulted in an increasing level of interaction between these fields. While early work on intelligent collaborative learning was performed in pre-Web context [START_REF] Chan | Learning companion systems[END_REF][START_REF] Hoppe | Use of multiple student modeling to parametrize group learning[END_REF], it's the Web and WBE that provided both a platform and an increasing demand for this kind of technology. In WBE the need for collaboration support tools is critical because students rarely (or never) meet in person. Intelligent technologies can dramatically extend the power of simple collaboration support tools (such as threaded discussion groups and shared whiteboards) provided by various course management systems. Currently we can list at least three distinct technologies within the intelligent collaborative learning group: adaptive group formation and peer help, adaptive collaboration support, and virtual students. A good example of adaptive collaboration support is provided by COLER [START_REF] Constantino Gonzalez | Coaching web-based collaborative learning based on problem solution differences and participation[END_REF] featured in this special issue.

Technologies for adaptive group formation and peer help attempt to use knowledge about collaborating peers (most often represented in their student models) to form a matching group for different kinds of collaborative tasks. Early examples include forming a group for collaborative problem solving [START_REF] Hoppe | Use of multiple student modeling to parametrize group learning[END_REF][START_REF] Ikeda | Opportunistic group formation[END_REF] and finding the most competent peer to answer a question [START_REF] Mccalla | A peer help system for workplace training[END_REF]. Both streams of work are expanding now. The pioneer teams have generalized and expanded their work [START_REF] Greer | Supporting Peer Help and Collaboration in Distributed Workplace Environments[END_REF][START_REF] Mühlenbrock | A Framework System for Intelligent Support in Open Distributed Learning Environments[END_REF]) and a number of new teams started research in this direction.

Technologies for adaptive collaboration support attempt to provide an interactive support of a collaboration process just like interactive problem support systems assist an individual student in solving a problem. Using some knowledge about good and bad collaboration patterns (provided by the system authors or mined from communication logs) collaboration support systems such as COLER [START_REF] Constantino Gonzalez | Coaching web-based collaborative learning based on problem solution differences and participation[END_REF] or EPSILON [START_REF] Soller | A computational approach to analysing online knowledge sharing interaction[END_REF] can coach or advise collaborating peers. This is a new but rapidly expanding direction of work that draws its ideas from classic ITS, CSCL and machine learning fields.

In contrast, virtual students technology is comparatively old. Instead of supporting learning or collaboration from a position of someone superior to students (a teacher or an advisor), this technology attempts to introduce different kinds of virtual peers into a learning environment: a learning companion [START_REF] Chan | Learning companion systems[END_REF], a tutee, or even a troublemaker [START_REF] Frasson | An actor-based architecture for intelligent tutoring systems[END_REF]. In the WBE context where students communicate mainly through low-bandwidth channels (e-mail, chat, forums) a virtual student becomes a very attractive embodiment to implement different support strategies. We expect more research in this direction and its further integration with animated agents and intelligent collaboration support streams.

Intelligent class monitoring is another AIWBES technology motivated by WBE. In the WBE context a "remote teacher" can't see the signs of understanding and confusion on the faces of the students. With this severe lack of feedback it becomes hard to identify troubled students who need additional attention, bright students who need to be challenged, as well as the parts of learning material that are too easy, too hard, or confusing. WBE systems can track every action of the student, but it's almost impossible for a human teacher to make any sense of the large volume of data they are collecting. Intelligent class monitoring systems attempt to use AI to help the teacher in this context. This stream of work was pioneered by HyperClassroom [START_REF] Oda | Searching deadlocked Web learners by measuring similarity of learning activities[END_REF] that used fuzzy technology to identify "deadlocked" WBE students. Until recently, HyperClassroom was the only example in this class, but the last two years have brought a few other examples [START_REF] Merceron | A Web-based tutoring tool with mining facilities to improve learning and teaching[END_REF][START_REF] Romero | Discovering prediction rules in AHA! courses[END_REF]. The earlier review [START_REF] Brusilovsky | Adaptive and Intelligent Technologies for Web-based Education[END_REF] grouped intelligent class monitoring together with intelligent collaboration support. Now we argue that this stream of work has to have a group of its own since it focuses on different goals (teacher support) and relies on a different group of AI technologies (mainly data mining and machine learning). At the same time, a few systems [START_REF] Chen | An instructional assistant agent for distributed collaborative learning[END_REF][START_REF] Mbala | Integrating of automatic tools got displaying interaction data in computer environments for distance learnings[END_REF] that monitor the collaboration process but report the problems to the teacher instead of influencing the very collaboration fall between intelligent class monitoring and collaboration support. Unfortunately, no examples of intelligent class monitoring are presented in this special issue and we are not able yet to identify different technologies within this class. We expect, however, that this stream of work will grow in the very near future.

ADAPTIVE AND INTELLIGENT WEB-BASED EDUCATIONAL SYSTEMS: A CHANGE OF AI-ED PARADIGM?

The analysis of adaptive and intelligent Web-based educational systems on the level of technologies reveals that they have a lot in common with pre-Web systems. Should we consider AIWBES simply as Web implementation of ideas explored earlier? Can we say that the only difference between Web and pre-Web adaptive and intelligent educational systems is the implementation platform? We claim that the difference between Intelligent Tutoring Systems of 1980 and 1990 and the new breed of Web-based systems that became popular at the end of 1990 is qualitative. While on the level of individual technologies we can easily see the similarity between Web and pre-Web systems, on the level of complete systems we can observe rather large differences in the major focus of these systems, their application context, and the overall set of supported features. The new platform and the new application context of Web-based systems are causing a major change of the development paradigm. Adaptive and intelligent Web-based educational systems are forming a new development paradigm in the field of Artificial Intelligent in Education.

If we analyze the variety of adaptive and intelligent educational systems developed since the birth of the AI-Ed field in 1970, we can distinguish at least three major development paradigms (Table 2). The motivation behind the earliest AI-Ed systems was to fix the obvious problems of the then dominant Computer-Assisted Instruction (CAI): provide more intelligent evaluation of student knowledge than traditional "yes-no" and "multiple-choice" questions and more adaptive sequencing of instructional fragments than traditional linear and branching approaches [START_REF] Carbonell | AI in CAI: An artificial intelligence approach to computer aided instruction[END_REF]. These systems were called Intelligent CAI (ICAI) or AI-CAI. ICAI did not attempt to change the then well-established application context and major goal of CAI systems, that is transferring new knowledge to the student and ensuring its acquisition. Both CAI and ICAI were intended to replace all or part of traditional classroom instruction. The major intelligent technologies were sequencing [START_REF] Brown | A model-driven question-answering system for mixedinitiative computer-assisted instruction[END_REF][START_REF] Carbonell | AI in CAI: An artificial intelligence approach to computer aided instruction[END_REF][START_REF] Koffman | A model for generative CAI and concept selection[END_REF] and intelligent solution analysis [START_REF] Brown | Diagnostic models for procedural bugs in basic mathematical skills[END_REF]. The major computing platforms behind original CAI were classic mainframes and (later) mini-computers.

At the end of 1970 the new "tutoring" paradigm was established [START_REF] Burton | An investigation of computer coaching for informal learning activities[END_REF][START_REF] Clancey | Tutoring rules for guiding a case method dialog[END_REF]. It was later propagated by John Anderson's school and become dominant in 1980 and early 1990. The champions of the new paradigm claimed that the main job of AI-Ed systems is not to replace the teacher in the classroom in presenting new material, but to provide an individual tutor that can support the students in the process of solving educational problems and procedural knowledge formation. Since the old "AI-CAI" name was not relevant anymore, the new systems and the whole field adopted the name Intelligent Tutoring Systems (ITS). On the level of technologies the change was more gradual -the new technology of interactive problem solving support quickly became dominant while the relative amount of work on older technologies gradually decreased. The interest in sequencing decreased since most ITS refuse to deal with presentation of educational material leaving it to the human teacher. As for intelligent solution analysis, it was considered inferior to the new problem solving support technology: the real challenge was to develop fully interactive support. The change of the application context and the dominated technologies were supported (technology advocates may even say driven) by the change of the implementation platform from mainframes to personal computers with their capabilities to implement attractive problem solving interfaces. technologies as well as the change in the usage profile of known technologies. Adaptive sequencing became popular again -now together with adaptive hypermedia and adaptive information filtering. Intelligent solution analysis became more attractive than interactive problem solving support due to its natural fit to low-interactive HTTP protocol. Collaborative learning and class monitoring technologies became an interesting new target for the application of AI techniques. More important, the set of the needs supported by a single system as well as the set of technologies used in a single system has grown quite visibly. While almost all pre-Web systems have focused on one specific need championing and extending one of the known technologies, almost all AIWBES use several technologies and become more complete as "onestop" educational systems. This trend is clearly demonstrated by ELM-ART system [START_REF] Weber | ELM-ART: An adaptive versatile system for Web-based instruction[END_REF] presented in this special issue. While ELM-PE [START_REF] Weber | ELM-Programming-Environment: A Tutoring System for LISP Beginners[END_REF], the prototype of ELM-ART was a purely problem solving support system, ELM-ART driven by WBE needs became a very versatile system supporting nearly all the needs of students and teachers.

THE PROMISES OF ADAPTIVE AND INTELLIGENT WEB-BASED EDUCATIONAL SYSTEMS

Adaptive and intelligent Web-based educational systems form a new and exciting stream of work in AI-Ed field. As demonstrated by the papers included in this special issue, the Web offers an opportunity to apply a much larger variety of AI technologies in educational context. It offers a number of new research challenges and a number of opportunities to fuse AI-Ed research with several neighboring fields. The Web also provides an excellent implementation platform for AI-Ed researchers. Systems developed on the Web have longer lifespan and better visibility. A research idea implemented in a Web-based system has much better chances to influence the research community than an idea simply presented in a paper. Moreover, AIWBES with their simplicity of access and visibility have much greater chances to influence practitioners working in the field of Web-based education. We expect that the ideas developed in these systems and the systems themselves will have a growing use in practical Web-based education. This will allow AI-Ed as a research field to provide a greater impact on the improvement of everyday educational process. As guest editors, we hope that the papers assembled in this special issue provide both a good overview of the emerging area and a good inspiration for the newcomers to the field.

Fig. 2 .

 2 Fig. 2. Classic AIWBES technologies and their origins

Table 1

 1 AIWBES technologies, their origin, and representative systems. Systems featured in the special issue are shown in bold.

	Sources of	Technologies	Sample systems
	AIWBES
	technologies
	Adaptive	• Adaptive navigation	AHA (De Bra, et al., 1998)
	Hypermedia	support	InterBook (Brusilovsky, Eklund, &
		• Adaptive presentation	Schwarz, 1998)
			KBS-Hyperbook (Henze, & Nejdl,
			2001)
			MetaLinks (Murray, 2003)
			ActiveMath (Melis, et al., 2001)
			ELM-ART (Weber, & Brusilovsky,
			2001)
			INSPIRE (Papanikolaou, Grigoriadou,
			Kornilakis, & Magoulas, Submitted)
	Adaptive	• Content-based filtering	MLTutor (Smith, & Blandford, 2003)
	Information	• Collaborative filtering	WebCOBALT (Mitsuhara, et al., 2002)
	Filtering
	Intelligent		HyperClassroom (Oda, Satoh, &
	Class		Watanabe, 1998)
	Monitoring
	Intelligent	• Adaptive group formation	PhelpS (Greer, et al., 1998)
	Collaborative	and peer help	HabiPro (Vizcaíno, Contreras, Favela, &
	Learning	• Adaptive collaboration	Prieto, 2000)
		support (coaches and	COLER (Constantino Gonzalez,
		monitors)	Suthers, & Escamilla De Los Santos,
		• Virtual students	2003)
			EPSILON (Soller, & Lesgold, 2003)
	Intelligent	• Curriculum sequencing	VC-Prolog-Tutor (Peylo, Teiken,
	Tutoring	• Intelligent solution analysis	Rollinger, & Gust, 1999)
		• Problem solving support	SQL

-Tutor (Mitrovic, 2003) German Tutor (Heift, et al., 2001) ActiveMath (Melis, et al., 2001) ELM-ART (Weber, et al., 2001)

Personal computers WWW

What we observe right now is a new change of the paradigm also driven to some extent by the change of the platform and the application context. The motivating application context behind Web-based educational (WBE) systems is, naturally, Web-based education. In this context with no human teacher, tutor, or even peer nearby, the educational system has to provide a one-stop solution for all student's needs. The old CAI motivation to "deliver knowledge" came back into focus and even became dominant (though the new generation of WBE systems choose to deliver the necessary educational material using flexible hypertext rather than rigid CAI). This is well demonstrated by the subset of systems presented in this special issue -the majority of them include (or ever focused on) the delivery of on-line course material -with adaptation as in MetaLinks, KBS-Hyperbook, ActiveMath, ELM-ART, MLTutor or without it as in German Tutor. The need to support problem solving remained in focus. New needs specific to modern WBE became critical -such as the need to support collaborative work and the need to support the remote teacher working with the invisible class. This context caused the appearance of new


A Serengul Guven Smith

Ann Blandford
email: a.blandford@ucl.ac.uk

MLTutor: An Application of Machine Learning Algorithms for an Adaptive Web-based Information System

One problem that commonly faces hypertext users, particularly in educational situations, is the difficulty of identifying pages of information most relevant to their current goals or interests. In this paper, we discuss the technical feasibility and the utility of applying machine learning algorithms to generate personalised adaptation on the basis of a user's browsing history in hypertext, without additional input from the user. In order to investigate the viability of this approach, we developed a Web-based information system called MLTutor. The design of MLTutor aims to remove the need for pre-defined user profiles and replace them with a dynamic user profile-building scheme in order to provide individual adaptation. In MLTutor, this adaptation is achieved by a combination of conceptual clustering and inductive machine learning algorithms. An evaluation technique that probes the detailed effectiveness of the adaptation is presented. The use of dynamic user profiles has been shown to be technically feasible; however, while a superficial evaluation indicates that it is educationally effective, the more thorough evaluation performed here shows that the positive results may be attributed to other causes. This demonstrates the need for thorough evaluation of adaptive hypertext systems.

INTRODUCTION

The idea of an intelligent personal assistant is not new. In the early 80's [START_REF] Michalski | Pattern recognition as rule-guided inductive inference[END_REF] anticipated that individuals, in the expanding information society predicted by [START_REF] Bush | As We May Think[END_REF], would need intelligent personal assistants to cope with the overwhelming amounts of available information and the complexity of every day decision making. In addition, [START_REF] Michalski | Pattern recognition as rule-guided inductive inference[END_REF] proposed that the knowledge and the function of such (computer based) assistants should be dynamic in order to adapt themselves to changing demands; in other words any such systems should be able to learn.

Traditionally, most research on computer based (machine) learning has dealt with the development of techniques for solving engineering problems and many of the systems developed have been tested on simplified artificial problems [START_REF] Reich | Towards Practical Machine Learning Techniques[END_REF]. Consequently, the machine learning research field has historically been very rich in terms of theoretical developments but lacks practical applications with direct links between theory and practice. This is particularly noticeable in the field of adaptive educational hypermedia, where many developments are restricted to small, hand-crafted systems and omit thorough evaluations of utility.

The research presented in this paper is an attempt to bridge the gap between theory and practice in the domain of WWW-based systems. The World Wide Web (WWW) is an excellent mechanism for the dissemination of information and a few WWW-based systems can provide support by adapting material to the needs of a user. A number of these systems employ machine learning techniques (e.g. NewsWeeder [START_REF] Lang | NewsWeeder:Learning to filter Netnews[END_REF]; Magi [START_REF] Payne | Interface agents that Learn: An Investigation of Learning Issues in a Mail Agent Interface[END_REF]; WebWatcher [START_REF] Armstrong | WebWatcher: A Learning Apprentice for the World Wide Web[END_REF]; LAW [START_REF] Edwards | Experience with learning agents which Manage Internet-Based Information[END_REF]; MANIC [START_REF] Stern | Adaptive Content in an Online Lecture System[END_REF]). However, the key challenge in such systems is to be able to capture an individual user's preferences and specific information needs and utilise this information to adapt the environment to the user. These systems do not meet the criterion for the ideal adaptive system as described by [START_REF] Brusilovsky | Methods and techniques of adaptive hypermedia. User modelling and User-Adapted Interaction[END_REF]:

" … while the user is simply working in an application system, the adaptation component watches what the user is doing, collects the data describing user's activity, processes these data to build the user model, then provides an adaptation. Unfortunately, such an ideal situation is very rarely met in adaptive hypermedia systems…". With few exceptions, such as the referrer page based personalisation of PWW [START_REF] Kushmerick | Towards Zero-Input Personalization: Referrer-Based Page Prediction[END_REF], existing systems intrude by needing to interrogate users about their requirements or interests. This can be in the form of an initial registration process where user needs are assessed, or during interaction with the system in the form of questions or the provision of relevance feedback. The information gathered in this process is typically used to allocate a pre-defined stereotypical profile to a user, which is used to control adaptation (e.g. [START_REF] Pazzani | Syskill & Webert: Identifying interesting web sites[END_REF]. The development of such profiles is a very time consuming and laborious task and consequently most prototypes are restricted to one domain [START_REF] Edwards | Exploiting Learning Technologies for World Wide Web Agents[END_REF]. The knowledge bases of these systems are likely to be "hand-crafted" [START_REF] Hohl | Hypadapter: An Adaptive Hypertext System for Exploratory Learning and Programming[END_REF]. There is an overhead in generating such stereotypical profiles and a danger that an inappropriate one may be selected for a user.

The work reported here addresses the ideal as outlined by Brusilovsky: basing adaptation on browsing history. No additional feedback is required from a user and, by using machine learning techniques to dynamically analyse the browsing history, there are no requirements for pre-defined profiles to be constructed.

The prototype system implemented to test our approach is called MLTutor. Although it is not a tutoring system, it has been designed within an educational context to support taskoriented learning activity. MLTutor is a hypertext system that provides suggestions to the user on the basis of their recent browsing history, indicating pages that are relevant to the user's current area of interest. MLTutor is designed for use in an educational context on the World Wide Web (WWW). It aims to provide adaptation without the need for any prior knowledge regarding a user's background or interests.

Since work on MLTutor commenced, the idea of analysing information requests as a primary source of data has become more widespread. The use of clustering techniques to learn a user profile from a collection of documents has been investigated by [START_REF] Crabtree | Identifying and tracking changing interests[END_REF]. In their system a user's word processing documents, emails and Web browsing activities are monitored to build an interest profile. Highest information bearing words are extracted from these documents to create vectors which are then clustered. These clusters are presented to users for feedback regarding relevance to their interests. The clustering technique used in this system is a top-down statistical approach. [START_REF] Crabtree | Identifying and tracking changing interests[END_REF] anticipate that the clusters produced by the system could be used for personalised information retrieval and filtering tasks. An overriding aim of this work was to reduce, as much as possible, the need for a user to provide input to the system. As with MLTutor the monitoring conducted by this system is unobtrusively performed, and keyword based page descriptions are used to cluster the accessed documents to identify user interests. The system aims to reduce the need for users to provide feedback but does not completely eliminate this.

The Syskill and Webert [START_REF] Pazzani | Syskill & Webert: Identifying interesting web sites[END_REF] system has similar objectives. The Syskill and Webert browsing assistant asks users to rate Web pages as interesting or not and learns a user profile which is used to suggest other pages of possible interest. One profile per topic is learned which is much more specific than a generic user profile could be. As with MLTutor this system used machine learning techniques to build user profiles but relied on users rating documents, which are used as training data for the algorithms.

We present the system design, focusing on the design and test of the machine learning component, then describe the evaluation method employed and the results of that evaluation, and close with a discussion of the implications of this work and its relation to other studies.

SYSTEM DESIGN

MLTutor is a Web-based client server system which has been built with the intention of combining Internet technology with educational hypertext. The client component of the system incorporates the user interface and runs in a WWW browser. The client captures data which is transmitted to the server using Internet technology. The server component of the system is executed when requested by the client. The server contains a machine learning component (MLC) which analyses the received data and transmits results to the client. The server based MLC of MLTutor has been designed so that learning does not require any initial training. This is achieved by the novel integration of attribute-based clustering and inductive learning techniques. To enable this learning, an attribute database is embedded within the system; entries in the database describe pages in terms of presence or not of keywords within the hypertext content of the system. Within MLTutor the catalogue of keywords is based largely on hypertext anchors.

The prototype version of MLTutor contains four Web sites covering information on 'Environmental Science' issues. These four sites contain a total of 133 pages. There are no intrinsic links between the four sites. For this reason, bookmark links were provided to allow transition from one site to another. The Web technology employed in the design of the MLTutor prototype should ensure extendibility to the wider Internet environment, and to other topics.

The interface of MLTutor has been built in the Java language. The educational hypertext document is loaded into a Web browser frame following a logon procedure controlled by the MLTutor applet. Once the user has visited ten pages, the MLTutor applet passes the URL addresses of the last 10 hypertext pages visited by a user to the server. On the Web server, a CGI script starts running the Machine Learning Component (MLC) of the system. The output of this process produces a list of recommended hypertext pages and this information is sent to the MLTutor applet which consequently updates the information displayed in the suggestion frame as shown in figure 1.

Figure 1: The MLTutor's suggestions, after 10 pages have been visited.

MLTutor's suggestions

The user then has the choice of following links presented on the current page, selecting a different site (e.g. from the 'bookmark' list, or by typing a new URL) or following a link from the suggestion list.

From this point on, MLTutor presents updated suggestions on a regular basis. It processes the most recent ten pages at any time; the ten page limit was selected to minimise the browsing required before learning can take place while also ensuring that the learning algorithms are presented with a sufficient volume of data to allow effective learning. Alan Hutchinson, the developer of the conceptual clustering algorithm [START_REF] Hutchinson | Algorithmic Learning[END_REF] used in MLTutor, advised (personal communication) that ten pages is sufficient for the algorithm.

The phases of the learning process in the MLC are illustrated in figure 2 along with their relation to the attribute database. In the first phase of the learning process, clustering is utilised to find inherent patterns within the hypertext pages browsed by a user. To find these inherent classifications within the hypertext a simple conceptual clustering algorithm [START_REF] Hutchinson | Algorithmic Learning[END_REF] is used. Applying this method eliminates the need for initial "hand-crafted" stereotypical profiles or any additional input from a user.

Client

In the second phase of learning, as shown in figure 2, a rule induction procedure is employed to generate rules. These rules describe the concept of cluster membership. This process works on the basis that the components of a cluster are in some way related to each other and as such are representative of a concept. Based on this, the content of a cluster is assumed to represent positive examples of a concept and anything beyond the boundary of the cluster is taken to be non-representative of that concept. The information concealed in clusters was initially interpreted by the ID3 algorithm [START_REF] Quinlan | Induction of Decision Trees[END_REF] to create a set of rules which can be viewed as dynamically created user profiles. The rules generated by this phase are used to search for other hypertext pages within the original population of pages, classified as belonging to the concept.

The results of the learning process in the MLC are the pages classified as belonging to one of the learned concepts. These hypertext pages are related to those which have already been explored by a user and form the content of the suggestion list displayed within MLTutor as depicted in figure 3. The suggestion list has been developed as a plug-in plug-out component; with this feature disabled the MLTutor system is a simple hypertext browsing system. The clustering and rule induction processes within MLTutor make use of an attribute database. The first stage of attribute database construction is to assemble a list of keywords from the Web pages within the system. In the development of MLTutor a manual process was used to generate a catalogue of keywords which is largely based on embedded hypertext anchors. The long-term aim for the approach presented here is that it should support users accessing information from the Web, using meta-data about page content to index pages; various methods of automating the indexing have been considered, for example using the DC-Dot tool (UKOLN, 1998); although such an approach has not implemented, it is believed to be feasible as part of further work.

Having established a keyword catalogue from hyperlinks and other context related words and phrases from the pages contained within MLTutor, a binary vector was created for each page to show presence (explicit or implicit) or absence of each keyword on a page. In the binary representation the absence of a keyword on a page was coded with '0' and the presence with '1'. Each vector forms a single record of the attribute database as shown in figure 4. In the clustering process the attribute descriptions of hypertext pages visited by a user are obtained from the attribute database and, based on these attribute descriptions, the clustering process puts maximally similar pages into the same clusters.

The role of clustering in the MLC is illustrated in figure 5 below. Let the dark coloured circles in the first ellipse represent the hypertext pages visited by a user out of the available pages, then the second ellipse illustrates the results of clustering these hypertext pages. In this case the clustering has identified three distinct trends within the input and formed three clusters. As a result of the clustering, the components of a cluster are in some way related to each other and as such are representative of a concept. Based on this the content of a cluster is assumed to represent positive examples of a concept and anything beyond the boundary of the cluster is taken to be non-representative of that concept.

The rule induction process generates attribute-based rules defining cluster membership. These rules are used to search the attribute database for other hypertext pages within the original population of pages classified by the rules as belonging to the concept. In figure 6 the grey zones extend the cluster boundaries and represent the hypertext pages suggested by the MLC as members of the same concept.

Figure 6: The rule induction process allows related pages to be suggested.

In MLTutor, the navigational steps taken by a user are the sole information source analysed to understand the user's motivation. This approach is the most unobtrusive way of gathering information about the user's interest during a task-oriented information search. Furthermore it eliminates the need for users to provide relevance feedback and eliminates the need for predefined stereotypical user profiles.

In summary, the machine learning approach proposed here facilitates a flexible, individualised approach to adaptation without the need for additional input from a user or preclassification of users. This is achieved in the MLC by dynamically generating rules which hold generalised information about a user's current area of interest and are used to construct a suggestion list. This suggestion list is adaptive, reflecting the on-going browsing activity. While suggestions will only be related to previously browsed pages, as browsing activity moves into new areas the suggested items will begin to reflect this new focus. The suggested items will not be able to suggest topics that a user has given no indication that they are interested in.

The implementation of the suggestion list in MLTutor demonstrates the analysis performed by the MLC; however, the dynamically generated rules, based on the browsing activity, effectively form a profile indicating the user's current area of interest at a point in time. This profile is continually updated as further pages are accessed and new rules are created.

RULE INDUCTION STRATEGIES

Research in the field of symbolic machine learning (ML) has resulted in the development of a wide range of algorithms. Typically, learning in these algorithms is accomplished by searching through a space of possible hypotheses to find an acceptable generalisation of a concept. However, ML algorithms vary in their goals, learning strategies, the knowledge representation languages they employ and the type of training data they use.

ML algorithms that do not require training are referred to as unsupervised algorithms e.g. clustering and discovery algorithms. Those that require training with a set of pre-classified examples are referred to as supervised learning algorithms e.g. decision tree learning such as the Classification algorithm, ID3, C4.5 etc.

Decision tree algorithms accept a training set of attribute-based positive and negative instances of a concept which must all be presented before learning commences. Top down induction of decision trees is an approach to decision tree building in which classification starts from a root node and proceeds to generate sub trees until leaf nodes are created. It is possible to categorise conjunctive and disjunctive descriptions of concepts with decision trees, and if-then rules can easily be lifted from the trees.

Typically in decision tree learning, instances are represented by a fixed set of attributes; Mitchell (1997) states that decision tree learning is well suited when attributes take on a small number of disjoint values. This maps well to the attribute encoding scheme employed by MLTutor which is based on the presence or not of keywords in hypertext pages. This suggests that a decision tree building algorithm is a suitable candidate for the rule induction phase in the MLC. ID3 [START_REF] Quinlan | Induction of Decision Trees[END_REF] was initially selected as being simple while providing the necessary functionality.

In order to test this a number of experiments were carried out. However, upon analysing the results of these experiments some concerns about the rule induction strategy used in the MLC were raised. Within the MLC of MLTutor the clustering of pages is used to detect inherent groupings within the hypertext pages browsed by a user, and the decision tree building ID3 algorithm is used to reveal information contained within the clusters.

For these experiments an attribute database with 123 keywords was used to test sets of browsed hypertext pages. Table 1 shows the two clusters created for these pages by the conceptual clustering algorithm.

Attributes that were common to all pages within the cluster are indicated in bold and referred to as primary determinants of cluster formation. Other attributes that are shared by only some of the pages are shown in italic and referred to as secondary determinants of cluster formation.

Attribute data base containing 123 keyword descriptions

Cluster 1 contains: page 5-7-11 common attributes: 1 2 22 Cluster 2 contains: page 2-3-4-9-10-2-32 common attributes: 31 84 99

Table 1: Two clusters were created.

In this example the ID3 algorithm was applied to the data in the two clusters to induce decision rules for each cluster. Each cluster in turn was treated as positive training data for the rule induction process; the negative training data was the pages in the other cluster.

The ID3 algorithm uses an information theoretic heuristic to produce shallower trees by deciding the order in which to select attributes. The first stage in applying the information theoretic heuristic is to calculate the proportions of positive and negative training cases that are currently available at a node. In the case of the root node, this is all the cases in the training set. A value known as the information needed for the node is calculated using the following formula where p is the number of positive cases and n is the number of negative cases at the node.

( )

p n n p n n n p p n p p n p I + + - + + - = 2 2 log log ,
All available attributes at the node are next considered. Available attributes are those that have not been used so far in the path from the root to the current node and so at the root all the attributes are available. For each of the available attributes in turn, for each value of the attribute, the number of the cases at the node which are positive and negative are counted. The formula above is used with these proportions to give a value called the information needed for the attribute, for example attribute A. A value is calculated for every value of attribute A. This scaled sum is known as the E-score or entropy ( ) ( )

i i v i i i n p I n p n p A E , 1 ∑ = + + =
and is subtracted from the information needed for the node to give an expected information gain for attribute A. The information gained by branching on A is therefore Gain

(A) = I(p, n) -E(A).
The ID3 algorithm is summarised as follows:

Input: A training set Output: decision trees 1. If all the instances are positive then terminate the process and return the decision tree.

2. If all the instances are negative then terminate the process and return the decision tree 3. Else Compute the information gain for all attributes, select an attribute with the maximum information gain, and create a root node for that attribute.

Make a branch from the root for every value of the root attribute.

Assign instances to branches.

Recursively apply the procedure to each branch.

The concept descriptions produced by the ID3 algorithm are in the form of if-then rules which are used to select other pages to suggest to the user. The rule developed for cluster 1 of table 1 is depicted in figure 7.

IF att-no

22 is 1

THEN Yes

Figure 7: The rule generated for cluster 1.

The pages within cluster 1 contain attributes 1, 2 and 22, and the ID3 algorithm needs only a single attribute, in this case 22, to create a rule describing the cluster. Consequently, only pages that contain the keyword represented by this attribute are eligible for suggestion using this rule. Within the context of the MLTutor this was not ideal as the suggestion rule failed to take into account all primary determinants of the cluster. This is due to the fact that ID3 maintains a single current hypothesis as it searches through the space of the given concept. As a result, ID3 is incapable of representing alternative decision trees which are consistent with the available training data (Mitchell, 1997). In order to rectify this weakness the SG-1 algorithm was developed as an enhancement of ID3. Prior to using both the ID3 and the SG1 algorithms in the machine learning component of MLTutor, they were tested using sample training data, including data from Quinlan (Quinlan, 1983).

THE SG-1 RULE INDUCTION ALGORITHM

The ID3 algorithm was used as the basis for the rule induction phase in the initial prototype of MLTutor. The algorithm is used to generate classification rules, which are then used to provide adaptive navigational support. However, as described above, the ID3 algorithm was found not to be ideally suited to this application.

The idea of replacing ID3 with C4.5 in MLTutor was considered, however, the additional features introduced by C4.5 were not seen to offer significant benefit due to the nature of the data in MLTutor. Consequently, the SG-1 algorithm, an enhancement of ID3, was developed.

SG-1 is a decision tree building algorithm based on ID3. Within ID3, if there are several ways of building the decision tree at a given point, the algorithm takes into account only one of these. In contrast, SG-1 has the ability to produce multiple decision trees in this scenario and treats each possible alternative equally, building a subtree for each of them. Conceptually, the SG-1 algorithm can be visualised as building three-dimensional trees.

The SG-1 algorithm is as follows.

Input: A training set

Output: Multiple decision trees 1.

2.

If all the instances are positive or negative then terminate the process and return the decision tree.

Else

Compute information gain for all attributes. For each attribute with the maximum information gain create a root node for that attribute.

Make a branch from each root for every value of the root attribute.

Assign instances to branches.

Recursively apply the procedure to each branch.

The consequence of the ID3 enhancement is described in the following example. Suppose the information theoretic heuristic adds attribute A to the decision tree as the root as shown in figure 8. If there are two values for attribute A, two branches are added to the tree and the next attribute is selected. Similarly, when the SG-1 algorithm considers attribute C, the second eligible attribute, a second subtree is constructed.

Decision rules from the SG-1 tree are created as for ID3. However, the additional dimension introduced by SG-1 potentially results in more decision rules being created as SG-1 maintains multiple concept descriptions.

In the example above, four rules for positive classifications are generated and similarly four rules for negative classifications. In this case the standard ID3 algorithm would have produced two negative and two positive classification rules only. The additional rules produced by SG-1 take into account alternative primary determinants from the cluster formation process. By using a disjunction of these rules to search for suggestions, the list of suggestions generated is more representative of the concept the cluster covers.

The SG1 algorithm was implemented and tested with the conceptual clustering algorithm, and found to perform satisfactorily, overcoming the shortcomings of ID3 identified in this context. This was therefore implemented with MLTutor, which was then evaluated using a battery of techniques to assess different aspects of effectiveness.

EVALUATION

In order to evaluate the effectiveness of the MLC of MLTutor, an empirical study was conducted. The evaluation aimed to assess the feasibility and also the utility of using machine learning techniques for the analysis of an individual user's navigational pattern.

Evaluating a system is an intricate task and, as noted by [START_REF] Hook | Evaluating the Utility and Usability of an Adaptive Hypermedia System[END_REF], it becomes more difficult if the system is adaptive. In recent years, although adaptive hypertext research has produced promising results (in terms of assisting personalised information gathering in an educational context) as reported by [START_REF] Brusilovsky | Methods and techniques of adaptive hypermedia. User modelling and User-Adapted Interaction[END_REF], a weak point of this research field is the lack of comprehensive empirical studies to measure the usefulness of adaptation within such systems and between such systems. One reason for this is that there is no standard or agreed evaluation framework for measuring the value and the effectiveness of adaptation yielded by adaptive systems.

One typical approach to determining the effectiveness of adaptation has been to compare the performance of an adaptive system against a version of the system with adaptation disabled. [START_REF] Hook | Evaluating the Utility and Usability of an Adaptive Hypermedia System[END_REF] states that adaptivity should preferably be an inherent part of a system, and so if it is removed from the system, the system may not be fully functional.

In MLTutor, the suggestion list is the adaptive component of the system. When the suggestion list feature is disabled, the MLTutor system becomes a simple hypertext browsing system. Consequently, it is feasible to create a non-adaptive version of MLTutor for comparison purposes. However, we considered additional questions about the details of the adaptation:

• If the previous ten pages form (typically) three or four clusters, which is the one the user is most likely to be interested in? The most likely candidates are the cluster containing the most recently visited page and the one containing most of the recently visited pages.

To address this, two variants of the MLC were implemented, as described below. • For a static web structure, it is possible to pre-classify the pages into clusters; while this would not be possible for the total web, we investigated the relative merits of preclassifying against dynamic clustering based on the user's browsing patterns. These questions were investigated within one study by comparing the performance of MLTutor versions containing four variants of the MLC. The four variants were compared with each other and against a non-adaptive control version.

Cluster selection strategies in MLC

The four versions of MLTutor were constructed with alternative cluster selection strategies as outlined below. The versions that employ pre-clustering do not use the conceptual clustering algorithm dynamically or the SG-1 algorithm to generate suggestions.

MLTutor Version 1

Rule induction based on the cluster containing the latest page visited: Within this version of

MLTutor the data passed to the MLC of the system is clustered dynamically based on the most recent ten pages visited. The pages within the cluster that contains the latest page visited by the user are treated as positive training data for the SG-1 rule induction process. The negative training data for the rule induction process are the pages passed to the MLC which are not within the cluster containing the latest page visited.

MLTutor Version 2

Rule induction based on the most heavily weighted cluster: In this version of MLTutor the data passed to the MLC of the system is assigned a weight based on how recently the page was visited by the user. The most recently visited page is given the highest weight and the least recently visited page is given the lowest weight. A total weight for each cluster generated by the clustering process is calculated by summing the individual weights of the pages that formed the cluster. This strategy aims to reduce the impact of the most recent page being a temporary diversion. The pages within the heaviest cluster are treated as positive training data for the SG-1 rule induction process. The negative training data for the rule induction process are the other pages passed to the MLC which are not within the heaviest cluster.

MLTutor Version 3

Pre-clustering using the latest page: Within this version of MLTutor the complete set of pages available within the system were clustered beforehand and these clusters stored within the system. The stored cluster which contains the last page visited by the user is selected and the other pages within this cluster, excluding those in the input data passed to the MLC, are selected for suggestion. This cluster selection strategy would not be suitable for a general domain as the space of possible pages is not predefined.

MLTutor Version 4

Pre-clustering using weights: Within this version of MLTutor the complete set of pages available within the system were clustered beforehand and these clusters stored within the system. The data passed to the MLC of the system is assigned a weight based on how recently the page was visited by the user, as per version 2.

Experimental set-up

The evaluation study aimed to compare the adaptive MLTutor against a non-adaptive hypertext (the same web pages without the suggestion list), and also to compare the alternative adaptation strategies outlined above. We were interested in users' perceptions of the different versions, in whether the adaptive component had a significant effect on their task performance (in terms of their ability to perform well on a teacher-defined information task) and in whether the adaptation component had a great influence on user behaviour with the system.

Thirty people were recruited to participate in the empirical study. As many as possible (about 50%) were environmental science students; the remainder were computer scientists. Subjects were balanced across versions of MLTutor (so that, as far as possible, equal numbers of environmental and computer scientists used each version).

An instruction sheet illustrating the MLTutor logon procedure and use of the navigational tools available within the system was prepared. A version of the instructions, with descriptions of the adaptive features removed, was also prepared for users of the control version.

An expert on environmental science set 13 questions based on the information covered in the MLTutor system, and also provided model answers indicating the hypertext pages which contained the answers. Answers to some of these questions specifically required several pages to be visited. A marking scheme for answers was established.

The participants were asked to complete the tasks set by the expert using the allocated variant of MLTutor. Following this, they were asked to complete a short questionnaire on their views of the system they had used.

Raw data collection

Data for the empirical analysis was captured in several forms:

• Answer Sheets: In the experiment, participants were asked to answer 13 questions while browsing the Web documents within MLTutor and provide their answers in written form. The written answers of the participants were assessed against the model answers. • User feedback questionnaire: In order to gather feedback on various aspects of the system a user feedback form was prepared consisting of two sections. In the first section, six questions asked for feedback on a scale; in the second section, the participants were given the opportunity to comment on various features of the system and provide any other feedback.

• Log files: During the experiment each participant's interaction with MLTutor was recorded in a log file. The MLTutor log files were used to identify the paths taken through the hypertext to reach pages containing the answers to the set tasks. Log files are the most effective method of unobtrusively determining how often adaptive features are being used and to trace interaction with the system.

Measures

The following data was extracted or calculated for the empirical analysis:

• Participant task results: These were used to see whether better performance was achieved using an adaptive MLTutor version, and if so which one, compared to the nonadaptive version. Each answer was marked using the marking scheme devised by the domain expert.

• Time spent to complete tasks: Calculated from log files, this data was used to see whether total task completion time was reduced by any MLTutor version. • Total link usage: Extracted from log files, this data was used to see whether total link usage was reduced for any MLTutor version, suggesting more purposeful browsing.

• Total suggestion list link usage: Extracted from log files, this data was used to see whether suggestion list link usage was higher for any MLTutor version, suggesting more focused suggestions.

• Total site transition link usage: Extracted from log files, this data was used to see whether site transition via bookmark link usage was reduced for adaptive MLTutor versions compared to non-adaptive.

• Navigation paths: Data within the log files was analysed to determine how participants reached pages containing answers to the tasks -directly or via the suggestion list -and whether tasks were answered correctly from these pages.

RESULTS

Analysis of the participants' answer sheets

In order to proceed with the answer sheet analysis the participants' written answers were assessed against the expert recommended model answers. The participants' scores were analysed based on usage of adaptive and non-adaptive versions of MLTutor. Means and standard deviations based on this evaluation criterion are summarised below (table 2).

Non-Adaptive MLTutor

Adaptive MLTutor These results show that scores using an adaptive version are slightly higher than for the non-adaptive version of MLTutor. Further tests for statistical significance could not be conducted due to inadequate sample sizes.

In the next phase of evaluation the participants' scores were analysed in terms of the MLTutor version used. Means and standard deviations based on this evaluation criterion are summarised below (table 3). Standard deviations for these results are quite high because each version was tested by participants with differing backgrounds (environmental and computer scientists), which resulted in large variations in test scores for each version.

In summary, these results only partly support the hypothesis that an adaptive version of MLTutor results in higher scores compared to the non-adaptive version. Although the results are suggestive, the number of participants who tested the variants of MLTutor is too small to apply any further parametric statistical analysis.

Analysis of feedback questionnaires

The participants in the evaluation were asked to complete a feedback questionnaire after using MLTutor to answer the set tasks. Here, we focus on the qualitative (freeform) responses.

For each free form question on the feedback questionnaire, the comments of participants were examined with a view to identifying common themes and significant comments. The common themes identified from comments made by users of the non-adaptive MLTutor were as follows:

• Unstructured information

• Not a tutoring system

• There is no inter-link between sites

The common themes identified from comments made by users of the adaptive variants of MLTutor were as follows:

• Easy to use

• Site transition links are useful

• Some suggestions are good, but there should be more useful suggestions

• Suggests already visited pages

• Time delay before useful suggestions appear

• The entries in suggestion list were very difficult to understand

• A layman may need further background knowledge

• Provides a short-cut to relevant pages

• Made aware of links which were not apparent

• Offers different forms of navigational aid

The comments made regarding the non-adaptive version of MLTutor, a plain HTML browsing system, tend to support the decision to develop the adaptive MLTutor. It was suggested by a non-computer literate user that a layman may need further background information than that provided by this implementation of MLTutor.

In many cases, information on the WWW is unstructured and the adaptive features of MLTutor aim to overcome this by providing links between sites which are otherwise unconnected. Users liked the seamless integration of web-sites with a common interface and, as noted by participants, the adaptation provided by MLTutor gave them additional choice while searching for information.

In addition, participants found the suggestion list entries a convenient shortcut to relevant pages that were otherwise not apparent or readily accessible. Although it was not heavily used (see below), the alternative form of navigation introduced by the suggestion list seemed to be appreciated.

Analysis of log files

The participants' browsing activity were recorded in a log file in the background during the experiment. The usage of three types of links and the task completion time were assessed from these log files. The types of links examined are built-in links, suggestion list links and site transition links via bookmarks.

A quantitative data analysis was applied to this data. The primary objective of this particular analysis is to investigate relative performance of using adaptive MLTutor compared with non-adaptive MLTutor. Means and standard deviations based on this evaluation criteria are summarised below (table 4). Table 4: Mean and standard deviation analysis of evaluation criteria.

The results indicate that the mean total task completion time was reduced for users of the adaptive versions, as was the total number of links followed. Although the suggestion list was used relatively infrequently by most users, it raised awareness of alternatives and helped make interactions more efficient. In this way, it appears to have had an indirect beneficial effect.

Cross analysis of log file and participant scores

In addition to the analysis described above, further in-depth analysis was conducted in order to investigate the use of built-in and suggestion-list links. The objective of this analysis was to determine how frequently built-in links and MLTutor system suggestions were followed by the participants and utilised to complete the given tasks.

For this analysis, four categories of link usage were established as follows:

X1: If a user accessed the expert recommended page by a built-in link and answered the question correctly when no suggestion link was available.

X2:

If a user accessed the expert recommended page either by a built-in link or by a suggestion list link and answered the question correctly when suggestion link was available.

O1:

If a user accessed the expert recommended page by a built-in link and failed to answer the question correctly.

O2:

If a user accessed the expert recommended page either by a built-in link or by a suggestion list link and failed to answer the question correctly.

Ideally, six categories would have been preferred allowing built-in and suggestion list links to be analysed individually, but the data available from log files was not sufficient to allow this and so usage of these link types were merged to form categories X2 and O2.

In order to assist with this analysis, a link usage analysis form was created (see table 5). Part 1 of the form contains details of the participant to whom the form refers. Part 2 of the form gives a count of the number of times a suggestion list link was used to access the pages listed in part 4. Part 3 of the form contains counts of the number of times a built-in link was used to access the page numbers in part 4 of the form. Part 4 of the form lists the pages which contain the expert recommended model answers. In part 5 of the form there is a row for each of the set tasks. Within each of these rows, the pages containing the model answers to the question the row corresponds to, are highlighted in dark grey. For example pages 63 and 127 are the recommended pages to answer question 4.

This form is populated with data from various sources. The log file of each participant was analysed in conjunction with the answer sheet completed by the participant. Each answer was rated in terms of the four categories defined above and transferred to part 5 of the form. Data to complete part 2 and part 3 of the form was also extracted from log files.

The percentage of correct answers where the answer page has been visited by built-in links

only is = + 2 1 1 X X X 85 258 219 =
and the percentage of correct answers where the answer page has been visited using only suggestion list links is less than

= + 2 1 2 X X X . 15 258 39 =
These results indicate that the preferred navigational method for completing tasks was to follow available built-in links. Although the results of the statistical analysis are indicative of the benefits of adaptivity, the log file and participant score cross analysis contradicts this evidence. The simple quantitative evaluation criteria used in the analysis, widely used to measure the effectiveness and efficiency of adaptation in adaptive hypermedia research, on their own, fail to reflect the actual usefulness of the adaptation. The results indicate that the use of an adaptive feature does not prove anything unless related to improved performance in some way, and that superficial measures of performance may be misleading. The enhanced results alone may simply be the consequence of an alternative interface and not directly a consequence of any adaptation. This issue needs further investigation.

Analysis of the MLC

Much of the adverse user feedback on the suggestion list focused on the existence of irrelevant suggestions. Since the clustering phase of the MLC is largely responsible for the quality of the suggestions made, a further technical analysis of MLTutor was conducted, focusing on the performance of clustering within MLTutor. Two aspects of the clustering algorithm used were investigated: sort step sensitivity and the 'bin' cluster effect.

Sort step sensitivity

The conceptual clustering algorithm [START_REF] Hutchinson | Algorithmic Learning[END_REF] employed by MLTutor contains a sort step which orders pairs of pages based on the distance between them. If two pairs of pages are equally far apart they can legitimately appear in any order following the sort. The order of the pairs of pages has a bearing on the clusters produced by the algorithm. The decision to use integer values to encode the page attribute descriptions and the metric used to measure the distance between pages leads to the likelihood of there being a high incidence of equally distant pages. The impact of this in terms of the resultant clustering in MLTutor is hard to determine from the available information but could have had an impact on the clustering and ultimately the suggestions made by MLTutor.

The 'bin' cluster

For the implementation of pre-clustering in versions 3 and 4 of MLTutor, all 133 pages available within the system were clustered applying the same algorithm used in the dynamic variants of MLTutor.

Running the clustering algorithm on 133 pages initially generated 10 clusters; however the 10 th cluster contained a large number of pages. The clustering algorithm was re-applied to this data. This second phase of clustering produced three more clusters and yet again another quite large (final) cluster. This re-clustering process was repeated until no further subdivisions could be achieved. Having repeated the clustering process six times, 16 clusters were created. The 16 th cluster was still very large.

During the pre-clustering process it was observed that each re-clustering attempt produced one heterogeneous cluster -which in each case appeared to be the largest cluster -that contained a combination of items which seemed to be semantically unrelated. This paper refers to this last and largest cluster as the 'bin' cluster. The 'bin' cluster has implications for both dynamic clustering and pre-clustered versions of MLTutor and the effect was observed in the users' log files.

In the case of dynamic clustering, if the cluster selected for inducing rules is the 'bin' cluster then it is very likely that any suggestions produced for this cluster would be unfocused. This problem was not appreciated when the MLTutor system was initially tested, and now needs to be addressed as a matter of priority.

SUMMARY OF ANALYSIS

The aim of the comparative study conducted on MLTutor was to determine whether users of the adaptive versions of the system were able to perform tasks more successfully than users of the non-adaptive version and, if so, whether any adaptive version was more successful than others. The principal measure used in the evaluation was the answers to questions completed by participants while using a version of MLTutor. Additionally, link usage and time taken to complete the exercises were used.

In terms of test scores achieved by the participants, the users of the adaptive versions scored on average higher than the users of the non-adaptive version. Within the versions themselves there was no clear favourite: users of three of the adaptive versions scored on average better than users of the non-adaptive version, while users of one of the adaptive versions scored particularly poorly. While it might be tempting to re-run the empirical study with larger user groups, this has not been done because qualitative and analytical results have highlighted areas where further development should be conducted before conducting further empirical evaluation.

Findings of the cross analysis indicate that there are a number of weaknesses related to the evaluation methods used in the field of adaptive hypermedia. These are that:

• The use of quantitative measures, on their own, may fail to reflect the actual benefits of adaptation.

• The use of an adaptive feature may not prove anything unless related to improved performance in some way.

In terms of MLTutor, although the results of the statistical analysis are indicative of the adaptivity having an effect on users, the log file and participant score cross analysis indicates that the adaptivity available within the system has hardly been used. By simply measuring differences in performance between adaptive and non-adaptive versions of a system, a fundamental assumption that the difference is due to the adaptivity is made. However, the cross analysis conducted as part of this research suggests that this assumption may not be valid.

Beyond the quantitative data gathered during the experiment, qualitative data was also collected in the form of feedback comments from the participants. Not all feedback from the participants who took part in the evaluation was positive. A number of enhancements to MLTutor were suggested by participants as follows:

• Already visited pages can be re-suggested without indicating that they have already been visited. There is no history-based annotation within the entries of the suggestion list and adding this feature was suggested as an enhancement to the system. An option to hide already visited pages from the suggestion list might also be considered.

• For the research prototype implementation, the file names, as opposed to the page titles, were used in the suggestion list. File names are not always as meaningful as the page titles, which should be used for any further development of the system.

• The suggestion list should be keyword based allowing links to pages containing the keywords as opposed to the current implementation which lists pages and allows the display of keywords covered on that page.

• The suggestion list should be permanently visible as opposed to being on a floating popup that can be obscured by the main browser window. Participants also commented that the content of the suggestion list should be more structured and an alternative representation, for example a graphical representation, would be useful. • Users also commented on the time delay in the suggestion process which is due to the need to build up a list of pages to generate suggestions from and the periodic nature of the suggestion list refresh. Within MLTutor 10 pages have to be visited before suggestions can be made. This is due to the need to collect sufficient data for the machine learning algorithm to process. Once 10 pages have been visited, the suggestion list is refreshed periodically. The time between refreshes is set within the application and can easily be adjusted.

These comments from users of the system suggest areas where effort should be directed for future development work with the system.

In addition a number of technical issues with the conceptual clustering algorithm used in the MLC were identified. These technical issues with the clustering algorithm will need to be addressed before further development of MLTutor takes place. based machine learning algorithms process attribute descriptions of objects. In both cases the selection of features to describe objects is fundamental to performance.

The MLTutor has based attribute encoding on a classification of hyperlink anchors within the hypertext. Hypertext links facilitate navigation and, as such, typically relate pages at a conceptual level. A distinct advantage of using hypertext anchors to describe documents is the ease with which they are identified within the hypertext. Although this strategy relies on hypertext documents being constructed in a sensible manner the strategy has been shown as a viable option. However, the MLTutor design is capable of incorporating any attribute based scheme for encoding documents due to the nature of the machine learning algorithms employed.

Adaptive navigational support

As a result of the machine learning process within MLTutor, the suggestion list is adaptive to the ongoing and changing requirements of the user. This is achieved by use of a sliding window technique that takes into account recent browsing. The use of browsing paths alleviates the need for any additional feedback from a system user at all.

Furthermore, the adaptivity provided by MLTutor can be disregarded without penalty or overhead to the user. By ignoring system suggestions, or turning the facility off, the MLTutor becomes a plain hypertext browsing system familiar to all users of the WWW. This solution to providing adaptivity is intended to prevent alienation of potential users; some users may not need to see suggestions and others may not be comfortable with unfamiliar adaptive features within the interface.

WWW based systems

While the WWW offers huge potential for distance learning, the mechanism of the Web can be employed to deliver information within an individual organisation or classroom. The WWW can be considered a vast network of interlinked documents, effectively a huge hypertext system. Within this network specific sites cater for specific needs, often with links to other related sites. However, the Web of documents is growing in an unregulated and unstructured manner with important connections between highly related documents missing. Consequently, finding specific or relevant information on the Web can be difficult.

The MLTutor presents a solution to this issue by introducing an adaptive facility, which aims to assist in the search for information. The MLTutor dynamically generates an individual profile in the form of suggestion rules based on a user's history of browsing activity. These rules are used to suggest additional pages the user may be interested in. A significant benefit of the MLTutor is that suggestions may relate to documents the user has not yet seen, or may not be aware of, as they are not directly connected to the document the user has accessed. The suggestion list mechanisms in MLTutor allows direct access to these additional pages even though no link physically exists between them.

The machine learning approach employed to build the list of suggestions ensures that the suggestions made are relevant to the user's current area of interest. Effectively, the MLTutor provides a mechanism for re-structuring a hypertext document to cater for individual preferences without restricting access in any way.

This approach has synergies with the approach suggested by [START_REF] Stotts | Dynamic Adaptation of Hypertext Structure[END_REF] who proposed a flexible structure, to overlay a fixed structure, as a solution to personalising a hypertext system.

As an alternative to analysing a Web page, a more fine-grained approach, splitting a HTML page content into smaller chunks [START_REF] Maglio | LiveInfo: Adapting Web Experience by Customization and Annotation[END_REF] may be applied. This approach may be possible with the growth of XML and the facility to define tags and the structural relationships between them.

CONCLUSION

This paper has presented the work undertaken on the MLTutor development to date. The objective of this research was to design, implement, test and evaluate a prototype system capable of testing the technical feasibility of using machine learning techniques to analyse browsing patterns within hypertext, and to use this analysis to provide adaptive navigational support without the need for pre-defined stereotypical profiles or user relevance feedback.

The MLTutor implementation serves as a proof of concept, demonstrating the feasibility of the approach. As a practical application of established machine learning algorithms, this work has identified limitations of algorithms that appeared to be well suited to this purpose; this has resulted in the implementation of SG1 (as an adaptation of ID3), and future work will be addressed at overcoming the limitations of the conceptual clustering algorithm discussed above.

In order to evaluate the system a comparative empirical study was conducted. The evaluation of adaptive systems is particularly complex as the results of the adaptation are personal to a specific user's set of circumstances and, as such, an empirical study is the most appropriate strategy for evaluation. The quantitative results from the evaluation study are indicative of improved performance for the adaptive versions but, due to sample size, not conclusively so. However, the qualitative elements of the study identified a number of issues that can very usefully be addressed before running any further empirical trials. In particular, it became apparent that the conceptual clustering algorithm has limitations (concerning sort step sensitivity and the generation of a 'bin' cluster) that need to be addressed; users also made various useful suggestions about the presentation of the suggestion list, as noted above.

Although faults in the experimental design limit the conclusions that can be drawn about MLTutor, the results of the evaluation do show that MLTutor is a robust and functional system and suggest the potential benefits of using a machine learning approach to provide adaptivity based on an analysis of browsing patterns. The empirical methodology also highlighted issues about the design that would have been missed by a simple quantitative analysis, and serves as a model for future studies of adaptive hypertext.

Figure 2 :

 2 Figure 2: The machine learning component (MLC) design.

Figure 3 :

 3 Figure 3: Selection of an entry from the suggestion list reveals the keyword pop-up window.

Figure 4 :

 4 Figure 4: The binary representation of five hypertext pages in the attribute database.

Figure 5

 5 Figure 5 Input pages are partitioned into three clusters.

Figure 8 :Figure 9 :

 89 Figure 8: Two values for attribute A.

page00110000000100000010000000000000000000000000000000010000000100000000000000000000000000………….acid.buildings page00210000000100000000100000001000000000000000000000000000000000000010010000000000000000………….acid.formation page00310000000100000000000000000000000000000000000000010000000010000000000000000000000000………….acid.home page00410000000100000000000000000000000000000000000100010000000000000000000000000000000000………….acid.how.big.problem page00500110000100010010000000000000000000000000000000010000000100000000000000000000000000………….acid.lakes

	Clustering process	Web
	Suggested	Browser
	keywords
	Suggested
	pages

Table 2 :

 2 Summary of means and standard deviations of scores.

	Mean	17.9	19.6
	Stdev	4.2	4.2

Table 3 :

 3 Summary of means and standard deviations of scores for adaptive versions. The results indicate that the highest mean score was attained by users of MLTutor version 1, which was an adaptive version, and the lowest mean score was attained by users of MLTutor version 4 -again, an adaptive version. The second lowest mean score was attained by users of the non-adaptive MLTutor version.

		Version 1	Version 2	Version 3	Version 4
	Mean	21.4	20.7	20.2	16
	Stdev	3.3	2.2	4.9	4.7

ACKNOWLEDGEMENT

This work was supported by a studentship from the School of Computing Science, Middlesex University. We are grateful to David Benyon, Paul Cairns, Alan Hutchinson, Ian Williams, Chris Huyck, Chris Kindberg, Steve Torrance, the 30 subjects took part in the experiment and fellow research students for useful discussions and feedback on this work as it was progressing.

Table 5: A link usage analysis form.

From an examination of the data gathered during the experiment, it became apparent that the pages containing answers to the questions had been accessed via various types of links i.e. suggestion list and built-in. Furthermore, the pages containing the answers had been repeatedly accessed, which had not been anticipated prior to the experiment. It was thus not clear which type of link had been used to answer the set tasks. This highlights a flaw in the design of the experiment, as the time the tasks were answered was not time stamped or audited. This would not be feasible with the paper-based format of the task completion which was used in this experiment. An on-line exercise, as suggested by one of the participants on the feedback questionnaire would be a solution to this problem.

The total occurrences for the categories X1 and X2 were summed from the link usage analysis forms and transferred to table 6.

Table 6: Summary of the X1 and X2 categories in the link usage analysis form.

Within the population of participants, across the adaptive variants of MLTutor, the total occurrences of categories X1 and X2 are equal to 219 and 39 respectively.

DISCUSSION

With this deeper understanding of the strengths and limitations of the implementation of MLTutor, we can relate this development to work in adaptive hypertext. [START_REF] Balabanovic | Exploring versus Exploiting when Learning User Models for Text Recommendation[END_REF] points out that a machine learning approach to support browsing without any particular goal in mind is useless. MLTutor has been designed for use in an educational context and specifically supports task-oriented browsing. If the browsing activity of a user is aimless, it is difficult to determine any regularity or any meaningful pattern in that behaviour. However, if the intention of a user's navigation is to complete a number of specific tasks, or to answer questions during browsing, then monitoring the user interaction in order to provide guidance becomes more feasible [START_REF] Taylor | Monitoring hypertext users[END_REF].

Browsing path analysis

MLTutor uses machine learning techniques to search for patterns within the content of material accessed during a user's information seeking activity. [START_REF] Beaumont | User Modelling and Hypertext Adaptation in the Tutoring System ANATOM-Tutor[END_REF] argues that the bandwidth of the information contained in a user's browsing pattern might be too narrow to elicit information about the user's interest; however, as noted by other researchers [START_REF] Hirashima | Context-Sensitive Filtering for Browsing in Hypertext[END_REF][START_REF] Mceneaney | Visualizing and Assessing Navigation in Hypertext[END_REF], browsing patterns are a fundamental source of information representing the user's interaction with the system. While such patterns have been investigated by several researchers [START_REF] Sun | Modelling Hypermedia Navigation: An AI Approach[END_REF][START_REF] Lieberman | Letizia: An Agent That Assists Web Browsing[END_REF][START_REF] Mceneaney | Visualizing and Assessing Navigation in Hypertext[END_REF] who have applied various AI techniques, such as heuristic search, dynamic programming and neural networks, little work has been done on the application of machine learning techniques to dynamically build user profiles in the field of adaptive hypermedia.

Within MLTutor, any patterns identified in the browsing history by the MLC of the system are used to dynamically generate suggestion rules which are used to recommend pages related to the browsing. By this mechanism the MLTutor system aims to help users to locate information relevant to their current interest.

The suggestion rules within MLTutor are generated by use of a novel combination of clustering and inductive machine learning algorithms. The dynamically generated rules form a profile that holds a generalisation of the user's current area of interest. This profile is updated as further pages are visited and new rules created.

In future development, augmenting the recommendations given by the MLC of MLTutor with social navigation [START_REF] Dieberger | Social navigation: Techniques fo Building More Usable Systems. Interactions[END_REF][START_REF] Riedl | A computational model and classification framework for social navigation[END_REF] techniques should also be considered. Social navigation is currently viewed as a new means of aiding users to find their way through an information space by making information trails left by previous users available to new users.

Attribute based systems

Information retrieval systems rely on document categorisation strategies and these strategies are typically based on keyword descriptions of information. These keyword descriptions are used by information retrieval systems to relate associated documents together. Similarly, attribute