From: Jessica Kristan Miller (jessica_at_cs.washington.edu)
Date: Mon Dec 08 2003 - 10:53:12 PST
Paper Reviewed: Proverb: The Probabilistic Cruciverbalist
Paper Author: Keim, Shazeer, Littman, et. al.
Reviewed By: Jessica Miller
Summary:
This paper describes a system that solves crossword puzzles using AI and
probabilistic techniques with 95.3% accuracy.
Two Important Most Ideas:
(1) The most novel element of this paper is how the authors cleverly
applied several AI techniques in order to solve a hard problem quite
accurately. The authors used probability techniques to determine measures
like confidence and weights for possible answers, information retrieval
techniques to take advantage of various pre-existing databases,
probabilistic optimization to fill in the grid with target candidates, and
hill climbing to set parameters when merging candidate information. This
paper demonstrates how well good partitioning of a problem and appropriate
application of techniques to the partitions can yield very good results.
(2) The architecture of the system seems very intelligent as well. The
division between candidate generation and grid filling seems to be a very
intuitive way to approach the problem. The way the authors identified
different classes of clues and then allowed their architecture to take
advantage of this fact (through the expert modules) again seems like such
a clean and insightful way to practically partition the problem. The type
of architecture is also very extensible.
Largest Flaw in the Paper:
One thing I noticed about the authors' is that the system is very
dependent on the CWDB. I am not sure if this is a flaw or if it is just
inevitable, but there may be some weaknesses associated with such
dependence. Another weakness is that some of the expert modules are
unable to calculate actual probability distributions for the candidates
that they generate. Although the authors claim that the merge step should
help compensate for this, I am unclear about how much the accuracy is
increased in that step.
Two Open Research Questions:
(1) One open research question is what other ways can one classify the
clues and add new expert modules in order to incur even higher accuracy.
(2) I find myself wondering if this type of architecture could lend itself
to other types of nlp problems. This could possibly be another open
research question, though, I admit I know very little about nlp much less
canonical nlp problems that this might help.
This archive was generated by hypermail 2.1.6 : Mon Dec 08 2003 - 10:53:13 PST