Chapter
25

Characterizing PBD Systems

Allen Cypher,
David S. Kosbie
and
David Maulsby

Introduction

We characterize PBD systems along the following dimensions:

• Uses and Users What is the application domain and who are the users?
• User Interaction How does the user interact with the PBD system to create, use, and modify programs?
• Inference Given the inherent ambiguity in inferring a generalized procedure from a limited set of examples, how does the PBD system select an interpretation for the user's demonstration?
• Knowledge What information can the system use in making inferences?

Uses and Users

Application domain

Intended audience

The expertise of the users is another factor that influences design. User expertise can be considered both with respect to the application domain, and with respect to the PBD system. It is interesting to note that most of the systems in this book assume experience in the application domain, although The Geometer's Sketchpad is intended for students of geometry, and Tinker is designed for beginning programmers.'

Systems also differ in their expectations of the user's expertise with the PBD system itself. Eager, for instance, is explicitly designed to be usable without instruction. while most of the other systems require some training or experience.

User Interaction

Chapter 8 (TELS) points out the practical value of designing for the incremental development and modification of programs. Given the great degree of inconsistency in real-world tasks that we consider "repetitive", it can be very useful to allow for constant interaction between the user and the program, so that there is no clear distinction between creating a program and using and modifying it.

Creating programs

Several systems offer alternatives to recording. In Tourmaline, the user presents a previously-created style to the system. And in The Geometer's Sketchpad, the user creates a program by making a geometric construction.

Guiding the generalization process

Data descriptions Whenever the user selects an object in a demonstration, the PBD system must determine why that particular object was selected, so that when the program is invoked in the future -- in a different context -- the appropriate object will be selected. A data description specifies how to select the appropriate object. The description might be "the rectangle created in the previous step", "the first word in the current document", or "a button named SEND". SmallStar has the user explicitly select a data description from a description sheet of predefined alternatives. A similar approach is used in Chimera's MatchTool 2, where the user specifies search properties by selecting them from a list. AIDE offers a search dialog which gives the user a fair amount of flexibility in specifying a data description. Chimera's macros by example facility infers several possible data descriptions and uses heuristics to select a most-likely interpretation, but the user can view the descriptions and select a different one. Peridot and Metamouse also choose a single interpretation, but they query the user in English before applying it. Eager chooses a single interpretation and presents it to the user by highlighting objects on the screen. Lantern [Lerner 89] chooses a single interpretation and performs it without asking, but then observes whether the user undoes the action.

Tinker offers an interesting alternative: it presents the user with an Object List which lists an object's name paired with its corresponding data description. The user can select an object by name, and at the same time see the corresponding data description that Tinker will use in place of that object.

Program constructs The systems in this book present a variety of interaction techniques for adding loops and conditionals to programs created by demonstration. Pygmalion has special commands for looping and branching. In SmallStar, the user inserts loops and branches manually into a previously recorded program. The Predictive Calculator, Peridot, Metamouse, Eager, Turvy, and AIDE all use inferencing to automatically detect the need for loops or conditionals. They differ in how they ask the user to verify these inferences.

Feedback

In addition to making users more aware of the inference process, PBD systems can give users some control by allowing them to turn inferencing on or off, to specify whether they want to be queried to confirm inferences, and to specify how confident they want the system to be before it makes an inference. Garnet offers the user some of these options. A further discussion of feedback can be found in Chapter 26.

The preceding discussion focused on human-computer interaction during the creation of a program by demonstration. We now turn our attention to the other phases of interaction with a PBD system: invoking, executing, viewing, modifying and debugging programs.

Invoking programs

Certain types of automation are only effective if their programs are invoked automatically when a certain situation occurs. Systems that maintain graphical constraints, such as Peridot, Chimera's constraint-based search and replace, Chimera's constraints from multiple snapshots, Geometer's Sketchpad, and Garnet's Lapidary are especially effective at automatic invocation. Whenever a constrained object is modified, constraints are invoked to maintain relationships. For instance, a program that keeps a line attached to a box in a drawing of an "org chart" needs to be invoked automatically whenever the box is moved. '

Chapter 21, "PBD Invocation Techniques", and Chapter 27, "Just-in-time Programming", offer further discussion of invocation.

Controlling the execution of programs

Users also gain control over execution if they are able to undo incorrect actions. Chimera and AIDE have infinite undo capabilities. Eager offers to save a copy of any document that it is going to modify.

Viewing programs

Modifying and debugging programs

One difficulty with modifying a program by demonstration is that later steps in the program may no longer be valid. Pygmalion accounts for this by allowing programs to be modified, but by then requiring that the remainder of the modified branch be re-demonstrated. In contrast, SmallStar and Chimera's macros permit any modification and do not check for validity.

Systems like Peridot and Tourmaline infer programs by looking at graphical or textual objects, and the user can modify the programs by editing the graphical or textual objects on the screen. This allows for program modification without the need for a visual representation of the script.

Inference

The alternative to asking for explicit abstractions is to infer the user's intent. An inference engine performs the actual computations involved in generalizing, and a knowledge base contains the information that the inference engine uses in its computations.

Inference engines

Peridot's inference engine examines its knowledge base of condition-action rules. If the condition applies to the current context, the user is asked if the rule should be applied. If so, the action part of the rule is applied, adding a graphical constraint to the procedure. For instance, the "centered-horizontally" rule has a condition which checks whether a newly-constructed rectangle lies within another rectangle, and if the margin on each side is about the same. The action part of the rule establishes a constraint so that the sides of the inner rectangle will always be located this fixed distance from the sides of the enclosing rectangle.

The Predictive Calculator keeps a history of all k-token sequences typed into the calculator (k is a fixed integer -- in the experiments described in Chapter 3, k = 4). Whenever the user types three tokens that match a previously recorded sequence, the Predictive Calculator predicts the fourth. Any sequence of digits is considered to be one token, representing a number, and any two numbers can be considered to match, since they might represent an input to the procedure. For instance, if the user types "7 X 12.4 + 9.6 =", the system will record the four-token sequences "7 X 12.4 + ", "X 12.4 + 9.6 " and "12.4 + 9.6 =". If the user later types "106 x 12.4", the Predictive Calculator will match this sequence with "7 X 12.4 + ", and predict " + ".

Metamouse analyzes each of the user's drawing actions individually, examining the state of the drawing before and after. All actions are assumed to have a goal of moving the mouse cursor (and any object attached to it) so that objects touch each other in a certain way; for instance, the user might drag a line to touch both top corners of a box. Metamouse represents the goal as a list of required touches. It generalizes from a single example, so it picks touches according to rules, rather than looking for the same touches re-occurring in multiple examples. The rules rank touches according to precision and causation, and the system guesses that the highest ranked touches are the intended goal. On the theory that more precise fittings are less likely to be caused by chance, it gives more precise touches a higher score. For instance, since a point-to-point touch has fewer degrees of freedom than a point-to-line touch, point-to-point touches are ranked higher. The other factor considered is whether or not the action caused the touch to happen. Touches that were caused score higher than those which held true anyway. Metamouse also records a history trace and matches actions when they appear to have the same goal. This enables it to predict loops or (when actions mismatch) discard a mistakenly inferred loop. It forms branches (and loop-exits) when it fails to achieve an action's goal, defaulting to alternative actions demonstrated by the user.

Eager's inference engine determines whether two or more commands fit into a regular pattern. It first checks that all of the commands have the same verb (e.g. "Cut Button"). Then, for each argument to the command, it consults the developer's knowledge base to see what properties of that argument can be used for a pattern. For instance, the argument to the Cut Button command is a button, and the HyperCard knowledge base states that the Name, Number or ID of a button can be used for a pattern. So if the user cuts a button named "A" and later cuts a button named "B", Eager can match the two Cut Button commands, because their Names fit into the pattern "A, B, C, ...".

Inferring data descriptions

Compound descriptors Suppose a user wants to select "all New England customers with small orders". For a PBD system to infer this concept, it might need to recognize the data description "all red rectangles that are less than 15 pixels high". One way to characterize capabilities of this sort, which is common in Machine Learning literature, is to specify whether the inference engine is able to infer conjuncts of features, or even disjuncts of conjuncts (see "Disjunctive Normal Form" in the Glossary). In this case, the data description is a conjunct: "Object with Type = rectangle AND Color = red AND Height < 15". Selecting "all East Coast customers with small orders" might entail selecting "all red, orange or brown rectangles that are less than 15 pixels high", which could be described as a disjunct of conjuncts.

Inferring program constructs

Iteration Iteration constructs can be classified as set iteration, iteration with a counter, and iteration until a condition is satisfied. SmallStar, Peridot and Metamouse support set iteration. Eager can infer set iterations, iterations with a counter, and some "repeat-until" iterations.

Conditional branches Conditionals allow a program to execute different code in different situations. They have traditionally been difficult to specify by demonstration, since it can be laborious to demonstrate each complete path through a program. Pygmalion, Tinker and Metamouse address this issue by allowing the user to postpone recording the "else" part of a conditional until that situation arises during the use of the program.

In Pygmalion, the user must foresee where conditionals will arise and explicitly specify an if-then-else operator at that point in the demonstration. Tinker automatically detects the need for a conditional whenever the actions in a new demonstration differ from the actions in the program, and it then has the user specify a predicate which will distinguish the new branch. Metamouse detects the need for a conditional when it fails to satisfy constraints. For example, suppose Metamouse predicts that the user will drag a line so that its endpoints touch two opposite corners of a box, but there is no box of the right size. Metamouse will tell the user that it cannot find a box and ask for a new action. It then forms a conditional, trying to find a box first, but doing the new action if that fails.

Arguments When a recorded procedure is invoked in a new context, it must establish bindings for the various objects in the program. In Peridot, the user specifies the arguments to a procedure in the same way as in a conventional programming language. An argument can be specified in Chimera's macros by example system by selecting an occurrence of the object in any of its graphical history panels and giving it a name. Arguments are then displayed in separate panels at the beginning of the macro window. In Mondrian and AIDE, objects selected prior to the start of a demonstration constitute the arguments to the demonstration, and the order of their selection is significant.

Multiple examples and negative examples

Felicity Conditions

Show all work Sometimes a user will not perform an action because the current example is fortuitously already in the desired state. For instance, a demonstration of a program which makes text bold and italicized might only include the "Make Italic" command if the current selection happens to already be bold. Such a demonstration violates the "show all work" rule, and makes it difficult for the PBD system to determine that the generated program should include a "Make Bold" command.

Be consistent Users are sometimes inconsistent in the order in which they perform the steps of a task, if the order does not affect the performance of the task. Nonetheless, this inconsistency is an added challenge for an inferencing system. Also, in cases where there are multiple commands which achieve the same result, users may use different commands from one demonstration to the next. Eager is capable of matching different sequences of navigation commands (i.e. commands for moving from card to card) that achieve the same effect. It is useful to note that non-trace-based systems, like Tourmaline, avoid these consistency problems altogether.

Correctness Users sometimes make mistakes during a demonstration. Most current systems require that the user performs the demonstration perfectly, although non-trace-based systems are unaffected by mistakes, as long as they are corrected. Possible remedies include an Undo command as in Chimera, detecting and removing error-and-fix combinations (see [Lerner 89]), and allowing the user to later edit errors out of the recorded demonstration, as in Chimera's graphical histories. Some machine learning algorithms can accept noisy data, but they generally require a large number of demonstrations as input.

No extraneous activity Users sometimes perform actions that are not incorrect, but that do not contribute directly to the goal of the task. For instance, users may make extraneous selections before making the appropriate selection and applying a command to it. It may be difficult for an inferencing system to detect and ignore extraneous commands.

Knowledge

Using knowledge to resolve ambiguity

• Rect-42 (the final pillar) is 40 pixels wide and 120 pixels high,
• Rect-40 (the first pillar) is "near" and to the left of Rect-42 and is 40 pixels wide and 120 pixels high, and
• Rect-39 (the enclosing square) contains Rect-42 and is 120 pixels wide and 120 pixels high.

• "40 pixels",
• "1/3 of its height",
• "1/3 of the width of Rect-39",
• "the width of Rect-40",
• "the width of the object created in the command before last", and
• "1/3 of the height of Rect-40".

• * "look for relationships between different parts of the same object",
• "look for relationships between the same parts of different objects",
• "the relationships 1/1, 1/2, 1/4, 1/3 are more important than other relationships",
• "relationships within an object are more important than relationships between objects" and
• "the proportional-relationship rule is more important than the within-object-relationship rule".

Types of information

• Information about user actions The main source of information for PBD systems is the user's demonstration. Typically, whenever the user performs an action, a description of that action is recorded in a history list. The description could be in scripting language or in an internal data representation.
• Most PBD systems work with high-level information that has semantic meaning for the application. For example: "Create rectangle Rect-42 with upper-left: (440,30), lower-right: (480,150)" for a graphical editor; and "Copy words 2 through 3 of line 1" for a text editor. The Predictive Calculator receives low-level information: it processes keystrokes rather than arithmetic commands. So instead of recording "(Add 4 1)", it records "4", "+", and "1". Triggers is unique in that it uses extremely low-level information -- namely, the bits on the screen. Tourmaline processes high-level information, but instead of recording user commands, it examines the final state of the text that has been formatted.
• Information about object attributes Any single description of a user action necessarily implies a particular way of interpreting that action. Since inferencing involves finding alternative interpretations, it is important for the PBD system to have access to additional information about the attributes of the action and the objects involved in the action. For instance, the attribute values of a rectangle could be "width: 40, height: 120, color: green", and a text selection could have the attribute values "Text: 'Meeting tomorrow', Font: Helvetica".
• Information about context In addition to information about the action itself, it can be useful to acquire information about the context in which the action occurred. Context includes information such as the global state of the environment (e.g. "Current paint color: red", "Current tool: eraser"), and information about objects "near" to objects involved in the action (e.g. "Text before the selection: 'Subject:'", "Objects intersecting the current object: Rect-39").
• PBD systems differ in the amount and kind of contextual information they consider when trying to interpret a particular object or event. To find relationships between objects, a PBD system might compare a parameter of the current command to the corresponding parameter in an earlier occurrence of that command, to all objects in the previous command, or to nearby objects in the current environment. Theoretically, the entire state of the environment before and after an action could be recorded as relevant context for interpreting the action, but this is generally not practical. Eager allows the application developer to specify what context should be used when looking for patterns for a given object. Chimera uses "Undo" and "Redo" to recreate the application state that existed when each of the commands was originally demonstrated, allowing the complete context to be examined during generalization.
• Information about the application domain Information about typical activities in a given application domain can be very useful for guiding generalization. For instance, Peridot has a rule to recognize "one rectangle nested inside another with the same size margin all around except at the top". This rule would be strange for a generic graphical editing application, but since Peridot's application domain is the creation of user interfaces, the rule is quite appropriate: it is common for windows and menus to have extra space at the top to accommodate a title. In contrast, the Predictive Calculator of Chapter 3 has almost no domain-specific knowledge about calculator sequences, and so it will learn meaningless sequences such as "1 1 + + 1 1 + +".
• General world knowledge A large part of the difficulty in inferring intent comes from the fact that users can interpret text as natural language and graphics as pictures. World knowledge, such as the fact that "Monday, Tuesday, ... are days of the week", or that "Jean Miller is the name of a person", can help systems detect patterns.
• Information about the user Analogous to information about an application domain, information about a user allows a PBD system to tailor its interpretations. For instance, a mail system could benefit from knowing that "this user considers messages from Jean Miller to be high priority", or that "this user always files messages from Jean Miller in the Miller folder". While this is the sort of information that current PBD systems produce -- that is, they could create programs that will flag messages from Jean Miller as high priority, or that will automatically file a message from Jean Miller in the Miller folder -- none of the current systems adds this sort of information to its own knowledge base so that it can be used in later inferencing.
• Inferencing knowledge All inferencing systems have some sort of rules which determine how they go about detecting patterns, as well as which patterns to detect. Most systems also have rules for rating the relative significance of different patterns. Rules need not be specified declaratively; they may be implicit in the procedures that implement the inference engine.
• Eager has an extensible declarative knowledge base of datatypes and pattern-matching predicates for them. For instance, the integer datatype currently has predicates to detect equality, increments or decrements by 1, linear patterns, and linear patterns within a fixed error. However, Eager's ability to detect set iteration is implicit in procedural code. Adding recognizers for other types of control flow would require modifying the program.
• Metamouse has heuristics for comparing the significance of different types of intersections, Chimera has heuristics for rating the likelihood of possible generalizations of a command, and Mondrian has heuristics for ranking the significance of relationships between objects. Peridot has declarative rules specifying possible graphical constraints between objects, when to infer loops and conditionals, whether an item is a constant or a variable, and how the interface should respond to the mouse. In Peridot, the rule order is hard-wired and heuristically determined.

Sources of information

When information comes from the user, we will be interested in the user interaction. For instance, Turvy accepts unsolicited advice, Chimera gets information implicitly from the user's construction lines (used in snap-dragging), and Peridot uses English queries to ask for confirmation.

Producible programs

Since we are ultimately interested in developing systems which help end users, any measure of a system's "producible programs" needs to be qualified by an understanding of whether users are able to effectively demonstrate these programs, and whether users do in fact want to create programs of this sort. Hopefully, the Test Suite in Appendix B will grow into a wide-ranging compendium of real-world tasks that end users want to automate by programming by demonstration.

Characterizing the Future of PBD

We look forward to seeing practical systems for programming by demonstration in the near future -- systems which strike a careful balance between ease-of-use and power, and which succeed in bringing the power of programming to end users.

Summary Sheets

System Summary

Uses and Users

Tasks within the domain:

Intended users:

User Interaction

Feedback about capabilities and inferences:

Inference

Types of examples:

Program constructs:

Knowledge

Implementation

Notable Features