Dan R. Olsen, Jr., Brett Ahlstrom, and Douglas Kohlert
Computer Science Department, Brigham Young University
Provo, UT 84602
{olsen,ahlst,dkohl}@issl.cs.byu.edu
This paper describes a tool called LEMMING (Learning Easy Maps to Make
Interesting New Gadgets) which allows new geometry based widgets to be created
by example. A major portion of most direct manipulation user interfaces consist
of interactive widgets of various sorts. These small fragments of interactive
behavior are composed together to form complex interfaces for a variety of
tasks. In almost all cases the model for these widgets is event based. That is,
a majority of the interactive functionality is based on the handling of input
events.
There are, however, some widgets which are geometrically defined. A prime
example being the scroll bar. Although the normal scroll bar does have event
behavior its primary model is the geometric manipulation of the thumb. The
position of the thumb is tied to the value being controlled by the widget.
Dragging the thumb changes the value. Changing the value, moves the thumb.
There are, however, a variety of other possibilities like those shown in Figure
1. One manipulates speed / direction. The other controls pan and zoom.
FIGURE 1. Geometric widgets
Current event-based tool kits provide little help for creating such
geometrically defined widgets. Programmers must, by hand, work out the geometry
and interactive behavior.
This paper describes a system for creating new geometry-based widgets by
example.
The model that we are using for a widget is that it consists of a presentation
part and a control part. The presentation part can be interactively changed by
a user. These changes must then be mapped to corresponding changes to the
control part. The application code can also change control data which the
widget must map to changes in the presentation part and then must update the
widget's display. The approach then is to provide general purpose mechanisms
for users to change the presentation and then automatically learn the mapping
between the presentation and the control.
To illustrate how new widgets are created, let us take the speed and direction
widget shown in Figure 1. Figure 2 shows three examples of the widget along
with the appropriate values controlled by the widget.
FIGURE 2.
Three widget examples
The designer would draw these three examples along with specifying the control
values for each example. The widget system then learns the relationship between
the arrow and the Direction value and between the oval position and the Speed
value. Once the relationships have been learned, a new widget can be generated
which has Speed and Direction as its control values and uses a highly
restricted version of the draw editor as its user interface. This restricted
draw editor can only drag objects that are not frozen and edit text that is not
a constant.
For purposes of our discussion the drawing of the widget will be called the
presentation data and the information on the right of Figure 2 will be referred
to as the control data. The widget creation tool must provide editors for both
presentation data and control data. Internally both presentation and control
data are represented in the same way.
A standard drawing program is not sufficient to serve as the presentation
editor. The reason for this is that the drawing must be constrained in how it
can be changed. The circle that forms the dial base must be fixed so that it
cannot be moved. The arrow must be fixed so that only its head can move and
that only along the perimeter of the circle. The small circle must be fixed to
move only along the shaft of the arrow. We have designed just such a draw
editor which allows users to readily define constrained movements without
complex equations or geometric constructions. This technique based on
parametric coordinate spaces is essential to our widget tool but is beyond the
scope of this paper. This technique will only be describe in general terms.
For our example, the arrow's position is defined in the parametric coordinate
system of the large circle. The parametric coordinate system of a circle is
polar, which means that the arrow's points are defined in terms of an angle and
a distance from the center. The small circle's position is defined in terms of
the parametric coordinates of the arrow. The arrow's parametric coordinates are
a Cartesian system with one axis along the arrow and one axis perpendicular to
the arrow. Our draw editor provides a natural interface for defining these
relationships that is not significantly more difficult than normal draw
editors. In fact other than the general nature of the coordinates (polar,
Cartesian or curved) of each object, widget designers are completely unaware of
what the actual coordinate values are.
Using the editors for presentation and control data the designer provides the
system with snapshots of presentation / control pairs such as those shown in
Figure 2. The algorithm first analyzes the presentation and control examples
independently to determine what has changed. This identifies the variable
information that must ultimately be linked between the two models to form the
working widget. In our speed/direction widget the presentation changes in one
of the parametric coordinates of the arrow head and in one of the parametric
coordinates of the small circle's position along the arrow. The control data
changes in the values of Speed and Direction.
Because the arrow is defined in the parametric coordinates of the dial (which
are polar) rather than in Cartesian coordinates, there is only one variable
(radial angle) when the arrow head is moved around the perimeter of the circle,
rather than the two which would be required for Cartesian-based drawing.
Because the small circle is defined in the parametric coordinates of the arrow,
it also changes in only one variable (along the shaft) regardless of the fact
that the arrow's position changes radically between the three examples.
Once the changing components of both sets of data have been identified, the
algorithm then learns mapping relationships between the presentation variables
and the control variables. In our example there is a linear relationship
between the arrow head position and the Direction control and there is a linear
relationship between the small circle's position along the arrow and the Speed
control. The algorithm also automatically learns the two coefficients for each
linear relationship.
Our map learning algorithm is general enough to work in Cartesian space but
there are serious problems in learning the maps and in constraining the
drawing. The pan and zoom widget in Figure 1 or a simple scroll bar could
easily be learned using a Cartesian rather than parametric drawing tool. To
learn the dial in Cartesian space would require learning sinusoidal
relationships between the (X,Y) position of the arrow head and the Direction
control. General sinusoidal relationships have four coefficients which must be
learned. This greatly complicates the learning algorithm. The relationship
between the oval position and Speed in Cartesian space is unlearnable for
practical purposes, as will be discussed later.
Once we have identified the variable parts of each side and the mapping
relationships that connect those parts, we have learned the heart of our
widget. To create a runtime version of the widget we combine a stripped down
version of the presentation editor with the mapping information.
As discussed earlier, traditional widget building techniques such as Motif [1],
Visual C++[2] or MacApp [3] are based on the handling of events and leave all
geometric issues to the programmer. Peridot [4] provides mechanisms for
creating the constraints among the picture components by example but provides
little help in connecting the visual components to application data. The
Peridot technique is in some sense related to the way in which we learn mapping
relationships but this connection is very distant. ThingLab [5] provides
mechanisms for visually creating constraints but the designer is required to
visually program the actual constraints and to work out the geometric
mathematics before building the constraints.
Juno [6] is much closer to the type of tool that we have built. Juno provided a
visual mechanism for defining constraints on drawings. The designer would not
need to understand or solve the underlying equations but would need understand
compass and straightedge style geometric constructions. The set of constraints
that Juno can handle is fixed and not easily extended.
Juno also only provided constraints between picture elements. As a drawing tool
rather than a widget design tool, it had no mechanism to tie pictures to
control data. The Juno approach was extended to widget design in GITS [7].
Additional constraints were added to tie pictures to data and an efficient
solver was added to overcome the numerical slowness of Juno. The complexities
of compass and straight-edge were still present, however, and the set of
constraints was even more rigidly limited than in Juno.
Our goal was to provide a widget builder which would not require the designer
to understand the underlying mathematics or geometry. It should be extensible
in that new kinds of relationships could be added to the algorithm and it could
be applied to a wide variety of presentations. This is in contrast with
Wolber's DEMO [8] system which only supports linear relationships. In this
paper we will focus on presentations which are 2D drawings in parametric
coordinates but the algorithm is in no way limited to that domain.
In discussion the implementation of our widget design system we will first
discuss the NIC data model and pattern language on which the algorithms are
based. The concepts embodied in this data model and its pattern language are
key to the widget learning algorithm. This data model provides the
extensibility in the kinds of presentations which can be used to learn new
widgets. This concepts and algorithms can be readily adapted to other data
models without difficulty. We next discuss the class of MapObjects which are
the heart of the mechanism for relating presentation variables to control
variables. This class provides extensibility in the kinds of relationships that
can be learned. This discussion is followed by the complete algorithm for
learning the mapping between the presentation and the control. Lastly these
techniques are assembled together in a working tool for designing widgets by
example.
LEMMING is implemented in NIC (Nucleus for Interactive Computing) which is
being developed as a comprehensive system for providing user interfaces to
information. This introduction only covers those portions of NIC which are
essential to LEMMING. For a more complete discussion of NIC the reader is
referred elsewhere [9]. The central concept of NIC is that, like Lisp,
everything in the system is represented in a single uniform data model.
Widgets, drawings, scripting language and user information are all represented
in the same data model. Also defined in this model is a pattern language based
loosely on unification which provides for general manipulation of data. These
two concepts are the heart of the map learning algorithm for creating widgets
by example.
As with Lisp, the NIC data model provides a set of primitive values. These
include long integers, floats, characters, symbols (as in Lisp) and an empty
value. Instead of Lisp lists, NIC defines an abstract class Object which is
defined in C++. Every object in NIC has an attribute part and an array part. In
the attribute part, component values are referenced by symbolic name.
As in Lisp, NIC defines a textual notation for its objects. For example, Figure
3 shows an object with the attributes A and Name and the values 1,George and 2
in its array part. This example is an object of class :NewCls. Attributes are
given with their names and values in square brackets. Array values are simply
listed in order without names. Note that the attribute Name has another object
for its value.
FIGURE 3.
Sample NIC object
There is a type Value which can hold any primitive or object. Most objects
store Values as their components which provides a data modeling capability
which is as flexible as Lisp.
The Object class does not define an implementation for objects. It only defines
the standard protocol for setting and getting attribute values and indexed
values. This puts a very flexible facade over very efficient implementations.
For example the Image class presents itself with all of its pixels in its array
part. In reality the pixels are stored in X image format for efficient display.
The built in push button object is a special NIC class where the attributes
Label and Action have special semantics. The point, however, is that given the
Object class interface, all of these kinds of objects can be manipulated in
terms of attributes and array indices without knowing how they are actually
implemented.
Our speed / direction widget uses parametric drawing for its presentation.
These drawings are defined as a set of special classes that know about drawing
and editing. We can have a very simple NIC view of a Line object such as
This view of a line describes the essential properties of the line including
its color and endpoint coordinates. The line objects in our draw editor are
somewhat more complex than this, but not in any ways that are important to the
widget learning algorithm. The Line class, however, in addition to is external
appearance as a NIC object contains a variety of functionality to draw itself,
perform mouse hit detection and other interactive chores. For our purposes the
NIC facade provides us with a uniform model the essential data values. The map
learning algorithm is based on this view of the data and is essential to the
extendibility of the algorithm.
In order to learn a map between the presentation data and the control data the
algorithm needs to learn a general description of each of the data objects. For
this we use NIC's pattern language. Only a brief introduction is given here.
More extensive documentation is elsewhere [10]. An object can itself be a
pattern. More general patterns can be created using don't care symbols (_). For
example, the pattern
[Age 24 ] )
Variables can also be added to patterns. A variable is a symbol beginning with
an exclamation point (!). For example the pattern
[Age 24] [ Weight 190 ] )
There is an additional pattern operation called modify. It works like matching
except that the object is changed by the variables rather than assigning to the
variables. For example if !FN = Fred and !LN = Smith and the example pattern is
used to modify the preceding data, the resulting object would be
[Age 24] [ Weight 190 ] )
The combination of the match and modify operations on patterns provide the
basis for a mapping between two objects. Take for example the objects in Figure
4.
FIGURE 4.
Objects to be mapped.
P is the presentation object and C is the control object. What we would like is
to link the X coordinate of the line's second point to the Location attribute
of the control data. The algorithm can do this with the two patterns shown in
Figure 5.
FIGURE 5
Identity mapping patterns.
Suppose that the Line object, P, changes its X coordinate to 20. The system can
then perform the presentation to control mapping by matching pattern P against
the new object P, which will assign the 20 into !V. It can then modify object C
with pattern C which will change the Location attribute to 20. If it was the
Location attribute that changed the process would be reversed to perform the
control to presentation mapping. This form of identity mapping between objects
is too restrictive for our needs but it is the foundation for the more complete
mapping algorithm.
When designers demonstrate new widgets they provide a set of snapshots of what
is wanted. The first step of our algorithm is to identify what varies among the
examples. Consider, for example, the three snapshots shown in Figure 6.
FIGURE 6
Examples to learn a map.
In this case the mapping between the X coordinate of the line's second end
point and the Width attribute in the control object is a linear mapping rather
than an identity mapping. The same is true of the Y coordinate and the Height
attribute. By comparing P1, P2 and P3 and also comparing C1, C2 and C3 the
system can generalize the snapshot objects into the patterns Pp and Cp shown in
Figure 7.
FIGURE 7
Patterns generalized from examples.
Since the mappings only require the variable parts of patterns the system can
prune away all of the constant portions of these patterns to produce the
patterns in Figure 8. The reader is referred to the pattern language
documentation for details of this pruning algorithm. The pruning step is not
required but significantly improves run-time performance on complex objects by
eliminating non-essential pattern information.
FIGURE 8
Pruned patterns.
The remainder of the map learning problem is to learn the linear mapping
between !P1 and !C1 and between !P2 and !C2. It is also a problem to learn that
!P1 is related to !C1 and not to !C2. A careful inspection of the examples will
show that such a linear map cannot exist but the algorithm must learn this
automatically.
There are a large number of ways in which variables in the presentation pattern
might be related to variables in the control pattern. Our examples have shown
the identity maps and linear maps. These maps must be two-way in the sense that
if either side of the map changes the other side must be recalculated and
modified to maintain the consistency. Examples of such mapping functions are
found in Figure 9.
FIGURE 9 Example mapping functions.
Each of these maps is invertable in the sense that P can be calculated from C
and C from P. What we need, however, is not a fixed set of such functions but
rather an open architecture for any such mappings.
In order to create an open architecture we define an abstract C++ class called
MapObject. This class has three methods which are important to our discussion.
These are:
The result of LearnMap is a confidence that a map of the desired type was
actually learned. If, for example a LinearMap object is given samples which are
not linearly related, LearnMap will return 0.0. If all samples are collinear it
returns 1.0. If the samples are close to linear then a value between 0.0 and
1.0 is returned depending on how close they really are. The computation and
meaning of the confidence depends on the particular class.
The method MapToPresent is invoked whenever the control variable is changed.
This will compute the presentation value from the control value using the
information learned by the map object. The method MapToControl will compute the
control value from a modified presentation value.
If we take the snapshots in Figure 6 and the patterns in Figure 8 we would have
the following lists of variable values:
An important question in demonstrational techniques is the number of examples
that a designer is required to create. In most cases this can be determined by
the number of unknowns in the mapping function plus one. If, as in the linear
map, there are two coefficients, any two pairs of real numbers will produce a
linear mapping. The LinearMap object requires at least three samples. Any two
of the samples define a line with the third sample confirming that a line
really is the appropriate choice. Any additional samples improve the estimate
of the accuracy of the map. One of the reasons that sinusoidal maps are not
used is that the equation "P = a sin(b C + d ) + e" has four coefficients. This
would mean that its map object would require 5 samples to confirm that a
sinusoidal map is consistent with the data. This is generally too many for
users to tolerate or to enter accurately.
Based on the MapObjects we now can define a complete interactive map as
consisting of
FIGURE 10 Complete data mapping.
The mapping algorithm then is
Match pattern P against object P
Run all maps using MapToControl
Modify object C with pattern C
With the MapObject and the facilities of the pattern language we can now define
the complete map learning algorithm. The inputs to the algorithm are:
highest to lowest priority order.
The algorithm takes all of the Present data values and generalizes them into a
pattern using don't cares wherever the values differ. It then replaces all
don't cares in the pattern with variables beginning with "!P", and then prune
out all constant information. The same is done for the list of Control data
values using variables beginning with "!C".
In order to discover the maps between variables in the Present and Control
patterns the system must extract sample data. For each snapshot we match the
Present pattern against the Present data and the Control pattern against the
Control data. Using the examples in Figure 6 and the patterns in Figure 10 the
system produces the objects shown in Figure 11. Note that variables are used as
attributes. This is the variable storage model used by both match and modify.
Figure 11. Variable values for snapshots.
The map learning algorithm then is as follows:
This algorithm compares all variables on the presentation side to all variables
on the control side using all possible mappings. The fact that this algorithm
is where N is the number of variables and M is the number of
maps, is not a problem. Because a widget with 20 variables would require at
least 40 examples to learn, the limiting factor on this algorithm is designer
patience rather than algorithm performance. It is rarely the case that a widget
requires more than 4 or 5 variables.
A cartoon of the interface for building geometric widgets is shown in Figure
12. Using the two editors, the designer creates snapshots and then presses the
"Learn Map" button to invoke the learning algorithm. The interface provides
feedback to indicate the success or failure of the process. Errors occur when
some variables end up without maps attached or when presentation variables end
up mapped to more than one control variable. This style of feedback is
acceptable for small examples. In more complex widgets the designer is informed
that there is a problem but is left with little help in determining what the
problem is.
FIGURE 12 Geometry Widget Builder.
What is needed is an indication of what the learned maps actually are. The
problem is finding mechanisms to convert the abstract information in the
presentation pattern back into something visual that the designer can
understand. As yet we have not solved this problem.
The output of the geometry builder is a special widget class constructed as a
stripped down version of the draw editor. Only the constrained dragging
facilities remain. When a user drags an unconstrained part of the object, the
Present-to-control mapping is run and when the control values are changed the
reverse is performed. The generated widgets can then be installed in NIC's
interface builder and used by interface designers as part of new interfaces.
The generated widgets behave programmatically in the same manner as the
built-in widgets in C++. The NIC interface system cannot really tell the
difference.
The problem of adequate feedback has been discussed earlier. There are two
additional problems with multi-way mapping relationships which need to be
addressed. They are multiple maps on the same variable and mapping objects with
more than two variables.
To illustrate this problem consider scroll bar in shown in Figure 13. It has a
single control value Cur.
FIGURE 13 Scroll bar widget.
Three examples where the white rectangle is moved while the Cur
attribute is changed will demonstrate this widget. The problem is that in the
presentation, there are two variables (the left and right X coordinates of the
rectangle) which both map to the same control variable. Let us suppose that the
end user interactively drags only the left edge. A match will be performed
which extracts the new value for the left edge and the old, unchanged, value of
the right edge. If the left edge map is run first it will change Cur to the new
value. If the right edge map is then run, it will change Cur back to the old
value.
This problem is overcome by checking presentation variables for change before
running the maps. Since the right edge variable does not change, the system
will not run that map. When the presentation to control mapping has been run
the system then runs all of the control to presentation mappings. This will
cause the right edge to change to correspond to the new value of Cur. Although
we allow multiple maps on a control variable we do not allow multiple maps to
apply to the same presentation variable since this would not make any sense in
our widget design environment.
The scroll bar is also an example of a more significant problem with our map
learning technique. In most cases a scroll bar does not operate between two
fixed bounds but rather between variable bounds. For example Cur might operate
between two other attributes Min and Max. If the Max attribute changes (such as
when new lines are added to a text document) the mapping of the current
location to the scroll bar position also changes. This would require a mapping
equation of the form
The first problem is that our simple algorithm for discovering
maps is not adequate because the equation defines a four-way relationship among
variables rather than a two-way relationship. A simple minded approach to this
problem is which for 5 variables is O(3125) which is doable
but significantly more expensive. A second and more serious problem is that C,
min and max can be bound in any permutation to Cur, Min or Max and still
produce a valid set of coefficients a and b. Exchanging the map
bindings of Min and Max will have no impact on the widget user. Exchanging the
map bindings of Cur and Max will mean that if P is interactively changed, Max
is changed rather than Cur. Solving this problem will involve more
sophisticated analysis of the examples than the current system can provide. We
pose it as a problem without a current solution.
Abstract
Algorithms are presented for creating new widgets by example. The basic model
is one of an editable picture which can be mapped to control information. The
mappings are learned from examples. The set of possible maps is readily
extensible.
Keywords
Widgets, Demonstrational Interfaces, Tool kit Builder, User
Interface Software
Introduction
Geometry-based Widgets by Demonstration
Overview of the Widget Learning Technique
Other Widget Building Techniques
Overview
NIC Introduction
Data Model
(:Line (10 20) (500 20) [Color Black]).
Pattern Language
( [Name ( _ "Jones") ]
will match any object which has Jones as the second element of the Name
attribute and has 24 as its Age attribute. Attributes which are don't cares are
omitted as well as any trailing don't cares in the array part.
( [Name ( !FN !LN ) ] [Age 24] )
will match any object which has a Name attribute with an object having two
array elements and has an Age attribute containing 24. If this pattern is
matched against the object
( [Name ( Dan Jones) ]
the match will succeed and the symbol Dan will be assigned to the variable !FN
and Jones will be assigned to the variable !LN. This is very similar to what
might happen if a Prolog clause were matched against a data object. The
generalization of objects into patterns and the assignment of values to
variables as part of the match operation are central to our map learning
algorithm.
( [Name ( Fred Smith) ]
Match assigns object values to variables. Modify assigns variable values into
objects. The two operations are converses of each other.Maps With Match and Modify
Generalizing Examples into Patterns
MAP FUNCTION OBJECTS
The Abstract MapObject Class
float LearnMap( PresentSamples, ControlSamples,
Accuracy )
Value MapToPresent (Value )
Value MapToControl (Value )
To create a new map of a particular type between two variables !P and !C, a new
map object is created. Lists of sample values for !P and !C are passed to the
method LearnMap along with a floating point number which indicates how accurate
the samples must be in order to the map to be successfully recognized. For
geometric maps this accuracy must be quite loose, since designers are not very
accurate in the inputs that they provide by drawing. Based on these two lists
of sample data, the MapObject will attempt to discover a map which is
consistent with the data. Any information about the map that is learned is
stored as attributes on the MapObject. An example of this would be the
coefficients for a linear map.
!P1: (6, 7, 4) !P2: (6, 10, 12)
!C1: (14, 16, 10) !C2: (12, 20, 24).
If we use an IdentityMapObj to compare !P1 and !C1 the LearnMap method will
return 0.0 because 6 is not remotely close to 14. If we use a LinearMapObj to
compare !P2 and !C1 it will also return 0.0 because there are no coefficients
a and b which will map values of !C1 to corresponding values of
!P2. If the LinearMapObj is used to compare !P1 to !C1 it would return 1.0 and
would set its attributes to be:
(:LinearMapObj [Present !P1] [Control !C1][a 0.5][b -1.0] )
Based on the MapObject abstract class a wide variety of maps can be implemented
as subclasses of MapObject. The map learning algorithm can use any MapObject
without knowing the exact map being learned.
Number of examples required
A Complete Map Model
Given the data in Figure 6 the algorithm can produce the map shown in Figure
10.
if the object P changes:
If object C is changed, then the reverse process is performed. This gives us a
general model for computing mapping constraints between two arbitrary data
objects.
A MAP LEARNING ALGORITHM
Discovering Patterns
Discovering Maps
1: ([!P1 6] [!P2 6] [!C1 14] [!C2 12])
2: ([!P1 7] [!P2 10] [!C1 16] [!C2 20])
3: ([!P1 4] [!P2 12] [!C1 10] [!C2 24])
For each presentation variable PV
{ For each control variable CV
{ LearnedMap = empty
For each map object MO in ascending order
{ CMO = copy of MO
if CMO.LearnMap( Listfor(PV),
Listfor(CV), accuracy)
> threshold then
LearnedMap = CMO
}
if LearnedMap != empty then
add LearnedMap to list of maps
}
}
, GEOMETRIC WIDGET BUILDER
Run Time
MULTI-WAY MAPS
Multiple maps on a variable
Mapping objects with more than two variables
P = a * ( (C - min) / (max - min) ) + b
