Paper Review

From: Annamalai Muthu (muthu@cs.washington.edu)
Date: Mon Dec 06 2004 - 10:16:26 PST

  • Next message: Anna Cavender: "PROVERB: The Probabilistic Cruciverbalist"

    Paper Title: PROVERB: The Probabilistic Cruciverbalist
    Authors: Greg A. Keim, Noam M. Shazeer, Michael L. Littman,
                    Sushant Agarwal, Catherine M. Cheves, Joseph Fitzgerald,
                    Jason Grosland, Fan Jiang, Shannon Pollard, Karl
                    Weinmeister

    Summary: This paper suggests an approach using which computers can
    solve crossword puzzles better than the average human. The approach
    utilizes large amounts of information (dictionary words, previous
    clue-target pairs) and probabilistic models.

    The important ideas:

    -At first sight, getting a computer to do something as complex as solving
    a cryptic crossword would seem impossible. But this paper suggests a very
    intelligent approach. They use expert modules to solve different portions
    of the problem, and then they combine the results. For example, one
    module solves the fill-in-the-blanks kind of clues, while another module
    would solve the synonym clues and etc. Each module tries to solve the
    clue in its own way and associates a level of confidence with the entire
    set of candidate solutions generated, and also with each individual
    candidate. The solution sets from each module are then normalized and
    merged. Techniques such as implicit distribution models add more
    candidates to the initial set of candidate solutions as more information
    becomes available. Though the approach suggested is put in context of
    crossword solvers, it can be used for very difficult problems. The key is
    to break the domain into pieces and solve each piece in its own efficient
    way, instead of solving everything using a unified approach.

    -The paper shows the manner in which different AI techniques have been
    wonderfully integrated. The approach uses constraint satisfaction,
    information retrieval, machine learning, natural language processing,
    state-space search and probabilistic optimization. The paper implicitly
    points out that the use of just one technique is clearly insufficient for
    extremely complex problems. We require a blend of a few AI techniques,
    and this paper shows a very good blend. Humans, while thinking, use a
    variety of techniques for reasoning and learning, and we can come close to
    that only through the correct integration of AI techniques.

    -Another takeaway point from the paper is that it might be smart to make
    use of vast amounts of information available. This implies that even a
    moderately intelligent approach will do decently well given such large
    amounts of data. This is a much simpler approach than to use little data
    and a very intelligent solver.

    Flaws:

    -The experimental section of the paper needs a lot more things in it.
    There are a lot of unanswered questions. The authors said that they
    omitted modules and reran the tests and found that the accuracy did not go
    down significantly. They concluded that this implies a certain amount of
    overlap. They never bothered to try and quantify the amount of overlap.
    If this had been quantified, we would have gotten an idea of the
    redundancies in the system, which could have then been eliminated, hence
    reducing the runtime. There were lots more results that I would have
    liked to see in the paper. They talked about various approaches and
    techniques. When doing so, the authors appealed to the intuition of the
    reader, and did not have too many experiments to backup their claims.
    They only have overall performance when all the modules are put together,
    and they mention that if they omit one module at a time, then accuracy
    does not suffer. For example, how can one module impact another module.s
    candidates by providing incorrect solutions with a high level of
    confidence.

    -They ran all the modules on each clue. This would take a tremendous
    amount of time. The authors neglect the fact that they could use some
    sort of learning approach which could identify a set of relevant modules
    which can solve the clues and not run modules which would not be of any
    benefit. Doing such a thing would have two positive consequences.
    Runtime would come down, and the irrelevant modules will not be given a
    chance to produce a set of solutions which could be incorrectly classified
    as being high on confidence and hence hindering the results produced by
    the other modules.

    Open research questions:

    -It is evident that for a problem like solving crossword puzzles, it would
    be difficult to beat human champions because the latter can solve new
    kinds of clues (when seen for the first time) and clues that do not fall
    into any clean category (such as synonyms, fill-in-the-blanks, etc). The
    former primarily solves clues that fall into a clean-cut category. For a
    computer to beat human champions, they should think like humans while
    solving crosswords. Hence, instead of mining for data, they should rather
    understand the clue and solve it. Is this possible to do? I guess this
    is a specific instance of the classic AI problem of whether computers can
    mimic human thinking. Solving this problem would have great impacts all
    over AI.

    -Another problem of interest is whether the large information database can
    be learnt in some fashion and using that to solve crosswords, rather than
    mine the data for solving the crosswords.


  • Next message: Anna Cavender: "PROVERB: The Probabilistic Cruciverbalist"

    This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 10:16:26 PST