1. Introduction
The aim of this report is simply to help put the design of computer-based systems to support learning on a more scientific footing. The aim is simply stated, but its achievement is more difficult. For one thing, it is not at all obvious what "more scientific" means in this context.
The rather clumsy expression "computer-based systems to support learning" will henceforth be abbreviated to "AI-ED systems", that is, "Artificial Intelligence in Education systems" on the grounds that the design principles will be primarily derived from and expressed in the language of Artificial Intelligence. It will become clear that we intend a broad interpretation of the term 'AI-ED system'. We mean any computer-based learning system which has some degree of autonomous decision-making with respect to some aspect of its interaction with its users. This decision-making is necessarily performed on-line, during its interaction with users. Consequently, the system needs access to various kinds of knowledge and reasoning processes to enable such decisions to be made.
Of course, computers may be used as presentational devices, through which carefully pre-designed instruction involving the new technological media is delivered to students. There are, no doubt, considerable potential benefits in this, as computers enable special effects, such as altered time-scales and alluring graphics, to focus students' attention. However, pre-designed instruction assumes that the designer can fully anticipate the reactions of all its users and can build in responses to those reactions, or that users themselves are sufficiently self-aware that they can reliably decide how to use systems (assuming that the required options are, in fact, available). It takes no account of the computer's ability to reason, for itself, about the course of the interaction, as we assume that a good human teacher needs to do.
As we will discuss, the field of Artificial Intelligence in Education (AI-ED) has had a short but chequered history. The initial explorations in the 1970s were marked by the kind of enthusiastic optimism characteristic of AI in general. This early work made significant contributions to both AI and Education. By the 1980s, the successful applied AI work on expert systems and several national programmes seeking to capitalise on AI research led to an imperative to develop AI-ED systems which were practically useful, rather than theoretically interesting. It is notable that few of the AI-ED pioneers ever expressed much confidence that the time was right for practical development. Inevitably, the eventual, perceived failure of the applied projects only confirmed that learning and teaching are intrinsically difficult processes.
Meanwhile, the new technologies, especially multimedia and networking, promised other solutions to what were considered to be serious educational problems. Consequently, it became unwise to continue suggesting AI-ED system development. Now, however, the pendulum is swinging back, again inevitably, as it is realised that the new technologies need to be supported by the kinds of analysis of learning and teaching which AI-ED research carries out.
Below the ebb and flow of research fashion, there has been continuing, if slow, progress in understanding the nature of AI-ED system design. Eventually, this understanding will find a proper place in the design of computer-based systems to help people learn. AI-ED systems are neither a panacea nor an irrelevance - they have a contribution to make. One of our aims is to help develop techniques to clarify its potential contribution.
1.1 The AI-ED context
In order to help place AI-ED systems in a realistic context, let us briefly consider four learning vignettes:
Aboriginal culture
Until recently, Australian aboriginal children would sit under the coolabah tree and listen to stories such as following:
"Brolga was the favourite of everyone in the tribe, for she was not only the merriest among them, but also the best dancer. The other women were content to beat the ground while the men danced, but Brolga must dance; the dances of her own creation as well as those she had seen. Her fame spread and many came to see her. Some also desired her in marriage but she always rejected them. An evil magician, Nonega, was most persistent in his attention, until the old men of the tribe told him that, because of his tribal relationship and his unpleasant personality, they would never allow Brolga to become his wife. "If I can't have her," snarled Nonega, "she'll never belong to anyone else." One day, when Brolga was dancing by herself on an open plain near her camp, Nonega, chanting incantations from the centre of a whirlwind in which he was travelling, enveloped the girl in a dense cloud of dust. There was no sign of Brolga after the whirlwind had passed, but standing in her place was a tall, graceful bird, moving its wings in the same manner as the young dancer had moved her arms."
The brolga is a beautiful grey bird which dances on the flood plains of northern Australia. Many aboriginal myths explain features of the environment (animals, rocks, stars, and so on) as being derived in some way from human beings. These stories, which were entirely verbal, there being no written form of communication, were accepted as truth and dictated all aspects of aboriginal behaviour. According to Roberts and Mountford (1969), young children did not "receive any formal education as we know it. They appear to do just as they please". At a certain age, a youth was taken from the main camp to live with the old men of the tribe, the sole repositories of tribal law and wisdom, who during many years of training, taught him the laws of his community, the relationship he bore to every member of it, and the secret myths and rituals of adult life.
All cultures have their myths and rituals which are communicated in a similar way. Only the most fervent technologist would imagine that computer systems could or should change these processes in any significant way. Whatever one's views of Australian aboriginal culture, its transmission by some multimedia AI-ED system is a bleak vision.
Funfair
physics
The traditional funfair provides many opportunities for children to learn or reinforce concepts of physics. The helter-skelter (a high spiral slide) gives lessons on centrifugal force, gravity and friction: most children can predict the effect of a higher slide or a heavier child, and know the direction they will shoot out at the bottom. The bumper car or dodgem is an exercise in the conservation of momentum: children soon learn where to bump to cause the maximum effect. The big dipper tells them about potential energy and kinetic energy: children know where to sit in the train to experience the greatest acceleration. The coconut shy is about force and impulse. And the ghost train warns children not to believe what they see and feel.
Funfairs are increasingly out of fashion but there are many other activities which enable children to develop intuitive notions of physics. Nowadays, children are more likely to find amusement in computer games, which may show activities violating the laws of physics and much else besides. We can, of course, imagine designing computer games which set out to be faithful to real-world physics and which may therefore lead to sound intuitive concepts. Maybe such games would help in the transition from intuition to a more scientific view of physics. In such a case, the computer game might benefit from some understanding of the nature of 'informal' and 'formal' physics. As we will see, AI-ED systems will be concerned with the nature of intuitive understandings and how they might be changed, and with the degree to which understanding has to be grounded in authentic situations.
The Play of
Daniel
University music students might be asked to write an essay on Beauvais' Play of Daniel, a medieval cathedral play. The successful completion of such a task requires the use of a range of skills and knowledge. Students need to know how to write essays in general, which presumes, of course, knowledge of a natural language. They need to be able to adapt the essay to meet the requirements, bearing in mind who will read it and for what purpose. They will need to have a broad knowledge of music in order to be able to make sense of the unusual Play of Daniel. They will also need to know about the social context at the time the Play was composed in order to understand the point of the Play. From all this, they will need to know just what points to emphasise to make a successful essay. Not all this knowledge will be to hand at the time the task is set, so students need also to know how to acquire the knowledge they need. This might involve knowing how to use various computer-based aids for accessing resources.
There are various ways in which computer-based systems might support this activity. Essay-writing is a rather complex skill with which computer-based systems will not (in the near future) be able to give detailed guidance, although various kinds of clerical assistance are possible. Computer-based systems might be able to give advice on how to set about gathering the information probably needed, for example, to determine the date of the music and how it was typically performed. They might also be able to monitor the student's use of the resources and to give advice if the student exhibits problems or deficiencies in her search strategies. Overall, the sheer volume and complexity of the knowledge involved suggests that computer systems will not be able to provide reliable step-by-step guidance for the whole process. However, given the nature of the students involved, this is not what is required, anyway.
Satellite
surveillance
Satellite activity analysts are employed by government defence departments to maintain dossiers on the behaviour of earth-orbiting satellites. In particular, they have to provide possible explanations for unusual behaviour, for example, that the satellite is mal-functioning or has been diverted to survey Colombian drug plantations. The satellite's behaviour is displayed on a complex computer graphics screen, which must, of course, be interpreted by the analysts. Naturally, their employers would like the analysts to develop excellent explanatory skills, because the cost of reacting to a faulty explanation can be considerable.
The analyst's task is not a simple one of mapping patterns of observations onto explanations. The data is generally voluminous but also incomplete and possibly unreliable. It would not be adequate to train analysts to recognise specific situations: they need to be helped to develop general explanation-forming skills, in which they propose hypotheses, gather evidence for those hypotheses, assess the reliability of evidence, and present a convincing argument for their conclusions. It is hard to imagine this training being successful in a context separate from that in which the task is normally performed. The trainee analysts would need full access to the computer display of satellites' behaviour and a way of exploring that system to create and test out hypotheses. In this case, then, the training would necessarily be computer-based, being embedded in the system used for task performance or in an extension of it. The computer-based system would probably need to know about general hypothesis-forming skills if it is to guide the trainee towards improving them. (I am grateful to the Mitre Corporation for showing me a prototype computer-based tutor for this task.)
1.2 What is education?
If a field is to call itself 'AI in Education', then it seems necessary for it to say what it considers 'education' to be. However, despite its name, AI-ED has never been concerned with education in its broad sense but only with the specific issue of learning. We may believe that the whole purpose of education is to promote learning but in reality the process of education includes many activities only indirectly related to learning, as any textbook or conference on 'education' will confirm.
The term 'education' is generally taken to mean 'formal education', that is, 'paid-for education', rather than the 'informal education' that we receive for free from our culture. There is a nostalgic preference for the latter, with the former being considered to stunt individual learning capabilities. These polemic views will not be our concern. We will be concerned only with the nature and effectiveness of the learning processes.
We will avoid simplistic assertions that learning happens in a particular way. Advocates of one method of learning will naturally belittle other methods. However, learning is a complex, many-faceted kind of activity, as our vignettes above indicate. The nature of computer-based support for learning will depend on the context and there is no particular approach which can be categorically labelled as wrong-headed.
Consider, for example, the teaching and learning of a skill such as playing the violin. This has evolved largely outside the formal education system and it shows an amalgam of many different kinds of activity. There is a lot of rather repetitive practice of scales. There is a fair amount of 'academic learning' to develop fluency with musical notation. There are occasional intense one-to-one tutorial sessions. There are some sessions in a group, as music playing is a social activity. There are specialised 'learning environments', such as small-scale violins and the Suzuki method. No one of these learning methods is intrinsically better than the others: they must all be integrated in a successful learning experience.
1.3 What is AI?
The key difference between AI and other forms of computer programming is that AI programs respond intelligently to situations not specifically anticipated by the programmer. In conventional programming, the programmer arranges for anticipated problems to be solved by specifying all the steps towards a solution. In AI programming, the programmer provides the means for the computer to solve problems as they arise. For example, a program to translate between languages could not be written by anticipating all possible sentences and providing translations of them, nor even by listing all the words and their translations and combining them in a simple way. A comprehensive translation program would need to reason about the meaning of the sentences, which implies that it has knowledge about both languages, about the content of the sentences, and about the world, so that ambiguities may be resolved.
AI is both an applied and a theoretical subject. AI applications are very diverse:
• to recognise bridges and buildings from photographs (so that they may be bombed perhaps).
• to work as autonomous robots in dangerous situations, for example, underwater mining.
• to help plan traffic flow.
• to diagnose diseases.
and so on. All these applications require skills we would normally describe as intelligent: some demand specialist knowledge (for example, of obscure diseases); others use everyday knowledge, which we all use without being aware of how complex it is (for example, recognising what is depicted in a photograph).
Important though AI applications might be, we will be more concerned with the theoretical side of AI. AI is not a science that studies objects in the natural world: it studies objects that AI programmers create. In order for these creations to be understood and analysed, their design has to be based on clearly-articulated principles capable of some kind of rigorous analysis. A program for, say, medical diagnosis should be based upon a computational theory of diagnosis. By a 'computational theory' we mean one that is amenable to conventional mathematical analysis and that is oriented towards implementation as a computer program. It should be possible to prove practical results, for example, that under specified conditions, a diagnosis will be possible in a certain time. It should also be possible to carry out empirical experiments with the program, for example, to measure how it performs under different conditions. The theory develops by coordinating mathematical and empirical studies. In this way, AI leads to the development of new theories, because if an adequate theory already existed it would presumably be programmed in a conventional way.
However, AI would not be a coherent field of study if every application required the development of its own computational theory. It turns out that a theory of diagnosis contains many components which are the same or similar to those required for a computational theory of, for example, planning traffic flow. Both, for example, require forming hypotheses from observations (a rash of purple spots suggests meningitis; a traffic jam suggests a traffic light failure), both require a form of hypothetical reasoning of the "What would happen if .." kind, both perhaps require reasoning from a library of previous cases so that the system does not have to solve every problem from scratch, and so on. Theoretical AI is concerned with the development of methods for analysing such processes independent of any particular application.
1.4 What is AI in Education?
The field of AI in Education is concerned with the application of AI techniques to educational problems. Therefore, AI in Education is part of applied AI, and indeed most practitioners are happy to regard it as so, seeking to develop important, practically useful systems based on AI. Most reports of AI-ED projects give details of the technical design of systems and provide some evidence that the systems are effective. In the next chapter, we will review the status and achievements of AI-ED research.
Our emphasis will be more on relating AI-ED to theoretical AI. As an application area, AI-ED is immensely complicated, not just because of technical difficulties but more especially because education and learning are controversial topics about which there are endless arguments. Any particular AI-ED project has to commit itself to a point of view if it is make any progress in implementing a useful system, which will then, no doubt, be criticised by those with a different view.
AI-ED is interesting because of this constant interplay of ideas and it is important because of the potential contribution to the socially central aim of improving the quality of learning. Contributions to AI-ED come from many directions: primarily from computer science, psychology and educational research, but also from sociology, anthropology, philosophy and the many fields which are the topic of AI-ED systems. Theoretical debate in AI-ED is generally expressed in lowest common denominator terms so that it is accessible to all participants, that is, in informal language. Our aim is to suggest that it is time AI-ED begins to move in the direction that all scientific endeavours take in due course, by developing a formal, technical language which can be used to make arguments more precise and AI-ED system design more analytic. The language of theoretical AI is the most promising starting point, because it already has partial formalisations of processes such as reasoning, learning, diagnosis and dialogue which are central to AI-ED.
1.5 Outline
The next chapter attempts to provide a brief, non-technical review of the AI-ED field. This is somewhat hard to do without lapsing into providing a catalogue of AI-ED systems, the various techniques used to implement them, and the educational philosophies which they demonstrate. It is also difficult because the boundaries of AI-ED are rather vague. The chapter tries to give an impression of the kinds of issues which concern AI-ED researchers at the moment and to indicate the level of practical achievement. The intention is that this chapter provide sufficient background to justify the need for the more theoretical descriptions of following chapters.
Chapter 3 introduces what we have chosen to call 'computational mathetics', for reasons that will be explained there. The general need for computational mathetics and its aims and methodologies are described. In brief, computational mathetics is intended to provide the more formal analyses needed to complement present informal argumentation and design. However, the level of formality is still low compared to other areas of theoretical AI, reflecting the difficulty of AI-ED and the little work so far done in this direction. At least this enables the discussion to be followed by those of a non-formal orientation.
The following chapters each consider a topic within the scope of computational mathetics: representing knowledge, reasoning, metacognition, learning, diagnosis, dialogue and instruction, respectively. These chapters review work in theoretical AI and in AI-ED itself from a computational mathetics perspective. There are two main objectives in these chapters. First, to show that there is a large volume of potentially relevant work which can be adopted and adapted to form a basis for the theoretical analysis of AI-ED research. If it is, we believe that it will lead, in due course, to improvements in AI-ED system design. The second objective is to show that there is much that needs to be done before the aims of computational mathetics may be achieved and hence to provide some targets and challenges for future AI-ED research.
2. A brief review of AI-ED
The preface to Wenger's comprehensive panorama of AI-ED before 1987 (Wenger, 1987) remarked that a similar review of a field then considered to be at an "important threshold of development" would not be possible five years later because there would be too much material to review. There has, in fact, been no general book published on AI-ED since Wenger (1987). All the many books related to the topic which have been published since 1987 have been monographs describing a particular project or edited collections of papers presented at workshops or conferences (Bierman, Breuker and Sandberg, 1989; Birnbaum, 1991a; Brna, Ohlsson and Pain, 1993; Clancey, 1987; Costa, 1992; de Corte, Linn, Mandl and Verschaffel, 1991; Elsom-Cook, 1990; Farr and Psotka, 1992; Frasson and Gauthier, 1990; Goodyear, 1991; Greer and McCalla, 1994; Lajoie and Derry, 1993; Larkin, Chabay and Sheftic, 1992; Mandl and Lesgold, 1988; Moyse and Elsom-Cook, 1992; Polson and Richardson, 1992; Regian and Shute, 1992; Schank and Cleary, 1995; Self, 1988). In addition to this spasm of new books, three new journals have started up (Journal of Artificial Intelligence in Education, Journal of the Learning Sciences, and Interactive Learning Environments) alongside longer-established journals with broader remits (such as the International Journal of Human-Computer Studies and Instructional Science). It is not easy therefore to gain a broad, balanced picture of the contemporary AI-ED field.
This brief chapter can hardly aspire to give such a picture. It aims merely to give a background to the issues which have been discussed in recent years sufficient for appreciating the more technical perspectives of later chapters. It is not organised, as Wenger's book was, as a historical catalogue of systems and projects. Today it is not possible to identify a similar set of classic on-going projects. The AI-ED field may have been on the 'threshold of development' in 1987 but it has, if anything, stepped back from this threshold rather than crossed it. There has been continued development of perhaps smaller-scale systems along 'traditional' lines, as we will see, but there has been much more debate about the direction of the AI-ED field, with many of the pioneers mentioned in the Wenger book leading the attempt to change it.
Any review of AI-ED should logically begin with a discussion of the educational problems which are being addressed before embarking on a survey of how AI might contribute to solutions. The main relevant issues appear to be the following:
• What is the nature of knowledge?
• How may knowledge be learned?
• Should systems instruct, tutor, guide or train students?
• How should new technologies be used in education?
• What are the measures of effectiveness?
Educationalists will debate such issues at great length but it is not the aim of this chapter to contribute to that debate except to the extent that it discusses the AI-ED field's views (implicit and explicit) on them. The review focusses on providing a basis for considering the technical contribution that AI is making and might make to education.
The following sections consider each of the
above issues in turn. Each section
illustrates a general discussion about AI-ED's views with exemplar AI-ED
systems. The sections do not
attempt to give a comprehensive account of implemented systems (there are now
too many for a short review) and those systems referred to are described only to
the extent necessary for the point under discussion. Technical concepts are usually only
mentioned, with a fuller discussion to come in later chapters (although we have
not interrupted with a multitude of forward references). The chapter ends with a discussion of
the main controversies within the AI-ED field today.
2.1 The nature of knowledge
Most AI-ED systems are intended to help their student-users become more knowledgeable in some respect. AI-ED system designers are well aware that education has broader aims - to develop ethical and moral values, to improve attitudes, to nurture better citizens, and so on - but this awareness has only indirectly influenced their system designs. It has been rather assumed (or hoped) that the context in which AI-ED systems will be used will convey these broader goals.
2.1.1 Objectivism
Given the focus on the knowledge-to-be-learned, it seems natural that AI-ED system designers often begin by trying to specify this knowledge as precisely as possible. To achieve this, the full panoply of AI knowledge representation techniques (production systems, frames, semantic networks, predicate logic, and so on) has been applied in AI-ED systems. In so doing, AI-ED designers might be considered to be adopting a philosophy of knowledge called objectivism, which holds that the world may be completely and correctly structured in terms of entities, properties and relations and that rational thought consists of the manipulation of abstract symbols viewed as representing reality (Lakoff, 1987). Thus, an AI representation of knowledge might be considered to be an attempt to describe this structure and the aim of an AI-ED system might be to help learners acquire the entities, properties and relations of this 'correct' propositional structure.
What might be considered the standard approach to AI-ED system design is illustrated by SPENGELS (Bos and van de Plassche, 1994), a straightforward intelligent tutoring system to help Dutch students learn the conjugation and spelling of English verbs, that is, to be able to use the correct form of verbs (such as 'prefer' and 'begin') in sentences such as "He ---- to work with pen and paper." The first step, as no spelling algorithm already existed, was to represent as a decision tree the morphosyntactic and spelling alternation rules taught in different Dutch textbooks. The decision tree effectively asks a series of questions: Is the verb form finite? Which tense is needed? Is the number singular? and so on, leading to a node of the tree showing the correct conjugation. This algorithm then becomes the basis for teaching the student, for deriving correct answers, for checking student answers, for determining misconceptions the student may have, and so on.
Some of the knowledge we wish students to acquire is objective because it is knowledge defined (by us) to be correct - for example, the syntax of programming languages or the allowable operations on an algebraic expression. It is no coincidence that the majority of AI-ED systems are concerned with such topics. The comment of GREATERP (Anderson and Reiser, 1985), a beginners' LISP tutor, that "You are within a PROG so you need to use a RETURN" leaves no scope for argument about the correctness of this statement (although there is scope for arguing about whether the student needs to be told so in a particular way and at a particular time).
There are many other domains where it seems necessary to adopt an objectivist view, to some extent. For example, a student on a first-aid course must be given the correct way of dealing with a child suspected of being accidentally poisoned. Again, this does not necessarily mean that a student must just be told the correct way. One can easily imagine that students will understand and remember better if they discover the correct way, in this case, preferably by experimenting with simulated patients, not real ones.
There are also domains where an objectivist view is adopted (temporarily, perhaps) as part of an academic game, by students and teachers. For example, the equations for uniform acceleration, although perhaps understood to be not always applicable, may be adopted as axioms to solve problems. In the case of English verb endings (discussed above), a pedant might point out that these endings are not fixed - they may be different in medieval English or American English - but if the learner's context is understood to be U.K. English, "preferred" is accepted to be correct.
There is a great debate within AI, and specifically within expert systems research, about the extent to which 'correct' knowledge can be specified in areas where it does not obviously exist. In the case of English verb endings it seems a reasonable expectation that correct rules can be specified but in more substantial areas of English use such an approach would probably not be contemplated. To the extent that 'correct' knowledge can be specified, such expert system representations may be used to convey it to students. The prototypical attempt to carry out this programme was the adaptation of the MYCIN expert system for medical diagnosis into the GUIDON tutoring system (Clancey, 1979, 1987).
However, even within domains for which objectivism seems reasonable, it soon becomes apparent that the real learning problems lie not in the objective knowledge but in its relation to less objective knowledge. For example, in programming, the focus moves from the syntax of the language to aspects such as programming design or debugging, where there is no definitively correct knowledge. The BRIDGE Pascal tutor (Bonar and Cunningham, 1988), for example, aims to guide the student through the stages of planning a program, from the initial English-like description through to the Pascal code.
Similarly, in algebra the issue is not so much what the operations are (syntactically) but when they should be applied. AI-ED algebra systems do not just check the correctness of operations (in fact, they often perform the operations themselves as that is assumed not to be the student's difficulty) but provide students with an environment in which they can experiment with the operators. For example, AlgebraLand (Foss, 1987) displays a problem-solving tree of the student's solution attempt. This is intended to make it easier for students to monitor their on-going solution and to reflect on their solution attempts afterwards. AlgebraLand itself gives no explicit tutorial support to these aspects - it only checks that an operator is applicable. The hope is that, relieved of the need to worry about the low-level detail of operator application, students will be more likely to engage in the desired metacognitive activities.
Even when a successful expert system can be built, it does not follow that the expertise embedded in it is a suitable basis for an educational interaction. The expert's performance-oriented knowledge may not be based on a conceptual structuring of the domain which a learner will understand (Clancey, 1984). To put it another way, many studies have shown expert-novice differences which suggest that novices may not learn well from experts. This conclusion is explicit in GREATERP, where the student's solution is not compared to an expert solution but to that of an 'ideal student'. The production rules of GREATERP do not summarise expert knowledge but are aimed to correspond to conceptual units that novices can understand.
2.1.2 Constructivism
A view of knowledge that is often presented as opposed to objectivism is that of constructivism, which holds that meaning is imposed on the world by us, rather than existing in the world independent of us. Constructivists therefore emphasise the processes of actively structuring the world and contend that there are many meanings or perspectives for any event or concept, rather than there being a single correct meaning towards which a student must be guided.
It does not follow that an AI-ED system which possesses a purportedly objective representation of knowledge has to adopt an interaction style which violates all constructivist principles. For example, the Socratic dialogues of WHY (Collins and Stevens, 1982) do not simply tell students the 'correct' conception but aim to help them construct one through subtle sequences of counter-examples and so on: "Do you think that any place with mountains has heavy rainfall?" "Yes." "Does southern California have a lot of rain?"
The designer of a system which possesses knowledge which is deemed to be correct may, however, be tempted to use that knowledge (usually acquired after great effort) in a direct knowledge communication mode: "No, southern California doesn't have a lot of rain." To avoid such temptations, an extreme constructivist might argue that an AI-ED system (assuming that it is still to be deemed an AI-ED system) should possess no such knowledge and simply present an environment for the student to explore. The deceptive word here is 'simply', for it is by no means easy to design environments from which knowledge can be discovered. The most well-known such project is LOGO (Papert, 1980, 1993) which has now been subjected to numerous studies and its constructivist foundation has become rather shaky, as the extent to which LOGO needs to be buttressed by other supports has been documented. Similarly, the recent enthusiasm for developing hypermedia and multimedia systems (Kommers, Jonassen and Mayes, 1992) for students to explore has to be tempered by the fact that unaided students have some difficulty in negotiating the vast search spaces. The technologists' manifestation of constructivism as microworlds and other exploratory environments - often contrasted with the tutoring systems of objectivists - is a rather pale image of the comprehensive philosophy of constructivism, which is "a discursive practice that provides the means through which one can describe the social, political and economic circumstances that surround and give meaning to a given piece of educational technology" (Sack, Soloway and Weingrad, 1994).
Advocates of constructivism might argue that both agents, the AI-ED system and the student, should adopt a constructivist approach. In this case, the system would not contain a priori correct knowledge but would attempt to discover it in a joint endeavour with the student. The PEOPLE-POWER system (Dillenbourg and Self, 1992) illustrates this approach. The student and the system are supposed to design experiments to be carried out on a simulated political system in order to determine what makes a system democratic in the sense that seats gained in a parliament are proportional to the votes cast for the corresponding parties. Both the student and the system can make (fallible) suggestions and interpretations. There is no target 'correct' knowledge available to the system.
2.1.3 Situationism
Situationism shares some tenets of constructivism but emphasises that the constructed knowledge does not exist in memory but rather emerges from interaction with the environment. It is argued that traditional AI, with its emphasis on symbolic knowledge representations, has assumed (sometimes explicitly, as in the classic Newell and Simon (1972) studies) that those representations have some psychological reality, that is, they correspond, not literally but functionally, with structures in memory. Situationists argue that representations are created in the course of activity but are not themselves knowledge, knowledge being a capacity to interact. Both constructivists and situationists deny that knowledge of the world can be defined independent of a mind, although the former but not the latter might accept that an individual mind creates its own idiosyncratic knowledge structures in memory.
The different perspectives of the proponents of situationism tend to lead to such a disavowal of one another's views that their intersection seems too small to provide an acceptable, brief summary of its principles. Any attempt, especially by non-situationists, to provide a simple statement is invariably met with detailed qualifications, conditions, extensions, and so on. Nonetheless, situationism is presented as a revolutionary philosophy providing a model of representation (which Bickhard and Terveen (1995) call 'interactivism') able to overcome the perceived impasse of contemporary AI (which they say is based on 'encodingism', that is, a presupposition that representation has the nature of encodings).
Situationism is very much a subject of debate within AI and cognitive science generally and within AI-ED in particular (Bickhard and Terveen, 1995; Clancey, 1992a; Hayes, Ford, and Agnew, 1994; Hoppe, 1993; Sandberg and Weilinga, 1992; Vera and Simon, 1993). As yet, there are no AI-ED systems which clearly illustrate its principles. Most discussions of situationism in AI-ED refer to the idea of cognitive apprenticeship (Collins, Brown and Newman, 1989) but cannot point to any exemplar systems in the way that objectivists might point to GREATERP, GUIDON, and so on. Clancey (1993) has, however, listed some principles for designers of such systems, contrasting them with the perceived emphases in objectivism-based AI-ED approaches:
• Participate with users in multidisciplinary design teams.
• Adopt a global view of the context in which a computer system will be used.
• Be committed to providing cost-effective solutions to real problems.
• Aim to facilitate conversations between people.
• Realise that transparency and ease of use is a relation between an artifact and a community of practice.
• Relate schema models and AI-ED systems to the everyday practice by which they are given meaning and modified.
• View the group as a psychological unit.
2.1.4 Connectionism
Connectionism is another view of knowledge which is presented as a contrast to the symbol-processing version of objectivism. Connectionism holds that knowledge is implicitly represented in the weights and links between large numbers of nodes modelled on neural networks. However, although connectionist representations lack the kind of symbolism characteristic of objectivist representations, they are still very much concerned with representations in memory, rather than in the situation. Connectionist methods have been used to develop components of AI-ED systems, but no AI-ED system follows a wholely connectionist philosophy, presumably because the representations themselves, with only implicit understanding, do not easily support learning interactions.
An interesting question, after reviewing how philosophies of the nature of knowledge relate to students' knowledge, concerns how those philosophies relate to teachers' knowledge (or AI-ED systems' knowledge of how to teach). Some researchers (for example, Clancey, 1987) have attempted to apply the expert system paradigm to teaching knowledge and to specify 'tutoring rules' to be interpreted by an AI-ED system. This, then, reflects an objectivist view that such knowledge exists and can be specified. Most AI-ED systems, however, do not have much explicit knowledge of how to teach: it is largely implicit in the way they react to certain situations. This might appear to be a situationist approach but, in fact, is not because the knowledge is clearly possessed by the system but not in a form which it is easy for observers to analyse.
2.2 The nature of learning
Philosophies of knowledge imply philosophies of learning, to some extent. For example, connectionism, with its assumption that knowledge exists in the weighted links between the nodes of large neural networks, implies that learning is a statistical process whereby the weights are adjusted as many examples and non-examples are encountered. Unfortunately, there is no unequivocal mapping from philosophies of knowledge to philosophies of learning and it is one of the difficulities of AI-ED research that heated arguments about the nature of knowledge often lead to similar conclusions about the nature of learning, teaching and AI-ED system design. For example, an objectivist might not demur from some of the principles derived from situationism listed above, for example, that it is time to move on from 'laboratory studies' to putting more emphasis on 'cost-effective solutions to real problems'.
One of the few attempts to link a theory of learning to that of AI-ED system design is that to relate ACT* (Anderson, 1983) to GREATERP and similar systems. The following principles are said to follow from ACT* (Anderson, Boyle, Farrell and Reiser, 1989):
• Represent the student as a production system.
• Communicate the goal structure underlying the problem-solving.
• Provide instruction in the problem-solving context.
• Promote an abstract understanding of the problem-solving knowledge.
• Minimize working memory load.
• Provide immediate feedback on errors.
• Adjust the grain size of instruction with learning.
• Facilitate successive approximations to the target skill.
These principles do not follow in the mathematician's sense of being derivable from axioms of the theory but are more like implicit implications. Moreover, the principles do not lead directly to design prescriptions. These weak links make it hard to argue that the success (or otherwise) of the systems implemented can be attributed to the psychological theory.
Overall, AI-ED system design reflects a rather eclectic view of the nature of learning, regardless of views of the nature of knowledge. Many different kinds of event and activity can lead to learning and many of them have been supported, to some extent, within AI-ED systems (usually without the dogmatic claims that accompany discussions about the nature of knowledge).
2.2.1 Failure-driven learning
ACT* is an essentially objectivist theory emphasising stored schemas in memory. Recently, ACT* has been modified to encompass some aspects of constructivism (Anderson, 1993) but these modifications have yet to lead to significantly modified principles for AI-ED system design. As they stand, GREATERP and its brothers are remediationist systems based on the assumption that learning is failure-driven, that is, that the occurrence of failure provides the opportunity for learning.
Many other approaches have the basic idea of failure-driven learning. For example, SOAR (Laird, Rosenbloom and Newell, 1986) is intended to be a comprehensive cognitive architecture based entirely on a process of 'impasse-driven learning'. An impasse is a situation where the architecture has insufficient knowledge to determine how to proceed. The impasse triggers a heuristic search to create a new operator to overcome it. Similarly, VanLehn's theory (VanLehn, 1990) is an impasse-driven one, derived from the influential 'repair theory' (Brown and VanLehn, 1980) originally developed to explain how students learned 'bugs' in subtraction.
2.2.2 Case-based learning
The 'failure' does not have to be a blatant exhibition of lack of success: it could just be some evidence which causes the student to consider whether their current conception is sound. For example, the idea of case-based teaching (Schank, 1990; Schank and Cleary, 1995), derived from the field of case-based reasoning in AI (Kolodner, 1993), is that students learn from stories (cases) presented at the precise point of becoming interested in knowing the information conveyed by the story. For example, DUSTIN is a language-training system with which students enter a multimedia simulated environment in which they interact with (images of) people they will deal with in their work environment. The student attempts authentic tasks, such as checking into a hotel, and on failure is shown a relevant example before re-attempting the task. This approach is an interesting merger of objectivist methods (there are ostensibly correct representations of how to perform the task) with a constructivist philosophy (with rationales such as "in order to assimilate a case, we must attach it someplace in memory") and a situationist style (with the emphasis on authentic tasks).
The 'case' presented to a student may be
• a very short piece of text (as in a counterexample in a WHY dialogue, as above);
• a complex photograph (as in the Sickle Cell Counselor (Bell and Bareiss, 1993), a system designed to teach museum visitors about sickle cell disease);
• a paragraph giving a case history (as in DECIDER (Bloch and Farrell, 1988), which gives summaries of events such as the U.S. invasion of Nicaragua while the student is expressing political beliefs);
• a longish video (as in JASPER (Crews and Biswas, 1993), where students are presented a story in which the characters are faced with challenges that the students must solve).
In the last example, the video becomes a motivating way to present complex problems for students to solve. The use of video supports an avowed constructivist philosophy, emphasising that students construct knowledge in realistic situations rather than receive divorced classroom instruction. Implicit in this approach is a belief in learning by problem-solving, an approach also characteristic of an objectivist philosophy, which would also emphasise that an AI-ED system itself should be able to solve the problems it sets. (In fact, of the systems mentioned in the previous two paragraphs only DECIDER does not have (or cannot work out) a correct solution.)
A learning by problem-solving approach can be rationalised by many different philosophies and supported by many different styles of AI-ED system; for example,
• GREATERP students solve problems and receive immediate feedback on mistakes (the system being able to monitor each step of a solution);
• LOGO students receive feedback from the system when solutions are executed but receive no didactic help;
• WEST students (who learn arithmetic skills in the context of a simple board game (Burton and Brown, 1979)) are given hints from the system if certain constraints are violated;
• JASPER students may receive hints to help them improve their solutions (earlier versions of JASPER had students solving the problems off-line).
So to say that most AI-ED systems reflect a learning by problem-solving philosophy is not very illuminating unless the nature of the problem and the degree of system support are clarified.
2.2.3 Learning through experimentation
A standard scenario is a problem-solving environment in which students perform experiments and are guided by the system in their interpretation. For example, QUEST (White and Frederiksen, 1990) provides a graphic simulation of circuits to enable students to understand principles governing the behaviour of those circuits by performing troubleshooting operations. For such an interaction to be useful to students, the system's interventions must be couched in terms analogous to those of the student: thus, for novices, the system needs representations of naive qualitative physics. The topic of qualitative reasoning is another broad field of AI whose application to AI-ED has still to be explored in detail, although it was arguably initiated by early AI-ED studies of the SOPHIE system (Brown, Burton and de Kleer, 1982).
The tension between extreme objectivist and constructivist/situationist views is well illustrated by discussions about how students might learn the kinds of causal models needed in science. An objectivist might present the standard formulas and require students to apply them to various (textbook) problems; a situationist might expose the student to many real-world instances and hope that generalisations will (implicitly, perhaps) evolve. White (1993) argues that causal models of an intermediate degree of abstraction can foster learning provided that they are:
• Understandable, that is, they build on intuitive notions of causality and mechanism;
• Learnable, that is, they generate explanations of key domain phenomena;
• Transferrable, that is, the objects and actions within them are represented in a decontextualised form;
• Linkable, that is, they help link different levels of abstraction and different model perspectives;
• Usable, that is, they can be used to predict, control and explain physical phenomena.
For example, the ThinkerTools curriculum includes a set of interactive simulations, such as the dot-impulse model, with which students apply horizontal or vertical impulses (using a joystick) to a ball with the objective, for example, of navigating a track to stop on a cross. There are four linked representations of motion: the motion of the ball itself, dots indicating the ball's velocity, arrows whose motion indicates velocities along the x and y axes, and a datacross, which represents a two-dimensional speedometer. The simulation is intended to help students develop the fundamental concepts of Newtonian mechanics such as impulse, velocity, force and acceleration.
2.2.4 Learning through dialogue
When students interact with a simulation, they tend to focus on tweaking the simulation to achieve the desired short-term effect without addressing the mistaken beliefs and conceptions which will continue to cause difficulties in the longer-term. There appears to be a need to engage the student in a dialogue to get at the fundamental misconceptions. This dialogue may be with a human teacher, other students or a computer-based learning environment - but in any case it reflects a constructivist view that knowledge is structured by interpreting events, albeit that this interpretation requires the mediation of other agents rather than isolated cogitation. Along these lines, Pilkington, Hartley, Hintze and Moore (1992) describe an environment with which students express and withdraw commitments during some debate, the system acting as a 'referee' using the guidelines of dialogue game theory to determine the validity of moves. Such an interface, it is argued, might help students not only clarify their conceptions of the domain under debate but also develop general reasoning skills. Eventually, the nature of such a debate may be sufficiently understood that the system itself may adopt the role of a player as well. As Baker (1994) describes, this work is derived from many fields of AI (belief revision, agent theory, distributed AI) and elsewhere (in cognitive and social psychology and the language sciences).
The work on self-explanation, that is, the hypothesis that better students spend more time explaining examples to themselves (Chi, Bassok, Lewis, Reimann and Glaser, 1989), can be interpreted as a theory about the benefits of arguing with oneself. The self-explanation line of research has recently (VanLehn, 1993) been developed into a proposed general methodology for AI-ED research:
• Collect experimental protocols of learners and divide them into good and poor learners (on the basis of outcome measures);
• Investigate what behaviours and processes were different in the two groups (e.g. self-explanation);
• Develop a cognitive simulation model to account for the identified differences (e.g. the CASCADE system (Jones and VanLehn, 1992));
• Design appropriate interventions to cause the more effective behaviour to occur (e.g. strategically hide information to encourage self-explanation);
• Test the resultant AI-ED system.
2.2.5 Learning as a social activity
AI-ED research has not taken much account of the social and cultural settings within which AI-ED systems have to be designed and used. Until recently, the emphasis has been on the technical challenge of constructing interesting systems within research laboratories. However, when such systems are used in classrooms, the effects are not usually as intended (perhaps not surprisingly). For example, Schofield, Evans-Rhodes and Huber (1990) report that when a geometry tutor (based on the Anderson principles itemised above) was tested in schools, both teachers' and students' behaviours changed in not entirely anticipated ways. Although teachers devoted more time to slower students and adopted a more collaborative style and students increased their effort on tasks (all presumably welcome changes), it was also found that the system increased competition among the students. Because students could progress at their own pace (unlike in the normal classroom) and could easily determine the progress of their co-students, a race developed between them - in fact, 40% of the students attributed their greater effort to the increased competition. The self-pacing feature also led to a modification in teachers' grading practices, as it was now less appropriate to mark students on the percentage correct. Instead they tended to assess on the effort invested.
These kinds of observation lead naturally to proposals for 'socio-technical design' (Clancey, 1993), where the emphasis is on designing a system within the social and physical context in which it is intended to be used. Such proposals are often couched in political terms, presenting such an approach as more 'democratic' because it involves user groups in the decision-making and control of the systems they will use (as opposed to a 'dictatorial' approach in which designs are delivered to users). In particular, user-participatory design, a trend in human-computer interaction and usability research, has recently been applied to AI-ED system design (Murray and Woolf, 1992). The project involved:
• developing a representational framework for domain content and tutoring strategies that was understandable by educators,
• implementing a set of knowledge acquisition tools, and
• involving educators in building the system, through conception, design, implementation and evaluation.
This line of work is part of a broader discussion about the general principles of instructional design theory and knowledge acquisition in AI.
An extreme objectivist might argue that when all the knowledge-to-be-learned and the knowledge-of-how-to-teach-it has been fully specified, the delivery of AI-ED systems to the classroom will not be problematic. The design will take account of all situations and the system will adapt itself accordingly. This assumes that a complete cognitive analysis will subsume the affective dimensions. As Lepper, Woolverton, Mumme and Gurtner (1993) remark, most AI-ED systems only indirectly consider issues such as motivation, whereas studies of human tutors show that they devote more time and attention to motivation and affect than to the strictly cognitive content, especially for certain classes of learners such as remedial students. Human tutors' techniques for maintaining or increasing motivation - based on manipulating the goals of confidence, challenge, control and curiosity - can be seen to be implicitly encoded in some AI-ED systems to the limited extent that some of these techniques seem applicable to such systems.
In any case, situationists would not accept that the goal of explicitly defining all relevant knowledge in deliverable AI-ED systems is a sensible one. It simply does not take account of the fact that the teacher-learner culture is too rich and that the people involved in the use of such systems are able to (indeed, must) contribute to successful design and use of the systems. Because situationists hold that knowledge does not reside in individual heads, they would also move away from one-to-one tutoring systems (which are caricatured as aiming to transfer knowledge to individuals) and encourage more collaborative learning systems, where understanding is developed by group negotiations (as constructivists would accept). Situationists would tend to play down the role of AI within computer-based systems, that is, to provide explicit symbolic reasoning, and argue that AI's role is to mediate the collaborative interactions. They would, therefore, seek bridges to work on computer-supported collaborative work and computer-mediated communication. This opens up a debate about the nature of educational institutions and students' activities within and without them which would be too broad to pursue here.
2.3 Styles of interaction
The view of teacher expertise embedded in present AI-ED systems is, it has to be admitted, rather naive. This is because the nature of teacher expertise is not sufficiently clearly known and because AI-ED system designers generally do not have themselves or have access to such expertise. In addition, perhaps surprisingly, the teaching component has often been considered to be of less importance than, for example, the representations of domain knowledge and, therefore, has often been added on as an afterthought.
However, the earlier sections have given many examples of the various teaching styles adopted by AI-ED systems. The old distinction between theories of learning as being descriptive and theories of instruction as being prescriptive is rejected by AI-ED research. For example, VanLehn's proposed methodology, given above, assumes that identifying learning differences will lead directly to prescriptions for instructional interventions.
The criticisms of the styles of present AI-ED systems which are often made are rather misplaced. Few of these systems aims to provide a comprehensive coverage of either a significant part of a curriculum or the range of teaching styles. Rather, each system is an investigation of one style applied to one rather circumscribed topic. Thus, we should consider whether the teaching style of a system is appropriate for the limited aims that its designers have. For example, it is inappropriate to criticise GREATERP for its domineering style of putting students right immediately they stray off the correct path if this is an effective strategy for bringing large numbers of beginning LISP programmers up to a standard of competence after which more subtle strategies may be needed. Similarly, those systems which have a clear training objective, for example, the Space Shuttle Fuel Cell Tutor (Duncan, 1992) and Sherlock (Lesgold, Lajoie, Bunzo and Eggan, 1992), an avionics troubleshooting tutor, where it is essential that students master the operation of complex equipment, may quite justifiably adopt an essentially objectivist approach of defining the knowledge-to-be-learned and ensuring that students acquire it as effectively as possible.
For many AI-ED systems, however, the aims are not so clear-cut. Often there is a 'surface' objective for the student (to write a program to draw a specific shape; to manipulate parameters to maintain an economic simulation in a stable state; to solve a specific algebraic equation) which masks the real objective (to develop various higher-order skills, such as planning and monitoring solution attempts). System interventions directed at the former objective (for example, to point out that a program is incorrect) are irrelevant or harmful if they interfere with the latter objective. Many years ago the designers of the WEST system (Burton and Brown, 1979) proposed instructional guidelines such as "do not tutor on two successive moves" which only make sense if it is accepted that the system's aims are more than to ensure that the student obtains the 'right answer'. With such systems the balance between 'guiding', 'telling' or 'leaving' the student, and hence the whole vexed issue of the balance of control between the learner and the system, is a continuing debate. The specification of precise and general guidelines has proved elusive and the design of the instructional component of AI-ED systems remains more an art than a science, as it does for other educational systems.
2.4 New technologies in education
Regardless of philosophy, psychology, or any other academic consideration, it is undoubtedly the case that the new technologies increasingly being applied to education have stimulated some of the trends discussed above. For example, the advent of high-fidelity multimedia and virtual reality systems naturally leads to its enthusiasts arguing for the merits of learning through 'immersion in a situation', which is a variation of the situationist's view. Similarly, the availability of high-speed networks permits a degree of distributed, collaborative working which was previously unattainable and this leads to discussions about the intrinsic virtues of 'social learning' mediated by technology.
This review is concerned specifically with the role of AI in education and we will not discuss the technical details of new technologies but only the potential relevance of AI to them. At the moment, the excitement with the new technologies owes nothing to AI. However, as the history of educational innovation shows, new technologies tend not to deliver all that they promise and it is quite predictable that as the limitations of the new technologies become clearer, so AI techniques will be adopted to help overcome them; for example:
• The successful use of multimedia interfaces requires models not only of the media themselves, but of the user, task and discourse (Maybury, 1994), aspects that have long been studied in conventional AI-ED research. No doubt existing work on, for example, student modelling and discourse management will not be immediately applicable and will need to be adapted but this is clearly work with an AI orientation.
• The effectiveness of virtual reality as a learning environment depends fundamentally on the relation between learning and social and perceptual experience, a relationship which is central to AI research. Even at the technical level, preliminary experiments have already shown the need for surrogate 'co-learners' and other intelligent agents in the environment (Shute and Psotka, 1994).
• According to Katz and Lesgold (1993), the demand for computer-supported collaborative learning environments for workplace training can best be met by adapting the coached practice environments, such as Sherlock (Lesgold, Lajoie, Bunzo and Eggan, 1992), originally developed for individual learning. If so, present AI-ED research can be seen as the basis from which the new theories required for these environments will evolve.
Whatever the future holds, recent technological advances have radically changed AI-ED systems. A few years ago, a review such as this would be profusely illustrated with screen images to show student-system interactions, usually involving natural language-like typed communication (see, for example, the illustrations in Wenger (1987)). Now, with graphic interfaces and multimedia, it is virtually impossible to capture on paper the richness and immediacy of such interactions.
2.5 Measures of effectiveness
AI-ED research has the misfortune to be concerned with a field of application of AI (i.e. education) which is riven and driven by demands for evaluation. No other field has such an ethos of evaluation built into it and therefore, compared to other areas of AI, AI-ED needs to take evaluation very seriously. We can distinguish two kinds of evaluation - those of complete systems (summative or external evaluations), which generally attempt to demonstrate some educational benefit of the system as a whole, and those of components or prototypes of systems (formative or internal evaluations), which generally aim to investigate the properties of parts of systems so that may be improved.
2.5.1 External evaluation
The evaluation of any educational innovation, including AI-ED systems, is inherently difficult (Mark and Greer, 1993; Winne, 1993). However, because of the expense of AI-ED system implementation, the demand for successful evaluations is quite reasonably made. It is only recently that AI-ED research has been able to respond to the challenge by carrying out large-scale empirical studies which show the benefits of AI-ED systems in real educational settings, for example, the evaluations of:
• The Geometry tutor, as mentioned above (Schofield, Evans-Rhodes and Huber, 1990).
• SMITHTOWN, a discovery world that teaches scientific inquiry skills in the context of microeconomics (Shute and Glaser, 1990).
• Sherlock, where twenty hours using the system were judged to be as effective as two years 'on the job' (Nichols, Pokorny, Jones, Gott and Alley, 1993).
• A STATICS tutor, where the instructional design effort per hour of instruction time was about 85 hours, compared to 100-300 hours for traditional CAI (Murray, 1993).
• The Space Shuttle Fuel Cell tutor, where NASA trainers were so convinced of its superiority over alternatives that it was adopted without need for a formal evaluation (Duncan, 1992).
2.5.2 Internal evaluation
These evaluation studies, however, use standard educational techniques with AI-ED products but do not themselves use AI techniques. More relevant to this review is the possible use of AI for evaluative purposes.
Any AI-ED system is an implementation of a (usually implicit) theory of learning and instruction. If the theory were sufficiently explicit it could be expressable in executable form and the outcomes from the AI-ED system could be predicted by running the system with 'simulated students'. VanLehn, Ohlsson and Nason (1994) consider the possible uses of simulated students to support teaching training, to enable an AI-ED system to act as a collaborative partner, and to permit formative evaluations. In the last case, for example, one can, in principle, determine which is the better of two proposed instructional designs by seeing which leads to better learning of the simulated students.
In this way, an AI-ED system may be used for formative evaluations before being used with real students. This is standard practice in other fields of computer use, but its usefulness in AI-ED may be doubted because of our lack of faith in the soundness of the theories of learning concerned. The principle, however, seems sound.
Similarly, we can imagine applying the student modelling component of AI-ED systems to assist with the thorny problem of assessment (Martin and VanLehn, 1993). Most AI-ED systems which are not entirely exploratory environments maintain some kind of student model, that is, some representation of what it is believed the student has understood. This student model may be used for many purposes within an AI-ED system, for example, to determine appropriate problems to set, to provide remediative feedback, and so on. Many techniques have been developed to build student models, some derived from well-known AI techniques such as:
• discriminative concept learning (Ohlsson and Langley, 1988), where the aim is to induce the student's problem-solving procedure from observations of his correct and incorrect results;
• resolution from computational logic (Costa, Duchénoy and Kodratoff, 1988), where the technique is used to suggest and prove hypotheses about a student's beliefs;
• neural networks (Mengel and Lively, 1991), where the network is trained to simulate a student's cognitive processes;
• fuzzy logic (Derry and Hawkes, 1993a), to provide an approximate diagnosis, recognising that a student's behaviour is not entirely consistent and induction from it is risky;
• Bayesian networks (Katz, Lesgold, Eggan and Gordin, 1994), also to provide a less precision-oriented approach to student modelling;
• model-based diagnosis (Self, 1993), to cast the student modelling problem in terms of general diagnosis in AI;
• logic meta-programming (Beller and Hoppe, 1993), to reconstruct hypothetical solution paths to check against constraints associated with correct solutions.
• belief revision (Kono, Ikeda and Mizoguchi, 1994), to keep the model consistent with observations;
The need for, and success of, these methods remains a controversial topic within AI-ED research (Lajoie and Derry, 1993; Spada, 1993). To the extent that these techniques are successful and so provide a useful evaluation of an individual student (useful in the sense that it may support individualised interactions) they may be used for assessment purposes. Educationalists must argue about the ethics of computer-based assessment and about whether what can be reliably assessed in this way is in fact what should be assessed, but again the principle seems sound: many AI-ED systems aim to build student models and to the extent that this is possible it may form a basis for assessment of the student and an evaluation of the system's effectiveness in helping that student to learn.
2.6 On-going debates
Education has been a controversial topic for two millenia at least: AI has been equally controversial for rather less long. AI in Education is bound to provoke debate. After two decades, a body of techniques has been developed which are beginning to be consistently re-applied in new systems. Some early AI-ED concepts are now routinely used in off-the-shelf computer-based learning systems: for example, a $50 typing tutor uses a student model with a bug catalogue to generate new practice lessons as needed. Some larger-scale AI-ED systems have been shown to be effective within larger organisations such as the military (as discussed above).
But still there is considerable argument about AI-ED research. Some of the arguments have been touched on earlier. We conclude by mentioning some more general questions:
• Is AI a dangerous metaphor for education? For some critics, AI is seen as supporting a rather behaviouristic approach to learning, in that it aims to adapt the learner the conform to the knowledge embedded in the AI system. As we have indicated, this is a simplistic characterisation of only a sub-class of AI-ED systems.
• Can AI-ED systems support student autonomy and open learning? The more that intelligence is put within AI-ED systems, the more the temptation may be to apply it to control and direct the student's interactions with the system. However, the range of AI-ED systems includes much more than overbearing tutoring systems.
• Will AI-ED systems ever be used in real educational settings? Of course, this depends on what is understood by a 'real educational setting'. The traditional school classroom is perhaps not a very promising setting for many systems, but the organisation of classrooms is changing rapidly. It also seems likely that more learning will occur outside the official classroom as access to computer technology improves and individuals learn at home or at work, for their own interest or career development.
• What will be the impact of new educational technologies and what role will AI play within them? At the moment, we are in a phase where the radically different nature of the new technology has side-lined AI. Eventually, however, there will be a merging of the more software-oriented field of AI-ED with the more hardware-oriented advanced learning technologies.
• Will AI-ED research continue to progress through the rather unprincipled implementation of demonstration systems, or will some theoretical basis for AI-ED system design be developed? Currently only certain components of AI-ED systems are amenable to any kind of theoretical analysis and no comprehensive 'theory of AI-ED systems' is likely in the near or medium-term future.
• Do AI-ED systems reflect a reasonable view of the nature of knowledge and learning? This brings us full circle. As we have discussed, there is no consensus within AI-ED research about these issues and we can find examples of systems which reflect many different philosophies. Apart from the perception of AI-ED research as a field oriented towards producing practically useful systems, AI-ED may also a provide a more technical contribution to such fundamental debates.
3. Introducing computational mathetics
The previous chapter aimed to provide a non-technical overview of the AI-ED field. You will have seen that the chapter did not use a single a, f, ", Æ, or any of the other formal symbols which adorn texts in other fields of AI (and AI-ED is still considered to be a field of AI - for example, "intelligent teaching systems" is one of the topic areas for the major AI conference of 1995). In this, the chapter is not being unduly lenient with the reader, for much the same can be said of all the books mentioned at the beginning of chapter 2. They all have a predominantly wordy style, in which concepts and issues are discussed in informal natural language, perhaps enlivened with the occasional illustrative screen dump, but devoid of any formal definitions, theorems, axioms, derivations, and the like. Superficially, then, AI-ED is very different from general AI, as is apparent from only a glance at the major AI journals and conference proceedings.
This would not matter at all if AI-ED were indeed a very different subject from general AI, whose methodologies were considered inappropriate for AI-ED. On the other hand, if AI-ED is to make a distinctive contribution to education, which I assume is the ultimate aim, then it must come, by definition, from the unique attributes of AI itself. AI-ED researchers must engage in broad educational, philosophical, psychological and sociological discussions but it would be rather arrogant of AI researchers to imagine that whatever expertise they have in AI enables them to resolve such long-standing debates. Whenever opinions are offered on such issues they risk being immediately dismissed as naive and unoriginal by those expert in the respective fields. For example, even the influential situated learning proposals of Collins, Brown and Newman (1989) and Brown, Collins and Duguid (1989) were welcomed with a tone of condescension - both Palinscar (1989) and Wineburg (1989) commented on the lack of references to related earlier work by Dewey, Vygotsky, Bruner and others, with Wineburg remarking that "one hopes that these ideas will interact with their antecedents and surpass them in the rigour of their formulation".
The challenge of contributing to broad educational debates is one that AI-ED must continue to face, but not necessarily in terms set by others. Rather than AI-ED attempting just to contribute in areas which already have established traditions and paradigms - and ones which, if we wished to be argumentative, we could claim have not been entirely fruitful - it could ask, or insist, that the debates be represented in its terms, that is, in the language of AI, and so perhaps provide the rigour which Wineburg and others profess to desire. To put it simply, the technical language of AI would be offered as a means of clarifying debates. Moreover, that language of AI, if it is found appropriate, would provide a much more direct link to the design of computer-based systems to promote learning. This, then, is the objective of the following pages but first it is worth reflecting on recent AI-ED developments.
3.1 The need for computational mathetics
Although it would be nice to imagine that the AI-ED field makes rational, scientific progress based on purely academic considerations, we must also take into account the social and cultural context in which AI-ED research is carried out, just as AI-ED itself is increasingly being urged to take into account such factors when designing AI-ED systems. In the twenty years from 1967 or so (when Carbonell and Wexler began their PhD projects (Carbonell, 1970; Wexler, 1970)), AI-ED research proceeded rather serenely, producing a body of work, surveyed in Wenger (1987), which seemed to lay out a panorama ripe for further investigation. In fact, the field then underwent a convulsion in which many of the tenets of the previous work were challenged - a convulsion led, perhaps predictably, by Wenger himself and his foreword-writers, Seely Brown and Greeno, who all, along with others, explicitly disassociated themselves from the 'knowledge communication' theme of the book and its basis in standard symbolic artificial intelligence. Suddenly "intelligent tutoring systems", which had become a broad term encompassing a range of AI-based systems (few of which were actually tutoring systems in the sense subsequently caricatured), became a term to avoid. Instead, AI-ED researchers were urged to widen their horizons beyond the panorama sketched in 1987, by taking account of previously neglected work in disciplines such as psychology, sociology, anthropology, linguistics, philosophy and biology in order to provide a theoretical rationale for the new kinds of learning environment made possible by new learning technologies such as multimedia, conferencing, and virtual reality.
Clearly, this was a timely development, for ITS research was in danger of becoming too blinkered. And yet, there were two odd features with this revolution. First, it was entirely US-led. Of course, this may not be thought odd, for most things are US-led, but pockets of AI-ED research existed in Europe, Canada, Japan and elsewhere and they were almost without exception puzzled by the missionary fervour with which the new paradigms were preached. Having come to many of the same conclusions about the status of AI-ED research themselves, they tended to prefer a more evolutionary development, rather than an explicit disavowal of all previous work. In some cultures, such as the Japanese, there was bewilderment at the idea that they were no longer supposed to talk about 'communicating knowledge'.
The second odd feature was that inspiration for the new approaches came mainly from European scientists and philosophers - Vygotsky, Leontiev, Heidigger, Marx, Piaget, Wittgenstein, Levi-Strauss, Bartlett - many of whom did not have English as their mother tongue and most of whom were unfortunately no longer with us. This had the effect that the inevitably obscure translations of their original writings could be imbued with all kinds of profound meanings which could not be fully resolved by reading the original text (for English-speakers, anyway) nor, of course, by asking the writers to elucidate. In some cases, the ideas had to some extent been absorbed into European thinking and it was difficult for Europeans to see what all the fuss was about. For example, the new emphasis on 'socio-technical design' seemed at first to ignore the fact that schools at Manchester and in Sweden had been advocating this for forty years. Sack, Soloway and Weingrad (1994) describe how their ideas about AI-ED system design have evolved as a result of their foray "into the wilderness of continental philosophy".
Anyway, it is clear that the significant recent changes in AI-ED research, especially in the US, are partly a product of the US culture, and therefore we should consider the situation as it was in the US in the mid-1980s, when the changes began. The paper which is now considered to be the catalyst for the 'revolution' (Collins, Brown and Newman, 1989, written in 1986) commented that "Current work on developing explicit, cognitive theories of domain skills, metacognitive skills and tutoring skills is making the crucial first steps in the right direction": hardly a clarion call for a revolution! The paper's points are illustrated by referring to standard AI-ED systems of the time. Similarly, Wenger (1987) appeared to indicate that the foundations had been laid and it was time to cross the 'threshold of development'.
However, a more careful reading of Wenger (1987) indicates that he and others had misgivings about the direction of AI-ED research. His organising theme, 'knowledge communication' is first (p7) defined as "the ability to cause and/or support the acquisition of one's knowledge by someone else, via a restricted set of communication operators". However, by the end of the book he has developed a view of knowledge communication in which "both the knowledge states involved in knowledge communication are modified: knowledge communication is viewed as a dynamic interaction beween intelligent agents by which knowledge states are engaged in a process of expansion and articulation" (p431). Similarly, as one reads his individual project descriptions, which are uniformly and exaggeratedly complimentary, it is striking that many of the protagonists were in fact withdrawing from the original aims of their projects. Subsequently, many have explicitly or implicitly disavowed their earlier work and have advocated different methods or have moved out of AI-ED entirely (Brown, 1990; Clancey, 1992b, 1993; Collins, 1988; Greeno, 1989; Lave and Wenger, 1991; Sleeman et al, 1989; Soloway et al, 1992).
There may be an element of getting one's criticism in first here. By the late 1980s, intelligent tutoring systems research had developed a reputation for failing to deliver what it promised or, rather, what had been promised on its behalf (the acronym ITS was sometimes rendered as 'invisible tutoring systems'). AI-ED researchers knew better than outside critics the reasons for this perceived failure and it was perhaps politically sensible to admit the error of one's ways and to propose radically different solutions. Whatever the reason, there was a sense of despair. Sack, Soloway and Weingrad (1994) comment that
"we made large catalogs of bugs we observed in student programs, gave them very long and complicated names, and then organized them into taxonomies. Unfortunately, these lists of bugs with formal identities never made it out of the laboratory and into the classrooms ... our old bug taxonomies are of no educational interest ... [now] we want to put powerful, real-world tools in the hands of students so that they might have the opportunity to create transitional objects which will serve to introduce them to the society-at-large."
Similarly, Clancey (1993) considers that
"Despite the use of advanced computer technology in the 1990s, the dominant form of instructional design in schools and industry is 1960s-style page-turning presentation. No commercial authoring tool has the complexity of GUIDON. At the same time, researchers in industry are finding that expert-system techniques, hatched in university laboratories, are inadequate for developing useful programs that fit into people's lives.... After more than a decade, I felt that I could no longer continue saying that I was developing instructional programs for medicine because not a single program I worked on was in routine use."
These 'failures' may be more ones of unrealistic expectations. In O'Shea and Self (1983) we had predicted that
"computerised tutors will play a minor role in education for many years to come. A few tutorial programs will be generally available in 1992, but there will be little incentive to develop more. The type of application where there is an incentive is in areas where failures in training result in great cost. For example, if errors in operating nuclear power plants could be reduced by training with an expert teaching system (like SOPHIE but incorporating a simulation of a power plant) then such a system might well be developed."
As mentioned in chapter 2, we do have a few off-the-shelf tutors, like SPENGELS, and most of the significant on-going AI-ED projects are in the area of expensive training projects, such as Sherlock and the Space Shuttle tutor. Our conclusion in 1983 was that ITS research should continue, despite this 'failure' to deliver products, because of its academic interest and longer-term potential.
However, in the US, at least, there was considered to be some urgency to find other ways of solving educational problems. In this context, the Institute of Research on Learning and the Institute for the Learning Sciences were established and they naturally had to advocate methods different to the failed ITS ones. The former's aim appeared at first to continue the line of ITS research:
"The institute will work on artificial intelligence systems for traditional classroom learning, as well as for training in the workplace. The focus of our research will be on how children and adults think and learn, and on expert computer systems that can coach them the same way a personal tutor would" (from the inaugural speech of George Pake, the first director of IRL, on November 12th 1986).
The IRL would work in association with cognitive scientists, sociologists, education professionals and anthropologists - the last because "anthropologists are experts in human beings as social animals ... Most of what we learn, we learn with others". The distinctive approach of IRL was thereby established, to become stronger over the following years.
The Institute for the Learning Sciences aimed to go "beyond today's generation of simulators and 'intelligent tutors'" and develop 'discovery systems' (Schank and Edelson, 1989):
"A 'discovery system' encourages a student to become an active learner by forcing him to generate hypotheses, test them, and revise them. The system develops the student's capabilities as a case-based learner by providing him with relevant cases at appropriate moments. It enables the student to learn through failure and encourages creativity by inviting him to pursue any hypothesis without attaching a stigma to possible failure. Finally, it allows the student to learn through experience by providing him with the opportunity to explore a simulated environment, while at the same time allowing him to learn from the experience of others through exposure to relevant cases."
Changes in AI-ED do not occur in a vacuum: they are part of more general attempts to change educational practice. A paper by Cohen (1989) is sometimes quoted to support the new mission of computer technology in education. This essay traces a history of teaching practice, discusses the 'new pedagogy' and considers the difficulties facing its adoption. Here are three quotations which might help us to understand what is happening in US education, and hence in AI-ED. First,
"Consider first the view that knowledge is purely objective - that it is discovered, not constructed. This notion has deep roots in medieval Europe. Recall that educated men of that age worked from hand-copied manuscripts that had survived the collapse of a glorious Empire, or found their way into Europe from more sophisticated eastern civilizations... Scientists and philosophers in the seventeenth and eighteenth centuries worshipped a rational Nature. They believed in the objectivity and authority of sciences that would open nature's lawful heart to investigators... During most of the modern age, then, there was little argument about the objectivity of knowledge, nor about the great authority of such knowledge... Only very recently have these old and deeply rooted ideas been broadly questioned."
History is in the eye of the beholder and alternative views are possible. The above quotation concerns an alleged prevailing philosophy of knowledge which if it did prevail then it did so in Europe, America and elsewhere until science itself indicated that it was untenable through the uncertainty principle, relativity, chaos theory and Goedel's theorem. However, the philosophy of objectivism does not necessarily entail a particular pedagogy, nor vice versa. The most influential teacher for Western society was arguably Jesus Christ, whose methods clearly followed the 'new pedagogy' rather than an objectivistic philosophy. His enigmatic parables were couched in 'authentic' situations and their meaning had to be constructed by listeners, as indeed they still are today. Similarly, in Chinese society, the writings of Confucius are still revered and re-interpreted after 2500 years. It is fairly clear that before medieval times versions of the new pedagogy were dominant. From medieval times almost all those who wrote about educational philosophy (such as Erasmus, Locke, Rousseau, Comenius and Froebel) espoused views which were more constructivist than objectivist. In fact, in all the recent constructivist writings that I have read I've yet to see a direct quotation from any educational philosopher arguing that knowledge should be 'transmitted'. Instead they invariably infer and attribute a philosophy from the practice. It could well be that practice was dictated by social and other factors rather than by philosophy. After all, what else could medieval monks do but laboriously transcribe rare texts? Cohen quotes the American icon Mark Twain's story of learning to become a Mississippi riverboat pilot to indicate that there was a popular rebellion against 'formal education'. Similar stories are common in European literature. For example, there can be no more biting satire on 'knowledge transmission' than Jonathan Swift's Gulliver:
"I was at the mathematical school, where the master taught his pupils after a method scarce imaginable to us in Europe. The proposition and demonstration were fairly written on a thin wafer, with ink composed of cephalick tincture. This the student was to swallow upon a fasting stomach, and for three days following eat nothing but bread and water. As the wafer digested, the tincture mounted to his brain, bearing the proposition along with it."
Similarly, Charles Dickens' Gradgrind is made a ridiculous figure for his 'facts, facts' philosophy. In short, popular educational philosophy never did support objectivism.
The second quotation is, following on a discussion of the impediments to adopting the new pedagogy:
"But where is it written that change will occur if only the 'obstacles' are removed? It is easy to understand why such an assumption would be common among educators, in view of many reformers' insistence that adventuresome teaching is possible anywhere. The idea that change is normal is particularly easy to understand among a people that embraces the idea of progress as avidly as Americans do. But why should researchers adopt these assumptions? Why should we accept that improvement is to be expected, or that change is the normal state of affairs? It may seem un-American, but perhaps stability is to be expected in teaching."
We should not pass over the phrase 'adventuresome teaching'. This term is not defined anywhere but it is another loaded term (like 'constructivism' itself) which can only be denied by painting oneself into a corner labelled 'unadventuresome teaching' (or 'destructivism', 'obstructivism' or, even worse, 'instructivism'). If we paraphrase it to, say, 'risky teaching' then it is not so obviously a good thing. Anyway, the main point is that American culture "embraces the idea of progress" more than others, that change is conflated with progress, and that the 'new pedagogy' is, by definition, change.
Finally:
"Recent efforts to make teaching more adventurous thus are a modest and recent chapter in a much larger and older story. Our struggles .. are only a few episodes in a gathering collision between inherited and revolutionary ideas about the nature of knowledge, learning and teaching... Efforts to sort out the intellectual content and practical implications of both traditions have only just begun, under the pressure of conflict and challenge. This is true even in the United States: While it is the nation most deeply committed to the new pedagogy, efforts to try the new ideas out in practice here still are isolated and quite fragmentary. Other countries, like France, Germany, or Spain remain largely untouched by new instructional ideas and practices. It seems reasonable to suppose that we are working on the frontiers of this great collision."
So, the new pedagogy is in the great American tradition of frontier-crossing. While in the US change is the normal state of affairs, other cultures ignore new ideas, for some reason. If everyone's cultural context were one in which, as in Chicago, on an average day 19% of the schoolchildren are playing truant then we might all believe in the need for adventuresome teaching (it would be an adventure to find the children, at least).
Actually, constructivism is a broad philosophy with adherents in the arts, humanities, social sciences and only relatively recently in education and technology. The term (or at least the Russian equivalent of it, konstruktivisma) was apparently first used by Russian artists in the early 1920s, who, in the aftermath of the revolution and the World War, were reacting against the straightjacket of production art and Marxist doctrine. Gan (1922) wrote that "constructivism is a phenomenon of our age". A 'Manifesto of International Constructivism' was signed in September 1922. The meaning of the term has evolved as it has been used through the century by artists, architects, linguists, and others, but its core still resonates with its recent adoption by educational technologists:
"What can be stated quite categorically about constructivism is that it rejects the comfortable assumption of a 'given' harmony between human feeling and the hostile world. In contrast, it implies that man himself is the creator of order in a world that is neither sympathetic nor hostile, and that the artist must play a central role in determining the type of order that is imposed." (Bann, 1974).
Intriguingly, the term 'situationism' also has a pedigree in the arts. There was an exhibition of situationist art held at the Centre Georges Pompidou and the Institute of Contemporary Arts in April 1989. The Situationists were an avant garde group of the 1950s and 1960s whose activities had a revival of interest in the late 1980s. The key features of their work were iconoclasm, a sense of purpose, an aura of radicality and by inference authenticity. So-called Specto-situationists claimed to have played a key role in stimulating the Paris riots of May 1968. I cannot resist giving a short extract from a transcript of a conversation between the art critics Ralph Rumney and Stewart Home, discussing the exhibition: "It was what was actually done that was important, far more than the theory. Theories are evanescent. Situationist theory was intentionally inspissated, to make it difficult to understand and extremely difficult to criticise." "And also to give an impression of complete originality!"
The Cohen essay is about education in general and says nothing directly about AI-ED. However, we can see the same re-writing of history happening over the much shorter timescale of AI-ED. I do not believe that many ITS researchers of the 1970s and early 1980s held the philosophies now attributed to them (if so, where are the quotes?). Like the medieval monks, they were doing what they could with the technologies of the time. I also do not believe that the foundations laid then will turn out to be completely irrelevant to the design of AI-ED systems to support the new pedagogy, whatever it turns out to be.
This discussion of the recent history and context of AI-ED research unfortunately violates the very principles which we aim to advocate. It engages in a vague polemical debate about very general issues which do not necessarily impact directly on the design of systems. The purpose of the above discussion is not to denigrate alternative approaches, for that would be to join an unnecessarily confrontational debate setting up false dichotomies. It is essential for AI-ED research to take better account of the concepts of 'situation', 'context', 'community', 'discourse', 'social learning', and so on, but these terms need to be defined, not used as mantra. The language of AI is offered as a way of defining and then analysing such concepts. That will be the aim of 'computational mathetics'. First, however, it will be fun to consider two analogies, risky though they always are.
3.2 An analogy with aeronautics
It has been said that the design of computer-based learning environments is a form of 'educational engineering'. If only it were so. The 'educational engineering' term is based on a derogatory characterisation of engineering as the undisciplined design of devices by tinkering with them until they appear to work. Modern engineering is different. Let us consider the case of aeronautical engineering.
After Greek mythology, Leonardo da Vinci (1452-1519) was the first person to develop detailed proposals for a flying machine, all based on flapping wings. These could never work because it is not possible in this way to attain the energy output per unit weight that birds achieve. The breakthrough - to base the design on a soaring bird not a flapping one - was made by Sir George Cayley (1773-1857), who in 1799 designed an airplane, indicating the lift and drag forces in his drawings, whirled his models through the air to carry out experiments, and published his results in the Journal of Natural Philosophy in 1809. Although this work explained the fundamental concepts necessary for flight, it was forgotten and the later aviation pioneers proceeded in ignorance of it.
Otto Lilienthal (1848-1896) was the first person to fly heavier-than-air craft in a more or less reliable fashion. He published a book on Bird Flight as the Basis of Aviation in 1889 and considered that the only way to develop a deeper understanding was to engage in actual flying experiments himself. Accordingly, he made 2000 glides, before he crashed and died in 1896. The Wright brothers systematically studied the writings of Lilienthal and others and began their own test flights of gliders in 1900. They built a wind tunnel to study wing design, discovering the crucial concepts of wing warping and adverse yaw. In 1903 they developed a generally sound theory of propeller operation. By 1905 they had made over 100 powered flights for durations up to 38 minutes, but the US War Department refused to believe that flight was possible and rejected an invitation to a demonstration. However, the test flights continued as occasions of great drama and apprehension - and danger, for Orville Wright had two serious accidents and killed an observer in 1908. Very soon, the test flight was displaced by more specialized environments, such as wind tunnels, and the elaboration of the theory of aeronautics.
Aeronautics is largely concerned with the flow of fluids over surfaces and therefore is a branch of fluid mechanics, which had been comprehensively studied in the 19th century. The first attempts to apply fluid mechanics to aeronautics produced theories which, although apparently correct, gave answers which did not agree with the results of tests. An important element, viscosity, had been omitted. Today, aeronautics is a "blend of beautiful theory and empirical fine tuning" (Shevell, 1983). The theory is expressed in the language of mathematical physics and includes a wealth of specific technical concepts, such as downwash, ground effect, and wake vortex turbulence, and its own sub-theories, such as the theory of circulation. The theory provides substantial confidence in the safety and efficiency of aircraft before any flight is attempted. If there are variations in design which need to be investigated then this may be done in specially designed test environments, not in a full-scale test flight. The successful development of aeronautics has been possible even though fluid mechanics itself is far from complete, with basic questions such as the nature and cause of turbulence still not wholly answered.
In comparison, AI-ED system design is about where airplane design was in 1905. Perhaps a thousand 'test flights' have been made and most have crashed. Empirical studies have been carried out on our 'target analogy', the human teacher, although these are likely to have missed the crucial aspects. Special test environments are beginning to be built, as we will see. The US Department of Defense is beginning to believe that AI-ED systems can solve some of their training problems. Unfortunately, there is unlikely to be a manuscript hidden in the archives which lays out the basic theoretical principles for AI-ED system design (although some people are looking). In fact, there is no ready-to-hand theory which is likely to be adaptable for our purposes, as fluid mechanics was for aeronautics. Our argument will be that AI is the best source for such a theory, although we can be sure that we will have more work to do than just identify missing components, such as viscosity. It may be that AI-ED system design is so fundamentally different from airplane design that no corresponding theory is attainable: we may see.
3.3 An analogy with computational linguistics
The ability to learn has some similarities with the ability to use language:
• They are both universal abilities in that they are developed by all normal individuals in all cultures.
• There are believed to be universal principles which hold for both abilities. The observation in 1786 by Sir William Jones, Chief Justice in Bengal, that modern languages "have sprung from some common source which, perhaps, no longer exists" was considered deeply insightful and is sometimes regarded as marking the birth of 'linguistics'. The search for linguistic universals, that is, properties of language which are necessary and innate, is very much part of modern linguistics. The assumption of 'learning universals' seems to have gone unremarked.
• Although all individuals develop both abilities they may be improved by a deliberate educational effort. In English-speaking countries 'English language' is a core of the primary and secondary curriculum, and courses such as 'study skills' are sometimes offered although more often teaching about learning is distributed opportunistically around other courses.
• Both abilities can be applied individually or within groups. It is arguable that the purpose of both abilities is to enable individuals to participate and contribute in society. At least, it is clear that both cognitive and social aspects have to be considered.
• Both abilities can be possessed (to some extent) by agents other than humans, for example, chimps and computers.
Linguistics, the scientific study of language, has been a recognised discipline for two centuries or more, with several established sub-disciplines: anthropological linguistics, applied linguistics, biological linguistics, clinical linguistics, computational linguistics, educational linguistics, ethnolinguistics, geographical linguistics, mathematical linguistics, neurolinguistics, philosophical linguistics, psycholinguistics, sociolinguistics, statistical linguistics, and theolinguistics (Crystal, 1987). Computational linguistics provides the theoretical and technical underpinning for the development of computer-based language systems, such as those for machine translation, natural language front-ends for information retrieval, and so on. The achievements of computational linguistics are a major reason why there are now many hundreds of computer-based language systems in routine use. A modern textbook on computational linguistics (such as Gazdar and Mellish, 1989) says very little about particular applications. It also says little about related sub-disciplines such as psycholinguistics and sociolinguistics. As Gazdar and Mellish (1989) say in their preface:
"The book is formally oriented and technical in character, and organized, for the most part, around formal techniques. The perspective adopted is that of computer science, not cognitive science. We have no claims to make about the way the human mind processes natural language ... This is a book about natural language processing techniques, not about their application."
The earliest books on computational linguistics make strange reading today. For example, almost half of Hays (1967) deals with elementary data structures and transient hardware, the remainder discussing miscellaneous applications, such as concordances. Gazdar and Mellish, in what is still only an 'introduction to computational linguistics', can write over 500 pages of technical material. In comparison, AI-ED system design is about where the design of natural language systems was in 1970. As remarked above, current AI-ED books are primarily non-technical descriptions of various applications.
3.4 The definition of computational mathetics
The scientific study of learning, in so far as it exists today, is distributed around psychology, education, sociology and artificial intelligence. It does not form a coherent, integrated field of study and does not contribute reliably to the design of computer-based learning systems. While not wishing to suggest that such a discipline be created, we can daydream about how the design of AI-ED systems would be different if it were.
According to the Shorter Oxford Dictionary, the word 'mathetic' is an adjective meaning "pertaining to learning", from the Greek 'manthanein', "to learn". We may coin the noun 'mathetics' to mean "the study of matters pertaining to learning", in analogy with linguistics, physics, aesthetics, and so on. Then the field of 'computational mathetics' would be "the study of matters pertaining to learning, and how it may be promoted, using the techniques, concepts and methodologies of computer science and artificial intelligence" (Self, 1992), in analogy with the definition of computational linguistics (Gazdar and Mellish, 1989). (Papert (1993) also finds the need to invent the word 'mathetics' for "a course on the art of learning". In fact, the coinage is not new. There was, I understand, a short-lived Journal of Mathetics in the 1960s.)
Computational mathetics would be, like computational linguistics, technically and theoretically based and oriented towards, but independent of, practical applications. In particular, it would be oriented towards the eventual design of computer-based systems to promote human learning. As a field, it would be related to but clearly distinct from educational mathetics, neuromathetics, psychomathetics, sociomathetics, and so forth. Most of what is written today about AI-ED systems could be considered to belong in those co-fields, not within computational mathetics. Those co-fields must continue to develop for they are complementary to, not in competition with, the field of computational mathetics.
Computational mathetics would be explicitly concerned with 'learning', not 'education' in its broad sense. This is a realistic view of what AI-ED systems aim to do, despite the 'education' in the title. The business of education involves much more than just that of learning, for example, the range of administrative and pastoral activities. These are outside the scope of AI-ED systems and therefore of computational mathetics. Computational mathetics would not be concerned solely with human learning and therefore would not be wholly within psychology. It would also not be concerned solely with the design of computer programs to learn (i.e. machine learning) but with the interaction between two or more agents, one or more of whom it is intended should learn. Computational mathetics would differ from other fields in scope but, more importantly, in approach.
The term 'computational mathetics' was first used as a private joke to ward off gullible colleagues who tended to mock anything to do with AI and education and especially both. The term also comes in useful to avoid those conversations that tend to occur in public houses whenever AI or education is mentioned. At first, the term sounds impressively pretentious. With use, however, it seems perfectly natural and what it connotes entirely worthwhile and sensible.
3.5 The approach of computational mathetics
To justify a neologism such as 'computational mathetics' it seems necessary to indicate what might be added to what we already have. Let us therefore consider the current style of theorising in AI-ED research and development. Here are four illustrative sets of principles which their authors propose for AI-ED system design (the first two are repeated from chapter 2):
Anderson, Boyle, Farrell and Reiser (1989):
• Represent the student as a production system.
• Communicate the goal structure underlying the problem-solving.
• Provide instruction in the problem-solving context.
• Promote an abstract understanding of the problem-solving knowledge.
• Minimize working memory load.
• Provide immediate feedback on errors.
• Adjust the grain size of instruction with learning.
• Facilitate successive approximations to the target skill.
Clancey (1993):
• Participate with users in multidisciplinary design teams.
• Adopt a global view of the context in which a computer system will be used.
• Be committed to providing cost-effective solutions to real problems.
• Aim to facilitate conversations between people.
• Realise that transparency and ease of use is a relation between an artifact and a community of practice.
• Relate schema models and AI-ED systems to the everyday practice by which they are given meaning and modified.
• View the group as a psychological unit.
Leinhardt and Ohlsson (1990):
• Begin instruction by activating relevant previous knowledge.
• Mark the beginning of a new lesson segment.
• Tell the student the nature of the lesson segment.
• Label knowledge items.
• Mark reference-preserving shifts of expression.
Reusser (1993):
• Design and use computer-based tools pedagogically, that is, as cognitive instructional tools for mindful teachers and learners in a culture of problem-solving.
• Extend and empower the minds of intentional learners.
• Provide learners with some guidance according to the "principle of minimal help."
• Have students construct and externalize their mental models.
• Provide students with intelligible and effective representational tools of thought and of communication.
• Promote the use of comprehension-related strategies.
• Encourage reflective and self-directed learning.
• Extend the use of computer-based instructional tools into a supportive classroom culture of collaborative learning.
These principles are a different kind of theoretical entity to those encountered in aeronautics or computational linguistics books. But regardless of that, we may ask: Where do they come from? In what ways were they derived? How do they relate to one another? Are they sound? Are they useful?
The Anderson principles are supposed to be corollaries of ACT*, a psychological theory of cognition. The principles are derived from the theory by a process of discussion (in English). It is not possible to prove, in a mathematical sense, that the principles do follow from the theory, that they are all the principles that follow, that they are the most important principles, or that contrary principles cannot be derived. The Clancey and Reusser principles follow from an even more tenuous argument from what is more a philosophy than a theory about learning. The Leinhardt and Ohlsson principles were specified after empirical observations of classroom teachers.
Taken together, they provide 28 principles for AI-ED system design. Or are some of the principles the same or even contradictory? Is "Encourage reflective and self-directed learning" the same as "Provide immediate feedback on errors" or do they contradict one another - if the latter, how, precisely? A scientific field cannot advance through the ad-hoc accumulation of unrelated principles. It seems encumbent on anyone proposing a new principle to say clearly how that principle supplements or overrides previously-held principles.
The soundness of the principles is hard to determine. For one thing, the principles are stated as recommendations not as propositions, that is, a principle such as "Encourage reflective and self-directed learning" is not of a form which can be said to be true or false. We must presumably read the principles as "If you <recommendation> then <result, for example, students will learn more>". Therefore, one way of evaluating the soundness of a principle is to implement a system according to the recommendation and see if the promised result ensues. According to Ohlsson (1991), Anderson, Conrad and Corbett (1989) "empirically validates" the Anderson principles, although Anderson, Boyle, Corbett and Lewis (1990) comment that "we do not really know what features of our tutors produced these positive outcomes nor do we know how optimal our tutors are". (As far as I am aware, no similar empirical validation has been claimed for any of the other principles.).
This kind of validation is problematic for several reasons:
• The 'result' is never explicitly stated, as we see. A scientific theory should make precise predictions: we need to know which students will learn what, how, and when.
• The 'recommendation' is not stated sufficiently clearly that a system implementation follows directly from it. Consider "Encourage reflective and self-directed learning". The early papers on cognitive apprenticeship referred to AlgebraLand as an exemplar system designed to promote reflection. However, the limited empirical studies that were carried out indicated that the desired reflection hardly ever occurred (Foss, 1987), as discussed further in chapter 6.
• It is not possible to implement a system to accord with only a single recommendation - inevitably, a whole set of other recommendations has to be adopted as well. Therefore, even if the promised result materialises it cannot be reliably attributed to a particular recommendation.
• There are ethical difficulties in carrying out experiments with students in realistic situations (not mitigated by the fortunate fact that most such experiments yield a 'no significant difference' outcome).
• It may be inefficient and costly to implement a complete AI-ED system to investigate a single principle.
Surely, nothing could be as unarguable as a successful empirical evaluation. Bhuiyan (1992) reports that users of his system (PETAL) scored 60% correct, compared to 0% for the control group (maybe we could say that they performed infinitely better). His project is exemplary in following the standard AI-ED research paradigm: carry out empirical studies of real learners; develop a theory to explain what causes good and bad learning; develop a system to promote good learning; carry out a comparative study to show that students do indeed learn better using the system, and hence validate the theory. Perhaps the results can be explained, almost regardless of the theory developed. Imagine that (1) a learning task is of the 'ah I see' variety, where performance improves in a quantum step from 0% to 100%; (2) a system with a specially designed interface enables students to 'see' the concept in time t1, which is less than the time t2 it takes under normal conditions; (3) the post test is carried out at a time t, between t1 and t2. Then the system users will score 100% and the non-users 0%. Maybe the PETAL experiment meets these conditions (in my experience, the concept of recursion, the domain of PETAL, comes close to meeting the first condition). It is important to reduce learning time if possible but it is not clear that any deep cognitive theory is validated by the experimental results. Of course, Bhuiyan did not set out to design a misleading experiment, but it is possible to see how impressive empirical results might be contrived, if that were the only criterion (which does not say much for the research methodology).
The AI-ED field is necessarily multi-disciplinary, involving aspects of computer science, education, psychology, and, to a lesser extent, other fields. It is not my purpose to imply that some disciplines are misguided in their methodologies or somehow incompetent in not providing what is needed. Nor is it the aim to argue that AI-ED should become 'computational mathetics', for want of a term. According to Ohlsson (1991),
"The educational literature contains few if any ideas about learning. The coarse level of analysis employed in most other writings on education only suffices for the formulation of principles which are so vague as to be useless."
As a result, he argues that AI-ED should simply become a part of cognitive psychology. Instead, I see AI-ED as a field where what I have called psychomathetics, sociomathetics, and so on must all continue to contribute but where the area of computational mathetics has been relatively neglected and may soon be able to play a stronger role. Established disciplines have relatively agreed-upon methodologies which differ from one another as well as from that of computational mathetics.
Computational mathetics would not just aim to make the vague theories and principles of other disciplines more precise, rigorous, formal and computationally useful. Its primary aim is to serve AI-ED system design, not to formalise general theories for other disciplines. For example, Lepper, Woolverton, Mumme and Gurtner (1993) found that human tutors tended to make indirect responses to student errors (such as "So, you think it's 126?") but it could well be that such responses would be inappropriate for AI-ED systems and therefore of little significance in computational mathetics. Computational mathetics should contribute its own techniques, concepts and methodologies to the field of AI-ED.
It would be idealistic but nonetheless desirable for computational mathetics to aim to be neutral with respect to the controversies of its associated fields such as psychomathetics and educational mathetics. In analogy with computational linguistics, computational mathetics would aim to make no claims about the way the human mind learns (or at least make it clear where it is making such claims). Maybe an appropriately defined formal language in computational mathetics could be used to express any relevant theory of psychomathetics or any other -mathetics. Computational mathetics would also take no position with respect to broad educational issues such as: What is the purpose of education? How can educational innovation be promoted? Again, the aim is not to imply that such questions are unimportant, but that they may be usefully separated from more technical, computational questions.
3.6 The language of computational mathetics
It is time to begin making choices in order to be more specific about the nature of computational mathetics. The basic notation which we will use is that of agent-oriented programming (Shoham, 1993). Rather than begin with a formal definition of its syntax and semantics, we will first give a few simple illustrative expressions in the notation in order to provide an intuitive feel for it and then refine the notation in later chapters.
The expression
Believes(John,Composer(Fidelio,Beethoven))
might be intended to indicate that John has been ascribed the belief that the composer of Fidelio was Beethoven. That is what it might indicate to us but, of course, it will hardly indicate this to a computer program which may not have a mapping between, say, the symbol Composer and the concept of 'composer' and even if it did it would not have such a rich appreciation of what the concept means. The general form of expression of which this is an instance is:
Modality(agent,proposition)
where the three parts need some preliminary explanation.
An agent is "an entity whose state is viewed as consisting of mental components such as beliefs, capabilities, choices, and commitments" (Shoham, 1993). Agenthood is in the eye or mind of an observer who views an entity. The observer finds it useful to ascribe beliefs, etc. to the entity. Such an ascription enables the observer to reason about the entity, for example, to make predictions about how the entity will behave. Ascribing a belief (etc.) to an entity is not making any claim about what that entity physically possesses, in some sense. Making such ascriptions is a common explicatory device. For example, a recent documentary on the nature of lightning commented that "the lightning does not know the ground is there at all". Clearly, there is no implication that an entity such as lightning is physically capable of possessing anything which we could reasonably call knowledge.
For our purposes, the two main classes of entity are students and programs. Just as we can ascribe beliefs to students, so we can ascribe them to programs:
Believes(program,Composer(Fidelio,Mozart))
It might seem odd to ascribe beliefs to a designed entity such as a program: we imagine that we could just inspect the design and see directly what it believes, i.e. what the designer has designed it to believe. However, programs are complex and the contents of its 'mental components' change while the program is running. We will find it useful to make ascriptions such as:
Believes(program,Believes(John,Composer(Fidelio,Beethoven)))
The term 'agent' has become widely used in computer science and AI, without a universally accepted definition. Shoham's definition above allows the term to refer to entities which are human or software, and that is the sense we have used previously, as an abstraction of the classes of intelligent entity which includes both humans and programs. According to Wooldridge and Jennings (1994a), in computer science, the term 'agent' is generally restricted to computer systems which possess the properties of:
• autonomy - being able to operate without the direct intervention of humans or others,
• social ability - being able to interact with other agents,
• reactivity - being able to perceive and respond to their environment, and
• pro-activeness - being able to exhibit goal-directed behaviour by taking the initiative.
We can accept this definition, as the properties are all ones which we would wish both programs and students to possess. In AI, the term 'agent' generally means (as Shoham's definition indicates) that an entity is conceptualised in 'human-oriented' mentalistic notions such as belief, knowledge, obligation, desire, and so on. From an AI perspective, the consideration of such notions seems necessary to provide the properties listed above, although this is debatable. As far as AI-ED is concerned, the term 'agent' is convenient as it does not pre-empt discussion of the possible roles and status of the participants (humans and programs) involved.
A proposition is, for the moment, simply a statement to which one may sensibly respond 'true' or 'false'. We may not know which response we should give, but we know that one or the other is appropriate. "I am not married" is a proposition, but "Will you marry me?" is not. We will use predicate logic with modal operators to express propositions (chapter 4).
The modality denotes the kind of 'mental component' which is ascribed to the agent with respect to the proposition. Typical modalities are Believes, Knows, Accepts, Is-aware-of, Wants, Intends, and Is-committed-to. For example, the expression
Wants(program,Believes(John,Composer(Fidelio,Mozart)))
might denote that we have ascribed to the program the 'want' or goal that John believes that the composer of Fidelio was Mozart. As we can anticipate, the precise interpretation of such modalities will be difficult.
We will also need performatives, that is, operators which specify some kind of communication between agents or some kind of updating of what has been ascribed to agents. For example,
Tell(program,John,Composer(Fidelio,Mozart))
might initiate some statement from the program to John, with some consequent change of beliefs ascribed to him. This will be discussed further in section 4.4 and afterwards.
The agent-oriented notation seems a possible basis for developing computational mathetics as it promises precision yet breadth. The idea of an agent as an autonomous, rational entity enables us to view both programs and students as communicating individuals, each with their own goals, with some degree of independence, and with some ability to reason for themselves and about others. Moreover, it may be possible to capitalise on the work done on multi-agent systems and related fields in artificial intelligence. Although the simple examples above illustrate a 'knowledge transmission' view of AI-ED, there is nothing in agent-oriented programming which prohibits other views, and we will seek to extend the notation to encompass those views in due course.
At this stage, we have only an informally-illustrated notation. We have no semantics to go with it. However, there is no need to expect or insist that we later define a complete formal semantics. This would be futile, for the 'real meaning' of any notation cannot be fully captured in culture-free symbolic representations, however complex. However, we can hope for sufficient agreement on our interpretations and for sufficient content in our representations that our analyses might be informative and useful.
By opting for an agent-oriented notation, we imply that the appropriate level for theorising about AI-ED systems is at what Newell (1982) called the 'knowledge level' rather than at the 'symbol level' or 'program level' or some level concerned with physical, mental structures. The knowledge level is where we ascribe knowledge, goals and actions to an agent. The knowledge level is said to lie "immediately above" the 'symbol level', where representations are specified. However, it is not possible to say anything very precise about the knowledge level without adopting some symbolic notation to say it. The only real distinction between the knowledge level and the symbol level lies in the kinds of symbols used. For our purposes, the point of operating at the knowledge level is to suggest that we are concerned with knowledge level entities which are symbol-independent, although we must use some symbols to say anything about them. Therefore, we have no particular commitment to the symbols actually used.
3.7 The aims of computational mathetics
The main aim of computational mathetics is to enable theories of learning, instruction and anything else of relevance to be expressed in a formal language so that designs for AI-ED systems to meet specified objectives can be derived analytically. This aim is unattainable now and possibly unattainable in principle. However, we can consider how aspects of the main aim might be achieved.
In any endeavour, the role of 'formality' passes through up to six stages:
1. To begin with, practitioners deny that it is necessary, possible or appropriate to try to express their activities in any kind of artificial, precisely-defined language. The content of their activities is just too complex to be adequately described at all without the full subtlety of natural language.
2. Eventually, perhaps, some recurring patterns in their activities will be recognised and in the interests of brevity some symbol will begin to be used to denote that pattern. In this second stage, there will be much confusion and argument over which patterns to symbolise and what the symbols 'mean'.
3. In due course, some consensus may emerge and all practitioners will become obliged to use the agreed-upon symbols. So, for example, in chemistry HCl denotes hydrochloric acid and in music k denotes a crochet. During this stage, the symbols are just abbreviations for concepts which could be written out in full, and in fact to begin with any use of the symbols will be accompanied by a translation into the full version, for example, to explain that
Believes(John,Composer(Fidelio,Beethoven))
means that "John has been ascribed the belief that the composer of Fidelio was Beethoven".
4. In the fourth stage, the notation itself becomes a vehicle to work with, regardless of the translated 'meaning' of the expressions in the notation. So, for example, a chemist will begin to carry out symbolic manipulations directly on chemical equations
2HCl + Na2CO3 = 2NaCl +
H20 + CO2
without pausing to consider the real meaning of the symbolic operations. For the result of a series of operations to be meaningful, each individual operation, in general, must be meaningful. When the abstract symbols are particularly powerful (for example, the ring notation for certain aromatic compounds) they seem to inspire the appropriate operations. It is only in the fourth stage that any real benefit begins to come from formalisation.
5. In the fifth stage, it is realised that the operations themselves can be formalised, that is, we can agree on a notation for the operations. In this case, we can, if we wish, represent the operations within a programming language and have a computer program carry out the manipulations.
6. As the operation of a computer program may be rather opaque and hence its output considered untrustworthy, we might identify a sixth stage (although it is not fundamentally different from the fifth) in which the content of the operations and the operations themselves are so precisely defined that they could in principle and maybe in practice be written down so that we could formally derive outcomes and engage in meta-theoretic activities such as proving that certain outcomes can or cannot be derived, or how efficiently outcomes can be derived.
Not all endeavours can or should pass through all stages. For example, most parts of chemistry have not passed beyond the fourth stage - that is, (as far as I know) in most cases the operations have not been defined so that programs or ourselves can carry out rigorous derivations of results.
Where among the stages does AI-ED lie? For some AI-ED researchers, it is resolutely at the first stage. The few who have attempted any kind of formalisation have not been able to progress beyond the second stage, because there is no agreement on whether, what and how to formalise. The terminology, even without precise definitions, is barely established. There are some efforts, as we will describe, which might be considered to be at the fifth stage, as they involve the use of computer simulations to make predictions, but they by-pass the stages of saying precisely how the simulations work.
At the moment, AI-ED systems are created by repeated iterations through a loop in which informal theories lead to experimental systems which are empirically evaluated (top of Figure 3.1). With the present state of AI-ED theory, the need for empirical evaluations seems inescapable. The potential problems of evaluation-based research were discussed in section 3.5.
AI-ED research should aim to eliminate (or at least greatly reduce) the need for empirical evaluations, not embrace them within the design process. With aircraft, the maiden flight is a demonstration, not an evaluation. All the essential properties have been theoretically determined, reducing the role of empiricism to fine-tuning the theory. Moreover, the empirical tests are carried out not in the real world but in environments specially designed to test aspects of the theory. Of course, we are a long way from an AI-ED theory from which designs may be formally derived (bottom of Figure 3.1).. However, there is an intermediate strategy (middle of Figure 3.1) which may enable us to move in this direction. Instead of deriving the design of a complete AI-ED system by some mathematical analysis, we may able to carry out such an analysis on components of a system and/or derive theoretical outcomes by computer simulation, rather than by analysis.
Figure 3.1. The progression from informal empiricism to formal demonstration
It should hardly be necessary to point out the potential benefits of formalisation to any scientific endeavour (which I assume AI-ED system design to be) but because it has been neglected heretofore a brief list may be worthwhile:
• The use of a formal language may help clarify otherwise vague principles.
• The use of an agreed formal language can make it easier for researchers to understand and build upon the work of others.
• An analytical study of a component of AI-ED systems can lead to precise statements about the power and shortcomings of that component and enable comparative studies of various proposed implementations of that component. Thus, formal tools may help us manage the complexity of AI-ED systems.
• An analysis of proposed systems may eliminate or reduce the need for costly experimental implementations.
• Knowing the theoretical properties of proposed systems, such as their likely run-time inefficiences, makes it easier to determine where practical compromises should be made.
• An appropriate formal language can serve as a high-level specification language and can be directly implemented in logic-based programming languages, enabling the efficient study of prototypes.
• It is possible that AI-ED may be able to capitalise upon the large body of formal work already carried out in AI.
Genesereth and Nilsson (1987) comment that "successful preparation in mature fields of science and engineering always includes a solid grounding in the mathematical apparatus of that field". Two sceptical responses to this are possible. First, AI-ED (and perhaps AI in general) is not a 'mature field' . Therefore, there is no 'mathematical apparatus' and it would be premature to try to establish one, or perhaps even misguided for in a new field what can be formalised first are inevitably the simplest, possibly least important, and maybe irrelevant aspects of the field. Secondly, AI-ED (and perhaps AI in general) is not a field of science or engineering at all. Within AI there has always been a vigorous debate between the 'neats' (the 'formalists') and the 'scruffies' (the 'experimentalists'). As always seems to be the case, these are not mutually exclusive options: the important question is how we combine the virtues of both approaches. AI-ED, because of its dependence on contributions from education, psychology and other disciplines, might be claimed to be more of a social science than a natural science or engineering. Some social scientists will argue that the ontological differences between humanity and the rest of nature (for example, that human beings are 'free agents' who create their own world) are such that the social world is not amenable to the kind of allegedly objective and reductive analysis characteristic of natural science explanations. As far as AI-ED is concerned, we can say that many perspectives are necessary and welcome: my own view is that it is time that the perspective of computational mathetics was applied. Debates about the scope of computational mathetics will not, by definition, be resolved by general discussion but by a determined effort to widen its boundaries.
Before embarking on this, some expectations may need to be lowered. The version of computational mathetics which follows does not achieve anything near the aims laid out above. In fact, in most cases it is not possible to do much more than indicate those areas of formal AI which promise to be useful for computational mathetics. Many of these areas are research fields in their own right and it would take a large-scale, coordinated programme to investigate in depth their applicability to AI-ED. But we must be realistic - computational linguistics has made progress despite the fact that its theoretical concepts are not complete, correct, or cognitively valid, and so may computational mathetics.
4. Representing knowledge
As the main aim of designers of AI-ED systems is that students come to know something (not necessarily something which the designers have completely specified beforehand) and the core activity of AI has been knowledge representation, we will begin the development of computational mathetics by looking at knowledge representation techniques from an AI-ED perspective. Any standard AI textbook (such as Rich and Knight, 1991; Winston, 1992; Ginsburg, 1993) provides a more general and complete coverage of knowledge representation. In this chapter the aim is to consider the foundations of knowledge representation in so far as they specifically affect AI-ED. We will consider whether the established techniques of AI can be extended to encompass different views of the nature of knowledge. In this chapter we are mainly concerned with developing notations which can be used to represent knowledge, belief, and so on in computational mathetics; the following chapters consider how knowledge can be used and acquired.
4.1 Behaviour, belief and knowledge
Imagine that you are driving in the dark and a car approaching you flashes its lights. In order to react appropriately to this communicative act, you ascribe beliefs and goals to the oncoming driver: he has recognised you and is saying 'hi'; or he is warning you of some hazard (an accident ahead, or a police speed trap, or that your own lights are off); or he is, on the contrary, encouraging you to go ahead (for example, to turn ahead of him) where normally you would not; or he actually intended to signal to turn but hit the wrong switch; and so on. Depending on the situation, some of these ascriptions are more plausible than others. At all events, you may (or may not) adapt your own behaviour. And all this happens literally in a flash - you do not pull over to contemplate at length the semiotics of car light flashing.
This is as simple a communicative act as there can be but it illustrates the essential characteristics of AI-ED system communications. Both (or all) participants are or should be continually ascribing mental components to one another and adapting their own behaviour as a result. Usually these ascriptions are not entirely reliable because of the shortage of information and time to consider it. Nonetheless, even though unreliable, the ascriptions can make a crucial difference to subsequent behaviour.
We need now to consider the relation between behaviour, belief and knowledge. This is philosophical quicksand but the designers of AI-ED systems have no choice but to build upon it.
Imagine now that every night at 10 o'clock I pick up my walking stick and my dog bounds up wagging its tail. We might well say that the dog believes we are going for a walk. Does the dog believe that we always go for a walk at 10 o'clock? If a dog does not understand the concept of '10 o'clock' can it be said to believe something about it? Does it really understand the concept of 'going for a walk' either? My dog not being keen on philosophical discussion, we cannot resolve this. So imagine instead that I tell Mary that "praseodymium is ductile" and she says 'yes'. Can we ascribe:
Believes(Mary,Ductile(praseodymium))
Maybe not, for she may not understand the meaning of 'ductile' or 'praseodymium '. Perhaps all we can say is that:
Believes(Mary,"praseodymium is ductile" is true)
assuming that she trusts me to say what is true, or perhaps that she believes that I say what I believe to be true (although I may be mistaken):
Believes(Mary,Believes(me,meaning("praseodymium is ductile")))
With Mary, we could try to unravel this, but the point is that it can be tricky in even the simplest cases to write appropriate ascriptions of the form Believes(a,p). In general, the p should be in the language of the person ascribed to, a, not that of the abscriber.
The notation Believes(a,p) means that the belief p has been ascribed to the agent a by some observer, not that a believes p (although we will often use the latter phrase as a convenient abbreviation). This ascription is the result of a belief of the observer, and if the observer is a second agent b communicating with a then we might need to specify: Believes(b,Believes(a,p)). This too is an ascription of some observer. If this observer is the agent a then we could specify this too: Believes(a,Believes(b,Believes(a,p))). This nesting of beliefs stops when we postulate that an ascription is made by some agent who is not a participant in the interaction and to whom beliefs do not need to be ascribed.
As we have taken 'belief' as the basic epistemic concept we cannot define it in terms of other concepts. All we can say, rather circuitously, is that if an agent has a belief p then it is disposed to behave as if p were true and that if an agent behaves in a certain way an observer is disposed to ascribe the belief p to it. The use of the word 'disposed' emphasises that there is no guaranteed mapping between belief and behaviour.
There are three senses of the word 'belief' in English which we do not mean to inherit. One is its use to imply that the ascriber of a belief p to an agent a actually believes that p is false. For example, "John believes the moon is a star" might be taken to imply that the speaker believes that the moon is not a star. Secondly, 'belief' is sometimes used in contexts precisely because the belief is one for which the agent has or can have no evidence, for example, "John believes he is the reincarnation of Mohammed". Thirdly, in English, we can say someone believes in abstract concepts ("John believes in Marxism") rather than a specific proposition. It is matter of considerable debate whether the former can be reduced to a set of the latter. By Believes(a,p) we just mean that, in our context, it helps in understanding and predicting behaviour to ascribe the belief p (a proposition) to the agent a.
The conventional definition of 'knowledge' is that it is 'justified, true belief'. This is disputed philosophically but it will serve our purposes. Obviously, we need to consider what counts as 'true' and 'justified'. Conventionally, again, a proposition is 'true' if it 'corresponds to the facts', but again we can worry about what is meant by 'the facts' and 'corresponds'. It seems clear that we would not want to specify:
Knows(John,Composer(Fidelio,Beethoven))
if we, as observer, knew as an incontrovertible fact that Beethoven did not compose Fidelio. The ascription:
Knows(Mary,Ductile(praseodymium))
seems less clearcut, as we need a precise definition of the predicate Ductile. For most interesting propositions, such as Honest(Churchill), the 'facts' are difficult to determine.
In the case of AI-ED systems, one of the agents concerned (the program) has two kinds of belief: those which it is has been explicitly given by its designer and those which it has determined 'for itself' while running, for example, beliefs about the student using it. As the system has no independent means of determining whether the former set of beliefs corresponds to the facts, we often speak loosely of the system 'knowing' those propositions. The system can have no justification for holding those beliefs, other than the fact that the designer has specified them. However, for the latter set of beliefs, and all the student's beliefs, we can require that an acceptable justification be given before we agree that a true belief is in fact knowledge. For example, a student may say that she believes that all metals are ductile and all her behaviour might accord with this belief but unless she can give some convincing justification for believing it (for example, that she has noticed that many metals are ductile, or she has a theory about the way the electron structure of metals causes them to be ductile) we might be reluctant to say that she knows that all metals are ductile.
This is a complicated issue because it means that for a proposition to make the transition from belief to knowledge an agent needs to keep or create convincing justifications for that belief. Human agents tend not to retain the original justifications (if any) for their beliefs - they tend to (re)construct them when needed. Maybe it matters only that the constructed justifications be convincing, whatever that may mean. At least, it seems that the transition to knowledge requires some degree of articulateness about that knowledge.
It might seem that if a student behaved exactly as if she held a particular true belief p then, to all intents and purposes, she may be said to know p. However, when some students were asked to use a simple simulation to predict the resultant speeds of two colliding inelastic balls of variable speed and mass, those students who were able to make predictions entirely in accord with the principle of conservation of momentum were unable to verbalise anything corresponding to that principle. In such a circumstance, it seems unreasonable to say that the students know that principle.
In the case of computer agents which have been designed to 'know' p with the intention that a student user should also come to know p there is clearly a problem, for if the computer agent cannot articulate any justification for p then the student may be unable to construct one. Even if a justification can be articulated then it must be expressed, as discussed above, in terms meaningful to the student. For example, in general, it is not sufficient that a program be able to apply the principle of conservation of momentum - it needs to be able to give some justification or explanation of it in terms of concepts believed or understood by the student. This is the basis for the black box - white box distinction which separates performance-oriented AI systems from AI-ED systems (Brown, Burton and de Kleer, 1982).
Newell (1982) defined knowledge to be "whatever can be ascribed to an agent, such that its behaviour can be computed according to the principle of rationality" where the principle of rationality says (circularly) that an agent will carry out a certain action if it has knowledge that one of its goals can be achieved by that action. This functional definition is less suitable for human agents than it is for computer agents, where the concepts of 'rationality' and 'computed' can be given precise operational definitions. For students, unfortunately, the relation between knowledge and behaviour is not so straightforward, not least because the notion of rationality is complicated (as discussed in the next chapter).
In the AI and AI-ED community discussions about the nature of knowledge are often merged with those about the behaviour resulting from the knowledge and the processes by which the knowledge is acquired - which we discuss in separate chapters because for students, at least, there is no necessary connection between the three. At this stage, we have not violated any principles of objectivism, constructivism, situationism, or any other -ism. For example, we can agree that "knowledge is not a thing or set of descriptions .. [but] a capacity to coordinate and sequence behaviour" (Clancey, 1995). Our ps and Believes(a,p)s are clearly not knowledge. We do not even need to claim that they are representations of knowledge. All we need to say is that they are representations which agents might find useful in deciding how to behave. The claim that the action made possible by knowledge is situated in the sense that it is constrained by an agent's understanding of its place in a social process challenges the claimants to try to specify precisely how this understanding constrains action.
The constructivist view that knowledge "cannot simply be received by students but must be constructed anew by them" (Self, 1990), i.e. dynamically as they behave, need not be interpreted as a radically different philosophy of knowledge. It is a view of knowledge acquisition rather than of knowledge itself, unless it is interpreted as a view that no knowledge exists other than at the instant it is (re)constructed. There is no way of showing one way or the other whether knowledge exists in some sense before some event causes it to be constructed, because any 'knowledge-detecting activity' is an event which may cause the very knowledge one is trying to detect to be constructed. However, there seem to be some knowledge-acquiring events which strain the idea of 'construction' as a complex, active process in which an agent assembles and synthesises something significant on the basis of the social context and, maybe, prior knowledge. If I look out the window and see that it is raining then for all except pedantic purposes I know that it is raining, without much constructive processing. If I ask someone looking out of the window then they may 'transmit' to me the knowledge that it is raining. If a student asks me the atomic number of carbon then, in some circumstances, I may reasonably be said to transmit to her the knowledge that it is 6 without any significant knowledge construction on her part. This is not to say that all, or even much, knowledge can be transmitted in this way.
The constructivist view that there is no knowledge of the world independent of what is constructed by us is a separate philosophical claim. Again, it is one which can never be disproved as it is always us doing the constructing. The idea that all knowledge is hypothetical and incomplete, although perhaps literally true, does not seem very helpful. I can assert that I know all there is (which isn't much) to know about when buses are supposed to leave my village Brookhouse for Lancaster and I can base my actions on this knowledge. I will miss the bus if I worry overmuch about whether this knowledge is correct or complete. Similarly, in most contexts where the knowledge will be used, it seems possible to say that one has correct and complete knowledge of, say, the atomic numbers of the chemical elements or of the present participle of the French word 'devoir'. Perhaps the constructivist view is not that knowledge itself is (always) hypothetical but that the processes by which it is acquired are hypothetical, i.e. depend on the development of hypotheses, but that is a different claim.
4.2 Propositions and logic
The object of a belief or other mental construct is a proposition which is represented in some language-independent, mind-independent, abstract, symbolic notation, or logic. The term 'logic' is not meant to suggest that what is represented is infallibly correct but that the notation and the operations which can be carried out on it are precisely defined. Most of our notations will be variations and extensions of predicate logic, the lingua franca of AI, which we therefore give a brief summary of.
A sentence in predicate logic, such as Composer(Fidelio,Mozart), is composed of different kinds of symbol: constants, variables, operators, and punctuation symbols such as commas and parentheses.
A constant may be of three kinds:
• an object constant, such as Fidelio and Mozart, which is used to name a specific element in the universe of discourse;
• a relation constant, such as Composer, which is used to name a predicate on the universe of discourse, i.e. a relation which maps a specified number of elements onto true or false;
• a function constant, which is used to name a function on members of the universe of discourse, such as father in the sentence Carpenter(father(Jesus)).
A variable is used to express properties of objects without naming the objects. There are two kinds of variable, those which are universally quantified and those which are existentially quantified. The former is illustrated by the sentence "x Red(x), which might be intended to mean that every object in the universe of discourse is red. The latter is illustrated by the sentence $x Red(x), which might be intended to mean that there is at least one object in the universe of discourse which is red.
An operator allows us to form more complex sentences from simpler ones. For example, in
Composer(Fidelio,Mozart) & Austrian(Mozart)
which might be intended to mean that the Composer of Fidelio was Mozart and that Mozart was Austrian, & is an operator. The standard operators of predicate logic, that is, & (and), v (or), -> (implies), ´ (is equivalent to), and ~ (not), are defined by specifying how the truth value of the complex sentence depends on the truth values of its components. If we use f and y to denote two sentences in predicate logic then
f & y is true if and only if f and y are both true;
f v y is true if and only if at least one of f and y is true;
f -> y is true unless f is true and y is false;
f ´ y is true if and only if f -> y and y -> f, i.e. f and y are both true or both false;
~f is true if and only if f is false.
We can use operators in sentences involving quantifiers, for example,
"x Toadstool(x)-> Poisonous(x)
which might be intended to mean that 'if x is a toadstool then x is poisonous' or 'all toadstools are poisonous'.
A mathematical or formal logic text would now give a precise syntax defining how all these symbols may be combined to form acceptable sentences in predicate logic. We will rely on intuition in this respect, and only comment on a few points where intuition may fail us.
What we consider to be the objects, relations and functions in our universe of discourse is up to us and not part of the syntax of the logic. An object constant does not have to be a simple, tangible, individual thing. For example, in Atomic-number(carbon,6) the constant carbon does not refer to an individual object but to a concept or class of objects. As we write sentences in predicate logic using even more unusual kinds of object and (in due course) make inferences from them, we need to be careful that undesired or even contradictory conclusions are not reached.
We should note that variables in predicate logic stand for anonymous objects but not anonymous relations or functions. So, for example, we cannot write "x x(Fred), which might be intended to mean that all the 1-argument relations in the universe of discourse apply to Fred. Also, relations can only be applied to terms, i.e. objects, variables, or functions of terms. So, for example, one cannot apply a relation to another relation, as in
Virtuous(Honest)
which might be intended to mean that the property of being honest is virtuous, or to a sentence, as in
Simple(Composer(Fidelio,Mozart))
which might be intended to mean that the sentence Composer(Fidelio,Mozart) is simple. Some of these restrictions will not hold in some of the 'nonstandard logics' introduced later.
Some of the language sketched above is redundant. For example, as $x Red(x) is equivalent to ~"x ~Red(x), we can make do with only one quantifier (and unless otherwise indicated our variables will be universally quantified). Similarly,
"x Toadstool(x)-> Poisonous(x)
is equivalent to
"x ~Toadstool(x) v Poisonous(x)
Therefore it is usual to convert sentences into a standard form, such as conjunctive normal form, i.e. as a conjunction of disjunctions of (negations of) expressions of the form P(t1,t2, ..) before any computational operation is carried out. There is a standard algorithm for carrying out this conversion (Genesereth and Nilsson, 1987).
In order to determine the truth or otherwise of a sentence it is necessary to give an interpretation to the constants in the sentence, for example, to interpret Mozart as a reference to a particular person, Wolfgang Amadeus Mozart, who lived from 1756 to 1791. With this and the other obvious interpretations, Composer(Fidelio,Mozart) is false. In our examples so far, the intended interpretations have been obvious, but this will not always be the case. If a sentence is true regardless of the interpretation of the constants in it, then it is called a theorem. For example,
Composer(Fidelio,Mozart) v ~Composer(Fidelio,Mozart)
is a theorem. The sentence Composer(Fidelio,Beethoven) is true, with the obvious interpretation, but is not a theorem. Most of the putative theorems which we shall be interested in will be of the form:
f1 &
f2 & f3 & ... -> y
where f1, f2, f3, ... are premises (i.e. sentences assumed to be true) and y is a possible conclusion. In the next chapter, we will consider ways in which such sentences may be proved to be theorems (or not).
Because the premises will, in general, contain universally quantified variables, theorem-proving will involve a process of substitution which should be distinguished from that of interpretation. A substitution involves the replacement of a variable by a term. A substitution and interpretation which makes a sentence true is said to satisfy that sentence. A sentence is satisfiable if there is some substitution and interpretation that satisfies it; otherwise, it is unsatisfiable. If a sentence is satisfied by all substitutions and interpretations then it is said to be valid or a theorem. If a variable is universally quantified then we should be able to replace the variable by any term whatsoever and the sentence, if it is a theorem, will be true. Conversely, if we can find one substitution for which the sentence is false, then it is not a theorem. This would seem to imply the need for a systematic search of all possible substitutions, which promises problems, as there are, in general, an infinite number of terms (from the recursive definition allowing terms to be functions of terms). We will return to this in the next chapter.
The above has outlined the syntax of predicate logic. It is possible to give a formal definition of the semantics of predicate logic but we will use an informal sentential semantics, whereby what is true is just what is defined to be true as a premise or can be shown to be true by applying rules of inference (to be defined later).
At this point, it needs to be repeated that this brief review of predicate logic is not meant to imply that the goal of computational mathetics is simply to adopt the logicist ambition that all knowledge in AI be represented in a completely use-independent way in predicate logic. McDermott (1987), Birnbaum (1991b) and others have criticised logicism in AI. Computational mathetics should welcome whatever notations and languages turn out to be useful, but as predicate logic has been the starting point for almost all formal work in AI we can anticipate that it will be a basis for computational mathetics. As we will see, we will adopt notations which transcend standard predicate logic whenever convenient.
4.3 Modal representations
Predicate logic may be suitable for a single agent to reason with its knowledge (as in AI generally) but in AI-ED we need an agent to be able to reason about its and other agents' knowledge and other ascriptions.
The Believes(a,f) notation does not conform to predicate logic syntax because we have a sentence f within the scope of what looks like a relation constant. Believes is in fact not a relation constant but a modal operator, i..e. an operator that takes sentential arguments. In English, the following constructions all seem to require the use of modal operators: "It is possible that ...", "It is necessary that ...", "I am sure that ...", "I doubt that ...", "I know that ...", "I accept that ...", "I desire that ...", "I hope that ...", "I fear that ...", "I am happy that ...", and so on. The syntax of a modal logic, with a modal operator M, can be defined straightforwardly by saying that a sentence is:
• a predicate logic sentence.
• a sentence constructed from modal logic sentences using the logical operators &, v, ->, ~, and so on.
• "x f or $x f where f is a sentence.
• M(f), possibly with non-sentential arguments as well, where f is a sentence. Normally, we would indicate the agent as the first argument, as in M(a,f).
Henceforth, for brevity, we will use B for Believes, K for Knows, c for the computer system or program, s for an arbitrary student, and a for any agent (human or computer).
This simple syntax does, however, mask a number of difficult technical and philosophical issues which indicate that modal logics must have very different properties to those of ordinary predicate logic. As computational mathetics is concerned with the development of belief and knowledge it can hardly ignore such issues, although in the interests of practicality it may well be necessary to make compromises in defined ways. Among the issues are the following:
• Modal logics of belief and knowledge are referentially opaque, that is, two equivalent terms cannot be interchanged. In predicate logic, if it is known that two terms are equal then either may be replaced by the other in any context. For example, if we have the premises:
aspirin = acetylsalicyclic acid
Medicine(aspirin)
then it follows that
Medicine(acetylsalicyclic acid).
But in a modal logic, from
aspirin = acetylsalicyclic acid
B(s,Medicine(aspirin))
it does not follow that
B(s,Medicine(acetylsalicyclic acid)).
• In predicate logic the truth value of a complex sentence depends only on the truth values of its component sentences. Therefore, we can replace any component sentence by one with the same truth value. Clearly, one cannot do this in a modal logic. For example, if we have two theorems t1 and t2 and B(a,t1) then we cannot infer B(a,t2).
• We need to be careful with the use of quantifiers in modal logics. The syntax allows us to write both
K(s,$x Composer(Fidelio,x))
and $x K(s,Composer(Fidelio,x)).
Do these two sentences capture useful differences? In English, the first means perhaps that the student s knows that someone composed Fidelio (but not necessarily who) and the second that there is someone (but we don't who it is) and the student knows of that person that he or she wrote Fidelio. Philosophers have discussed this as the 'de dicto' and 'de re' distinction. If this distinction is important to us we cannot move the quantifiers inside and outside the scope of modal operators at will.
• Similarly, modal operators do not necessarily commute with the logical operators. For example,
B(s,~Composer(Fidelio,Beethoven))
is clearly not the same as
~B(s,Composer(Fidelio,Beethoven)).
It is not so clear whether or not
B(s,Composer(Fidelio,Beethoven) v Composer(Fidelio,Mozart))
is equivalent to
B(s,Composer(Fidelio,Beethoven)) v B(s,Composer(Fidelio,Mozart))
• Modal logics are not necessarily consequentially closed. That is, if f1, f2, f3, ... -> y then it is not necessarily the case that M(y) follows from M(f1), M(f2), M(f3), .... For example, a student may not believe everything that follows from what she believes. A modal logic which is consequentially closed is said to be logically omniscient.
• In predicate logic a set of premises has to be consistent otherwise anything follows. In a modal logic of belief we can allow a set of beliefs to be inconsistent - as the logic may not be closed, this is not necessarily a problem. However, we might expect a set of beliefs to have some degree of coherence, for example, an agent maybe cannot believe a proposition and that it doesn't believe it:
~B(a,(p & ~B(a,p))
• The syntax allows sentences to be nested to any depth and an obvious extension would allow different modal operators and agents to be used, so allowing sentences such as
B(c,Accepts(s,K(c,B(s,f))))
i.e. the computer system c is ascribed the belief that the student accepts that the computer knows she believes f. We can be sceptical that we will be able to specify what kinds of inference we would like to make from such sentences and that we will need such sentences at all. But for any child who understands the Hansel and Gretel story, at the point when the trail is to be laid, we seem to need to make ascriptions equivalent to:
B(child,Intends(mother,abandon))
B(child,Intends(Hansel,trail))
B(child,B(Hansel,Intends(mother,abandon)))
B(child,B(mother,B(Hansel,Intends(mother,walk))))
B(child,B(Hansel,B(mother,B(Hansel,Intends(mother,walk)))))
• We can try to use modal representations to clarify what is meant by some difficult constructions in English. For example, "John knows whether Mozart composed Fidelio" is perhaps
K(John,Composer(Fidelio,Mozart)) v K(John,~Composer(Fidelio,Mozart))
Maybe "John knows who composed Fidelio" is
$x K(John,x=composer(Fidelio))
We will consider the sentences "John knows about Fidelio" and "John knows how to compose Fidelio" later.
A satisfactory treatment of modal logics requires the use of advanced theoretical apparatus. Sufficient progress has been made (Halpern and Moses, 1992) that it is possible to imagine their use as the theoretical basis for AI-ED system design, as AI-ED systems are essentially concerned with the development of a student's beliefs and knowledge. Practically, efficient reasoning in modal logics remains a problem because there are no standard theorem-provers as there are for predicate logic (one approach, in fact, is to convert modal logic sentences into ordinary predicate logic). These kinds of theoretical and practical limitations help to clarify what can be realistically attempted with AI-ED systems.
The semantics of modal logics is usually defined in terms of possible worlds (Hintikka, 1962). The intuitive idea is that besides the true state of affairs there are a number of other possible states of affairs, or possible worlds. The worlds are connected by an accessibility relation R which may be defined to satisfy various constraints. For example, it may be transitive, i.e. uRv and vRw implies uRw, where u, v and w are worlds. In each world, a proposition is given a truth value. An agent in a world w is said to believe a proposition if it is true in all worlds accessible to w.
The modal logic based on a transitive accessibility relation (called 'weak S4') can be given a sound and complete proof theory comprising the following rules of inference and axioms:
R1 necessity p => Mp
R2 modus ponens p & p->q => q
A1 tautologies p, where p is a propositional tautology
A2 distribution Mp & M(p->q) -> Mq
A3 positive introspection Mp -> MMp
Other logics, perhaps less suitable for representing belief, have different accessibility relations and use one or more of the following axioms:
A4 knowledge Mp -> p
A5 negative introspection ~Mp -> M(~Mp)
A6 consistency Mp -> ~M~p
We may note in passing that modal logics of knowledge and belief (with and without axiom A4) omit any consideration of the need for justifications (as discussed above). The completeness and complexity of variations of these modal logics is discussed by Halpern and Moses (1992). As the semantics associated with different accessibility relations can be equivalently represented by a set of inference rules and axioms, we will use a sentential semantics (as above) rather than possible worlds (Konolige, 1988). We assume that an agent has a base set of beliefs and a (possibly incomplete) set of inference rules. An expression M(a,f) is true if and only if f is a member of the base set or can be derived from that set using the agent's inference rules.
Further consideration of this reasoning process will be deferred to the next chapter, except that we should comment that the nature of this process will be different for different kinds of agent. In the case of AI-ED, we have a program agent which might aim to reason as efficiently as possible on its own behalf, but when it is reasoning about a student's reasoning process, it is necessary to take account of psychological aspects. For example, any modal logic of belief which includes A1 and A2 (as does every modal logic using the possible worlds approach) suffers from the problem of logical omniscience, that is, the agent believes all implications of its beliefs. This is considered psychologically implausible. Therefore some kind of 'limited reasoning' might be defined (as discussed in chapter 5). Also we might need to consider short-term and long-term memory issues, which (roughly speaking) correspond to beliefs which are 'active' and 'inactive'. We might also consider how more global attributes of agents, such as that they are gullible, arrogant, narrow-minded, and so on, might be related to properties of their reasoning and other processes. (section 6.9).
4.4 Situation calculus
Our sentences in predicate logic and modal logic have so far been timeless, that is, we have not specified when sentences such as B(John,Composer(Fidelio,Beethoven)) are supposed to hold. This is inadequate for AI-ED systems, whose express purpose is to change beliefs and knowledge.
Suppose we wanted to represent a simple 'transmission' principle: "If a student does not know something and we tell her it then she will know it." The following attempt:
~K(s,f) & Tell(teacher,s,f) -> K(s,f)
is a logical nonsense. The operators in predicate logic do not have an implicit temporal semantics: & and -> do not mean 'and then' and 'causes'. The sentence is in fact equivalent to ~p & q -> p. Also, Tell is not naturally a relation constant but a performative (section 3.6).
One approach to tackling this is to use the idea of a situation, that is, an entity which is supposed to denote a snapshot of the universe and which can be regarded as a term in predicate logic. Then, to say that a student does not know a proposition in a particular situation, say s27, we may write:
~K(s,f,s27)
where we have introduced an extra argument to denote the situation in which the assertion holds. Now, to represent the above principle, we need to relate the situations before and after the telling act. This we may do by regarding the performative Tell as a function mapping a situation into a new situation. So,
tell(teacher,s,f,s27)
is the situation obtaining by applying the tell function when in situation s27. Then the transmission principle can be written:
~K(s,f,t) -> K(s,f,tell(teacher,s,f,t))
where t represents a situation variable. In this way, we may develop a language for expressing instructional principles, although, of course, any worthwhile principle will be much harder to express than the above. We will consider this further in chapter 10.
A variation on the above notation is to rewrite expressions of the form P(t1,t2,..,t) as Holds(p(t1,t2,..),t), which asserts that state p(t1,t2,..) holds in situation t. For example, the above rule becomes:
~Holds(knows(s,f),t) -> Holds(knows(s,f),tell(teacher,s,f,t))
In other words, the relation constant P is re-expressed as a function p, so that p(t1,t2,...) can be regarded as a predicate logic object. The process of converting relations into objects is known as reification. Although the notation is more wordy, it allows us to quantify over and apply functions to states. Also, it allows a more natural notation for modifiers of states, such as
thoroughly(knows(s,f))
than the use of an arbitrary number of extra arguments, as in
K(s,f,thoroughly,t).
The concept of a situation, which have glibly introduced as an object in predicate logic, is of considerable potential philosophical and practical importance. As is well known, the meaning of indexicals such as 'here' and 'you' is situation-dependent, and the same may be said of almost any concept or proposition. For example, a 'billion' is different in England and America:
Holds(billion=109,America) & Holds(billion=1012,England)
A student would need to know which context she is in in order to carry out arithmetic involving the concept of a billion. Not only do words mean different things in different contexts, but people have different abilities in different contexs:
Holds(can-subtract(Fred),darts) & ~Holds(can-subtract(Fred),classroom)
We often ask students to work within a specific context, i.e. to adopt a set of assumptions temporarily. For example, we might ask an economics student, who perhaps believes most in Keynesian principles, to nevertheless adopt a Marxist point of view for the purpose of some exercise.
While the concept of a situation or context is ubiquitous, for everything we say is said within a situation, and we can try to write expressions capturing our intuitions, it is very hard to specify a satisfactory semantics for situations (although, thankfully, we can achieve something without it). For example, it is not clear that an expression Holds(p,t) should even have a truth-value:
Holds(Lorentz-transformation=...,Newtonian-mechanics)
may rather be considered meaningless. One way to try to define a semantics for Holds(p,t) is to try to specify a set of rules of inference and axioms, as we indicated with weak S4 for modal logic. For example, we could wonder about:
Holds(holds(p,t1),t2) -> Holds(holds(p,t2),t1)
Holds(holds(p,t),t) -> Holds(p,t)
and so on, and, using the modal operators:
Holds(knows(a,p),t) -> K(a,Holds(p,t))
Meanwhile, computationalists are already using the basic ideas of situations and contexts for practical purposes. For example, we can specify that some subset of a knowledge base holds only in a specified situation and so work more efficiently on only a portion of the knowledge base. We can also specify relationships among situations so that, for example, properties may be inherited. For example, from
B(s,Holds(exist(black-holes),universe))
B(s,Subset(solar-system,universe))
B(s,Holds(p,t) & Subset(t1,t) -> Holds(p,t1))
we may infer
B(s,Holds(exist(black-holes),solar-system))
As the example indicates, we need to be careful in defining such relationships. As we will see, we can allow propositions associated with a situation to be inconsistent, and we can also associate rules of inference, even unsound ones, with a situation, giving great flexibility in representing how an agent reasons.
So, the technical concept of a 'situation' has been well-established in theoretical AI since the situation calculus was introduced by McCarthy and Hayes (1969). It has been refined and extended to provide a broad basis for reasoning about time and change. It is not clear that it is broad enough to encompass the notion of 'situation' in situationism. Here, a situation is "not a physical setting" but more to do with a 'community of practice' or a 'culture' (Clancey, 1995). One can hardly deny that culture is important, but what precisely does it mean? Brown, Collins and Duguid (1989) say that a culture is "a system of beliefs about some aspects of the world", which, on the surface, does not seem very different from what we have above. Saying that the situation calculus cannot in principle be extended to capture the rich notion of a culture that situationists have in mind is like saying that mere words cannot capture the taste of wine. However, unless we can be more precise about 'culture' then AI-ED systems will simply have to swallow whatever vague notion of culture is built into them (for it would be a mistake to assume that any system could be culture-free). Situated learning theorists argue that learning is or should be a process of enculturation. This is fine, but which culture do we mean? There are a very large, if not infinite, number of cultures. Consider the students in the four scenarios described in section 1.1: what, precisely, are the cultures into which they are enculturating themselves? Situationists seem to discuss cultures as though, unlike knowledge, they already exist in some objective sense. If asked, however, they would no doubt argue that a culture, like knowledge, has to be 'constructed' - which sounds quite a challenge for a learner. Otherwise, AI-ED systems would be engaged in a process of "culture transmission" which sounds even more invidious than mere "knowledge transmission". The general point is that vague polemical arguments about the role of such all-encompassing concepts as 'culture' have limited utility for AI-ED unless they are grounded in technical definitions amenable to theoretical analysis and practical application, especially when those arguments use or re-use terms like 'situation' which are already part of the technical lexicon.
4.5 Structured representations
As the above discussion of situations, contexts and cultures indicates, the propositions which are ascribed to an agent as beliefs or knowledge are rarely to be considered independent members of an unstructured set. A set of propositions may become structured in basically two ways: by partitioning the propositions into (possibly overlapping) subsets; and by specifying relationships between pairs of propositions.
Let us define an agent's belief-set Beliefs(a) to be the set of beliefs that have been ascribed to the agent a:
Beliefs(a) = { p | B(a,p) }
Similar sets can be defined for the other modal operators, such as a knowledge-set:
Knowledge(a) = { p | K(a,p) }
An agent's vocabulary V(a) may be defined to be the set of object, relation and function constants referred to in the agent's belief-set, knowledge-set, etc.:
V(a) = { c | c is an object, relation or function constant
& c occurs in Beliefs(a) or Knowledge(a) or ... }
An AI-ED system is concerned with some 'domain': we talk loosely of programs in 'the domain of algebra' or 'the domain of meteorology'. An agent's domain-vocabulary DV(a) is some subset of V(a) which the agent considers to be part of the language for that domain. Obviously, the contents of DV(a) will differ for different agents. An agent's beliefs about a domain, Domain-beliefs(a), is the subset of Beliefs(a) which concerns elements of DV(a):
Domain-beliefs(a) = { p | B(a,p) & $c (c in p & c is member of DV(a) }
Domain-knowledge(a) = { p | K(a,p) & $c (c in p & c is member of DV(a) }
(In the following, we will restrict consideration to the Believes operator.) The set Beliefs(a) also contains the agent's beliefs about the problem at hand and its ongoing solution, denoted by Problem-specific-beliefs(a). So, we can define an agent's background beliefs by:
Background-beliefs(a) = Beliefs(a) - Domain-beliefs(a) - Problem-specific-beliefs(a)
When solving problems in a domain an agent may need recourse to beliefs in Background-beliefs(a), i.e. to propositions which appear unrelated to the domain or the specific problem. This is because Domain-beliefs(a) may contain references to constants which are not in DV(a) but which are referred to in other propositions in Beliefs(a). These beliefs are indirectly or implicitly related to the domain. We could define:
Implicit-DV(a) = { c | $p c in p &
(p is member of Domain-beliefs(a) or
p is member of Implicit-domain-beliefs(a)) }
Implicit-domain-beliefs(a) ∫ { p | B(a,p) & $c (c in p & c is member of Implicit-DV(a) }
The distinction between Domain-beliefs(a) and Implicit-domain-beliefs(a) may be helpful in cases where an agent does not bring to bear beliefs which are not explicitly, obviously useful, and is related to the discussion of what constitutes a 'context' in the previous section.
If we consider a particular constant c (say, Fidelio), then we can form a set of the agent's beliefs (or knowledge) which are explicitly about c, i.e. have a reference to c:
Beliefs-about(a,c) = { p | B(a,p) & c in p }
Knows-about(a,c) = { p | K(a,p) & c in p }
These sets might be considered to represent the agent's beliefs or knowledge about the 'concept' c. That is, what an agent beliefs (or knows) about a concept is just the set of propositions which the agent believes (or knows) about that concept. For example, if we take the concept of 'metal', we can imagine that for a novice chemist:
Beliefs-about(a,metal) = { Isa(iron,metal), Isa(steel,metal), ...
"x Isa(x,metal) -> Shiny(x), ... }
For an expert chemist, some propositions will be in terms of the electron structure of metals. This seems to accord with the intuition that a concept is not a 'black-and-white' notion, that one knows all or nothing about. We could plausibly define:
Knows-of(a,c) = ~(Knows-about(a,c) = {})
Computationally, there are clearly potential practical benefits in 'gathering together' propositions which appear to be related, rather than have to search for them in an unstructured set. This is the basis for all the standard AI work on frames, scripts, schemas, semantic networks, and so on, which is obviously relevant, but not specific, to computational mathetics, and so will not be elaborated on here. In formal terms, there is no difference in these representations, because they can all be converted into one another and predicate logic, although there is much discussion of their merits in particular applications.
The idea of a frame begins to illustrate the second way of structuring belief sets mentioned above, that is, by defining relationships between propositions. A frame is essentially a set of relation constants (or slots) which are applied to (or filled by) particular values to define a certain concept. A frame (e.g. iron, steel, ..) may be defined to be a subclass of other frames (e.g. metal, noble-metal, ..), in which case it may inherit values from the superclass (just as from "x Isa(x,metal) -> Shiny(x) we may infer Shiny(iron)) . It may not always inherit values, for sometimes values are only default assumptions which may be overridden. For example, most metals are solid at room temperature (we will consider this in the next chapter).
4.6 Multiple representations
AI-ED research has always emphasised the need for 'multiple representations' of knowledge, appreciating that the different agents (such as students and experts) have different views and that in most domains different views are necessary (such as different economic theories). We must distinguish three different uses of the term:
• For different representations of the same knowledge, for example, the use of predicate logic or semantic networks to represent the same knowledge of metals. In this case, the concern is to enable conclusions to be reached more efficiently, not to find different conclusions.
• For representations of different knowledge of the same agent, for example, to view a prison as a place for incarcerating criminals or for rehabilitating them. This is the idea of context or situation, as discussed in section 4.4. Here, the problem is to find an 'appropriate' view to enable conclusions (which might differ from those of another view) or to coordinate the use of more than one view.
• For representations of different knowledge of different agents, for example, to view a metal in terms of visible characteristics (such as shininess and hardness), as a student might, or in terms of electron structure, as a teacher might. In this case, the issue is to coordinate or negotiate communication between the two agents.
Computational mathetics is most concerned with the second and third uses. For example, the aim of some AI-ED systems is expressed in terms of enabling a student to progress through a succession of representations corresponding to increasing levels of expertise in the domain (White and Frederiksen, 1990). In addition, a number of studies (for example, DiSessa, 1987) have shown that students bring idiosyncratic views of their own to problem-solving and these have to be taken account of when interacting with the student, for example, when giving explanations.
For example, Kamsteeg (1994) describes (in English) six "naive mental models" which students may have about heat and temperature and which we can try to define in terms of their beliefs:
• A 'simple particle model':
Beliefs(s) = { Temperature(body) µ number-of-'heat particles' }
i.e. heat is a kind of substance which holds a certain amount of temperature.
• A 'refined particle model':
Beliefs(s) = { Temperature(body) µ number-of-'heat particles' / Size(body) }
i.e. as above except that bigger bodies need more heat particles for the same temperature rise.
• A 'resistance model':
Beliefs(s) = { Temperature(body) µ number-of-'heat particles'
/ Size(body) x Heat-resistance(body) }
i.e. as above except that bodies have a 'heat-resistant layer' off which heat particles are 'bounced' and lost. The more heat-resistance a body has, the less its temperature rises for a given amount of heat.
• A 'magnet model':
Beliefs(s) = { Temperature(body) µ number-of-'heat particles'
x Heat-holding-capacity(body) / Size(body) }
i.e. as in the refined particle model except that bodies have different capacities for holding on to their heat particles.
• A 'simmer model':
Beliefs(s) = { Temperature(body) µ number-of-'heat particles'
/ Evaporation-rate(body) x time
Temperature(environment) µ number-of-'heat particles'
x Evaporation-rate(body) x time }
where time is the time since the heat particles were added to the body (assumed all at the same time, for simplicity), i.e. a body loses heat particles to the environment.
• A 'battery model':
Beliefs(s) = { Temperature(body) µ number-of-'heat particles'
x quality-of-'heat particles' }
i.e. some heat particles are of better 'quality' than others and are not so quickly lost (just as some batteries lose volts faster than others).
The precise definitions of these models is obviously more complex. Some of them, for example, make subtly different predictions about changes of temperature over time, which we haven't addressed above. We should note also that the six models are not all mutually exclusive: they can be combined in various ways to give more models than just those listed above. The ambition to use such models to explain and predict student behaviour is fraught with considerable difficulty. Among the problems, some of which will be discussed later, are:
• Students do not use such models completely consistently - they may switch from one model to another, or misapply a model.
• The models themselves may be inconsistent or incomplete.
• It is often hard to ascribe a particular model to a student on the basis of her behaviour.
• Students may not be able to discuss such models directly, at least not in the terms which we have used in the model descriptions (for example, the analogies with resistors, magnets and batteries are ones which we, as observers, might make, but which students themselves may not).
Nonetheless, students do not tackle problems of elementary thermodynamics in a random fashion. They do, to some extent, try to develop and apply coherent theories. For an AI-ED system, it seems plausible that it would be useful for the system to have some conception of the student's current model(s).
This example from physics might be taken to imply that the student is seeking to develop the one 'correct' model. The same idea of multiple representations can (or should) be used in domains, like economics, where no one model is distinguished as correct and where the students task is more to apply, combine and compare a range of models. In summary, multiple representations are important in AI-ED for two distinct reasons: to improve problem-solving efficiency, because different views of a domain are possible, and to develop better psychological models of students. The reasons for adopting multiple representations influence how we deal with theoretical and practical limitations in using with them.
4.7 Social knowledge
Our notation allows us to nest modal operators concerning different agents, for example, to write
B(a,B(b,p))
to mean that we have ascribed to agent a the ascription of belief p to agent b, or more simply that a believes b believes p. This provides our means to describe the interrelationships and interactions between members of a society of agents, an understanding of which "is vital for story understanding, in automated teaching and in intelligent interactive systems" (Davis, 1990), all components of computational mathetics. However, our current ability to describe these aspects formally is very limited.
As previous sections discussed, we may partition an agent's beliefs or knowledge into views or contexts. Clearly, there is likely to be some overlap between these views and those of other agents. It will be useful to identify those propositions which are common to the belief-sets or knowledge-sets of all agents in a society. For example, as they are common, such propositions may not need to be communicated or explained to one another. If
"x K(x,p)
"x1,x2 K(x1,K(x2,p))
"x1,x2,x3 K(x1,K(x2,K(x3,p)))
and so on, then we say that p is common knowledge to the set of agents:
Common-knows({a1,a2,a3,...},p)
Common-knowledge({a1,a2,a3,...}) = { p | Common-knows({a1,a2,a3,...},p) }
This set of agents is sometimes called 'any fool'. As with single-agent modal logic, we can try to define some axioms for common knowledge, for example,
Common-knows({..,a,..},p) -> K(a,p)
Common-knows(x,p) -> Common-knows(x,Common-knows(x,p))
Common-knows(x,p) & Common-knows(x,p->q) -> Common-knows(x,q)
The idea of common knowledge has been studied in fields as diverse as distributed computer systems (Halpern and Moses, 1992) and philosophy (Strawson, 1971). Implicit in the notation is a view that the (common) knowledge of a set of agents is the intersection of the individual agent's knowledge. Of more potential relevance to AI-ED, given the enthusiasm for collaborative learning, is the view that the knowledge of a set of agents is the union of the individual agent's knowledge. Unfortunately, no formalisations of this view seem to exist. We could imagine that the set's knowledge can be used to solve a problem not solvable by any single agent, perhaps leading to each agent believing all propositions necessary to solve that problem:
B(a1,p,t) & B(a2,p->q,t) -> B({a1,a2},{p,p->q},t)
B(x,{f,f -> y},t) -> Solves(x,y,{f,f -> y},t)
Solves(x,y,z,t) -> "a,p (a is member of x &
p is member of z -> B(a,p,solved(y,t)))
There has been more work on multi-agent collaborative or cooperative planning than there has on multi-agent problem-solving. This may have relevance to computational mathetics as student and teacher agents have common and conflicting goals which should be taken into account. Issues that need to be considered include:
• The division of tasks between the various agents.
• The communication of relevant information between agents.
• The prediction of how other agents will react to a request.
• The coordination of plans which may hinder or obstruct one another.
Some of these issues will be considered in later chapters.
4.8 Procedural representations
The idea touched upon in the previous section that knowledge exists (only) as a social construct is offered as a radical alternative to the standard cognitive science view that knowledge is an individual cognitive construct. Another possibility is that knowledge exists (only) in action:
"Action is involved in knowledge ... in the sense that knowledge is a form of action, and that action is one of the terms by which knowledge is acquired and used." (Hofstadter, 1962)
The relation between knowledge and action has also concerned philosophers. For example, Ryle (1949) is often selectively quoted for writing that "It is ... possible for people intelligently to perform some sorts of operations when they are not yet able to consider any propositions enjoining how they should be performed" in order to justify a 'knowledge without representations' philosophy (Brooks, 1991). In fact, Ryle was arguing that mental concepts refer not to unwitnessable activities in the body or mind but to dispositions to behave in certain ways in appropriate circumstances (much as we have assumed). One can have behaviour without (symbolic) knowledge and also knowledge without behaviour. Whitehead (1932) referred to 'inert ideas', that is, knowledge which appears to exist (perhaps because it can be stated) but which cannot necessarily be applied when it should.
This split between explicit knowledge and behaviour is not necessarily desirable. The fact that humans can behave without knowing and can know without behaving is not a reason that AI-ED systems should aim for such an outcome. Sometimes it is sufficient to be able to behave without being able to articulate propositions underlying that behaviour. For example, I can use my phone without being able to say precisely how, by giving a description of the layout of buttons. But then I never use my phone without it being literally to hand, so that the layout of buttons is not a problem. However, if I were incapacitated (perhaps after being attacked by a burglar) then it might be useful to be able to articulate an explicit procedure executable by my four-year-old daughter (if I had one).
Ryle (1949) commented that "efficient practice precedes the theory of it". To which, one may respond "not always". Sometimes there is a lot of efficient practice and no theory; sometimes there is more inefficient practice than there is efficient practice; sometimes a good theory precedes efficient practice. Usually, practice and theory develop together in mutual support. In some ways, the rationale for our own discussion about AI-ED mirrors this debate. We might believe that AI-ED system designers can successfully design AI-ED systems without being able to consider any propositions enjoining how they should be designed. Or we might believe that the development of a good theory might contribute to the efficient practice of AI-ED system design.
Situationists believe that the link between mental structures and behaviour is the wrong way round in conventional cognitive science and AI, which emphasises transition 1 in this diagram, i.e. the view that behaviour follows from instantiating and interpreting underlying mental structures.
Situated cognition, on the other hand, focusses on transitions 2 and 3. Hanks (1991) writes that there is a "potentially radical shift from invariant structures to ones that are less rigid and more deeply adaptive. One way of phrasing this is to say that structure is more the variable outcome of action than its invariant precondition ... It (i.e. behaviour) involves a prereflective grasp of complex situations".
The field of AI has debated the 'declarative/procedural controversy' (Winograd, 1975) almost to exhaustion. In order to situate the situated cognition position, it is worth briefly summarising the use of production systems, a common representational scheme in AI-ED and in expert systems and psychological modelling. With this scheme an agent is ascribed a set of production rules, or condition-action rules. The 'condition' is expressed as a list of patterns which are matched against items in a working memory (the agent's problem-specific knowledge). The 'action' is a set of individual actions which change the contents of the working memory. Typically a problem is solved by repeatedly applying rules whose conditions match items in the changing working memory. For example,
Knows-how(a,to-boil-an-egg):
Water-in-pan-is-boiling -> Put-egg-in & Turn-egg-timer
Pan-is-empty -> Add-sufficient-water
Egg-timer-has-run-through -> Remove-boiled-egg & Turn-gas-off
Pan-has-water & Gas-is-off -> Turn-gas-on
Egg-timer-is-running -> Do-the-daily-crossword
As rules only fire if their conditions are satisfied, the order of the rules (in simple cases) does not matter and therefore it is possible to add rules to handle further situations. The refinements of production systems are discussed in any standard AI text. That the distinction between 'procedural' knowledge and 'declarative' knowledge is hazy is clear from considering the similar notation of the Prolog programming language, where a single definition can serve as both a proposition, returning true or false, and as a procedure computing a value.
Usually, production systems contains many hundreds of rules. Their main virtues are said to be that the rules can be independently associated with individual actions, and that the rules can be independently articulated. The virtues and limitations of production systems for AI-ED purposes have been thoroughly discussed (Anderson, Boyle, Corbett and Lewis, 1990; Clancey, 1987). The main point to make here is that the approach does indeed emphasise transition 1 (in the above diagram) but it does not entirely neglect the other two transitions. The rules themselves do not entirely determine behaviour - they are adapted by the 'situation' represented by the working memory. Also, the actions may, if desired, change the mental construct itself, by amending existing rules or adding new ones. Of course, these processes may not fully capture what situationists have in mind.
Similarly, as the above quote from Hanks (1991) shows, situated cognition does not entirely ignore the role of mental structures in determining behaviour. However, we may ask:
• What exactly is a "less rigid and more deeply adaptive" structure? Is it a different kind of structure to the productions systems, blackboards, frames, and so on developed in AI? All of these are adaptive to some extent - but what extra or different does "deeply adaptive" mean?
• How is such a structure used to provide "a prereflective grasp of complex situations"? How does this differ from, for example, a production rule which carries out a very 'superficial' matching of the situation to provide a 'grasp' of it?
• What kind of structure is it that "is more the variable outcome of action"? Is the structure produced as outcome of action very different in kind to that postulated in standard cognitive science as the input to action? If not, is it acceptable to use standard schemes to represent such outcome structures?
• How long do these outcome structures last? Can they be used as the 'less rigid' structures providing 'prereflective grasps' of later situations? If not, why do agents bother to create such structures?
As more precise answers to these kinds of questions are developed, it is likely that situated cognition will become seen mainly as a theory emphasising aspects of cognition which have been neglected in previous approaches and which are particularly important in some circumstances, but not as a theory warranting the wholesale jettisoning of theories and techniques already found useful in other circumstances.
5. Reasoning
In this chapter we will consider how agents reason with mental components such as beliefs. We will interpret the word 'reason' broadly to include any process by which an agent derives conclusions from premises during the course of problem-solving. The process need not be considered sound or rational in the logical sense, because, of course, some agents are not always sound and rational. We will try to be explicit about these reasoning processes because:
• In current AI-ED systems these processes are often buried in executable code and not amenable to any kind of theoretical comparison.
• An AI-ED system which has access to explicit reasoning processes may be able to reason about them and not just about beliefs and knowledge. The system may be able to discuss and explain such reasoning processes, possibly in a domain-independent way, and so move beyond solely domain-related issues.
• It may be possible to customise representations of reasoning processes in order to describe different agents (for example, different students) or the same agent at different times (if, for example, a student learns a new reasoning process).
• By identifying reasoning processes appropriate for different agents we may be able to separate computational and cognitive issues, which are currently intertwined. For computer agents, it may be that efficiency considerations are most important; for student agents, psychological validity may be most important.
• In order to discard beliefs, it may be useful to record how they were derived, which is only possible if the reasoning processes can be monitored.
A range of reasoning processes will be described, with a modest degree of formality. It is not the aim to develop a complete, 'correct' representation. Rather the aim is to develop illustrative notations of sufficient precision that we may determine which properties of reasoning processes are relevant to particular AI-ED applications. Considering the computational complexity of the various notations might help clarify the compromises necessary to achieve practical performance. Just as the previous chapter tried to consider belief and knowledge independently of the uses to which it may be put (the subject of this chapter), so in this chapter we will consider the reasoning processes that an agent may have available without considering which of the processes an agent may choose to apply in any particular problem-solving context (which is considered in the next chapter).
5.1 Reasoning schemata
reasoning schemataA representation such as
B(a,Metal(x) -> Shiny(x))
which is intended to denote that an agent a has been ascribed the belief that all metals are shiny, does not indicate how the agent may use this belief to derive conclusions. We could imagine that the agent might in different situations, such as the presence of an object b which is or is not a metal or is or is not shiny, infer Shiny(b) or ~Shiny(b) or Metal(b) or ~Metal(b), respectively. Some of these inferences are valid in standard logic, and some are invalid but nonetheless plausible. For more complex beliefs it is naturally harder to say what inferences might follow.
We will use the notation
Reasons(a,f1, f2, f3, ... => y)
to indicate that we have ascribed to agent a the 'reasoner' f1, f2, f3, ... => y. The reasoner f1, f2, f3, ... => y indicates that if we have ascribed beliefs f1, f2, f3, ... to the agent then it may be necessary to also ascribe the belief y, as the agent considered to hold those beliefs may make that inference. So, for example, from
Reasons(a,f->y, y => f)
B(a,Metal(x) -> Shiny(x))
B(a,Shiny(steel))
we may need to make the ascription
B(a,Metal(steel))
As this simple example indicates, a reasoner is a schema which needs to be instantiated to match particular beliefs (we will consider this further below). We use the term 'reasoner' to avoid the connotations of phrases such as 'rule of inference' or 'operator'. As we did in section 4.5 for beliefs, so we may define an agent's reasoner-set Reasoners(a) to be the set of reasoners ascribed to the agent:
Reasoners(a) = { r | Reasons(a,r) }
We may now illustrate some reasoners which may be relevant to AI-ED.
5.1.1 Reasoning in standard logics
The reasoner:
f->y1, ~f->y2 => y1 v y2
or equivalently
~f v y1, f v y2 => y1 v y2
describes the rule of inference called resolution, which is known to be sound and complete in predicate logic. To apply the rule all the sentences have to be in conjunctive normal form (section 4.2). The rule of resolution is the basis for standard theorem-provers in predicate logic, the programming language Prolog, and the rule-matching mechanism of production systems. The precise definition of resolution, explaining how variables may be substituted to make expressions unify, is given in any theoretical AI textbook (such as Genesereth and Nilsson, 1987).
A special case of the rule is when y1 and y2 are both empty:
~f , f => false
i.e. the agent may infer false if there are two propositions in the belief-set which directly contradict one another. As resolution is complete (i.e. any sentence logically implied by a set of sentences can be derived by repeated applications of the rule of resolution), if a set of sentences f1, f2, ... fn is contradictory then false may be derived from them. In such a case, ~(f1 & f2 & ... & fn) is a theorem, by definition; or, equivalently, f1 & f2 & ... -> ~fn is a theorem. Therefore, to show that an expression of the form f1 & f2 & f3 & ... -> y is a theorem (as discussed in section 4.2) one may negate the conclusion y and show that f1 & f2 & f3 & ... ~y leads to false after applying resolution. Although this procedure is not guaranteed to terminate (as predicate logic is an undecidable system), there has been much research on developing efficient theorem-provers.
This reasoner may be used by a system agent to reason about its own knowledge, or to reason about what is implied by the beliefs ascribed to a student. However, the reasoner is of little use if the system needs to reason about the student's beliefs in the same way that the student does or might, because it is implausible, to say the least, that a student will apply anything comparable to the rule of resolution. The reasoner is also of little use if the system needs to reason about its own knowledge and explain its reasoning to a student (as resolution is not likely to be comprehensible). Thus, resolution cannot be used to model students' reasoning processes or to explain reasoning processes.
Rules of inference for a logical system may be defined which are intended to give proofs that are closer to those that human theorem-provers produce. We could, for example, have reasoners such as:
f & y => f
modus-ponens: f->y, f => y
modus-tolens: f->y, ~y => ~f
f->y, y->f => f´y, ...
Such a 'natural deduction' set of reasoners might be more useful for modelling the reasoning processes of students than the rule of resolution. For convenience, we can attach names (such as modus-ponens and modus-tolens above) to individual reasoners, as indicated above.
If the aim of the reasoner-set is to provide an ascription to a student which corresponds to problem-solving performance then it might be necessary to include reasoners which are unsound:
f->y, y => f
f->y, ~f => ~y
Apart from having faulty reasoning schemata, students may also not have a complete set of 'correct' reasoners. All the issues which arise when attempting to model students' knowledge (chapter 8), arise also with respect to their reasoning processes, although few AI-ED systems attempt to model the latter. (Note that the process of reasoning unsoundly is different to the process of reasoning with inconsistent premises, the latter being discussed briefly in section 5.4.)
The previous examples suggest that our reasoners are just rules of inference in a formal logic system. However, we would also consider what are in some domains called 'operators' to be examples of reasoners. For example, in algebra, we might consider that an equation such as x=c*(e) where c is an integer and e an expression, can be rewritten as x=c*e where c*e denotes the result of applying a multiplying-out operator. We could represent this by:
Equation(x=c*(e)) => Equation(x=c*e)
In this case, because we are likely to need to keep a record of the operators applied, we might use the situation variable introduced in section 4.4:
Equation(x=c*(e),t) => Equation(x=c*e,multiply-out(t))
We could similarly represent normal rules of inference, to label them and keep a track of problem-solving performance:
(f->y,t),(f ,t) => (y,modus-ponens(t))
where (f,t) refers to the condition of having ascribed B(a,f,t) to the agent.
AlgebraLand (Foss, 1987) provides a menu of such operators. In this case, it is assumed that students understand all the operations denoted by the menu items. Therefore, the problem of ascribing an appropriate reasoner-set to the student is bypassed. Many simulation-based systems adopt a similar approach. For example, a simulated chemistry lab might provide a menu of chemical operations for students to select from. It would be assumed that students know what the operations are and that their problem is more one of determining an appropriate sequence of operations (in this case, perhaps, to prepare a specified chemical). In more open envi