From: Craig M Prince (cmprince@cs.washington.edu)
Date: Mon Dec 06 2004 - 08:33:31 PST
PROVERB: The Probabilistic Cruciverbalist
By Greg A Keim, Noam M Shazeer, Michael L. Littman, et al.
This paper describes a system for solving crossword puzzles that relies on
a series of special purpose clue solvers whoes results are combined with a
grid constraint solver in order to optimize the solution to the crossword
puzzle.
One of the most important ideas presented in this paper was that the
system is able to leverage a tremendous amount of knowledge that is
available today and bring it to bear on the problem. These online and
offline databases of knowledge form a sort of "common knowledge" database
that is sufficient for this domain. The authors believe that enough such
information is becoming available that solving other AI problems may
benefit from this approach as well.
Another important idea from the paper was that they use a two-tiered
approach to solve the problem, first looking directly at the clues and
trying to solve them, then taking those solutions and trying to fit them
to the grid (and allowing for some further generation here). Although
perhaps not the most realistic, this does a good job of making the task
tractable. The idea of using specialized solvers seems similar to the
"ensemble of classifiers" idea from decision tree learning.
While this paper had many contributions there are some aspects where I
felt the work could have been improved. The authors system seems to have
been constructed in an ad hoc manner. They do not give very good intuition
into why their architecture is better that others and don't seem to
explore other architectures fully. This leads me to believe that there may
be better or more efficient ways to solve crossword puzzles.
One aspect of the paper that I felt was particular promising for future
research was that the authors currently "prime" the system by providing a
set of rules, expert solvers, and databases that they observe are useful
for crossword puzzles. Is there a way that given a set of databases the
expert solvers can be generated automatically and their usefulness
automatically be determined? That is, to try to take the human out of the
loop even more?
A second promising aspect for future research is to try to apply these
techniques to other areas besides just crossword puzzles. What is unique
about crossword puzzles are that the clues often contain puns, idioms, and
common knowledge. Can this approach be used for NLP to disambiguate these
cases. How about in automatic translation?
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 08:33:32 PST