We designed WebCrow’s architecture using some insights from Proverb’s. The information flow is similar: in a first phase the clues are analyzed and then processed by a set of candidate-list generators (the expert modules). Among these the preliminary role is played by the NLP experts and the Web Search Module (WSM). Each list contains a global confidence score and a set of words ordered by probability. These candidate lists are passed to a merger system that produces a unique list for each clue. In a second phase, a constraint-satisfaction algorithm carries forward the grid-filling, in order to place the correct words within the slots.
Expert Modules
The road which leads to the correct answer for each clue is not the same. This is for sure the challenging and fascinating part of crossword solving. For this reason, WebCrow is constructed in order to engage any kind of clue-answing expert. There are some experts built inside WebCrow, such as the rule-based expert, the web search module and the crossword DB module, which can be activated or disactivated. All the other experts are engaged by using Redis channel. These modules can be written in different coding languages and can run in other machines. It a sort of distributed intelligence which is involved in generating candidate answers list for each clue in the crossword.
NLP Experts
Finding meaning in language includes making inference and reasoning from different bits of knowledge, such as Ontologies, Knowledge Graphs, self-updating Web Knowledge and previously seen crosswords. Moreover, clue words meaning must be correctly discovered and understood. This is the challenging part of crosswords. Often there is not a direct match with the context in which the answer can be placed. The correct answer can be found searching in a Knowledge Graph or analyzing a Web page or having a look to previously seen clue-answer couples.
NLP experts is one of the project novelties introduced recently. These experts make use of Expert.ai NLP technologies, such as rich Knowledge Graphs and deep language analysis. We also introduced new NL approaches.
One approach we explored is developing experts which make use of word embedding. Words belonging to clues or other text sources are mapped to vectors of real numbers. Each word-vector represent the meaning of a word and word-vectors with similar context occupy close spatial positions. Experts using word embedding go beyond the strict meaning of each word or concept and find more broad matches and language inferences. This approach seems to be very effective in finding answers for clue crosswords.
The Web Search Module
The Web Search Module represents the heart of WebCrow and the main innovation with respect to the literature. The goal of this important module recalls that of a Web-based Question Answering system. The idea is to exploit the Web and search engines (SE) in order to find sensible answers to questions expressed in natural language. However, with crossword clues, the nature of the problem changes sensibly, often becoming more challenging than classic QA. The only evident advantage in crossword solving is that we priorly know the exact length of the words that we are seeking. We believe that, thanks to this property, web search can be extremely effective.
The inner architecture of the WSM is based on three main sub-modules:
- a web-based list generator that extracts possible answers to a clue from web documents by picking the terms (and compound words) of the correct length
- a statistical filter that ranks the candidates using statistical information retrieval techniques
- a filter that ranks the words according to their NLP category.
The WSM (Web Search Module) is able to produce impressive answering performances, providing a very good coverage/precision balance. The overall coverage of the system is mainly guaranteed by other module which makes use of Ontologies or Knowledge Graphs, but the introduction of the WSM is fundamental to increase sensibly the rank of the correct answer. The WSM guarantees very good performance even with long word targets, which are of great importance in the CSP phase.
Merging and grid filling
Merging candidate answers
No expert module is capable of giving all correct answers for all crossword’s clues. Therefore, a merging phase is necessary for collecting all candidate answers and have a unique candidate list for each clue.
This coud seem a quite straitfoward task, but experiments show that superficial merging can deteriorate the information comming for each expert module and produce a flat weighted candidate list for each clue. If this is the case, the grid filling phase would get in big trouble trying to select the most probable correct answer.
Therfore, WebCrow merging module goes under a training phase, in order to learn the best way to merge the lists based on serveral parameters: the expert module that produced the condidate list, the list conficende, the clue type and the answer length.
Filling the grid
Crossword solving can be successfully formalized as a Probabilistic-CSP problem. The slots of the puzzle represent the set of variables, the lists of candidates provide the domain of legal values for the variables. The goal is to assign a word to each slot in order to maximize the similarity between the final configuration and the target (defined by the crosswords designer). To compute this similarity we adopted the maximum probability function. We search among the various solutions for the one that
maximizes:
where pxi (vi) is the probability that the value vi is assigned to the variable xi in the target configuration.