paper review : PROVERB: The Probabilistic Cruciverbalist

From: Mathias Ganter (mganter@u.washington.edu)
Date: Sun Dec 05 2004 - 22:11:56 PST

  • Next message: Beltran Ibarra Davila-Armero: "PROVERB Review"

    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?

     


  • Next message: Beltran Ibarra Davila-Armero: "PROVERB Review"

    This archive was generated by hypermail 2.1.6 : Sun Dec 05 2004 - 22:11:58 PST