From: Beltran Ibarra Davila-Armero (bida@cs.washington.edu)
Date: Sun Dec 05 2004 - 23:23:09 PST
PROVERB : the probabilistic cruciverbalist
By GregA.Keim,NoamM.Shazeer,MichaelL.Littman
This article describes how the authors have created a crossword solver,
PROVERB, by using AI techniques and other features, such as expert
modules, and its results.
I think the authors dealt with several good ideas all along the article.
First, I thought it was interesting the way they analysed the crossword
problem through the different categories of clues, the novelty of these
and the increasing difficulty, as in the NYT. Afterwards, a major axis
of their work was the expert modules part. In fact, they calculate lists
of possible words for the targets with a probability, for each of the
words in the lists, of being the right one,. By doing this they have
different ways of finding possible words which, I think, is a good way
of dealing with the problem of having different types of clues. The
authors did a description of each of the modules. Finally, another
important point of the paper was the explanation of how they merged all
these lists to come up with a grid and the results of their
experimentation. We see how they used different AI techniques and that
their crosswords problem solver has quiet good results even though it is
far from being competitive with human crossword champions, especially in
terms of speed.
I thought that this paper didn�t have many flows as it was the
description of a system that worked quite well. The experimentation
seems to be correct as they tested PROVERB in two different situations
to see how it would react. But nevertheless, some points needed some
more explanations (maybe they didn�t want a too long article). I thought
they should have explained more how parameters are found in the merging
lists part. They quote the hill climbing search to find the spread, the
scale and the length-scale but they never say in which state space they
search, for example. We don�t really know what those parameters are and
how they find them. Another flaw is the explanation of the modules. The
authors go through an explanation of all the modules but in fact they
don�t really go into depth. As I think that these modules are the key
fact about this article, maybe some deeper explanations would have been
welcomed.
One open question on the topic is the evolution of hardware. As they
stated, their crossword solver is far from being fast enough compared to
human crossword champions and that could come from the calculating
limitations. But the question is: with faster and larger memory
machines, would PROVERB be more effective or are there also algorithmic
improvements to do to in order to have a better solver? Another open
question is about the modules. As we saw that many of them came up with
the good word, could there be a way to know which module works better
for which type of clue and so reduce the calculating modules depending
on the clue type and thus reduce the calculation time?
This archive was generated by hypermail 2.1.6 : Sun Dec 05 2004 - 23:23:16 PST