From: Mathias Ganter (mganter@u.washington.edu)
Date: Sun Dec 05 2004 - 22:11:56 PST
Authors and Title
Greg A. Keim, Noam M. Shazeer, Michael L. Littman, Sushant Agarwal,
CM.Cheves, J.Fitzgerald, J.Grosland, F.Jiang, S.Pollard, K.Weinmeister :
PROVERB: The Probabilistic Cruciverbalist (1999), AAAI
Remarks
This paper by Keim et al. presents a crossword-solver for American style
crosswords called PROVERB (PRObabilistic CruciVERBalist). They give a short
introduction to crosswords puzzles, especially to the crossword solving
problem, the architecture emphasizing "expert modules" and its results. They
also mention the knowledge that has to be made available to PROVERB for
solving everyday crosswords to find an optimal set of words that fit the
grid best, i.e. "an extensive knowledge of language, history and popular
culture".
The most important ideas are:
- the importance of a good crossword-database
- the implementation of expert modules to give special answers to
each clue based on information retrieval, database search and machine
learning; followed by a merging of all possible answers into a single
candidate list with a common weighting scheme that make the various
candidates comparable
- combination of many AI techniques: ideas from state space search,
probabilistic optimization, constraint satisfaction, information retrieval,
machine learning and natural language processing
The major flaws are:
- The whole procedure can only be used for evaluating crosswords that
strongly depend on their given crossword-database.
- Lack of information on the performance of the expert modules
- The authors mention many AI techniques in their paper, like machine
learning, but where are they applied?
Open research questions are:
- Can you implement a multi-language crossword solver, i.e. one that
solves crosswords efficiently in other languages, like Roman languages or
Asian languages using signs?
- How is its performance on different sized grids (like to Sunday
NYT)?
- Can its performance be improved (compared to human champions) by
implementing a more human way of thinking?
- What happens if there is interaction between the expert modules
before their candidate lists are re-weighted by the merger?
This archive was generated by hypermail 2.1.6 : Sun Dec 05 2004 - 22:11:58 PST