From: Raphael Hoffmann (raphaelh_at_u.washington.edu)
Date: Sat Dec 06 2003 - 13:59:26 PST
"PROVERB: The Probabilistic Cruciverbalist"
by Greg A. Keim, Noam M. Shazeer, Michael L. Littman et. al.
[Summary:]
PROVERB is a system that combines various data sources and AI techniques to
solve crossword puzzles. The paper presents its probabilistic design and
analyzes its performace.
[Pros:]
PROVERB has a two-stage architecture that allows the combination of several
AI techniques (CSP, hillclimbing, ...) and makes the system very flexible.
New data sources can easily be integrated as "Expert modules" and the value
of each can be quickly determined by comparing the performance of using all
modules vs. all-but-one modules.
Additionally, applying probability theory to solving crossword puzzles is
definetly a creative approach. Thinking about the problem, one might first
try a simple and direct way of searching for solutions. However, I find that
their idea resembles the way humans tackle this problem: experienced
crossword puzzle solvers first check the words that are most likely to fit
according to prior experiences. This leads to solutions a lot faster.
[Cons:]
Not surprisingly, the performance of PROVERB depends heavily on the CWDB
database. The reason is that the same questions appear in crossword puzzles
over and over. This fact makes the system somehow weak and limits its
capabilities in solving new, unusual and hard cw puzzles.
Furthermore, the authors used crossword puzzles from various sources, e.g.
NYT, TV-Guide etc., and built a single system, PROVERB. However, as they
stated themselves, the difficulty of the crossword puzzles depends on their
source. I believe that the kind of questions is correlated with the source,
e.g. TV-Guide crossword puzzles might more often ask about actors, stars
etc., whereas the NYT crossword puzzles more often ask about Greek
philosophers or Jewish customs. Therefore, it could be better not to train a
single set of weights for the merging component of PROVERB.
[Future ideas:]
I am wondering what would happen if the authors made their software publicly
available. Most probably, NYT editors would try to fool the program by
exploiting some of its weaknesses: PROVERB can only be as good as its data
sources. Although the architecture is flexible by allowing the integration
of new data sources, that can be time-consuming and difficult. I believe a
solution would be to use the web as a data source. However, unlike Google
that simply searches for a site containing the specified words, we are now
looking for words with a specified length and whose appearance close to our
search string (question) is statistically significantly higher than overall.
As stated above, it might make sense to set PROVERB's parameters according
to the type of crossword puzzle. A classification of the puzzle bevore
trying to solve it could be advantageous.
This archive was generated by hypermail 2.1.6 : Sat Dec 06 2003 - 13:59:28 PST