Automatic Crossword Clues Extraction for Language Learning (2024)

Abstract: Crosswords are a powerful tool that could be used in educational contexts, but they are not that easy to build. In this work, we present experiments on automatically extracting clues from simple texts that could be used to create crosswords, with the aim of using them in the context of teaching English at the beginner level. We present a series of heuristic patterns based on NLP tools for extracting clues, and use them to create a set of 2209 clues from a collection of 400 simple texts. Human annotators labeled the clues, and this dataset is used to evaluate the performance of our heuristics, and also to create a classifier that predicts if an extracted clue is correct. Our best classifier achieves an accuracy of 84%.

## introduction this paper presents a series of experiments on automatically extracting clues from a text, that could be used to generate a crossword puzzle. crosswords are a very interesting tool that can be used in educational contexts, in particular for developing vocabulary @xcite . in this work, we will focus on extracting words and generating definitions for crosswords in the context of teaching english as a foreign language, in particular for students at the beginner level. a crossword (see fig. 1 ) is a type of puzzle where words are arranged horizontally or vertically, and often intersect each other. the puzzle is presented with blank spaces where the letters should be, and is accompanied by the set of definitions of the target words. in our case, these words and definitions will be related to a text, for example an article or story that an english teacher wants to work with in class. the crossword in the figure could be obtained by processing the following article 1 : in order to do this, we must detect a set of interesting words from the text, extract their corresponding definitions, and create the crossword puzzle. in this work, we are not focusing on building the actual puzzle grid, but on extracting appropriate clues from the text that could be used to populate the crossword. this kind of crosswords could be used as reading comprehension exercises, so it is expected that a student reads the text first, and then tries to solve the associated crossword. notice that in this situation, the types of definitions we are trying to extract will generally be tied to the accompanying text, and would not exactly be dictionary definitions. throughout the text we will use the term "definiendum" for a word that could appear in a crossword, and "definition" for a short phrase that defines that word. likewise, when we mention a "clue", we are referring to @xmath0, defini-@xmath1. in this project, we created a series of heuristics for extracting clues from simple texts, stories and articles. we used the heuristics to create a small annotated dataset @xmath2, defini-@xmath3, labeled according to how correct they are to be used in a crossword and how grammatical they are. with this dataset, we trained several machine learning systems that try to predict if new clues would be suitable for creating a crossword. the main contributions of this work are the following: 1) we present a set of heuristics that can extract clues from simple english texts. the heuristics range from simple linguistic patterns extraction to more complex question-answer generation, and could also combine information from different sentences in a text. 2) we annotated a dataset of 2209 clues, generated using our heuristics, with information about grammaticality and correctness as a clue for a crossword (i.e. it would be suitable to include this definition for this definiendum in the context of a crossword) foot_0 . 3) we did experiments on automatic classification of clues, with the best classifier achieving 84% accuracy and 78% macro-f1 for detecting correct clues. the rest of the paper is structured as follows: section 2 presents some relevant related work, section 3 describes the corpus we used and the heuristics we created for extracting clues, section 4 shows the quality evaluation of the extracted clues and presents the classifier we built, and finally section 5 presents some conclusions and future work. ## related work the works on automatic generation of crossword clues from texts are scarce. we comment below those that are closer to our objectives. in @xcite , the authors present two approaches to the generation of crossword puzzles, with the aim of using them for teaching english as a second language at the beginner level. on the one hand, a set of definitions organized by classical categories (e.g., colors, food, animals) is created, from which crossword puzzles are automatically generated according to the selected category. the definitions are extracted from different sources: existing children's dictionaries were used, and new definitions are also generated by applying patterns on simple wikipedia texts and filtering those that do not correspond to the expected categories by applying heuristics based on word embeddings. on the other hand, crossword puzzles are generated from texts entered by teachers, from which @xmath4, @xmath5, as in our work. for this, some heuristics based on information from a dependency parser are applied, using the verb "to be" as a central element, and each clue is extracted from a single sentence. in @xcite , a traditional approach based on linguistic analysis tools is presented. a pipeline is applied to generate crossword clues from texts obtained by web crawling. the system processes the texts by applying different analyzers in sequence: sentence splitter, pos-tagger, chunker, and specific rules for the identification of subject, object and predicate (verbal or nominal) of each sentence. then a finite state automaton is applied to detect which sentences are definitions, and finally, to generate the crossword clue, the subject of the sentence is removed. the system was used to create italian crosswords. in @xcite , a system for crossword generation from spanish news texts is presented. they use tools for linguistic analysis -a pos-tagger, a constituency parser, and a clause segmenter-and from the information they provide they define recursive regular expressions to extract clues from the texts. the paper presents a wide variety of patterns, and includes a tool implemented in prolog to generate different crossword grids. this last task of actually generating the crossword grid has been explored in the past @xcite , and is not particularly relevant from an nlp perspective, although some of the ideas in @xcite such as using different priority levels for words when building the grid might be relevant in an educational context to make sure the words that the teacher wants to highlight are included in the puzzle. in @xcite , a platform for language learning is presented. the platform includes crossword-based exercises created from stories. the crosswords are composed of words taken from the story, the student has to guess the words in their correct grammatical form. some of our extraction heuristics that use linguistic patterns bear some resemblance to the classic method proposed by @xcite in the context of hyponyms extraction, although in that work there is an iterative step in which previously extracted information is used to generate new patterns from a large corpus. we have not tried the iterative process in this work, although a similar approach has already been explored in the context of clues extraction for crosswords in the past @xcite , where it was unable to find new productive patterns. a similar task to the one addressed in this paper is the generation of question & answering exercises for english teaching, aiming at the same objective, which is to evaluate the comprehension of a text. the extraction of question/answer pairs from texts can be used as input to generate clues for crossword puzzles, by means of some transformations, as we show below. in @xcite neural approaches for generating q&a exercises for teaching are presented, in @xcite a similar work is presented using patterns based on different linguistic analyses (pos-tagging, semantic role labeling, coreference resolution, named entities recognition). another related nlp task is definition extraction, although with important differences from the problem addressed in this paper. our goal is to extract clues for creating crosswords from texts. these clues may not make any sense outside the context of that text since they are not true definitions of the terms, in the strict sense of a dictionary definition. an important reference on definition extraction is semeval-2020 shared task 6, "definition extraction from free text with the deft corpus" @xcite , in which a specific corpus for definition extraction was used to train models. fifty-one teams participated in this competition and most of them based their approaches on the use of pretrained language models. ## dataset and clue extraction we created a number of heuristic rules or patterns that can be used to @xmath6, defini-@xmath7. these rules were created by experimenting with a corpus of short texts, manually exploring and analyzing the frequencies of different expressions and patterns. we used a dataset comprised of 400 short texts obtained from the readworks website foot_1 , an educational technology nonprofit organization. read-works contains thousands of short texts and stories ranked in levels k, 1, 2, 3, 4, and 5 and categorized in the lexile scale. the texts are written by experts and curated by educators, and could be non-fiction, fiction or poetry, within these three thematic areas: science, social studies and art. in our experiments we used 400 texts, most of them belong to level 1, and a few to level 2. these texts include short articles about history, geography and science, and some short stories. our clue detection and extraction rules begin with a pre-processing phase in which we perform coreference resolution using the allennlp tool @xcite and simple sentence splitting. then we have a series of modules that apply different extraction patterns based on: syntax, semantic role labeling (srl), extended patterns that combine sentences, named entity recognition (ner), and question-answering (qa). all these patterns extract rough clues, and we use a post-processing module to improve the shape of the definienda and definitions. ## experiments after running our heuristics methods on all 400 texts of our dataset, our process generated 2321 <definiendum, @xmath8. however, the quality of these clues might be very variable, depending on the pattern and on the text they were extracted from. it is very important to analyze which clues were correct and could be used for crosswords, and also we are very interested in making the whole process more accurate. one way to do this would be having a classifier that could discriminate if a new clue was correct or not according to some criteria. in this section, we describe the annotation of our corpus and the classifier we built. ## conclusions we presented some experiments on automatic extraction of clues for crosswords from simple texts, considering a clue as @xmath9, @xmath10. we created several heuristic patterns for detecting and extracting clues using different nlp tools, like constituency parsing, srl, ner and qa. with these heuristics, we extracted 2209 clues from a dataset of 400 documents from readworks, and annotated them with information about correctness and grammaticality. the best heuristic pat-terns for extracting clues, according to our annotation, are the ones based on srl. using our annotated dataset, we trained several classifiers on the problem of detecting whether an extracted clue is correct for a crossword. the best model for this turned out to be a distilbert model finetuned on our training data, obtaining 84% accuracy and 78% macro f1. in the future, we want to explore the possibility of using large language models such as gpt or llama for this task, which have shown promising results according to some preliminary experiments. we also want to explore the possibility of improving the qa based pattern by using better qa extraction modules. currently we are in the process of testing our extraction system integrated to a crossword generation tool in a real case @xcite , with school children that are beginning to learn english, which would give us a better sense about how well our heuristics work and how they can be improved.