Review 2

From: Vaishnavi Sannidhanam (vaishu@cs.washington.edu)
Date: Mon Dec 06 2004 - 00:56:53 PST

  • Next message: Jiun-Hung Chen: "Review 2"

    PROVERB: The Probabilistic Cruciverbalist
    -------------------------------------------
                    By Keim, Shazeer, Littman, Agarwal, Cheves, Fitzgerald,
    Grosland, Jiang, Pollard, Weinmeister

    * One-line summary
    ------------------------
    This paper talks about the design and techniques involved in developing an
    artificially intelligent crossword puzzle solver along with an evaluation of
    how well it fares.

    * The (two) most important ideas in the paper, and why
    -------------------------------------------------------------
    The paper is very well written describing what each approach is and how each
    of these approaches (probabilistic modeling, candidate generation,
    information retrieval, dijkstra's algorithm etc) are used and why these
    approaches are needed/significant. The idea of using various approaches and
    finally getting an answer from all of them though not novel (because it can
    be seen in Ensemble method in decision trees) is very well used.

    The paper identifies that solving crossword puzzles is highly dependent on
    the database of words (or previous occurrences of words). Without this
    identification, PROVERB would have failed miserably. Hence, this is a big
    contribution to the field of developing artificially intelligent crossword
    puzzle solvers.

    The paper as it says in the conclusion section identifies many problems
    specific to the field of crossword puzzles like constraint satisfaction,
    board knowledge, speed, what words to solve first, how to search through the
    databases etc.,.

    * The one or two largest flaws in the paper
    -------------------------------------------------
    The main complain I have about the paper is the lack of a good evaluation
    section for all the modules they use and for each of the modules. It would
    have been better if they had some information as to how each module
    contributed in the puzzle solving and how varying weights for the modules
    would have affected the system. (This is basically how we looked at Othello
    and the heuristics in it for our mini project 1).

    It would have been better if the authors incorporated more of the machine
    learning techniques they talk about instead of using large databases for
    solving puzzles. Using of huge databases makes the reader question if
    solving crosswords is more a database problem than an AI problem.

    * Identify two important, open research questions on the topic, and
    why they matt
    ----------------------------------------------------------------------------
    -----------
    One important research question as told in the flaws section is to study how
    various machine learning techniques can be used to improvise the performance
    while database size remains constant or while it is reduced.

    Another thing that one could answer is if it would be possible to mimic
    human crossword champions and how they solve the puzzles. Do they put in
    more constraints to make the process of searching for a solution easier? Do
    they have particular experience with crosswords published in NYT as opposed
    to those in Reader's Digest? One can also ask the question, if mimicking
    human brain process could be extended to solve other kinds of crossword
    puzzles (like cryptic crosswords).


  • Next message: Jiun-Hung Chen: "Review 2"

    This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 00:56:59 PST