Interactive Learning of Structural Shape Descriptions from Automatically Generated Near-miss Examples

Summary:

Hammond and Davis present a debugging system in LADDER for shape definition errors. Errors can be either syntactical or conceptual, where a syntactical error is an error within the definition expressions themselves, whereas a conceptual error deals with over- or under-constrained definitions. An under-constrained definition finds many false positives due to too few constraints, whereas an over-constrained definition has many false negatives by allowing only very specific instances of a shape to be recognized.

The paper does not go into depth on handling syntactical errors, but the GUI for LADDER notifies the developer of any syntactical errors by highlighting definition problems in red. For over-constrained errors, the system first needs to have a drawn example and a definition that positively recognizes that example. Once this is given, the system scales and rotates the drawn shape and asks the user whether the new shape should be positively recognized. The system removes constraints from the initial list if needed. Then, the system generates near-miss examples by looking at the remaining constraints and testing them one at a time. Each constraint is negated, and if the user indicates that the resulting image should be recognized, then the tested constraint is removed from the list.

For under-constrained errors, the system again requires a drawn example and a definition. A list of possible constraints is then generated for the image and the constraints are tested one at a time by adding the negation of the constraint into the current constraint list. If the new set with the negation constraint should be positively recognized, then the constraint is not added to the system.

To generate the shapes during the testing process, each shape is converted into a set of numerical features that can be used in equations to stretch, rotate, and translate parts of the shape.

Discussion:

Knowing that this system existed in LADDER before I started creating my shapes would have been helpful. The idea behind eliminating or adding constraints is relatively simple, since constraint and not constraint cannot both exist in a definition.

Yet, after working with LADDER, I have found that one of my most frequent errors is not with over- or under-constraint, but more with the constraints themselves. For instance, when drawing a rectangle, I want the endpoints of lines to be touching or close to touching. But I cannot edit the value for "close", so instead I have to either force the user to draw a rectangle in a certain fashion so I know that the lines are connected, or I have to eliminate the close endpoints constraint. Both options are not optimal, and I'll experiment with the LADDER debugging system to determine if the system finds new constraints I did not know existed.