From: Stephen Friedman (sfriedma@cs.washington.edu)
Date: Mon Dec 06 2004 - 11:36:05 PST
Review of _Proverb: The Probabilistic Cruciverbalist_ by
Greg A. Keim, Noam M. Shazeer, Michael L. Littman,
Sushant Agarwal, Catherine M. Cheves, Joseph Fitzgerald,
Jason Grosland, Fan Jiang, Shannon Pollard, Karl Weinmeister
The authors used a database of known puzzles and several expert
modules combined with a constraint satisfaction grid filler to produce a
crossword solver that could solve puzzles at the tournament level.
An important aspect of their solution was the modular approach
they took. They had several expert modules, and ablation tests showed
that no single module was the workhorse, and that there was significant
overlap. Using this approach allowed them to have a robust system and
split the work up across several people. The other important aspect was
the use of a probabilistic approach that allowed them to combine these
modules successfully into a single tool. This shows that probability is
a sufficiently powerful framework to combine several narrow domain
algorithms in order to generate a broad-coverage system.
The weakest part of this paper was probably the conclusion. It
would have been nice to see a better breakdown of where they used the
techniques listed as useful. They also suggest that this work shows
computer resources are sufficient to attack larger problems, but failed
to give any suggestions.
One open research question is what would be the best way of
merging candidate lists. They use an optimization algorithm on training
data, but there may be a better way. Good integration methods like this
could allow other hard problems to be broken up into more tractable
pieces, making solutions to these hard problems easier to see and
generate. Another interesting aspect covered in this paper was the
novelty measure of the elements of the problem. The novelty measure for
solution words was surprisingly low to me, and it would be interesting
to see if other hard problems that people are good at have similar
novelty trends. The importance of the CWDB in this problem with such a
low novelty characteristic leads me to wonder if having a good novelty
measure for a problem may suggest the power of a knowledge-base approach.
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 11:36:11 PST