Reading Review 12-06-2004

From: Craig M Prince (cmprince@cs.washington.edu)
Date: Mon Dec 06 2004 - 08:33:31 PST

  • Next message: jklink@u.washington.edu: "PROVERB review (Jonas Klink)"

    PROVERB: The Probabilistic Cruciverbalist
    By Greg A Keim, Noam M Shazeer, Michael L. Littman, et al.

    This paper describes a system for solving crossword puzzles that relies on
    a series of special purpose clue solvers whoes results are combined with a
    grid constraint solver in order to optimize the solution to the crossword
    puzzle.

    One of the most important ideas presented in this paper was that the
    system is able to leverage a tremendous amount of knowledge that is
    available today and bring it to bear on the problem. These online and
    offline databases of knowledge form a sort of "common knowledge" database
    that is sufficient for this domain. The authors believe that enough such
    information is becoming available that solving other AI problems may
    benefit from this approach as well.

    Another important idea from the paper was that they use a two-tiered
    approach to solve the problem, first looking directly at the clues and
    trying to solve them, then taking those solutions and trying to fit them
    to the grid (and allowing for some further generation here). Although
    perhaps not the most realistic, this does a good job of making the task
    tractable. The idea of using specialized solvers seems similar to the
    "ensemble of classifiers" idea from decision tree learning.

    While this paper had many contributions there are some aspects where I
    felt the work could have been improved. The authors system seems to have
    been constructed in an ad hoc manner. They do not give very good intuition
    into why their architecture is better that others and don't seem to
    explore other architectures fully. This leads me to believe that there may
    be better or more efficient ways to solve crossword puzzles.

    One aspect of the paper that I felt was particular promising for future
    research was that the authors currently "prime" the system by providing a
    set of rules, expert solvers, and databases that they observe are useful
    for crossword puzzles. Is there a way that given a set of databases the
    expert solvers can be generated automatically and their usefulness
    automatically be determined? That is, to try to take the human out of the
    loop even more?

    A second promising aspect for future research is to try to apply these
    techniques to other areas besides just crossword puzzles. What is unique
    about crossword puzzles are that the clues often contain puns, idioms, and
    common knowledge. Can this approach be used for NLP to disambiguate these
    cases. How about in automatic translation?


  • Next message: jklink@u.washington.edu: "PROVERB review (Jonas Klink)"

    This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 08:33:32 PST