From: Keith Noah Snavely (snavely_at_cs.washington.edu)
Date: Mon Dec 08 2003 - 01:02:12 PST
"PROVERB: The Probabalistic Cruciverbalist", by Greg A. Keim, Noam
M. Shazeer, and Michael L. Littman, describes a system for solving
crossword puzzles.
The main contribution of this work is to present a system that
combines many different AI techniques to solve a difficult problem.
The method for merging information from different modules by learning
about the accuracy of each one is also interesting. I also liked how
well the problem of solving crosswords was analyzed (for instance how
the authors recognize that there are distinct categories of clues such
as fill-in-the-blank and movie trivia), and how the results of this
analysis were well captured in the resulting system. The success of
this approach is evident in the fact that PROVERB performs well on new
crosswords it sees.
I think that one reason why PROVERB does not outperform the best
humans is that it lacks the ability to think creatively. As the
authors mention, it cannot solve puzzles that don't adhere to the
normal rules of crosswords (for instance, when symbols other than
letters are allowed, or when targets can span multiple clues), nor can
it realize when it is being tricked. In my experience with
crosswords, I have a hard time with this too -- it often takes me some
time to realize that there is a trick, because the rules governing
crosswords are so standard. However, little clues -- such as target
spaces that seem to have one letter too few to contain the obvious
answer -- eventually make the trick evident. There is probably some
generalization of this phenomenon beyond crosswords; it seems that
humans usually operate with a set of assumptions that hold under
normal circumstances, but are sometimes flexible enough to realize
when an assumption is being violated (for instance, if an identical
twin posed as Dr. Weld in the 573 lecture, given enough time someone
would probably figure out the ruse). These kinds of boundary cases
pose a problem to PROVERB, and it would be interesting to think about
how to make it smart enough to identify both when it is being tricked
and what the trick is, and how these techniques might apply to other
problems, such as NLP.
Along the same lines, PROVERB probably does not do very well with puns
(for instance, in this week's Sunday NY Times crossword there is a
clue "When said three times, a crew member's fraternity? [3] = rho";
PROVERB might get this clue if it appeared in the database or if it
associated fraternities with Greek letters, but I don't think it would
try and make sense of the pun). Solving them requires creative
thinking about both the meanings and the sounds of words. It might be
that solving crossword puns is as simple as adding a module that
linked similar sounding words, but it seems that something smarter
would perform better.
Finally, is it really true that the time is ripe to revisit old
problems that were too hard with the available technology? Can new
research be done by combing literature from decades ago and finding
places where people gave up due to limited resources? Maybe, but
it is not clear to me that this would advance the field of AI very
much.
This archive was generated by hypermail 2.1.6 : Mon Dec 08 2003 - 01:02:13 PST