<<< Monday, November 22, 2004 11:42 PM


Wednesday, November 24, 2004 11:00 PM >>>

solving bongard problems

Monday,  11/22/04  11:52 PM

I found a great site from Harry Foundalis about his Research on the Bongard problems.  What's a Bongard problem?  Well, here's one:

These problems were devised by the Russian scientist M.M. Bongard in 1967, as a test for automated pattern recognition systems.  Each of the 100 problems consists of two groups of six patterns.  The boxes on the left each conform to some rule, while the boxes on the right are counter-examples to the rule.  The problem for the automated pattern recognizer is to determine the rule for each problem.  Can you find the rule for the problem above?  Click here for the answer

Okay so that one was pretty easy - for a human - what about this one?

Do you see the rule?  I've worked with these quite a bit so I see it right off, but it might not be obvious.  Click here for the answer.

Okay, now for a pretty hard one.  What's the defining rule for this one:

Pretty tough, eh?  Just when you think you have it, you find one of the patterns on the left doesn't match, or one of the patterns on the right does.  Anyway click here for the answer.

I finally, some of these are maniacal, consider this one:

It would be pretty tough for an automated pattern recognizer to figure this one out!  If you give up, click here for the answer.

Harry Foundalis actually developed software to parse and analyze these figures.  It is a tough problem; first you have to get from pixels to lines, shapes, etc.; just the representation is tough.  Then figuring out the set of all possible rules is really hard - the set is almost infinite - and winnowing down the list to the rules that match on the left and don't on the right is pretty tough.  To date his program can solve about 20 of the hundred, including the top two above.  Pretty impressive.

The rule is "isocoles triangle".  Click to return to problem.

The rule is "convex".  Click to return to problem.

The rule is "dots on same side of neck".  Click to return to problem.

The rule is "ends are parallel". Click to return to problem.