PROVERB Review

From: Beltran Ibarra Davila-Armero (bida@cs.washington.edu)
Date: Sun Dec 05 2004 - 23:23:09 PST

  • Next message: Pravin Bhat: "review-2"

      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?


  • Next message: Pravin Bhat: "review-2"

    This archive was generated by hypermail 2.1.6 : Sun Dec 05 2004 - 23:23:16 PST