From: Jiun-Hung Chen (jhchen@cs.washington.edu)
Date: Mon Dec 06 2004 - 02:48:51 PST
PROVERB: The Probabilistic Cruciverbalist
G. A. Keim and et al.
Review by Jiun-Hung Chen
Summary
Knowledge from different expert modules is combined together to solve crossword puzzles and
the combination is done by using constraint propagation and probabilities to select best target.
Most important ideas
Building different expert systems and then combining them together to solve a difficult problem
is very important and can be seen as divide and conquer, a principal and elegant algorithm design
paradigm. It is typically much more efficient than dealing with a problem as a whole.
Learning transformations to clue-target pairs is a very interesting idea. By doing so, more information
can be obtained by performing some inference in original knowledge bases. In addition, handling
targets which are not included in any database but more probable than random with implicit distribution
modules is a good idea, too.
Largest flaws
I think the proposed architecture can not scale up because each module works independently before
their results are merged. It is inefficient because a clue is solved by each module. An ideal way is to
classify a clue into a domain and only experts for this domain are used. In addition, in learning theory,
it is hoped that each module makes independent errors in a glue so that the ensemble can perform
substantially better than each module. However, I can not find that this issue is carefully considered
in this paper. So, I doubt that some modules may be redundant and I guess it is an another reason
why this system is slow.
Open research questions
A more efficient and powerful computer solver for crossword puzzles is very challenging. I think it
definitely needs further understanding of many key questions such as knowledge representation
and search in AI. In addition, WWW can be seen as a very huge knowledge base today and I think
you can get almost all information you want. So, using WWW to solve crossword puzzles is a very
interesting direction.
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 02:48:52 PST