From: Annamalai Muthu (muthu@cs.washington.edu)
Date: Mon Dec 06 2004 - 10:16:26 PST
Paper Title: PROVERB: The Probabilistic Cruciverbalist
Authors: Greg A. Keim, Noam M. Shazeer, Michael L. Littman,
Sushant Agarwal, Catherine M. Cheves, Joseph Fitzgerald,
Jason Grosland, Fan Jiang, Shannon Pollard, Karl
Weinmeister
Summary: This paper suggests an approach using which computers can
solve crossword puzzles better than the average human. The approach
utilizes large amounts of information (dictionary words, previous
clue-target pairs) and probabilistic models.
The important ideas:
-At first sight, getting a computer to do something as complex as solving
a cryptic crossword would seem impossible. But this paper suggests a very
intelligent approach. They use expert modules to solve different portions
of the problem, and then they combine the results. For example, one
module solves the fill-in-the-blanks kind of clues, while another module
would solve the synonym clues and etc. Each module tries to solve the
clue in its own way and associates a level of confidence with the entire
set of candidate solutions generated, and also with each individual
candidate. The solution sets from each module are then normalized and
merged. Techniques such as implicit distribution models add more
candidates to the initial set of candidate solutions as more information
becomes available. Though the approach suggested is put in context of
crossword solvers, it can be used for very difficult problems. The key is
to break the domain into pieces and solve each piece in its own efficient
way, instead of solving everything using a unified approach.
-The paper shows the manner in which different AI techniques have been
wonderfully integrated. The approach uses constraint satisfaction,
information retrieval, machine learning, natural language processing,
state-space search and probabilistic optimization. The paper implicitly
points out that the use of just one technique is clearly insufficient for
extremely complex problems. We require a blend of a few AI techniques,
and this paper shows a very good blend. Humans, while thinking, use a
variety of techniques for reasoning and learning, and we can come close to
that only through the correct integration of AI techniques.
-Another takeaway point from the paper is that it might be smart to make
use of vast amounts of information available. This implies that even a
moderately intelligent approach will do decently well given such large
amounts of data. This is a much simpler approach than to use little data
and a very intelligent solver.
Flaws:
-The experimental section of the paper needs a lot more things in it.
There are a lot of unanswered questions. The authors said that they
omitted modules and reran the tests and found that the accuracy did not go
down significantly. They concluded that this implies a certain amount of
overlap. They never bothered to try and quantify the amount of overlap.
If this had been quantified, we would have gotten an idea of the
redundancies in the system, which could have then been eliminated, hence
reducing the runtime. There were lots more results that I would have
liked to see in the paper. They talked about various approaches and
techniques. When doing so, the authors appealed to the intuition of the
reader, and did not have too many experiments to backup their claims.
They only have overall performance when all the modules are put together,
and they mention that if they omit one module at a time, then accuracy
does not suffer. For example, how can one module impact another module.s
candidates by providing incorrect solutions with a high level of
confidence.
-They ran all the modules on each clue. This would take a tremendous
amount of time. The authors neglect the fact that they could use some
sort of learning approach which could identify a set of relevant modules
which can solve the clues and not run modules which would not be of any
benefit. Doing such a thing would have two positive consequences.
Runtime would come down, and the irrelevant modules will not be given a
chance to produce a set of solutions which could be incorrectly classified
as being high on confidence and hence hindering the results produced by
the other modules.
Open research questions:
-It is evident that for a problem like solving crossword puzzles, it would
be difficult to beat human champions because the latter can solve new
kinds of clues (when seen for the first time) and clues that do not fall
into any clean category (such as synonyms, fill-in-the-blanks, etc). The
former primarily solves clues that fall into a clean-cut category. For a
computer to beat human champions, they should think like humans while
solving crosswords. Hence, instead of mining for data, they should rather
understand the clue and solve it. Is this possible to do? I guess this
is a specific instance of the classic AI problem of whether computers can
mimic human thinking. Solving this problem would have great impacts all
over AI.
-Another problem of interest is whether the large information database can
be learnt in some fashion and using that to solve crosswords, rather than
mine the data for solving the crosswords.
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 10:16:26 PST