Some Thoughts about Representing Knowledge in Instructional Systems

Introduction

Functionally,question-answering systems and computer-aided instructional systems (CAl-systems) are similar, and it seems appropriate to transfer AI-techniques de­ veloped for Q/A-systems (11,13) to CAl­ systems. But so far, research on 0/A­ systems has not given much thought to the questions a user could or should be asked, or how the system's reply should be ex­ pressed as to be easily understandable by the user. These features are not only re­ quired in tutoral dialogue, but should also be present in any interactive system, where at least two partners jointly strive to achieve a goal, and each may request use of the capabilities of the other. Clearly, a teacher needs some know­ ledge of his student's knowledge and goals aside from knowledge about subject matter. That knowledge is referred to as a use~­ modBZ. Other interactive applications like operating systems, debuggers for pro­ gramming languages, or information-retrie­ val systems would also benefit from expli­ citly considering a model of the user in preparing their messages.

We will outline (1) how subject-matter knowledge may be represented in semantic nets, and then (2) how planning of in­ struction is directed by an instructional model.

Building semantic nets in a subject area

SCHOLAR by Carbonell (3) and SOPHIE by Brown (2) are examples of the use of a semantic net for representing subject­ matter knowledge and using it in gener­ ating problems, or answering queries. Simmons has hypothesized that semantic nets may serve as the central cognitive structure (11). We will show how a seman­ tic net of a subject-matter area can be built (using the notation of (8)), and how the notion of a semantic net may be expanded in order to achieve greater flex­ ibility in using it.

Basic objects and relations

First, certain concepts are decided to be pre-requisite and known to any student. Some objects and relations are also used as primitives in the problem-solving com­ ponent of the system. The relation "north­ of" may either be assumed basic or ex­ plained to the student in terms of lati­ tude, as well as computed in terms of lat­ itude. In choosing basic relations and objects, it has to be considered that nat­ ural language sentences may be conve­ niently generated.

Concept nodes

Secondly, the concepts to be taught are defined in terms of relation-object tup­ les (like a Lis'p property list). E.g. if we teach, say "Chine.se Cookery", some bas­ ic objects may be: rice, soy-sauce, pan etc., and some basic relations are : in­ gredient-of, made-by, shape etc ·· An ob­ ject like a "wok" is not basic because the student might need to know that it is like an iron pan, having a bowl-like shape with two handles, and is used main­ ly in a cooking method called "stir-fry­ ing":

Several questions about a "wok" may be asked by the student, and it is possible to retrieve respective answers. General­ ly, it is a problem to decide, how many nodes deep we shall go into the net when retrieving the subnet used for the answer. Carbonell . (3) used irrelevancy tags as weights to determine the subnet included in the answer. We feel that this is a weak point in SCHOLAR, and that the rele­ vancy should rather be determined on the basis of an instrutional model.

Situation nodes or frames

Finally, concept nodes serve as building blocks for larger structures capable of expressing situations, events and compo­ sitions of events. A situation can be thought of approximately as the descrip­ tion of part of the (hypothetical) world at an instance. Again, teaching "Chinese Cookery", we may describe the initial sit­ uation before preparing a course by lis­ ting each ingredient, respective amount, state of preparation, tools, relative po­ sition etc .. Anything altering a given situation is called an event. The descrip­ tion of an event should express the changes it will make, if applied to the network structure representing that sit­ uation. As a consequence it is natural to allow compositions of events (nested, se­ quential or parallel concatenations). In order to include such knowledge, semantic nets require procedures within them.

We follow Minsky's notion of a fl'ame "as a data structure for representing a ster­ eotyped situation"(10), and interpret it for representing subject-matter in an in­ structional system: "A frame is a collec­ tion of questions to be asked about a hypothetical situation; it specifies is­ sues raised and methods to be used in deali~g with them." (Minsky (10)). Organi­ zing a curriculum for a CAl-course should then start by identifying such situations, applicable questions, and the ways they are connected, rather than building a "hierarchy of principles" (�agn~ (4)). Some of the questions associated with a situation might be, what concepts are pre­ requisite, how a similar situation would look, which solutions are possible, or methods could be tried, etc ·· We shall not dig further here now, but look for a way to extend the computational aspect of a semantic net in order to give it some of the capabilities of a frame-system. A frame differs from a conventional node in a semantic net in the sense that:

• (a) Before any node being pointed to (terminal) is accessed from a frame head, an applicability test is made. If it fails, a list of alternative frames is made available. If it suc­ ceeds, it may determine which arcs to access and in what order.
• (b) If a frame is accessed, it may take over control and not return to the c.alling frame.
• (c) The terminals may specify conditions that have to be satisfied. These con­ ditions are functions that may have as arguments values of other termi­ nals of this frame, or a frame through which the current frame has been previously activated. If the condition fails, a default value is given.

Schematically, we visualize a node in the net now as:

The Ri are relations in the usual sense, while the F are atoms with a function property. Ii case a terminal is accessed through his arc, the function body is eval' ed. An Fi may test conditions, and speci­ fy defaurt values. The Control arc is op­ tional, tests applicability of its frame, and determines access of terminals and return of control.

We give some examples of extended nets where the subject-matter taught is "Pl'o­ gzoamming in LISP": aond7~t \ntax

If an example for a cond 1 -statement is required by the student, the arc labelled "example" is accessed. Since it has a function property, the body is eval'ed making it possible to generate an example applicable in the current programming problem. The advantage is, that examples for cond-statemcnts can be adapted to the student's current goal.

The frame itself may take over control, and evaluates itself. Whatever is sup­ posed to be done with control is speci­ fied in its body.

Take the previous example:

When control is regained, return to caller.>

The basic operations of creating, storing, retrieving, and removing concept nodes are handled by standard LISP-functions. For frames such functions must be redefined. Also, nodes should be retrievable by pat­ tern-directed invocation (5). The develop­ ment of such tools promises to be valuable for implementing a teaching system more versatile than SCHOLAR. Nevertheless it was SCHOLAR which motivated these reflec­ tions.

Planning instruction

Assume, a semantic net representing know­ ledge in a subject-area has been built along these lines. How could an algorithm to teach it be designed? One approach is to wait for a user query, understand it, invoke the frame(s) relevant to it, and call a procedure which generates a natural language reply. A different way is to let the system decide what the current goal of instruction should be, and proceed as be­ fore. Since the initiative of the dialogue is either on the system's or on the user's side, Carbonell used the term mixed-ini­ tiative dialogue to express that SCHOLAR enabled both modes (3). But it is impor­ tant to notice, that both modes need a specification of the dialogue's goal. The user's query must be understood as a fur­ ther specification of the (possibly vague­ ly expressed or implied) instructional goal. Its meaning depends upon the context of previous dialogue, assumptions about the user's knowledge, and the purpose of instruction.

A human instructor (hopefully) knows what he wants to instruct, and also takes note of what he believes his student has al­ ready understood. Sometimes, before star­ ting to teach a new concept, he makes sure that the student has grasped alle pre-req­ uisite concepts by asking questions. The student's answer is then used for updatin~ his notes. This illustrates sone of a hu­ man teacher's intelligence. How can it be made artifici~l?

Let us define an instructional model as a representation of (1) goals of instruction, (2) methods to achieve them, and (3) a user model. The goals may be formulated in terms of a set of concepts the student can apply to a set of situations. These goals may be modified by particular user pre­ ferences. The methods include 9eneral, hence transferable knowledge a teacher ha& The user model contains the history of un­ derstood concepts and solved problems, a description of situation features the user is likely to be motivated by, and possibly some characteristics of his ability (like reading speed, preferences for inductive or deductive reasoning, forgetting factor etc.). The function of an instructional model within a CAl-system would be to search the semantic net, retrieve the frames to be taught, match their pre-req­ uisites with the prior knowledge of the student and interpret user queries and answers as updates of the instructional model.

A CAl-system should explicitly incorporate such model, but presently only few at­ tempts have been made to do so (6). The traditional approaches to this problem using decision theor·y and stochastic learning models (1,7,12) have reached a dead end due to their oversimplified re­ presentation of learning. The reason for stochastic learning models failing as models for instruction is their lack of representing the content to be taught. The teacher's decision can in general only be made, if he knows what is understood, but not the probability that a specific re­ sponse will be given to a specific stim­ ulus.

A new approach would be to express the in­ structional model as a structure of goal­ directed processes (in a language such as CONNIVER (9) or PLANNER (5)). We can sketch the idea for a (overly simplistic) first approximation to such algorithm:

Let the goal of instruction be that the student can solve problems generatable from a list of situation nodes of the net­ work. This list could be a tree implying a default ordering of concepts (e.g. in terms of the pre-requisite relation). In planning his next move, the instructor takes a node from this list, and tries to find out whether it is answerable by the user model.

A problem generated from a situation node is answerable if its listed pre-requisites are marked as known or if a problem-sol­ ving procedure containing only steps pre­ viously demonstrated in other situations can be successfully applied. The function that evaluates whether a problem is an­ swerable may in case of failure return a list of unknown pre-requisites, and also recommend other frames to be examined first.

To find whether a pre-requisite is met, or a substep in a solution sequence is avail­ able to the user, the model may yield insufficient information such that a test b~ comes necessary. A special logic for re­ trieving tests can be constructed: For ex­ ample, knowing that a given relation holds for the superset node of a concept implies that it is known for any node that is con­ nected via the "Isa"-relation. Similar theorems hold for other relations like part-of or temporal ordering. They should also be used when analyzing answers to problems not given for test ourpose in or­ der to mark the probable knowledge-state of concepts.

If it turns out that a pre-requisite con­ cept is necessary. we search for a node designed to exampZify it. The net is built to facilitate such search by having "Ex­ ample"-arcs from concepts to frames. Also, special procedures for generating examples may be constructed: Find a previous situ­ ation where the solution would have been simplified through the use of that concept, or a situation which in case a terminal is bound differently requires that concept in order to be answerable.

Rather than looking for problems with an­ swerable pre-requisites, a different plan would present a situation node first in "general terms" by binding some terminals to simple cases, and proceed interaction with the user, specifying terminals in the direction indicated by the student's know­ ledge and interest. In SCHOLAR it is a problem, how deep one should follow arcs to retrieve relevant information at a given instant. If the instructor .marks the arcs already retrieved, he can avoid being repetitious. Furthermore, it seems good pedagogic practice to connect new concepts with ones already known. This leads to finding connections from the presented node to already marked ones, retrieving only differences or similarities (to en­ hance discrimination or generalization). All this may not yet involve any restric­ tions by user goals. But his history may indicate that he is more interested in say political facts about South-America than its main rivers. The dialogue should be used to extract special procedures that evaluate the student's motivation when re­ trieving a node and filling its terminals.

The system has to have the probZem-soZving abiZity it tries to teach (at least within the topic of discourse). A student query concerning a concept, may force the in­ structor to explain the concept in the context of the current problem. Or, if the student has correctly solved a problem and indicated his steps, some of the used con­ cepts may be inferred (or guessed) since each step is solvable by the instructor too. These used concepts can then be mar­ ked as "known"(or "probably known"). What does the instructor do about a bug in a user answer? He can try to produce the same bug by using heuristics about pre­ ferred errors detected in users (like leaving out a")" or a terminating con­ dition for recursion in LISP). Another hypothesis to test is, whether the user's answer was a correct reply to a similar problem, indicating that the situation was not correctly understood. Finally, if the instructor is not intelligent enough to understand why the proposed solution is wrong, he can tell the user facts contra­ dictory to his solution or ask for inter­ mediate results.

It appears within reach of AI-methodology to develop CAl-systems that act more like human teachers. A crucial step in this de­ velopment is the separation of subject­ area knowledge from instructional planning knowledge. What has been said is provi­ sional, and may serve as a guideline that will need to be further extended and spe­ cified.