Summary
Hammond and Davis are concerned with shape description languages and the way they are used by both human users and computer programs that automatically generate descriptions given a shape. The problem is that descriptions tend to either be over-constrained, in that the description is too specific to one particular example and not generalized enough, or under-constrained, that the description does not accurately capture all of the defining characteristics of the shape. The problem, then, is to create a system that can help the user identify both unneccesary and missing constraints using automatically generated near-miss examples, and having the user tell the learning algorithm whether the example is a positive instance of the shape or not.
The system starts with a hand-drawn shape and a set of constraints that provide a positive match for that shape. If the set of constraints is automatically generated from the shape, the match is guaranteed to be positive but lacks the flavor of capturing user intention. If the description is hand-written, user intention is captured, but the constraint list might not accurately reflect what the user intends. In either case, the set of constraints will probably need to be modified.
The authors start by removing constraints that are too specific (meaning the description is over-constrained). Constraints are tested by negating one constraint at a time and generating example shapes with that negated constraint. If the shape is said to still be a positive example of what the user intended, the negated constraint is said to be unneccesary and is discarded. Constraints that are needed will turn the generated shape into a negative example of the user's intention and will be kept. Shapes are tested for scaling and rotational invariance here, as requiring certain lines to be horizontal or a certain length is possibly an over-constrained description.
Second, the description is tested for being under-constrained by generating a list of possible constraints (using some heuristics and filters to keep the list to a reasonable size) that are not included in the shape description. Again, one at a time, the negation of these constraints is added and examples are generated. If the example is said to be positive, the constraint is truly not needed (the negation still held). If the example is said to be negative, the constriaint is needed (the negation was false -> not not -> true).
Shapes are generated using a set of algebraic equations that describe the shapes. The unknowns are solved using third party software (Mathematica). Once the system of equations is solved, the values can be used to draw the shape (if a solution exists).
Discussion
This is a pretty solid paper and is easy to understand. It doesn't feel like the authors have left out too much. One thing I am wondering, however, is the running time and storage requirements for the algorithm. The over-constrained case doesn't seem to be a problem because you're starting with a fixed set of constraints and pruning it. However, when adding constraints, even with the heuristic method, you're going to have a large number of constraints to add. Admittedly this is a heuristic, but is it a good one? Do the authors have any way to show that this does better than some other way? Even limiting the number to n^2, that's still n^2 systems of equations to solve, n^2 shapes to show to the user, and n^2 times the user has to say 'yes' or 'no'. Is that simply the price one has to pay to get a "perfect" description?
Overall I would like less "this is how we do it" and more "this actually works" out of the paper. How does the system do at generating final descriptions that work? How long does it take? How many constraints does it remove/add on average? It's a good idea, it sounds like, but is it worth it to me in the real world, or is it just something that's nice to talk about.
No comments:
Post a Comment