LADDER, part 2

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

Summary
The authors present an extension of the previous version of LADDER, focusing on the refinement of constraints to ensure the shapes described are not overly specific or too general. Two types of constraint errors are considered, inclusion of an extraneous constraint and omission of a required constraint. More complex errors, such as substitution, are treated as a combination of both basic error types. Shape descriptions can be generated in two ways. The first is user description, in which the user inputs directly the constraints for a given shape. LADDER provides online debugging tools through auto-completion and marking syntax errors in red. Next, a sketch corresponding to the shape must be drawn, and if the sketch does not meet the constraints, it is assigned to the shape for which it fails the least constraints. Alternately, the constraints may be automatically generated by drawing the shape and allowing LADDER to generate all constraints seen in the sketch and heuristically pruning the constraints. Next, the shape description is examined for over-constraint. For each constraint a near miss is generated in which that constraint is false while all others hold. If the user believes the near miss represents the same shape concept, the constraint is overly specific and is deleted. Next, under-constraint is examined. Additional potential constraints are generated similarly to the generation of all possible constraints for automatic description generation, and are filtered to omit those that are directly derivable from the current set of constraints. To test if a constraint should be added, its negation is added to the constraint list and a sketch is generated. If the sketch is representative of the shape concept, the new constraint is not added as it would over constrain the description, while if the sketch is rejected the constraint is added as descriptive of the concept. For both methods, example sketches are generated by converting the set of constraints to a set of equations (along with some general rules about shapes) and the set of equations is minimized. In this equation, required constraints and optimal constraints are distinguished by weighting. Required constraints are those that must be true to be considered representative of a shape concept, while optimal are not necessarily true. If the minimization process fails or reports a high error, the shape is considered impossible and eliminated.