[This local archive copy is from the official and canonical URL, http://www.cc.gatech.edu/faculty/ashwin/papers/git-gvu-98-20/; please refer to the canonical source document if possible.]

Abstract

1. Introduction

Suppose that you are a homeowner faced with the problem of a leaky faucet. If you are reasonably comfortable with home repair, you might be able to just plunge on in and make the repair. But if you are not familiar with that kind of repair, you might seek help, perhaps using a book or even one of the new multimedia guides to home repair for your PC. Will the book present the information you need at the level you need it? Maybe you know home repair well in general, but don't know faucets. Then you probably want a book that presents the key steps, but without a lot of detail. But if you are a novice at home repair, you probably need a lot of examples (with photos and diagrams) and detailed descriptions. In the case of both the book and the multimedia guide, you may encounter the problem of reading the book or the PC screen while your hands have tools in them and you are in the midst of the repair.

This hypothetical scenario is the focus of our research. How can information be presented, dynamically, to meet the needs and prior knowledge of the learner? How should content be encoded so that the developer can present information tuned to the audience and perhaps even presented in the medium of choice?

One of the central issues in the development of multimedia systems, whether on the Web or as a standalone system, is the representation of the content, that is, the information that is to be displayed to the user of the system. For example, an educational system that teaches chemistry must contain information about atoms, molecules, and gas laws; a training system for computer technicians must contain information about memory chips and buses; and a Web site for amateur home repair must contain information about kitchens, showers, and faucets. In designing such systems, however, one must attend not only to the knowledge to be represented but to how that information is to be presented. Is the system's information about showers to be displayed in graphical form? Is information about installing memory chips to be displayed as an itemized list of textual imperatives? Is information about gas laws to be displayed using an animated video clip showing the movement of molecules as a gas is compressed? Typically, the system designer must consider both content and presentation and, in doing so, create a system in which the two are inseparably linked; a specific presentation is chosen for each piece of information, perhaps combining several available media such as text, pictures, animations, and sound, and hard-coded into the system so that it is available for presentation in exactly the form that the system designer intended. Specific navigational aids are also chosen and hard-coded into the system so that a predetermined hypermedia structure is encoded and available to the user.

We argue that knowledge representation and presentation design should be treated as separate activities. The knowledge engineer or content designer should focus on the knowledge that is being represented: what is known about molecules, buses, and faucets, how this knowledge is structured, and how it might be represented using basic media elements. The presentation designer should focus on the multimedia presentation of this knowledge: how should a diagnostic procedure be displayed to the user? At what level of detail, and for what level of expertise should it be presented? What should it be linked to? What navigational aids should be provided? What issues concerning how people comprehend text, graphics, animations, etc. need to be considered?

Such an approach has several benefits. First, it is easier for domain experts (who may not be presentation experts) to build the knowledge representation without regard to how the information will ultimately be displayed. Second, it is possible to design different presentations for the information based on the user's level of expertise, or on the task that the user is engaged in (for example, learning vs. troubleshooting), or on other factors. Third, this approach permits the development of truly interactive multimedia systems in which the system creates appropriate presentations on-the-fly based on the current interactions and context. Only the knowledge needs to be specified beforehand, but whether a diagnostic procedure, for example, is presented as an itemized list of textual bullets, a graphical flow chart, an animated movie, or some combination thereof can be determined dynamically. If knowledge and presentation were tightly coupled, all these presentations would have to be created manually in advance and stored as alternative depictions of the same information.

Of course, the knowledge representation must ultimately bottom out in media: a textual definition of a gas law, a photograph of a faucet, or a schematic of a VLSI chip. Thus, it is important to provide a principled means of coupling the knowledge representation structures with the underlying media, but in a manner that provides the flexibility needed for interactive and dynamic presentations. We argue that knowledge structures should organize media according to their cognitive role [Recker, Ram, Shikano, Li, & Stasko, 1995]. Consider, for example, a student who is using an educational multimedia system to learn chemistry, or a homeowner who is using a home repair CD-ROM or Web site to help fix a leaky faucet in a bathroom. The user is unlikely to say, "I would like to see some text now" or "I could really use a WAV sound file now." Instead, the user may say, "I could really use an example," leaving it up to the system to determine whether that example is best presented as text, sound, animation, or some combination thereof. In other words, we argue that multimedia content, consisting of physical media such as text, sound, video clips, and so on, should be organized and coupled to knowledge structures using cognitive media roles, such as definition, example, simulation, worked problem, and so on. A cognitive media role, such as "example," specifies the function that the information plays in the cognitive processes of the user. The user might ask for an example of a faucet or a simulation of molecular forces, which in turn would be displayed using an appropriate combination of physical media as determined statically by the presentation designer and/or dynamically by the system itself.

There has been a significant amount of work attempting to disentangle knowledge representation from presentation in multimedia. Maybury [1993] has emphasized this distinction in his work with intelligent multimedia interfaces. Feiner [Feiner, McKeown, 1991] has shown a system that can actually construct multimedia representations on-the-fly, drawing from a knowledge base of content and a separate knowledgebase about representations. Research teams such as the Hyper-G group in Austria [Tomek, Maurer, & Nasser, 1993] have created Web-based applications that allow for separation between representation and presentation (e.g., keeping link information separate from the multimedia document itself). What we add to the existing science is (a) a theory of effective organization for multimedia used forlearning (specifically, cognitive media roles), and (b) a notation for encoding knowledge such that an effective representation can be generated.

To facilitate the development of a system outlined above, we propose and describe in this article a new notation called Procedural Markup Language (PML).  PML is a markup language written in XML that allows the content designer to encode domain knowledge in an intuitive and flexible manner by specifying the knowledge structures, the underlying physical media, and the relationship between them using cognitive media roles. We focus specifically on procedural task domains, in which the primary type of knowledge to be represented concerns the performance of procedures. The highlights of our formalism are:

• Information about a domain (e.g., plumbing) is encoded in knowledge nodes that have connections, called knowledge links, to other knowledge nodes.
• Information within a particular knowledge node (e.g., information about a faucet) is represented using physical media clusters containing media elements such as text, graphics, animations, video clips, and sound files.
• Physical media are organized under knowledge nodes using cognitive media roles, such as "definition," "example," etc. Any cognitive media role under a knowledge node could potentially contain one or more different physical media (e.g., an example of a faucet might be represented using some text and a graphic).
• The information contained in the combination of knowledge nodes, knowledge links, physical media clusters, and cognitive media roles forms the raw material that can be used by a presentation system to determine what the user or learner will see and hear, and what navigational connections and devices will be available on the screen. Different presentations may be created from the same underlying representation, depending on various factors such as the expertise of the user in the domain, the information that the user has previously seen, the current goal of the user, and so on.

2. Technical Details: Knowledge Representation

Before describing the markup language itself, it is instructive to look at the representational structures that the language will need to encode. Let us briefly discuss the necessary nodes and links.

Knowledge Nodes

A knowledge node represents a concept that the system knows about. Information about the concept is represented using media clusters while relationships between concepts are represented using knowledge links. Following basic ontological principles that are commonly used in representations systems in artificial intelligence and cognitive science, we divide the entities being represented into things, states, and procedures(see Table 1). Based on our experience with several different domains, this ontology appears to sufficient to capture the distinctions necessary to represent our target domains where the knowledge being represented is mainly procedural. In general, though, the robustness of the language can only be determined by representing a large number of domains using this formalism.
 

Knowledge Links

Knowledge nodes may be linked to other knowledge nodes using knowledge links that represent conceptual relationships between those knowledge nodes (see Table 2). Note that knowledge links are strongly typed; for example, the precondition link always connects states to procedures. The order in which multiple links of the same type are listed under any givennode is not significant, with the exception of steps which are listed in the order in which they should be carried out. Knowledge links may be traversed in either direction by the system, although each link has an explicit source and destination endpoint. The reverse links are also listed in Table 2.  These reverse links are managed by the system and not manually created by the user. Our formalism provides the following set of knowledge links; as before, determining the sufficiency of this set is an empirical question, although this set has been adequate for several domains that we have investigated.
 

Physical Media Clusters

A physical media cluster (or simply media cluster) contains the actual information about a knowledge node that the system can display to the user. We will see below that all media are stored in separate files, referenced via the MEDIA tag, with the exception of text which may be included in-line in the PML document for authoring convenience. A media cluster may contain more than one type of physical media (text, video, etc.). A knowledge node may contain one or more media clusters; these are organized using cognitive media roles that provide the connections between the knowledge structures and the media clusters.

Cognitive Media Roles

The media clusters within a knowledge node are organized in terms of the cognitive roles they play in the problem-solving task in which the user is engaged. For example, a particular mixed-media text-and-pictures description of a faucet may serve as an "example" of a single-lever faucet; in this case, the knowledge node for "single-lever faucet" will contain an "example" role which contains a media cluster that represents that text-and-pictures description. Our formalism provides the following cognitive media roles [Recker et al., 1995].
 

Example

To illustrate how these nodes and links fit together to provide an overall representation of the domain of interest, consider a snippet of the representation of faucets from the home repair domain, shown in Figure 2 in pictorial form.
 

3. Technical Details: Procedural Markup Language

We have developed a language called PML that allows authors to encode our knowledge representation in a set of files. Authoring in PML is analogous to authoring in HTML or other markup languages, but with the crucial difference that the author focuses on representing information about the domain and not primarily on information about presentation. That is, the two types of information are decoupled. For example, if one were to create a Web page in HTML describing how to install the latest release of a piece of software, one might do this as follows:

To install this release, perform the following steps: <BR>
<OL>
<LI> Download the file.
<LI> Unstuff the file.
<LI> Double-click on the installer icon.
</OL>

<PROCEDURE ID="install">
<TITLE>Installing the software</TITLE>
<DESCRIPTION>To install this release, perform the following steps:</DESCRIPTION>
<LINK TYPE="steps"
      <TARGET ID="download"/>      <TARGET
ID="unstuff"/>
      <TARGET ID="execute"/>
</LINK>
</PROCEDURE>

PML is written in Extensible Markup Language (XML) [Bray, 1998], a language for describing other markup languages. XML is a simplified version of Standard Generalized Markup Language (SGML) [Sperberg-McQueen, 1993], an international standard for creating structured documents. A markup language is essentially a set of tags that an author uses to describe parts of a document and a document that uses these tags is one kind of structured document. Currently, the most well-known markup language is HTML which contains tags like <TITLE>, <H1>, <IMG>, etc. While these tags are useful for describing basic document structure, they do not describe the content of a document very well. More powerful and most likely domain-specific markup languages are needed for this purpose and XML was developed as a common way to define these different markup languages. XML, however, has utility far beyond the World Wide Web; it can be thought of as a platform-independent way to represent knowledge in a machine-readable format. XML has already been used to specify markup languages for dozens of applications ranging from chemistry to electronic commerce [Cover, 1998]. Having a common way to specify these markup languages allows tools to be built that can work with any of the languages specified in XML. For example, we have developed a PML-to-HTML translator that uses a PML parser. This parser is generic, however, understanding XML and therefore any markup language specified using XML.

The notation used in XML descriptions is fairly standard (see [Bray, 1998] for details). Each ELEMENT statement is a production rule with the first item being the left-hand side of the rule and the second item (in parentheses) being the right-hand side. Every element corresponds to a tag in the markup language. A vertical bar indicates a choice and a comma indicates a sequence. The plus sign stands for "one or more" and the asterisk stands for "zero or more." An ATTLIST statement lists the attributes for a particular element (i.e. tag). It specifies the type of the attribute and whether it is required (REQUIRED) or optional (IMPLIED). The complete specification of our PML language is given in Table 4. Appendix A contains an annotated example PML representation of a snippet of an everyday procedural domain: baking a cake.
 

<!---- Things ---->

<!ELEMENT thing   (title, (author | description | justification | link |
                 
appspecific | example | counterexample )*) >
<!ATTLIST thing           id  
ID   #REQUIRED>


<!---- States ---->

<!ELEMENT state   (title, (author | description | justification | link |
                 
appspecific | example | counterexample )*) >
<!ATTLIST state 
          id   ID   #REQUIRED>


<!---- Procedures ---->

<!ELEMENT procedure   (title, (author | description | justification | link |
                     
appspecific | example | counterexample )*) >
<!ATTLIST procedure 
          id   ID   #REQUIRED>


<!---- Cognitive Media Types & Identifying Information ---->

<!ELEMENT title          (#PCDATA | media)* >
<!ELEMENT author         (#PCDATA | media)* >
<!ELEMENT description    (#PCDATA | media)* >
<!ELEMENT justification  (#PCDATA | media)* >
<!ELEMENT example        (#PCDATA | media)* >
<!ELEMENT counterexample (#PCDATA | media)* >

<!ATTLIST description 
          type   CDATA   
#IMPLIED>
<!ATTLIST justification 
          type   CDATA   
#IMPLIED>
<!ATTLIST example 
          type   CDATA   
#IMPLIED>
<!ATTLIST counterexample 
          type   CDATA   
#IMPLIED>


<!---- Media ---->

<!ELEMENT media  #PCDATA>
<!ATTLIST media
          src      
CDATA    #REQUIRED
          caption   CDATA   
#IMPLIED>
 

<!---- Links & Targets ---->

<!ELEMENT link   (target+)> 
<!ATTLIST link
          type   (uses | is-a | has-a |
connects-to | related-to | 
   steps | precondition | outcome | problem-state | repair-procedure) #REQUIRED>

<!ELEMENT target  EMPTY>
<!ATTLIST target    
         
id            IDREF   
#REQUIRED>


<!---- Application-Specific Key/Value Pairs ---->

<!ELEMENT appspecific   EMPTY>
<!ATTLIST appspecific
         
key           CDATA    #REQUIRED
         
value         CDATA    #REQUIRED>
] >

  Authoring tools

In order to facilitate the authoring of PML documents, we have developed a graphical editing tool called tkPML that can be used to create the knowledge node/link networks graphically (see Figure 3). As might be expected, textual hand-authoring of PML structures can be tedious and mistake-prone. The tkPML graph creation interface replaces the task of entering the node and link information by hand with a point-and-click interface with form fill-in for the required text entry. We expect that this tool will help designers to better establish and maintain mental models of their PML representations.
 

In tkPML, nodes and links can be created and positioned with simple mouse actions, and the layout can be seen at various levels of detail to obtain an overview of large knowledge structures as well as a more informative view of a smaller number of nodes. Each node can be expanded to view and change the knowledge contained in it (see Figure 4).
 

 
The tkPML tool saves a PML description file in an augmented PML format file. The one addition is simply node location, which is not part of the standard PML definition and is saved as a comment. Thus, designers can edit the saved files by hand or run presentation interpreters on the files without modification. In addition, tkPML can import files written in PML, even files that were not created using tkPML. For such files, tkPML uses a simple graph layout algorithm to generate an initial display.

As the name suggests, tkPML is written in Tcl/Tk, a platform-independent graphical scripting language that can run on Unix machines, PCs, Macintoshes, and within browsers over the World Wide Web [Ousterhout, 1994]. This allows PML representations to be exchanged and edited by users on different platforms and even published on the Web.

Presentation tools

In order to create a presentation based on a PML document, one may develop a PML interpreter-generator that can interpret PML descriptions, retrieve the appropriate media in those descriptions, and create a hyperlinked presentation based on the situation and needs of the user. For example, if a novice user is considering whether to call a plumber to repair a leaky shower, the system need not display all the details of the repair procedure but instead may choose to summarize the time, expertise, and tools necessary to perform the procedure. If the same user has previously repaired a leaky faucet, the system may display an overview of the repair procedure (the top-level steps) and provide links to the substeps that are different from the previous procedure with which the user has experience. Truly interactive and dynamic multimedia systems will need such capabilities, and PML is designed to support the development of such systems. The PML interpreter-generator would need to be based on principles of instructional and interaction design.  PML is designed to support experimentation with such principles.

Alternatively and more simply, one may develop a PML interpreter that can construct a small number of predetermined presentations (such as one that always displays substeps in detail and another which always displays substeps as titles with links to the details) and use a simple heuristic to decide which presentation to use. We have chosen this approach for our initial implementation in order to test PML representations. Specifically, we have developed a PML-to-HTML translator that can create presentations based on simple, predetermined presentation rules (see Figure 5). This allows us to experiment with PML and gain knowledge that will facilitate later development of a fully dynamic presentation system.

Both of the presentations in Figure 5 are designed to help the user unplug a toilet drain using an auger. The left presentation is aimed at a novice, and the right presentation is aimed at an expert. For the expert, the basic steps are presented with minimal explanation, but with links that lead to more information, if desired. For the novice, more introductory information is provided (not shown) such as what an auger is, and each step is expanded with its explanation and any examples available for the step. Both of these presentations assume a web browser on a personal computer as the target platform. If the target were for, say, a handheld personal computer (which might be more useful when working in the bathroom) or even an audio presentation, a different structure should be generated (e.g., the handheld should not have a long scrolling presentation, as does the novice presentation depicted in Figure 5).

4. Conclusions

Cognitive media roles have been used succesfully in educational multimedia systems for teaching graph algorithms in an undergraduate computer science course [Recker et al., 1995; Shikano, Recker, & Ram, 1998; Shippey, Ram, Albrecht, Roberts, Guzdial, Catrambone, Byrne, & Stasko, 1996], and Lewis structures in an undergraduate chemistry course [Byrne, Guzdial, Ram, Catrambone, Ram, Stasko, Shippey, & Albrecht, 1996]. PML has also been used for other tasks and domains; we are using it to represent cases of object-oriented design and programming [Guzdial 1997], and to encode process information about operations in an electronic assembly "Clean Room" [Realff et al., 1998]. While these earlier systems were not dynamic, they do illustrate the generality and value of the knowledge representation and the notational tools.

In our own research, we are developing PML-based systems to investigate cognitive issues relevant in the design of dynamic multimedia systems. More broadly, in a learning situation, the goals that students bring to the learning task will affect their learning processes [Ram & Leake, 1995] and therefore a hypermedia support system for learning should have the capability to adjust itself in response to the user's goals. PML allows us to examine these issues empirically. For example, we would like to conduct systematic experiments that look at what factors actually play a role in the effectiveness of different presentations to the user or learner. For instance, is it really the case that a "high-level" presentation of a procedure for a more knowledgeable person is more effective (measured, perhaps, in how well the person can do the procedure and how long it takes, counting presentation time) than providing him or her with all the details? In order to empirically answer questions such as these, we need a system capable of creating alternative presentations of some underlying information, which is precisely the goal of PML.

Acknowledgements

References

** JS - MANY REFS FROM THE BODY ARE MISSING HERE.

T. Bray, J. Paoli, C.M. Sperberg-McQueen, Eds. (1998). Extensible Markup Language (XML) 1.0. W3C Recommendation 10-February-1998, http://www.w3.org/TR/REC-xml-19980210.html.

M. Byrne, M. Guzdial, P. Ram, R. Catrambone, A. Ram, J. Stasko, G. Shippey, & F. Albrecht (1996). The Role of Student Tasks in Accessing Cognitive Media Types. In Proceedings of the Second International Conference on the Learning Sciences, Evanson, IL.

R. Cover (1998). XML: Proposed Applications and Industry Initiatives, http://www.sil.org/sgml/xml.html#applications.

S. Feiner, K. McKeown, (1991) Automating the Generation of Co-ordinated Multimedia Explanation. IEEE Computer, 24(10), pp. 33?41.

M. Guzdial (1997). Technological support for an apprenticeship in object-oriented design and programming. Proceedings of the OOPSLA'97 Educators Symposium. Atlanta, GA, ACM. Accepted.

M. Maybury (1993), ed. Intelligent Multimedia Interfaces, MIT Press.

J.K. Ousterhout (1994). Tcl and the Tk Toolkit, Addison-Wesley Publishing Company.

A. Ram & D.B. Leake (1995). Goal-Driven Learning. MIT Press/Bradford Books.

M. Recker, A. Ram, T. Shikano, G. Li, & J. Stasko (1995). Cognitive Media Types for Multimedia Information Access. Journal of Educational Multimedia and Hypermedia, 4(2/3):185-210.

T. Shikano, M. Recker, & A. Ram (1998). Cognitive Media and Hypermedia Learning Environment Design: A GOMS Model Analysis. International Journal of Artificial Intelligence and Education, 9(1), in press.

G. Shippey, A. Ram, F. Albrecht, J. Roberts, M. Guzdial, R. Catrambone, M. Byrne, & J. Stasko (1996). Exploring Interface Options in Multimedia Educational Environments. In Proceedings of the Second International Conference on the Learning Sciences, Evanson, IL.

C.M. Sperberg-McQueen, L. Burnard, Eds. (1993). A Gentle Introduction to SGML. In TEI Guidelines for Electronic Text Encoding and Interchange, Text Encoding Initiative, Chicago, IL. http://www-tei.uic.edu/orgs/tei/sgml/teip3sg/

M.T. Realff, T. HŸbscher-Younger, et al. (1998). Multimedia Support for Learning Advanced Packaging Manufacturing Practices. ECTC'98, IEEE.

Tomek, I., Maurer, H., Nasser, M. (1993). Optimal Presentation of Links in Large Hypermedia Systems. Proceedings of ED-MEDIAÕ93, pp. 511?518. See also http://www.hyperwave.com

Appendix A