English. Crossword clues represent an extremely challenging form of Question Answering, due to their intentional ambiguity. Databases of previously answered clues are a vital source for the retrieval of candidate answers lists in Automatic Crossword Puzzles (CPs) resolution systems. In this paper, we exploit language neural representations for the retrieval and ranking of crossword clues and answers. We assess the performances of several embedding models, both static and contextual, on Italian and English CPs. Results indicate that embeddings usually outperform the baseline. Moreover, the use of embeddings for retrieval allows different ranking strategies, which turned out to be complementary, and lead to better results when used in combination.
Italiano. Le domande dei cruciverba rappresentano una forma di Question Answering particolarmente complessa a causa della loro intenzionale ambiguita`. I risolutori automatici di cruciverba sfruttano ampiamente basi di dati di domande precedentemente risposte. In questo articolo proponiamo l’uso di embeddings per la ricerca semantica di domande-risposte da tali databases. Le performances sono valutate in cruciverba di lingua sia italiana che inglese, confrontando diversi tipi di embeddings, sia contestuali che statici. I risultati suggeriscono che la ricerca semantica e` migliore della baseline. Inoltre, l’utilizzo di embeddings permette di applicare differenti strategie di retrieval, che, Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). migliorano la qualita` dei risultati quando usate congiuntamente.
Crossword Puzzles (CPs) resolution is a popular
game. As almost any other human game, it is
possible to tackle the problem automatically. CPs
solvers frame it into a constraint satisfaction task,
where the goal is to maximize the probability of
iflling the grid with answers consistent with their
clues and coherent to the puzzle scheme. These
systems
In the problem of candidate answers retrieval
from clue-answer knowledge sources, answers are
ranked according to the similarity between a query
clue and the clues in the DB. The similarity is
provided by the search engine that assigns a score to
each retrieved answer. Several approaches have
been carried out to re-rank the candidates’ list by
means of learning to rank strategies
The re-ranking of answer candidates attempts to improve the quality of candidates’ lists, assuming that the correct answer belongs to the list. Differently from previous work, we aim at directly retrieving richer lists of answer candidates from a clue-answer database. In order to do so, we exploit both static and contextual distributed representations to perform a semantic search on the DB. An embedding-based search extends the retrieval to semantically related clues that may be phrased differently. Moreover, it also allows us to map in the same space questions and answers, which opens the way for ranking answers directly based on their similarity with respect to the query clue. Our approach requires no training on CPs data and it can be applied with any pre-trained embedding model.
In summary, the contributions of this work are: (1) a semantic search approach to candidate answer retrieval in automatic crossword resolution; (2) two complementary retrieval methodologies (namely QC and QA) detecting candidate answers that when combined together (even naively) produce a better set of candidates; (3) a comparison between different pre-trained language representations (either static or contextual).
The paper is organized as follows. First, we describe in Section 2 distributed representations of language. In Section 3, we present the two answer retrieval approaches proposed in this work. Then, in Section 4 we outline the experiments in detail, and discuss the obtained results. Finally, we draw our conclusions in Section 5. 2
Assigning meaningful representations to language
is a long standing problem. Since the inception
of the first text mining solutions, the bag-of-words
technique has been widely adopted as one of the
standard approaches to text representation.
Inverted indices and statistical weighting schemes
(as TF-IDF or BM25) are still to this day
commonly paired with bag-of-words, providing a
scalable and effective approach to document retrieval.
On the other hand, in the last decade, we have
assisted to tremendous progress in the field of
Natural Language Processing. Huge credit goes
to the diffusion of distributed representations of
words
In general, the goal is to assign a fixed length representation of size d, aka embedding, to a textual passage s such that similar text passages syntactically and/or semantically - are represented closely in such space. An embedding model fe is a function mapping s to a d-dimensional vector, i.e: fe : s → Rd. Since language is a composition of symbols (typically words), embedding models ifrst tokenize text and then process such tokens in order to compute the representation of such textual passage.
Nowadays, there are lots of embedding
models, and for some of them pre-trained
embeddings are available in a plethora of languages
Most of the proposed methods for contextual
embeddings were based on recurrent neural
language models
Traditional CPs solvers rely on Similar Clue Retrieval mechanisms. The idea is to find possible [stan, totò, step,.... nasali] ranking [stan, ines, mike,.... nasali] rankng QC Il nome di Laurel
....
Il comico Laurel Le consonanti come la n ...
Clue-Answer
DB
Query: L'indimenticabile
Laurel <Il nome di Laurel, stan>
....
<Il comico Laurel, stan> <Le consonanti come la n, nasali> ...
stan .... nasali ...
QA answers from clues in the database that are similar to the given query. This is particularly effective for crosswords, since the same clues tend to be repeated over time, or may have little lexical variations. Retrieval of similar clues is based on search engines based on classical IR algorithms such as TF-IDF or BM25, representing clues in the database as documents to retrieve, given the target clue as query.
Here instead, we retrieve and rank documents with semantic search. We propose two strategies, namely QC and QA. QC is analogous to classical similar clues retrieval systems, with the difference that text is represented with a dense representation. The approach retrieves and ranks from the DB clues similar to the query and returns in output the answers associated to those clues. QA, instead, ranks the answers directly by computing the cosine distance between the query and the answers themselves. Intuitively, the latter approach ranks well answers semantically correlated to the question itself, particularly useful for clues about synonyms. As we will show in Section 4, due to their different nature, the list of candidates retrieved by the two approaches are strongly complementary. A sketch of the two approaches is outlined in Fig. 1. Let us describe them separately. 3.1
We are given a query clue which is a sequence of n words q := (w1, . . . , wn), and a clue-answer DB (C, A) constituted by M clue-answer pairs, where C and A indicate the list of all the clues and answers, respectively, while we denote a clue-answer pair as: (c, a).
We assign a fixed-length representation qe ∈ Rd to the query clue q, computed with an embedding model: qe = fe(q). (1) For contextual embeddings fe is the model itself, since they work directly on the sequence, whereas for static embeddings we have to collapse n word representations together into a single vector. For simplicity, we simply average such embeddings.
Analogously, each clue c ∈ C is encoded as in Equation 1. Then, we measure the cosine similarity between the query and each clue: score(q, (c, a)) = cos(qe, fe(c)), (2) score(q, a) = where cos(· , · ) denotes the cosine similarity. Thus, we obtain a similarity score for each clue-answer pair. In order to finally rank answers we average all clue-answer pairs having the same answer: 1
X score(q, (c, ak)), (3) · |A| ak∈A where A indicates the set of clue-answer pairs where the answer ak is equal to a. All the answers in A are then ranked. Since we know a priori the length of a query answer, candidates with incorrect lengths are filtered out. We refer to this approach as QC (Query-Clue). 3.2
Since we can map text into a fixed-length space, we can also rank by measuring the similarity between the query and the answer itself. The query is encoded exactly as in Equation 1. In this case however we only need the clue-answer DB to retrieve the set of unique answers, denoted as A. Similarly to Equation 2, we compute the cosine similarity between query and answer embeddings: score(q, a) = cos(qe, fe(a)), (4) for each a ∈ A, then we rank as in QC. We call it QA (Query-Answer). It is important to remark that QA is only feasible using latent representations, traditional methods like TF-IDF are not suited because of their sparsity of representations. Moreover, QA is somewhat an orthogonal strategy with respect to QC. We will see in Section 4, how even a trivial ensemble of QA and QC is beneficial to the performances.
In the experiments we aim to prove the effectiveness of semantic search to retrieve accurate lists of candidate answers, and to show that the QA approach carries out complementary information that can increase the coverage of the retrieval. 4.1
We considered for our experiments three well known embedding models, two static (Word2Vec12, FastText3) and one contextual (Universal Sentence Encoder4), briefly denoted as W2V, FT and USE, respectively. We exploited pre-trained models for all of them. In absence of an Italian USE model, we used for the Italian crosswords database, the multilingual version of USE, that was trained on 16 languages (Italian included). Embedding models are compared against TF-IDF, which is a typical text representation in document retrieval problems.
To measure performances, we used well known metrics of Retrieval systems. In particular we considered Mean Hit at k (MH@k) and Mean Reciprocal Rank (MRR). Hit at k is 1 if the correct answer is within the first k elements of the list, 0 otherwise. The hits at k are evaluated for k = {1, 5, 20, 100}. MRR is defined as follows: 1 Pn 1 n q=1 rank(q) . 4.2
We consider two different clue-answer databases
for our experimentation. In particular,
experiments were carried out on two languages, Italian
and English, respectively on CWDB dataset
1English: https://code.google.com/archiv e/p/word2vec/
2Italian: https://wikipedia2vec.github.io/ wikipedia2vec/ 3https://fasttext.cc/ 4https://tfhub.dev/google/collections /universal-sentence-encoder/1 1.0 0.8 0.6 0.4 0.2 0.0
USE
TF-IDF
0
500
1000
1500
2000
2500
3000
English Crosswords. The data consist of a
collection of clue-answer pairs for crossword
puzzles published in the New York Times5 in 1997
and 2005, previously collected in
All the results for Italian and English crosswords are outlined in Tables 1 and 2, respectively. From them, we can catch several interesting insights. First of all, contextual representations from Universal Sentence Encoders are gen5https://www.nytimes.com/ 6https://ikernels-portal.disi.unitn.i t/projects/webcrow MH@20 27.78 27.29 30.01 44.09 42.66 32.67 49.34 54.34 MH@100 42.62 43.42 45.17 49.54 57.38 46.64 63.35 69.00 MRR 12.66 12.75 14.25 31.46 25.65 20.20 32.12 EnsembleUSE− W 2V erally the most effective ones, especially on similar clues retrieval (QC), where both the query and the elements to rank are textual sequences. Nonetheless, Word2vec embeddings work surprisingly well, outperforming FastText almost all the times. Furthermore, they are the best ones on QA search in Italian database. We believe the reason why Word2Vec outperforms USE on Italian QA is twofold. First, the advantage of contextual embeddings is less evident in QA setup, indeed USE brings less benefits on English QA as well. Second, USE is a multilingual model, therefore its embeddings are less specialized than Word2Vec which was instead trained for Italian only.
When comparing semantic search models against the baseline (TF-IDF) - which is only possible in QC - we can notice that, static embeddings struggle to outperform it. Indeed, the sparse nature of TF-IDF induces crisp similarity scores, very high for clues sharing the same keywords, extremely low for all the rest. On the contrary, similarity scores are more blurred with dense embeddings. As a consequence, TF-IDF achieves high MH@1 and MH@5 scores (and MRR too). However, TF-IDF leads to a poorer coverage when the candidates list grows (MH@20 and MH@100). This behavior is also evident in Fig. 2, where we compare the cumulative distributions of ranking with USE and TF-IDF. After the initial bump, TF-IDF hits growth is almost linear (i.e. random), whereas the Universal Sentence Encoder keeps growing significantly.
Ensembling QC and QA. Analyzing the results, we observed that ranks from QA and QC had low levels of overlaps. We reported in the last line of Tables 1 and 2, performances of a naive ensemble approach to combine QC and QA strategies. Due to the limited levels of overlaps, we decided to merge the two ranks taking the first K/2 ranks from each strategy to compute MH@K, K = {5, 20, 100}7. We chose the best embedding model on each strategy. Despite its simplicity and the large room for improvements, the ensemble significantly improved the performances in both languages. This suggests possible directions for further improving the retrieval of CPs solvers.
7Since K=5 is not even, we took the first 3 ranks from QC and the first two ranks from QA.
In this paper, we proposed two different semantic search strategies (QC and QA) for ranking and retrieving answer candidates to CPs clues. We exploited pre-trained state-of-the-art embeddings, both static and contextual, to rank clue-answer pairs from databases. Embedding-based retrieval overcomes some of the limitations of inverted indices models, leading to higher coverage ranks, and allowing similar answers retrieval (QA). Finally, we observed that, even a simple ensembling that combines QC and QA, is effective and improves overall retrieval performances.
This opens further research directions, where learning to rank methods could be exploited in order to better combine candidate answer lists from complementary approaches like QC and QA.
We thank Nicola Landolfi and Marco Maggini for the great support and fruitful discussions.