Crossword puzzles are both a popular language game and a fascinating area of research in artificial intelligence. Solving them requires a combination of language comprehension, rich and extensive knowledge and sound reasoning. This is a unique skill set for humans to possess and unheard of for machines…until now.
In this stream, Marco Ernandes discusses WebCrow, an AI-based software that can complete crossword puzzles using NLP expertise and the richest self-updating repository of human knowledge available: the web. Developed by expert.ai and the University of Siena, WebCrow is the first Italian and English crossword puzzle solver, and it is designed to be multilingual.
Transcript:
Brian Munz:
Hey everyone and welcome to our latest edition of the NLP Stream, which is a weekly series dedicated to the latest and greatest in natural language processing. I am your host, as usual, Brian Munz, I’m product manager and developer experience manager at Expert.ai, the leaders in NLP technology. And today we have a really interesting topic, talking about the WebCrow AI project, which is one which uses AI to solve crossword puzzles, and it’s just going to be a really interesting one and I want to get right into it because there’s a lot to talk about. And so our special guest today is Giovanni Angelini, and we’re going to start actually with a video which gives an overview of the WebCrow project, and then Giovanni’s going to get right into it so [inaudible 00:01:14].
Giovanni Angelini:
Hi to everybody. Hi everybody, so I’m Giovanni Angelini. Let me share my slides where, that I’m going to use for presenting my… Share screen, here window, for… Okay, is this correct? No. Stop sharing. Share again. I’ve done this before. Okay. Here I am. Okay. Let me introduce myself. I’m Giovanni Angelini, I work in expert AI in a group called Hybrid Language Technology which is doing research and development for Expert.ai. I work in this project, WebCrow 2.0, with different members coming from Expert.ai, like Marco Hernandez, which unfortunately is not here, [inaudible 00:04:53] and [inaudible 00:04:53] and some professor from the University of Siena. What’s about, what WebCrow deals with. Well, actually, the question is-
Brian Munz:
I think you might be sharing the wrong screen, actually.
Giovanni Angelini:
Okay. I’ll stop. [inaudible 00:05:20].
Brian Munz:
[inaudible 00:05:20]. Yeah. Sorry.
Giovanni Angelini:
Okay. I went your computer. I’ve done this before. Why? Okay. Yeah. This one.
Brian Munz:
Yeah, I think that’s the one.
Giovanni Angelini:
Oh, okay. So let’s go back again. Sorry about this delay. I am Giovanni Angelini and I work in expert AI in the Hybrid Language Technology Research and Development Group. So we’re going to talk about WebCrow 2.0. So this is a second version of WebCrow, which started time ago in the University of Siena, and now we actually are presenting a second version of WebCrow which is a work which is brought through the University of Siena and Expert.ai. Well, actually, what the question we are trying to solve in this project is, can machine actually solve crosswords puzzles? Crosswords puzzles, actually, it’s something that it’s not new for us in human beings because we are solving them since less than a century. And what makes them so interesting is that actually it’s not always the same, it’s quite of complex index.
Giovanni Angelini:
This complexity comes out from language. So actually what we have to do is we have to deal with language, which is not the same thing that has happened in previous challenges. For example, we have dance AI, have actually in history have other challenges with humans, machine against human, like with chess. In the case of chess, we have a domain which have strict rules in it. And it’s a strict domain, while this is in, it’s an open domain because it has to do with language. Here, we have two example of crosswords which were presented to human beings more than 100 years ago. One is the Italian crossword and one is an English crossword which came out in 1913 in the [inaudible 00:08:10] World magazine. Since then, let’s say we have published thousands and thousands of crosswords. What make it difficult for AI is actually that we are managing language. Language is not a closed domain situation like chess, but it’s an open domain and it has its complexity as we have to understand semantics in its meaning.
Giovanni Angelini:
So let’s go and see what actually WebCrow uses to manage crossword solving. Basically, I would like to highlight that we have three main things that we have to keep in account when solving crossword. The first thing is that we have to understand the clues, which means to read the clues for human beings. Obviously, this is quite straightforward, but for machine, it means to understand what the meaning inside the clues, the language, which is used, the concept, which actually are inside the clues. Then we have to actually make use of different pieces of knowledge, not just one kind of knowledge, but different ways of trying to find an answer to the clue.
Giovanni Angelini:
So we start from the clue, and then making some linguistic and logic steps, we try to find a way to find a candidate answer for that clue. That answer has to be put in a grid. So what we would like to show is that for solving crossword, we actually need a combination of tools, of techniques, which came from AI, from natural language processing, machine learning, and also constraint satisfaction. Constraint satisfaction, it’s part of solving crossword clues as we have to, let’s say, as each puzzle, it contains different answers and each answer has to actually be… It should match both across and down answers in the grid. What kind of knowledge we actually use for solving crossword clues? Let me show you three kind of knowledge we actually make use in WebCrow. The first one is a knowledge coming from ontology and lexicon. In this case, WebCrow makes use of Expert.ai knowledge graph, which is much more than us, a dictionary.
Giovanni Angelini:
We have different concepts which are related with each other through relationship and each concept actually has different information like which words we can use to say that concept with kind of grammatical role they have and what actually is the meaning of that comes it. Then we have, we need somehow an encyclopedia knowledge, which is knowledge coming from human, and nowadays, and also when WebCrow project started, actually we found that the web, it’s actually, it’s vast and continuously updating collection of human knowledge, which means that basically, if we’re talking about a film or we’re talking about a person or someone in a history, we can find something about these concepts inside the web. Obviously the hard part is actually trying to find it using the words inside the clues.
Giovanni Angelini:
And then last but not least, one of the things we use for solving crosswords is using knowledge which comes from puzzles, from crossword puzzles, which means that basically, what we do is what also human dos. The first time you solve a crossword puzzles, you actually have to learn how solving crossword puzzles works so you have to understand the logics. And then moreover, once you solve some crossword puzzles, you actually get some knowledge from crossword puzzle previously seen, which means that if you already seen a similar clue or a similar definition or an answer, you actually can try to use the knowledge you achieve by solving crossroad puzzles with new puzzles, and that’s basically what also WebCrow does.
Giovanni Angelini:
So for solving puzzles, we mainly go through three steps. The first steps, it’s the clue answering step. We have clue-answering experts which actually have a goal which is produce a list of candidate answer for each clue, which means it has to understand the clue and use some pieces of knowledge and some expertise, which means also AI tools and NLP tools to answer the clue. There are also some modules which actually are in charge of analyzing the clues in order to know what kind of answer we should expect. We will see this later, what it means. And then each list has to be evaluated, eventually enriched, with the two main goals. The first one is that basically, and this is very true for machine, we cannot afford, or least we have to try to not missing a correct answer in a list, which means we have very long list of candidate answer.
Giovanni Angelini:
But what the second goal is that we have to have, on top of this list, the correct answer, and this is something very, very important. In this new version of WebCrow, what we have done, we have changed architecture and we put an architecture which enables other expert modules to give their contribution to WebCrow. So basically, WebCrow sent some messages throughout [inaudible 00:15:52], a [inaudible 00:15:53] channel, and expect that some experts can solve or give their contribution and giving some answers to some, on some clues, using its abilities. So nowadays we have a technology which is open to other external contributions.
Giovanni Angelini:
The second step is basically, once we have a list of candidate answer for each clue, what we are going to use is the concept that we have to fill in a puzzle grid, and we have some constraints so we use the list in order to propagate the probabilities of each list to the other list which are near or have some constraint with the slots in the grid. We will see this a little bit better moreover. And for third thing, once we have done this belief propagation, we are going to fill in the grid. It’s a little bit different from human beings, human beings usually, to start, answering the clues, putting the solution inside the grid. And instead we have to, and machine has to think about it before filling the grid.
Giovanni Angelini:
So let me show you some example which will explain the concepts and ideas that I showed before. Here, we have a puzzle and I highlighted some slots. For example, we have one across, supportive kind of column, three down, sick, and then we have 25 across, Emilia Jones Best Picture winner, and then we have 14 down, cylindrical storage vessels, and then another clue, which is 46 down, which is drive, dot, dot, dot. Let’s go through these.
Giovanni Angelini:
The first definition I would like to talk about is the one across, supportive kind of column. So this, it’s clue which actually, it fits back with the knowledge coming from ontology and lexicon. Lexi, why? So the solution, the answer, the correct answer to this definition is spinal, because it’s something which is connected to column and to the fact that it’s something which is support. In Expert.ai knowledge graph, we can actually find two kind of columns. The first one is column in zoology, which is something which belongs to plants and animals, and the second one, it’s spinal column, which is related to column whereas a specification of column, hyponym of column, it’s a backbone which enabled animals to go on with their muscles and in human beings, cats and dogs.
Giovanni Angelini:
So using our knowledge graph, it’s possible to grab this information and put it inside at the top of the list as spinal column is very close to column and also to the fact that’s something which supports human beings and vertebrates to actually walk around. The other definition or clue I would like to show, it’s much more easy definition, which is the three down is sick. What we are trying to find here is a concept which is strictly related to sick and basically this relation is very, very strict and, as we can see in the knowledge graph, sick is, it’s a synonym of ill, and basically this is the solution of this clue. And we can found this situation in many other clues in crosswords and the knowledge graph obviously can grab this information very straightforward.
Giovanni Angelini:
Let’s go to another definition, to another clue, which is a definition which needs some encyclopedia knowledge. Here, we’re talking about a film, a Best Picture, who won something and when it was done by, or is connected to, Emilia Jones. Here, what WebCrow usually does in a web search model, it goes and try to search for some information related to this clue, go find a website which talks about Emilia Jones, about Best Picture, about winning something, and find out that actually CODA could be a good answer to this close definition. Be aware, it’s not as easy as it seems. Here, we need some NLP to understand the clue, we need NLP to go through the website language and extract, actually, what we’re looking for.
Giovanni Angelini:
And we are looking for something, a proper noun, which is CODA, which is the title of this film made by Emilia Jones. So basically, we need some NLP technology to actually grab this information and put it on top of the list. Then, let’s go through knowledge which comes from puzzles. In this case, we have this definition, 14 down, cylindrical storage vessels. Probably some of you already know the solution of this, the answer to this clue, and it’s actually silos. And silos, actually, it’s an answer to other clues in previously seen crosswords like tower for storing grain, where to store grain, cylindrical buildings and so on. What actually we do here, what Crow does here, is to actually manage the clues and the answer of previously seen crosswords. It needs NLP techniques to actually match the clue in the new crossword and try to see which is the best fit.
Giovanni Angelini:
And here we actually make use also of word embeddings, we make use also of neural ranking. So AI technology, in order to, we are not making an exact match, what we’re trying to do is a [inaudible 00:23:47] a smart match with the knowledge which comes out from previously seen crosswords and new clues we find in crosswords. Sometimes it’s good like in this case, some other times it’s not as good as it see. Here is another clue, which I would say, which it shows how clues which are typical of American crosswords we have like, what we call, fill in the blank, so we have a word we have to put after drive in order to find the correct answer of this clue. This also happens in Italian. Let me show you what in Italian happens.
Giovanni Angelini:
I don’t know. This is obviously an Italian clue, but let me explain in English what we do in WebCrow. So this is a definition in which we’re looking for something which is not in the web, not in our knowledge graph, not even in previously seen crossword clues. But it’s basically, in this definition, we are looking something which is inside a word in the clue. It’s in Italian. Let’s say it’s sort of… If I would say it in English it’s something like, say, a little bit of this word. So the word is ebbro and we are taking the first two letters of this word. Or other definition, which are what we call rule based, or like in the middle of ball. It’s not actually what we’re looking for something which is in the middle of the ball, but we actually are looking something which is inside that word.
Giovanni Angelini:
So we’re quickly running out of time so let me show you, what are the goals of the next step? Which has much more to do with constraint satisfaction. So we have a candidate answer list, we have different lists which are ranked by probability. We have the constraints. What we are trying to do is to maximize the probability of the chosen answer. So there are different ways in which we can fill in the grid. Basically, we could also choose a letter for each blank cell, but basically we know this is not good. What we have to choose is that if it’s our answer, which fill in the grid across and down, and we have to basically take care about the constraints.
Giovanni Angelini:
So what we do is we have some, like here on the right part of the screen, we see that silos is on top and here we have a true, a very strong candidate answer. And while we have other lists like in setups where the correct answer, it’s very low. So we basically propagate the probabilities in order to keep into account how are the constraints trying to higher, to score, make… The idea is that the score should go up for, if it fills well, down the constraints. And then the two goals is obviously to increase the correct answer based on the constraints and then to make the system robust to missing answers.
Giovanni Angelini:
So let me show you very quickly. The idea is that we have different probabilities. The red one means that WebCrow was not able to find the answer of the clue. And then we have very strong answers in some lists and this propagates the probability so it managed to higher up score of many, many, many lists which are around the lists with strong candidate answers. Let’s go through this a little bit quicker. In this, then we have to fill in the grid. And nowadays, WebCrow fills in the grid by calculating the probability of each letter and then this enables us to have even a much more stronger probability set, probability score, for each candidate answer and for each letter.
Giovanni Angelini:
Let’s go to the last part of the project, what we are doing in the next months. We are actually trying to challenge humans. We are going to do this at our international conference, WCCI conference, in 2022, which is in Padua. We will have two different kind of crosswords. Languages, which is Italian and English language, language crosswords puzzles in Italian and in English, American crosswords.
Giovanni Angelini:
These crosswords will be given by two different editors, one is an Italian editors, another one it’s an American editors, and we will try to challenge competitors both on site and both online using our challenging platform, which basically, it’s not a WebCrow challenging platform, so basically it will be a fair challenge. And we will actually give some special prizes and some gadgets who will compete during this competition in July, it’s the 20th July. Well, what I would like to say is that actually, Italian crosswords and American crossroads differ so there are many things which make the two crosswords different. Although this, the overall over structure of WebCrow can manage to solve both Italian and American crosswords. We also trying to extend WebCrow in order to solve other crosswords in other languages like French, and we hope to do this soon. So I think we’ve run out of time.
Brian Munz:
Great. No, thanks. That was actually very, very interesting. Yeah. I mean, I know I have questions, but we’re out of time. So if anyone has any questions, you can put them wherever you’re watching this and I’d like to thank Giovanni for presenting because this is a very interesting subject that’s kind of off the beaten path a bit. So thanks again for coming and presenting. And of course, I’d like to plug that you should check out the WebCrow project, as well as go to our try site, our demo site, for our APIs that have NLP and NLU capabilities. You can try them out yourself. But yeah, thanks everyone for tuning in. Again, if you have any questions, leave comments below and please join us for next week which is when someone from Accenture is going to talk about reducing operational costs with a content recognition center of excellence. So, until then, I will see you next week. Thanks.
