From: Anna Cavender (cavender@cs.washington.edu)
Date: Mon Dec 06 2004 - 10:20:18 PST
PROVERB: The Probabilistic Cruciverbalist
Greg A. Keim, Noam M. Shazeer, Michael L. Littman, Sushant Agarwal,
Catherine M. Cheves, Joseph Fitzgerald, Jason Grosland, Fan Jiang,
Shannon Pollard, Karl Weinmeister
One line summary:
This paper describes PROVERB, a computer system that can solve crossword
puzzles at a rate of under 15 minutes for a 15x15 puzzle with 95%
accuracy (not quite competitive with human champions). This is
accomplished through a solution generator that mergers probable results
from expert modules (including a large database of clue-target pairs, CWDB).
The two most important ideas in the paper:
Due to the nature of the problem (filling a grid of words using clues
that require knowledge of language, history, pop culture, etc.), this
project is ideal for combining several different ideas in AI such as
information retrieval, database search, and machine learning.
The authors took a unique approach by creating a decentralized
architecture where several expert modules (a database of clue-target
pairs from previous crossword puzzles, encyclopedias, thesauruses, and
movie, literature, and geography databases) guess the target for each
clue and return a weighed list and a confidence probability to a
solution generator that finds a best fit for all of the slots in the grid.
The one or two largest flaws in the paper:
The paper would have been stronger with an included discussion of the
broader impact of the work. The two major contributions listed above
seem like they could be applied to several other types of AI problems
where many different types of knowledge are required to solve a central
problem. I would have appreciated further discussion of the
responsibilities of each module and algorithms used to bring information
from each module together, but the length of paper was probably an issue.
The design of PROVERB, especially with the extremely large database of
clue-target pairs from old crosswords (up to 34% of new pairs are
expected to be in the database) seems to be a classic example of an
“expert system” pumped full of knowledge in a look-up style versus a
system that employs actual reasoning.
Two important open research questions on the topic and why they matter:
I wonder if the system could be made faster if it was designed to think
a bit more like a human. For example, the solution generator could
integrate its work with the expert modules by sending them more
information than just length. As it becomes more sure of the solution to
particular areas in the grid, the work of the experts could be reduced
if they new they were looking for words with particular properties (such
as word whose fourth letter is M). Also, if the solution generator was
equipped with a bit more intelligence, it might be able to eliminate
certain modules on particular clues. For example, the WordList-Big
module often generates over 100,000 words so it may be a costly
computation, but it is the predictor for only 0.1% of clues. Thus, this
module could be used only as a last resort rather than on every clue.
It would also be interesting to take the ideas from this paper and find
a similar domain where they could be applied.
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 10:20:23 PST