From: Vaishnavi Sannidhanam (vaishu@cs.washington.edu)
Date: Mon Dec 06 2004 - 00:56:53 PST
PROVERB: The Probabilistic Cruciverbalist
-------------------------------------------
By Keim, Shazeer, Littman, Agarwal, Cheves, Fitzgerald,
Grosland, Jiang, Pollard, Weinmeister
* One-line summary
------------------------
This paper talks about the design and techniques involved in developing an
artificially intelligent crossword puzzle solver along with an evaluation of
how well it fares.
* The (two) most important ideas in the paper, and why
-------------------------------------------------------------
The paper is very well written describing what each approach is and how each
of these approaches (probabilistic modeling, candidate generation,
information retrieval, dijkstra's algorithm etc) are used and why these
approaches are needed/significant. The idea of using various approaches and
finally getting an answer from all of them though not novel (because it can
be seen in Ensemble method in decision trees) is very well used.
The paper identifies that solving crossword puzzles is highly dependent on
the database of words (or previous occurrences of words). Without this
identification, PROVERB would have failed miserably. Hence, this is a big
contribution to the field of developing artificially intelligent crossword
puzzle solvers.
The paper as it says in the conclusion section identifies many problems
specific to the field of crossword puzzles like constraint satisfaction,
board knowledge, speed, what words to solve first, how to search through the
databases etc.,.
* The one or two largest flaws in the paper
-------------------------------------------------
The main complain I have about the paper is the lack of a good evaluation
section for all the modules they use and for each of the modules. It would
have been better if they had some information as to how each module
contributed in the puzzle solving and how varying weights for the modules
would have affected the system. (This is basically how we looked at Othello
and the heuristics in it for our mini project 1).
It would have been better if the authors incorporated more of the machine
learning techniques they talk about instead of using large databases for
solving puzzles. Using of huge databases makes the reader question if
solving crosswords is more a database problem than an AI problem.
* Identify two important, open research questions on the topic, and
why they matt
----------------------------------------------------------------------------
-----------
One important research question as told in the flaws section is to study how
various machine learning techniques can be used to improvise the performance
while database size remains constant or while it is reduced.
Another thing that one could answer is if it would be possible to mimic
human crossword champions and how they solve the puzzles. Do they put in
more constraints to make the process of searching for a solution easier? Do
they have particular experience with crosswords published in NYT as opposed
to those in Reader's Digest? One can also ask the question, if mimicking
human brain process could be extended to solve other kinds of crossword
puzzles (like cryptic crosswords).
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 00:56:59 PST