Structure and Rules in Automated Multimedia Presentation Planning

1 Central Problems of Multimedia Presentation Planning

The automated creation of multimedia presentations contains a number of challenging and interesting problems. Given a collection of information to display, what is the nature of the process of designing a multimedia presentation? What information does the process start with and what does it produce? On what information are its decision criteria based?

·The first author was supported in part by Rome Lab­ oratory of the Air Force Systems Command and the De­ fense Advanced Research Projects Agency under contract no. F30602-91-C-0081. The second author was supported in part by Rome Laboratory of the Air Force Systems Command under RL contract no. FQ7619-89-03326-0001. The third au­ thor, a graduate student at the University of Nijmegen, Ni­ jmegen, The Netherlands, spent a research visit of six months at USC/lSI working on this project for her Master's degree. Views and conclusions contained in this report are the au­ thors' and should not be interpreted as representing the offi­ cial opinion or policy of DARPA, RL, the U.S. Government, or any person or agency connected with them.

Borrowing from the conceptually related field of auto­ mated text generation, one might consider starting with a text planner that performs the tasks of information selection and organization, and then add to that a pro­ cess that allocates the information to specific media for presentation. One may even hope that a single planning mechanism rather like a text planner will perform all three these tasks simultaneously; after all, it is dealing with the same information in all cases. Unfortunately, this appealing idea is not feasible. We argue in this pa­ per that such integration cannot work because since the information-to-medium allocation process depends upon the overall structure of the discourse, this structure has to be determined before allocation can take place.

This fact may seem obvious when stated, but it is a problem that bedevils many current presentation plan­ ning systems, and has caused them to make significant simplifying assumptions in some cases or to finesse the issue in others. Although the timing of application of multimedia rules has serious consequences for the con­ struction of multimedia presentation planners, we do not know of any work that solves the problem adequately. The process and timing of presentation rule application in WIP has only been described verbally (Andre, personal communication, April 1992), while the COMET reports we have seen are not specific on this point.

In this paper we argue the case as follows: first, we describe briefly the kind of background information re­ quired to perform flexible media allocation. Then we outline the need for the separation of planning and al­ location processes. Next, given this separation, we de­ fine Discourse Structure and Presentation Structure and outline the nature of the transformations from the for­ mer (which is pre-media) to the latter (which is media­ dependent), which can be quite significant. Finally, we provide two examples produced by a prototype media al­ location planning system to illustrate the points made.

2 Background

2.1 Presentation Planning: Art or Science?

If humans and computers are to collaborate easily and well, computers will have to master the art of felicitous multimedia communication. Just like people, they will have to know when and how most appropriately to use words, pictures, and diagrams, as well as how to inte­ grate different media into a coherent communication, since it is well established that different types of in­ formation are most clearly presented in different media [Dwyer 78, Thfte 83, Twyman 85].

Several research projects suggest that multimedia communication is a science, not an art: it can be cap­ tured in rules. The nature of such rules is an important question. If a system's rules are simply collections of states and actions that are not theoretically well mo­ tivated, the system may well work for some particular task, but its operation will be uninformative and, even­ tually, probably collapse under its own weight. On the other hand, if the rules are based on the principles of communication using accurate representations of perti­ nent aspects of media, data, and interlocutors, then the rules will probably continue to be useful, in some form or another, in future multimedia communication systems.

In this paper we argue for specific levels and types of representation as the most promising basis for rules for multimedia presentation planning. In particular, we ar­ gue that the planning process should convert a discourse structure - represented using intentional and rhetorical terms- into a presentation structure. We claim that the rules, to be appropriately general and powerful, should be based on very fine-grained features of four kinds of in­ formation that characterize the communication, the in­ terlocutors, and the situation. Although we make no ar­ guments here about the nature of the processes involved, we describe a prototype presentation planner that varies its output depending on delicate variations in features of the data to be communicated. This planner uses the kinds of representation features and other structures we believe are required for flexible , powerful, and theoreti­ cally interesting multimedia communication.

2.2 The Knowledge upon Which Rules Depend

Before describing the data structures and transforma­ tions, we outline the individual features of data upon which presentation building rules should be based.

In the simplest, most direct approach to multime­ dia presentation planning, the question of clustering and allocating information to appropriate media is han­ dled simply by fixed rules that specify exactly what medium is to be used for each particular data type, as in the following rule from the Integrated Interfaces system [Arens et al. 88]:

1. Ships' locations are presented on maps.

For generality, portability, and flexibility, this is clearly not a satisfactory solution. For this reason, most ap­ proaches generalize this type of rule by using features, instead of data types and media, in both sides of the rule. One possible generalization is:

• 1 '. Data duples (of which ships' locations are an example) are presented on two-dimensional media (such as maps, graphs, and tables) .

Another possible generalization is:

1 ". Data with specific denotations (such as spa­ tial location) are presented on media which can convey the same denotations.

Determining appropriate features upon which to base the rules is unfortunately not a simple mat­ ter. In an attempt to systematize the bewildering amount of relevant information, we surveyed several relevant fields, including some of the more theoreti­ cal literature on good presentation design [Thfte 90, Bertin 83, Thfte 83], recent studies in Psychology (Hartley 85, Fleming & Levie 78], Cognitive Science (Roth & Mattis 90, Mayer 89, Larkin & Simon 86], and Computer Science [Mackinlay 86, Wahlster et al. 92, Feiner & McKeown 90, Neal 90]. It was clear that the large number of parameters playing a role and their com­ plex interrelationships, makes it imperative that features be defined with care at the proper level of generality to ensure their successful interaction.

As a result of our reading, and after analysis of mul­ timedia aspects in business reports, instruction man­ uals, cookbooks, etc., we have identified and taxono­ mized four distinct collections of information features that play a role in the design of multimedia presenta­ tions [Vossers 91, Hovy & Arens 91, Hovy & Arens 90, Arens & Hovy 90] . These four classes of information are: characteristics of the information to be conveyed, charac­ teristics of the media at hand, the presenter's goals, and the perceiver's interests and abilities. In [Arens et al. 92] we describe a feature-based formalism for this informa­ tion, organized in an And-Or dependency network, and provide some examples of presentation rules based on these features . Some example features appear in the pro­ totype system rules below. One rather satisfying finding is that many of the rules governing presentations oper­ ate cross-modally; that is, the same rule can be used to control the analysis or generation of some aspect of both a diagram and a piece of text, when the right represen­ tation formalism is employed, resulting in a reduction of the complexity and number of rules [Arens et al. 92] .

Computational attempts to plan multimedia presen­ tations make clear that describing the information to be presented, the goals of the presenter, and the nature of the media and interlocutor merely as lists of features is too restrictive and simple to permit realistic displays to be created. The underlying intentional structure of the communication as a whole plays an important role. Different portions of the information presented support, elaborate upon, or contrast with other portions, and such relationships have to be taken into account dur­ ing presentation planning. Consequently, the presenta­ tion planning rules cannot apply solely to the features we identified above; they also have to take into account a more global view of the structure of the discourse. We next describe the nature of presentation planning based upon the discourse structure.

3 Discourse & Presentation Structures

In recognition of the importance of the structure of the communication, almost all multimedia presentation systems construct some sort of internal tree-like rep­ resentation of the presentation before actually produc­ ing any output . The WIP system (Wahlster et al. 92, Andre & Rist 92, Graf 92] plans a text/graphics descrip­ tion of the use of an espresso machine, starting with a database of facts about the machine and appropriate communicative goals, and using text and presentation plans to build a presentation tree. The COMET system (Feiner 88, Feiner & McKeown 90] plans text/ graphic presentations of a military radio using text schemas and pictorial perspective presentation rules. The AIMI sys­ tem (Burger & Marshall 91] builds a tree to produce pre­ sentations using text, maps, and tables about database information of military operations and hardware.

Considerable difference of opinion still exists about the nature of the presentation tree and the changes it un­ dergoes during planning. Is there one tree, which once built is read and possibly annotated by the media spe­ cialists but never fundamentally altered (as in COMET)? Or should it be dynamically constructed in collaboration with the media specialists, depending on what informa­ tion they can handle - in which case some complex co­ ordination is required to ensure that everything is indeed output (as in. WIP)? Or is it simpler to plan the commu­ nicative structure and then allow local reorganization by media specialists?

While we believe that the answer depends on the par­ ticularities of the presentation task, we find it probable that the simplest and most useful answer is to organize overall communication planning and media-specific pre­ sentation planning as a pipeline by maintaining a clear distinction between the intentional structure (which we call here discourse structure) and the presentational structure, and by viewing presentation planning as a pro­ cess that transforms the former structure into the latter using rules based on the features of data, media, and the interlocutors 1 . In this architecture, the information placed into the Discourse Structure by the Communi­ cations Planner is the minimum amount of information that has to be contained in the communication. The Presentation Planner is free to add to the Presentation Structure (a small amount of) additional material when its rules require so, usually the kind of material that supports the presentation itself, such as captions for fig­ ures. We do not anticipate the need for feedback from the Presentation Structure to the Discourse Structure.

This view results in the general conceptual architec­ ture of a preSentation system shown in Figure 1.

We define a Discourse Structure as follows:

1 Not surprisingly, the same simplification can be found in the text planning literature, where several researchers have argued for a distinction between what can be called text planning (using communicative intentions to construct a dis­ course structure) and sentence planning (using linguistically oriented knowledge about focus, theme, pronominalization, sentence length and organization, etc. to create input for the sentence generator) (Rambow & Korelsky 92] .

Discourse segment: A discourse segment is a tuple (name, purpose/relation, content), where:

• The name is a unique identifier for the segment.
• The purpose/relation is a communicative goal the presenter has WRT the perceiver's mental state. For example, the EQUATIVE relation represents the goal to indicate to the perceiver that the two dis­ course subsegments express the same information in different form, while the JOIN purpose/relation has no communicative semantics (no linguistic connota­ tions are implied in a discourse structure) .
• The content is either:
• o the semantic material to be communicated (usually "small" enough to be generated in lan­ guage using a single clause) . This material is usually a set of knowledge base assertions or a database fact; or
• o a single discourse segment; or
• o an ordered list of discourse segments.

Discourse structure: A discourse structure is a dis­ course segment which is not contained in any discourse segment and all of whose leaves (the innermost segments) contain semantic material to be communicated.

In our formulation, the discourse structure simply pro­ vides the basic organization of the information to be pre­ sented. It is neutral with respect to the media and layout of the eventual presentation.

The discourse structure relations are taken from our work expanding the relations of Rhetorical Structure Theory (Mann & Thompson 88], which holds that tex­ tual discourses are coherent only if adjacent segments are related according to the constraints imposed by a small set of relations such as PURPOSE (signalled in text by "in order to" or "so that"), SEQUENCE (signalled by "then", "next", etc.), SOLUTIONHOOD (no English cue phrase), and so on. We provide a taxonomy of approximately 100 relations in (Maier & Hovy 91] and an expanded taxon­ omy of over 170 in (Hovy et al. 92] . In the work reported here, however, the relations are used differently - to in­ dicate communicative constraints among portions of the discourse, not necessarily linguistic realizations (if any) of such constraints.

By applying its media allocation rules, the presenta­ tion planner transforms the discourse structure into a presentation structure, which we define as follows:

Presentation segment: A presentation segment is a tuple (name, purpose, medium, position, content),

where:

• A: Total Sales (absolute amount in Ktons): 120.1
• B: Total Sales (relative X over previous year): +10%
• C: Doa . Sales (absolute amount in Ktons): 87.8
• D: Doa. Sales (relative X over previous year): +3X
• E: Exp. Sales of Edam in 86 (abs. Ktons): 11
• F: Exp. Sales of Gruyerzer in 86 (abs. Ktons): 10.9
• G: Exp. Sales of Sbrinz in 86 (abs. Ktons): 8.6

Figure 2: Portion of data from cheese domain.

• The name is a unique identifier for the segment.
• The purpose is one or more communicative goals the presenter has with respect to the perceiver's mental state.
• The medium denotes the medium of presentation of the segment.
• The position specifies where in the overall presen­ tational layout the medium should appear in the presentation (see for example the layout algorithm of [Graf 92]).
• The content is a list of the semantic material to be communicated, taken from the leaves or branch nodes of the discourse structure.

Presentation structure: A presentation structure is a list of presentation segments in order of communication.

Once the presentation structure is complete, each pre­ sentation segment is sent to the appropriate medium gen­ erator, whose results are then composed by the layout specialist and presented on the screen .

4 A Prototype Media Allocation Planner and Presenter

In this section we describe examples of presentation plan­ ning in order to elucidate the nature and role of the various structures, the underlying features, the media allocation rules, and the process of applying them. We describe here one possible way to address the issue of timing media allocation rules. Our prototype system ap­ plies the rules to an existing predefined discourse struc­ ture and then creates a multimedia presentation of the information using graphs, bar charts, pie charts, and text . We further discuss the nature of the rules and de­ scribe how they encapsulate the information we outlined in [Arens et al. 92] and [Van Mulken 92].

This prototype media allocation planner operates over a collection of data regarding the domestic and expoert sales of cheese in Switzerland during 1986, taken from an annual banking report . An English paraphrase of some of the system's data appears in Figure 2.

4.1 The Prototype in Action: Example 1

In our design, the discourse structure would be built by a communication planner on being activated by the user or host system with one or more communicative goals of the form Describe entity X to the perceiver, or Mo­ tivate the perceiver to perform action Y using resource Z, where X, Y, and Z are database or expert system do­ main entities or processes. For more details on text plan­ ning see [Hovy 88, Moore 89, Maybury 90, Cawsey 90, Reithinger 91, Hovy et al. 92] .

Since however we have not yet built a communications planner and we are here interested primarily in the prob­ lem of media allocation, we activate our prototype media allocation planner with a hand-crafted discourse struc­ ture representing the communication to be made. An example discourse structure appears in Figure 3.

The ELABORATION relation holds between a nuclear concept and material providing more details about its parts, instances, specific details, etc. The EQUATIVE relation holds between two equivalent descriptions of the same underlying material. The JOIN relation holds among two or more blocks of material among whom no more detailed relation is found.

Since the allocation rules must take into account char­ acteristics of the information to be presented, the plan­ ner has to begin by applying them to the leaves of the discourse structure. Since, as we argue, the rules must also take into account the discourse relations and over­ all shape or balance of the discourse structure, they have to be applied while traversing the discourse struc­ ture. Combining these two requirements, one necessar­ ily arrives at a rule application procedure that traverses the discourse structure bottom-up, creating presentation structure nodes at the leaves of the discourse structure and then gradually filtering them upward until finally the entire presentation structure emerges at the root node. At any point during the discourse structure traversal, presentation information has been determined by the media application rules for the subtree beneath it, and the rules are applied to the node at that point and to the presentation nodes for the subtree. Earlier decisions may be, and often are, overruled by rules applied at higher nodes of the tree- i.e., when a more global view of the situation is available. Thus media allocation rules de­ pend crucially on the nature of the discourse structure relations. For example, it is possible to merge informa­ tion related by EQUATIVE into a single medium display, but not so when the relation is PURPOSE.

To make this clearer, consider the two EQUATIVE nodes of the discourse structure in Figure 3: though they are separated by several intermediate nodes and one level in the structure, their contents may be in­ termixed in the presentation, since the two EQUATIVE left hand sides both contain absolute numbers (of cheese sales, in Ktons) while the two right hand sides contain the corresponding relative changes (as a percentage of the previous year's sales). Given the similar nature of the information to be presented in the two cases, appro- In the example, as we move up the tree, Rule Rl applies to both EQUATIVE subtrees (since the leaf content is not identical), and hence presentation segments are created at both EQUATIVE relations. Subsequently, the presen­ tation segment for the rightmost EQUATIVE relation is filtered upwards to the top JOIN relation. Finally, when the traversal process arrives at the ELABORATION node, Rule R2 applies, and corresponding portions of the two lists of presentation segments are merged to form P 1 and P3, which then give rise to the two bar charts in Figure 5.

Whenever two or more presentation segments are bound by a relation and are not merged, a default rule creates a new presentation segment between them to state in a sentence the relation binding them. At present, the linking sentence is canned; it will eventu­ ally be generated by lSI's PENMAN sentence generator [Mann & Matthiessen 83] .

4.2 Altering the Data: Example 2

If the media allocation rules are to prove their worth, they must effect appropriate changes even with subtle changes in the data characteristics. In order to test our rules, we performed several trials by changing just one or two basic characteristics of the data in order to see what the resulting presentations would be. In general, we found the results satisfactory.

As mentioned above, in order to ensure the clearest presentation of information, the media allocation rules must be sensitive to the discourse structure as well as to particularities of the media and information itself. We il­ lustrate this in the following example. Starting with the same data as in the previous section, we changed one data characteristic, namely the value of node B, from a relative percentage ( + 10%) to an absolute amount (+10.9 Ktons). Given the sensitivity of the allocation rules to such characteristics, the merging of node B with node D cannot occur, resulting in two distinct presenta­ tion nodes. These two nodes remain unmerged through­ out the media planning process; they percolate up the discourse structure, until eventually they appear sepa­ rately in the presentation structure Figure 6 (Cf. Fig­ ure 4). The final presentation is shown in Figure 7.

5 Conclusion

In this paper, we recall that multimedia presentation planners require information to medium allocation rules based on very specific kinds of knowledge: the charac­ teristics of the data (including its organization into a discourse structure), the characteristics of the media at hand, the communicative intentions of the presenter, and the characteristics of the perceiver. We argue that the medium allocation planning process should transform the discourse structure into a presentation-oriented con­ struct we call the presentation structure by performing a bottom-up filtering traversal of the former . To illustrate the ideas, we outline a prototype planner that changes its output depending on subtle differences in the data to be presented. Two examples show how rules based on single data characteristics and discourse structure re­ lations successfully handle display requirements which fixed data-to-medium mappings could not .

The operation of the media application rules is clear from the example. In all cases, their actions move pre­ sentation segments from one level in the discourse struc­ ture to the next higher level, and eventually out of the root in the form of a presentation structure, which is linear. Operating (in the example) on .characteristics of the information (the data) itself and on the discourse structure relations, they perform three types of action:

1. create new presentation segments containing data,
2. combine presentation segments into new ones that then contain lists of presentation segments, and
3. simply copy lower-level presentation segments up the discourse structure.

Specifically, we note that the data characteristics that media allocation rules must consider include the dis­ course structure, which embeds data and the presenter's goals using purpose/relations, as defined in the paper. Without knowledge of the discourse structure, it is im­ possible to formulate rules that correctly distribute in­ formation among the available media.

Finally, we note that the explicit separation of Com­ munication Planning from Presentation Planning (and the accompanying separation of Discourse Structure from Presentation Structure), where the Presentation Planner is allowed to add material to the Presenta­ tion Structure that is not present in the Communica­ tion Structure, facilitates the separation of the various kinds of knowledge that play roles at various stages of the planning of multimedia presentations, and may help solve some of the difficult problems inherent to this task.