From: Karthik Gopalratnam (karthikg_at_cs.washington.edu)
Date: Mon Dec 08 2003 - 00:48:59 PST
Paper - "PROVERB: The Probabilistic Cruciverbalist"
Authors: Keim, Shazeer, Littman, et. al.
Review By: Karthik Gopalratnam
This paper describes an architecture that incorporates components drawn
from various areas of AI in order to tackle the problem of solving
crossword puzzles in a wholly automated manner. The major techniques
employed are drawn from probabilistic pattern matching, a form of EM
learning and constraint satisfaction.
The authors present a very carefully analyzed overview of the domain,
and point out the major features of general American NYT type crossword
puzzles that make them a likely candidate for designing an AI system for.
Based on the characteristics that are identified in this section, the
authors describe an AI architecture that revolves around specialized
"experts", each of which tackles a specific type of crossword clue. The
candidate solution words generated by these probabilistic experts are then
merged using constraint satisfaction methods. The authors report very good
results with this carefully constructed system.
Despite the fact that the authors have done a very thorough job of
describing a problem, a complete solution and a thorough analysis of that
solution, the fundamental impact of this paper remains questionable. The
architecture that the authors describe is very well *engineered* to solve
the problem at hand, and relies very heavily on specific knowledge of the
domain. It is not clear if this type of architecture is generalizable to
other problems. That being said, the paper does show that an apparently
"essentially human" pursuit can be realized almost exactly by a machine.
It seems from the paper that a more careful process of engineering of
the CWDB modules should yield an arbitrarily good crossword solver, since
the error is probably because of clues that do not fit into any of the
categories that the CWDB's address. Therefore, in terms of future work in
crossword solving problems in general, there does not seem to be anything
more interesting to do.
It would however be interesting to see whether the general architecture
described here is applicable to other problems as well. (I do believe that
the theoretical basis for merging the hypotheses generated by a mixture of
experts has already been established in Learning Theory.)
This archive was generated by hypermail 2.1.6 : Mon Dec 08 2003 - 00:49:00 PST