"Interactive Learning of Structural Shape Descriptions from Automatically Generated Nearmiss Examples"

by Tracy Hammond, Randall Davis

Summary

This paper describes a visual debugger of shape descriptions using active learning that automatically generates its own suspected near-miss examples.

A near-miss shape is a shape that differs from the initial hand drawn positive example in only one aspect. The debugging is done by classifying near-miss shapes as positive or negative to help correct overconstrained (constraints too tight) or underconstrained (constraints too loose) descriptions.

This approach needs a positive hand-drawn example and a user-typed description that will correctly recognize that shape. Then a recognizer is generated using the description. If the known to be correct example is not recognized, the description must be overconstrained. And it's corrected by first finding a match between the typed description and the drawn shape that has fewest failed constraints. The system shows those failed constraints in red and asks the developer if they could be removed to correct the description. If the description is automatically generated, the list of constraints could be quite long, so the authors applied a set of heuristics to prune the list.

The initial hand-drawn example and the initial description may be both overconstrained although the example can be recognized with that description. So they use a constraint candidate list. Each time a positive example shape is encountered, any constraint not true of the new example is removed from the list. They also generate a list of constraints known to be part of the correct description by examine the negative examples. Each time a negative example shape is encountered, a list of the constraints that are in the constraint candidate list but are not true of the negative example shape is constructed. At least one constraint in this list is part of the correct description, because it correctly classifies the new example as negative. For scaling and rotation, the developer is asked to indicate the status of each example individually in the case of scaling, while he/she is permitted only to say whether or not all of the examples are positive for rotation. A constraint is tested by creating a description in which the constraint is replaced by its negation.

Under-constrained description is checked by making a list of possible missing constraints. As the list could be very long, the authors uses a filtering process. Whether or not a constraint is missing from the description is tested by adding its negation to the description. If the shape in which the constraint is met is a positive example, and the shape in which the constraint is not met is a negative example, then this constraint is necessary in the shape's concept.


Discussion

This paper talks about a positive learning approach to debug the shape description in LADDER in an interactive way. It is both efficient and necessary because human testers may never draw shapes that expose the bug in the description.