From: Russell Power (rjpower_at_u.washington.edu)
Date: Mon Dec 08 2003 - 00:24:56 PST
PROVERB: The Probablistic Cruciverbalist by Keim, Shazeer, Litmann, et al.
This paper introduces PROVERB, a piece of work that utlizes a probablistic
infrastructure to quickly find near-optimal solutions to what at first might
appear to be an intractable problem: solving crossword puzzles.
The paper describes the basic infrastructure of PROVERB: a large assembly of
expert modules, the results of which are fed into a merger which attempts to
fit the returned solutions into the puzzle grid. The expert modules are
built to return weighted lists of answers to clues - the more confidence a
module has in a result, the higher the weight it assigns. The merger then
uses these weights, along with confidence metrics for the solvers themselves
in concert with a grid filling algorithm to determine the 'optimal' solution
to a crossword problem. Certain modules may be reinvoked after portions of
the graph have been constrained by the grid filling, in order to obtain more
results.
The problem tackled by the paper is interesting, and the effectiveness of
the solution is noteworthy. The evaluation is also quite clear and good.
The only objection I had to the paper was the lack of a more extensive look
at potential future work, and the fact that the solution to the problem
wasn't exactly useful.
As the authors of the paper mention, the success of this solution brings to
the surface any number of other problems. The probablistic method used in
the paper would also be interesting to see applied to other common AI
problems.
This archive was generated by hypermail 2.1.6 : Mon Dec 08 2003 - 00:25:04 PST