Paper #12 - Ambiguous Intentions: a Paper-like Interface for Creative Design

Paper:
Interactive Learning of Structural Shape Descriptions from Automatically Generated Near-miss Examples
(Tracy Hammond and Randall Davis)

Summary:
LADDER is a sketching language which lets developers structurally describe a shape in a way that can be recognized, displayed, and edited in their domain of choice. In a multi-domain recognition system, these descriptions can be automatically given as input to recognizers, exhibitors, and editors. When an incorrect number of constraints describe a shape, false positives (from too few constraints) and false negatives (from too many constraints) occur. Shape descriptions automatically generated from one example can be difficult and too vague, while descriptions created by hand can be time-consuming and too specific. The authors of this paper therefore propose a visual debugger which uses active learning to generate suspected near-misses (shapes which differ from positives examples by one stroke) for the developer to classify as either positive or negative examples.

The approach used requires a positive hand-drawn example and its description as an initial condition. Descriptions can either be generated automatically or written with syntax-checking. After conceptual errors are corrected, the system finds a description with a variable assignment that contains the fewest failed constraints. The user is then required to remove enough constraints to achieve shape recognition. Thus, the given example is guaranteed not to be over-constrained on the single example. In the case of general over-constrained testing of general examples, a complete list of true constraints on the initial sketch was generated earlier. Known constraints in a correct description are then taken by creating a list of constraints in the true constraints that are not true in an encountered negative example. For under-constrained testing of general testing, a list of possible missing constraints are created. Removed constraints are composed of related constraints which: already exist, are more general, and follow transitively from the description. Afterwards, each of those constraints are tested if they’re missing by adding the negation to its description.

Shapes are generated based on the new descriptions to the user and tested for being either positive or negative examples. In each instance, the description is modified by adding or removing more constraints, depending on the type of example encountered. After executing this process, a shape description which is neither over- or under-constrained is created.

Discussion:
It’s not easy to have a system correctly recognize a sketch, simply due to the fact that a target symbol is bound to have variety. Being able to encapsulate that variety correctly would ease that aspect for the system. Using a sketching like LADDER helps construct shapes so that designers can focus on constraining a shape just right, but it still seems like perfecting those constraints acts more like an art than a science. The procedure used in this paper takes a nice step in the right direction in trying to eliminate a shape’s constraints from being too over- or under-constrained, and that is what I found to be important in this paper. One fault mentioned by the author is the fact that it can be an expensive process, so the use of heuristics was employed to reduce that cost. From my prior experience with using LADDER, I think improvements could be made by removing constraints that can be compensated by more valuable constraints. An alternative solution…more heuristics?