Automatic Documentation Generation: The Rnteraction of Text and Examples

1 Introduction

Good documentation is critical for user acceptance of any sys­ tem, and, increasingly, it comes in both conventional manuals as well as on-line facilities. These are often based on hyper­ text or similar retrieval methods. Advances in areas such as knowledge-based systems, Natural Language Generation (NLG) and multi-media now make it possible to investigate the automatic generation of documentation from the underly­ ing knowledge bases. This has several important ~nefits:. it is easily accessible; it avoids frequent problems of mconsis­ tency (as the information presented is obtained directly from the knowledge bases); and not the least, it can take the user, and the dialogue context into account.

Examples can greatly contribute to the effectiveness of documentation. Empirical studies have found that the inclu­ sion of examples in documentation can increase user com­ prehension, e.g., [Reder eta/., 1986], sometimes by as much as 100% [Charney eta/., 1988]. In order to provide useful documentation automatically, then, a system must not only generate good descriptions, but it must also provide examples. This raises at least two issues: (1) finding appropriate exam­ ples and (2), making effective use of them. While the first issue has been investigated previously, e.g., [Rissland, 1980;

The authors gralefully acknowledge support from NASA-Ames grant NCC 2-520 and DARPA contract DABT63-91-C-0025.

Rissland et al., 1984], the second one remains largely unstud­ ied. This is the issue we are addressing in our effort to build a user-oriented documentation facility for the Explainable Expert System (EES) framework [Swartout eta/., 1992].

Building on work in psychology, education, computational generation of examples and NLG, we are studying how text and examples interact with each other. In this paper, we argue that example generation should be considered an integral part of the documentation generation process, as examples must be integrated within the surrounding text. Indeed, psycholog­ ical evidence shows that badly integrated text and examples can be detrimental compared to using either text or examples alone, e.g., [Chandler and Sweller, 199ll. We present a text generation system that achieves this integration by planning a presentation (text and examples) taking into ~unt ~ele­ vant factors in the generation of these two rhetoncal devices. Finally, we present a specific example from our system, in which documentation about a specific programming language is generated.

2 Previous work and Open Issues

There have been considerable efforts in analyzing the type of examples that may be useful to present to the user (e.g., [Mich­ ener, 1978]), as well as in deciding whether an example should be retrieved or constructed, and on how to retrieve the appropriate example, e.g., [Rissland and Ashley, 1986; Rissland, 1980; Suthers and Rissland, 19881. Other work has focused on when to present examples [Woolf and McDonald, 19841. However, none of these studies looked at generating both text and examples, and thus did not look at the issue of ensuring their integration.

In NLG, researchers have used examples as one of the rhetorical strategies used to produce texts, e.g., [McKeown, 1985; Moore, 1989], but did not address the issue of choosing the examples to fit a specific description and integrating them into the text.

Finally, there is a large body of work on the use of examples in education, e.g., [Houtz eta/., 1973], cognitive science and psychology, e.g., [Reiser et al., 1985], and documentation, e.g., [Charney et al., 19881. Although much of this work is not immediately computationally applicable, it suggests constraints to take into account when generating texts and examples.

Our work builds on the work mentioned above and our own analysis of documentation material to develop a system that generates appropriate examples in the context of a surround­ ing text to form a coherent, well-structured presentation.

A UST contains zero or more pieces of data elements. Examples of lists are: (aardvark) (red yellov green) (2 3 5 11 19) (3 trench tries) ;; a list of one element ;; a list of several elements ;; a list can contain numbers ;; data elements can be of ;; different types

Given the three lists: ( 1 2), (3 4) and (5 6), the following is

also a list: ((1 2) (3 4) (56)) ;; a list can contain other lists

Figure 1: Using prompts to make explicit the infonnation contained in the ordering of the examples [Touretzky, 1984].

3 Interactions between Text and Examples

In order to identify the relevant factors in the interaction between text and examples, the system must consider at least the following points:

1. what should be presented through text, examples or both?
2. will there be one or multiple examples? If more than one example, how many? what infonnation should each one convey? How should they be ordered?
3. can the example cause additional text to be generated that may not otherwise have been presented?

To address these issues, example and text generation have to be considered together. For example, to decide which aspects of the presentation should be illustrated with examples, a sys­ tem must know the important features to convey. But, feature importance depends upon the context, and is based on factors such as the type of text (e.g., tutorial vs reference) and what the discourse is about. Much of this infonnation is important when constructing a text as well, and will already be available in the discourse planning context. A module for generating examples can thus take advantage of this infonnation.

The interaction actually goes both ways: a decision on which aspects of the infonnation are to be presented through examples affects the textual description as well. 1 Consider for instance, the following definition of the LISP concept list:

A list consists of a left parenthesis, zero or more data elements, followed by a right parenthesis. The data elements can be eilher symbols, numbers, or a com­ bination of these two types.

Compare this definition with that in Fig. 1. In the figure, the information that, above, is expressed in italics was instead communicated through examples.

Another source of interaction occurs when an example embodies more than one point, or when a group of examples illustrate a point together. In such a case, the system needs to generate a prompt (i.e., a marker focusing attention on the points being made; for example, the comments next to the examples in Fig. 1 are prompts). Since these prompts can be textual, they will also need to be planned by the text-planner. 1b plan them, the system needs to know not only what the examples illustrate but also what is implied by their ordering. Consider for instance, the definition in Fig. 1. The examples illustrate the fact that the data elements in a list can be of different types and in any number. The order of the examples is important as examples are introduced from simplest to most complex, each building on the previous one. In this case, the author chose to make explicit the infonnation that is implicit in the ordering of the examples and included a comment (a prompt) for each example.

1 Note that these issues are similar to the ones that arise in the planning and presentation of other explanatory devices - such as diagrams, pictures and analogies, e.g., [Feiner and McKeown,1991].

Furthennore, it might be necessary to include yet more text between the examples to ensure the coherence of the presentation, or in order to set up an example properly. This is also done in Fig. 1, where the three lists ( 1 2), ( 3 4), and ( 5 6) are introduced before the last example.

To generate coherent descriptions which include examples, the generation of examples must thus be tightly integrated within the generation process: text and examples must co­ constrain each other. In the next sections, we describe our documentation context, present a system that achieves the desired integration and illustrate it with an actual scenario.

4 Generating integrated explanations

Our system is . part of the documentation facility we are building for the Explainable Expert Systems (EES) frame­ work [Swartout et al., 1992], a framework for building expert systems capable of explaining their reasoning as well as their domain knowledge. In EES, a user specifies a domain model (in the high level knowledge representation language Loom [MacGregor, 1988]2), as well as problem solving principles, i.e., methods for solving problems in the domain. Given these and a variabilized goal to achieve, EES generates an expert system to solve goals of the same fonn.

The problem solving methods have to be written in a specific plan language, INTEND. INTEND is specified in the Backus-Naur Fonn (BNF), 3 a fragment of which is shown in Fig. 2. The grammar contains productions, and, option­ ally 'filter-functions' on the productions, i.e., tests that have to be satisfied (for instance 'pred-relation-fonn-test' on the pred-relation-:torm production). 4

The grammar of INTEND is quite complex, and thus pro­ vides a good test-bed for a documentation facility. With such an on-line facility, users can get infonnation as to what might be wrong when a plan does not parse, as well as descriptions of the various constructs involved, together with examples.

The documentation for the grammar symbol predi­ cate-:torm, whose BNF definition is shown in Fig. 2,is shown in Fig. 3. Consider the examples and the textual explanation in this figure. The first three examples are positive, while the fourth is a negative example (or counter-example). (All of the examples are from our domain of local area networks.) The mutual constraints of the text and the examples can be seen again in many places:

1. The examples illustrate features mentioned in the text, namely the syntax of the predicate-relation-form.

2 Loom is a KL-oNE type language.

3 For use by the generation facility, the grammar is transformed into an equivalent form in Loom.

.,-ransforming the BNF form to a Loom representation was a fairly straightforward task. However, the filter-functions on the pro­ ductions could not be extracted automatically. These were annotated by hand.

if-form : .. '( 'IF predicate-form 'THEN expression { 'ELSE expression } ') ; restricted-expression : .. var-name I concept-desc function-form I predicate-form ; predicate-form :- pred-relation-form I pred-logical-form I pred-action-form ; pred-relation-form :- '( relation-name restricted-expression + ') I > pred-relation-form-test ; pred-action-form :- action-form 1 > pred-action-test ; pred-logical-form :- '('AND predicate-form+') I '( 'OR predicate-form + ') I'( 'NOT predicate-form '); function-form :- '( relation-name restricted-expression + ') I> function-relation-form-test ;

1. The first three examples are introduced with 'back­ ground' text, to make sure they are understood as pos­ itive examples: "Examples of predicate-relation-forms are ... "
2. Because the positive examples are introduced with text, they occur together, rather than interspersed with the negative example.
3. The sentence "However, the following is not a . . . " is generated to make a contrast between positive and negative examples.
4. The negative example selected causes the generation of additional text both before and after the presen­ tation of the example. This is because the exam­ ple is not just not a predicate-relation-form, but it is also a function-form, a different (but similar) construct which can be contrasted with the predicate-relation-form. Additional text is gener­ ated first to introduce the negative example as a contrast to the positive ones, and then to explain the differences between the two similar constructs.

This scenario also illustrates the other aspects that have to be taken into consideration when generating integrated text and examples:

1. It is not enough to know the important features to con­ vey. The system also has to differentiate between vari­ able features and fixed features. Fixed features are those that cannot vary. In this scenario, the fact that a predicate-relation-form must begin and end with a parenthesis is a fixed feature. On the other hand, vari­ able features are those which can vary within a certain range in a positive example - in this case, the relation­ name is a variable feature. It is usually necessary to provide several examples to communicate the variable nature of the feature [Clark, 19711. In this case, several relation names are used in an attempt to ensure the user realizes their variable nature. On the other hand, it is not always necessary to explicitly state fixed features, as they will become obvious from examples.
2. The presentation order of the examples is especially im­ portant to communicate the critical features of a concept.

A predicate-form is a restticted-expression. It returns a boolean value, and the number of arguments in a predicate-form is equal to the arity of the relation. A predicate-form can be of three types: a predicate­ relation-form, a predicate-action-form, or a predicate­ logical-form.

A predicate-relation-form is a relation-name followed by some arguments. The arguments are restticted­ expressions, such as variables, concepts, function-forms and predicate-forms. Examples of predicate-relation­ forms are:

(IIDICATOR-ST!TE LED-1 OJ) (HARDWARE-STATUS L!IBRIDGE-2 FAULTY) (COllECTED-TO DECSERVER-1 VAl-A)

However, the following example is not a. predicate­ relation-form, but a function-form, because the number of arguments is not equal to the arity of the relation:

(COllECTED-TO DECSERVER-1)

The difference between a function-form and a predicate­ relation-form is that the function-form takes one less ar­ gument than the arity of the relation, and returns the range of the relation, while the predicate-logical-form takes as many arguments as the arity and returns a boolean value.

A predicate-action-form is ...

Figure 3: The documentation for 'predicate-form'.

Critical features are features which, if modified, cause the example to change from positive to negative. In this case, the relationship between the arity and the number of arguments is a critical feature. By contrasting the third and fourth example, which are identical except for the number of arguments, the pair highlights the crit­ ical feature. In general, examples should be pairwise maximally different if they are positive examples, and minimally different if they are a positive-negative pair [Feldman, 1972].

We now describe how our generation system can generate integrated explanations, and present a trace of the system as it generates the explanation presented in this scenario.

4.1 The Generation Framework

Our framework implements the integration of text and ex­ ample within a text-generation system. More specifically, we use a text-planning system that constructs text by explic­ itly reasoning about the communicative goal to be achieved, as well as how goals relate to each other rhetorically to form a coherent text [Moore and Paris, 1989; Moore, 1989; Moore and Paris, 1992]. Given a top level commu­ nicative goal (such as (KNOW-ABOUT BEARER (CONCEPT PREDICATE-FORM) ), 5 the system finds plans capable of achieving this goal. Plans typically post further sub-goals to be satisfied. These are expanded, and planning continues until primitive speech acts are achieved. The result of the planning process is a discourse tree, where the nodes repre­ sent goals at various levels of abstraction, with the root being the initial goal, and the leaves representing primitive realization statements, such as ( IIFORM .·. ) statements. The discourse tree also includes coherence relations [Mann and Thompson, 1987], which indicate how the various portions of text resulting from the discourse tree will be related rhetor­ ically. This tree is then passed to a grammar interface which converts it into a set of inputs suitable for input to a grammar.

~See the references given above for details on the notation used to represent these goals.

Plan operators can be seen as small schemas which describe how to achieve a goal; they are designed by studying natural language texts and transcripts. They include conditions for their applicability, which can refer to the system knowledge base, the user model, or the context (the current text plan tree and the dialogue history). Two of the plan operators used in our system are shown in Fig. 4. The first one is used to describe objects by describing a concept in terms of its parent and possibly elaborating on this description. The second one can be used to elaborate upon a description by describing the sub-types of a concept.

Using this framework, the generation of examples can be accomplished by explicitly posting the goals of providing examples while constructing the text, i.e., some of the plan operators include the generation of examples as ene of their steps. This ensures that the examples embody specific infor­ mation that either illustrates or complements the information in the accompanying textual description, and that the text to be generated will reflect the presence of examples. The con­ straints of the plan operators indicate how the text and the examples co-constrain each other. Because the same plan­ ning mechanism is used to plan the text and the examples, integration is achieved in a straightforward way.

4.2 A Trace of the System

We illustrate how our system integrates text and examples by working through the generation of the example shown in Fig. 3, that is, a description of a grammar concept for a non-expert user.

The system initially begins with the top-level goal: (KIOW-ABOUT H (COICEPT PREDICATE-FORM)). The text planner searches for applicable plan operators, and, finding the first plan presented in Fig. 4, 6 posts the two subgoals in­ dicated in the plan: one to give a make the hearer believe that (predicate-form) is a restricted-expression (its par­ ent in the Loom hierarchy), and another (optional) to provide more information (elaborate).

6 When several plans are available, the system chooses one using selection heuristics designed by [Moore, 1989].

At this point, the discourse tree has two on-­ expanded nodes: (BEL H (!SA PREDICATE-FORM REST­ RICTED-FORM)) and (ELABORATIOI PREDICATE-FORM). The planner expands the first subgoal by first indicat­ ing the concept-parent relationship ("a predicate form is a restricted expression'') and then informing the user of the attributes differentiating a predicate-form from a restricted-expression ("it returns a boolean value ... ").

The goal to elaborate upon a concept is expanded in turn. The plan chosen here is the one shown in Fig. 4, which presents the different types of predicate-forms that exist, namely predicate-relation-form, predicate­ action-form, and predicate-logical-form. Because these sub-types might be of differing complexity, and it is important to present the information from the sim­ plest one to the most complex one (according to the maxim of end-weight in linguistics [Werth, 1984]), one step of the plan operator explicitly orders the sub-types be­ fore presenting them to the user. This ordering is done based on some general complexity heuristics: in this case, predicate-action-formis considered more complex than predicate-relation-form because it is allowed to have an action-form(agoal-postingconstruct)as oneofitsargu­ ments. The predicate-logical-form is considered most complex because it is recursive in definition. After informing the user of the sub-types, goals to elaborate upon each of the sub-types are posted and expanded in turn. Each such elabo­ ration results in posting the goal of describing each sub-type. This portion of the planninf process is recorded in the skeletal text-plan shown in Fig. 5.

Let's consider the expansion of the goal: (KIOW-ABOUT H (COICEPT PREDICATE-RELATIOI-FORM) ). Unlike for the similar initial goal given to the system, the system does not pick the operator that defines the concept in terms of its parent, since the concept-parent relationship between a predicate-relation-form and a predicate-form has already been mentioned (since predicate-relation-form was introduced as a sub-type of predicate-form). In­ stead, a plan operator that describes the concept syntax is chosen. In this case, the syntax is: ( relation-name arguments+ ).

7 All the text plans shown in this paper are simplified versions of the actual plans generated: they do not show the coherence relations that hold between the text spans resulting from this planning, and the communicative goals are not written in their formal notation, in terms of the hearer's mental states, for readability's sake.

Instantiating the plan, the system realizes that it can de­ scribe the syntax by both text or examples (from the syntax definition, the system attempts to construct examples that match this syntax). The steps of the plan operator now com­ pute the parameters that determine what get explained via text, via examples or both. In this case, the system determines 8 that there is one critical feature, i.e., the number of argu­ ments in the predicate-relation-form must be equal to the arity of the relation, and one variable feature, i.e., the relation-name.

At this point, the system also determines that the parenthe­ ses do not need to be mentioned in the text as they will be mentioned in all the examples, are fixed-features, and more than one example will be presented. The system now has enough information to continue with the presentation plan­ ning process: it constructs the text: "a predicate-relation­ form is a relation-name followed by ... ",and posts a goal to generate examples. The plan chosen to achieve this goal posts the goal to generate text to introduce the examples for the variable features as background, the goal to generate the examples for the variable feature, and the goal to generate examples for the critical features.

The system picks two positive examples to illustrate the variable feature. In general, as mentioned before, adjacent positive examples must be as different from one another as possible. In this case, the system picks two different relations, II not equal to the ar1ty of the relation"

8 The system determines critical features and variable features by modifying the definitions and seeing whether an example of the modified definition becomes a negative example of the concept, using the Loom classifier.

Figure 7: Text-plan fragment for the generation of the exam­ ples for the critical feature.

and the first two examples are generated. This part of the text plan is shown in Fig. 6.

Now the system must generate an example for the critical feature, i.e., that' the number of arguments of a predicate-relation-form must be equal to the arity of the relation. Because this is a critical feature, the system decides to generate one pair of positive-negative examples to highlight the feature. The positive example of the pair will be presented first because the discourse tree shows that positive examples were already given and introduced with text. It is thus possible to simply give a new positive example without introducing it. To present the negative example, the system posts the goal of contrasting the positive example given.

There are two ways in which a negative example can be constructed in this case: by changing the number of argu­ ments from two to three, or from two to one. The system con­ structs descriptions of both types, and checks to see whether one of these is a known concept (this can done easily using the classifier in Loom). It finds that a relation with one argument is a construct in the grammar, namely a function-form. It thus uses that as a negative example, after posting the appro­ priate goal to generate text to introduce the example. It also posts a goal to elaborate with text on the differences between a function-form and a predicate-relation-form to ensure that the user is not further confused by the use of a (possibly) new term. The relevant portions of the text-plan are shown in Fig. 7.

The planner continues expanding goals in this fashion, un­ til all the goals are primitive speech-acts (such as IIFORM). Finally, the completed discourse tree is passed to an inter­ face which converts the IIFORM goals into the appropriate input for the sentence generator. The interface chooses the appropriate lexical and syntactic constructs to form the indi­ vidual sentences and connects them appropriately, using the rhetorical information from the discourse tree. For example,

5 Conclusions and Future Work

In this paper, we have shown how examples and text interact with and co-constrain each other. It is important to recog­ nize this interaction in order to provide an appropriate, well­ structured and coherent presentation to the user. We have also argued that a generation system capable of providing examples as part of its presentation must consider example generation as an integral part of the generation process. We have presented our documentation system which illustrates this idea.

While our system is already capable of generating inte­ grated text and examples, some issues remain to be studied. In particular, we want to investigate issues related to goal (and example) interaction at a more global level than cur­ rently done: that is, how can a system "re-use" an example that was given to illustrate a different concept in a previous part of the dialogue.