Learning to Rank Answer Candidates for Automatic Resolution of Crossword Puzzles

Proceedings of the Eighteenth Conference on Computational Language Learning, pages 39–48, Baltimore, Maryland USA, June 26-27 2014. c⃝2014 Association for Computational Linguistics Learning to Rank Answer Candidates for Automatic Resolution of Crossword Puzzles Gianni Barlacchi University of Trento 38123 Povo (TN), Italy gianni.barlacchi@gmail.com Massimo Nicosia and Alessandro Moschitti Qatar Computing Research Institute 5825 Doha, Qatar m.nicosia@gmail.com, amoschitti@qf.org.qa Abstract In this paper, we study the impact of rela- tional and syntactic representations for an interesting and challenging task: the au- tomatic resolution of crossword puzzles. Automatic solvers are typically based on two answer retrieval modules: (i) a web search engine, e.g., Google, Bing, etc. and (ii) a database (DB) system for access- ing previously resolved crossword puz- zles. We show that learning to rank models based on relational syntactic structures de- fined between the clues and the answer can improve both modules above. In particu- lar, our approach accesses the DB using a search engine and reranks its output by modeling paraphrasing. This improves on the MRR of previous system up to 53% in ranking answer candidates and greatly im- pacts on the resolution accuracy of cross- word puzzles up to 15%. 1 Introduction Crossword puzzles (CPs) are probably the most popular language games played around the world. It is very challenging for human intelligence as it requires high level of general knowledge, logical thinking, intuition and the ability to deal with am- biguities and puns. CPs normally have the form of a square or rectangular grid of white and black shaded squares. The white squares on the border of the grid or adjacent to the black ones are associ- ated with clues. The goal of the game is to fill the sequences of white squares with words answering the clues. There have been many attempts to build auto- matic CP solving systems, which have also par- ticipated in competitions such as The American Crossword Puzzle Tournament (ACPT). This is the oldest and largest CP tournament for cross- word experts held in the United States. The goal of such systems is to outperform human players in solving crosswords more accurately and in less time. Automatic CP solvers have been mainly tar- geted by the artificial intelligence (AI) community, who has mostly focused on AI techniques for fill- ing the puzzle grid, given a set of answer candi- dates for each clue. The basic idea is to optimize the overall probability of correctly filling the entire grid by exploiting the likelihood of each candidate answer, fulfilling at the same time the grid con- straints. After several failures in approaching the human expert performance, it has become clear that designing more accurate solvers would not have provided a winning system. In contrast, the Precision and Recall of the answer candidates are obviously a key factor: a very high value for both of them would enable the solver to quickly find the correct solution. This basically suggests that, similarly to the Jeopardy! challenge case (Ferrucci et al., 2010b), the solution relies on Question Answering …

Content truncated to 500 words