From: Daniel J. Klein (djklein_at_aa.washington.edu)
Date: Mon Dec 08 2003 - 11:10:06 PST
Title: PROVERB: The Probabilistic Cruciverbalist
Authors: G. Keim, C. Cheves, M. Littman , et. al.
Summary: On the problem of computerized solutions to crossword puzzles,
the authors present a melange of expert modules to generate possible
words. From this possible word list, the "best" solution is chosen.
Main Ideas:
Turns out, solving a crossword puzzle is a challenging problem for
artificial intelligence. The are two main parts to the problem. First,
the clue must be interpreted. This requires a cursory understanding of
NLP. Second, the correct (or best possible) word must be chosen based
on the information given in the clue and the grid constraints. To solve
the clues, the authors present a decentralized architecture based on
experts. These experts are neat in that they allow a conglomeration of
computerized "experts" to take a guess at the clue solution.
The meeting of the minds (answers from all the experts) are combined in
the "Merger" module. This module uses training data to weight each
expert. This is a necessary task to be able to compare the results of
different experts and to come up with a unified word solution
probability distribution. Finally, the "Solver" looks for the "best"
solution using a belief net called "turbo decoding" (sounds a bit hokie
to me!).
One Small Flaw:
As with any training algorithm, it is easy to over-train and difficult
to generalize. This is the exact problem the authors encountered when
presented with the tournament puzzles. These puzzles tended to be more
difficult for humans which means that the learned parameters are no
longer optimal. I guess there is no real reason the authors could not
have learned over previous tournament puzzles.
Future Research:
It seems natural to add more experts to the system. This is easy to do
due to the modularity of the architecture. It is possible that, with
the aid of new experts, this very artificial system could beat the best
human cruciverbalist, despite the drawbacks of learning on
non-tournament puzzles. Also, learning over past tournament puzzles
will definitely help the proverb be a competitive cruciverbalist.
This archive was generated by hypermail 2.1.6 : Mon Dec 08 2003 - 11:10:09 PST