PROVERB: The Probabilistic Cruciverbalist

From: Anna Cavender (cavender@cs.washington.edu)
Date: Mon Dec 06 2004 - 10:20:18 PST

  • Next message: Stephen Friedman: "PROVERB Review"

    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.


  • Next message: Stephen Friedman: "PROVERB Review"

    This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 10:20:23 PST