Karthik is a senior technical member of staff member and manager of a text analytics group at IBM Research India. His primary interests are in statistical modeling, applied to text and speech. He leads the team working in several aspects of text analytics, including information extraction, retrieval and machine translation. Prior to joining IBM Research India in 2008, he spent eight years in IBM's TJ Watson Research Institute and Human Language Technologies group working on improving speech recognition technologies. He obtained his PhD from Princeton University in 1999 and BTEC from Indian Institute of Technology Madras. Karthik, that's yours. Okay, thanks. So what I'll be talking about today is about the building of Watson and an architecture that enabled the building of Watson. So a few years ago, IBM Research undertook this effort to build a machine that plays this game called Jeopardy, better than the best human champions, right? And about a year and a half ago, you know, on television, the machine actually beat a couple of people who, you know, until then, I think one of them was unbeaten and the other had the longest winning streak or something like that. Okay, so Watson is the name of the system, you know, that played Jeopardy. And Deep QA is the architecture that sort of enabled the building of Watson. So, I mean, this system was a large system and obviously in a 40-minute talk, I'm only able to give you a flavor of the challenges and some of the ideas behind, you know, the building of the system and sort of, and the architecture that really enabled, there's basically no single thing that worked really well, right? The architecture enabled you to plug in a lot of things and that's what enabled finally the system to win. And just to mention at the start, the work was done mainly at the Watson Research Center in York, led by a team called, led by Dave Ferrucci, and the work happened over some years, right? Okay, so just to start off, like, I just want to talk a little bit about Jeopardy, just to give you a feel for what the system was trying to do, right? So, Jeopardy is this, essentially, it's a quiz show.  So, the categories may indicate, you know, the answer type. So, you know, the classics, great outdoors, things like that. But it's kind of a little bit vague, right? Often can't tell what the answer, you know, what is the type of the answer that's being looked for. And there's, you know, different levels of difficulty, okay? There's basically three players, right? And one of the players has the chance to select a clue, so they can pick on this board, you know, which clue they want to select. The question is read out, right? Something like this. And you give the answer in the form of a question, but that's, you know, not really important. So, all players complete to answer. So, one person gets to choose the board, all players complete to answer. Whoever buzzes in first, right, gets to answer.  If you answer wrong, you lose that dollar amount, right? And the goal, of course, is to have the largest amount of dollars at the end. And there's some details that we can skip it. Prior to, you know, this challenge of deciding to build a computer that plays the best humans, there was this previous thing that IBM had undertaken. I think in 97 this happened. So, you know, the challenge of playing chess better than the best chess players at that time. And, you know, the reason this new one was undertaken is, you know, just to get into the space, which is kind of very different from chess. In chess, the rules are, you know, well-defined. The search space is finite and, you know, although it's large, it's finite and well-defined. Whereas human language is sort of ambiguous, you know, words don't have meaning by themselves. It's all, there's context and there's, humans tolerate a lot of ambiguity in, you know, while conversing in natural language. And essentially the search space, you know, you can say, yeah, maybe it's larger, right? In this case. But essentially it's quite a different sort of a challenge than playing chess, right? That's the basic point. Now, before getting into, like, what is hard about this, you know, some things that a computer finds really easy, right? Some large calculation. You know, as humans we can't do this, but for a computer it's easy, right? And some other things, right? If you want to answer a question, like, what prize did David Jones pay for a laptop? If you have a database where, you know, you have, you know, people, the serial numbers of the items they bought, serial number linked to the invoice number and the invoice number linked to the payment, you know, this is just, this is simple, right, for computers. Already, like, if, you know, if instead of David Jones you say Dave Jones, then it's a little bit tricky, but still it's, you know, it's just this little bit of a fuzzy match to do. But these are the sort of things that, you know, is easy, basically, for a computer, right? Natural language, like I mentioned before, it's implicit, highly contextual, ambiguous, right?  If you had a database which had, you know, people and their place of birth, you know, then it would be easy to just look up the person in this database. But, you know, like, so the thing that Jeopardy, this Watson system is trying to solve is trying to get to that same information from text like this, right? So, you know, from this sentence, you can tell that Einstein was born in Ul, but it's kind of hard to figure it out, right? And certainly it's hard to build a system that can figure these things out.  So that's basically the challenge that the system is trying to address. So, just to summarize some of the things, right? Why did IBM pick up this particular challenge? So the thing is it is broad and open domain. So it isn't that you can sort of go and say, okay, I'll make a database of all people and where they were born and, you know, people and the organizations they ran and, you know, just a few databases like that wouldn't cover the range of questions, like that you would get in a quiz show like this. The language is very complex, right? So, I mean, if you look at the questions, some of the questions are shown up there, right? The language is complex. Often, you know, there are meant to be jokes in the questions that are puns and so on, right? So it is, the questions are essentially not easy to understand. They're not of the sort like where is X born, right? Where the question is simple and you can sort of potentially write rules to decide how to understand that sort of text. The other thing is high precision is required, right? You need the answer. If you don't get the right answer, you lose money, right? So you have to be very precise and the next point is accurate confidence, right? You have to know when you know the answer so that you don't buzz in when you aren't sure of the answer, right? So the confidence that the system needs to know what it knows, right? And the other thing is high speed. So the game, it's a quiz show where everybody is buzzing in. If you don't buzz in before the other players, you don't get to answer. So you know, you need to do this. All the calculations that you need to do to come up with the right answer, those need to be done really fast, right? So these were sort of some of the considerations in deciding to, you know, choose this as a challenge to go after. So just sort of just illustrating one of the points, right? Broad domain. So this graph is actually showing on the x-axis is the answer type, right? And on the y-axis is the fraction of questions that had that answer type, right? And, you know, this is just collating statistics over previous Jeopardy games, right? So if you look at, you know, the most frequent answer type is he, right? Which is, you know, so you know it's a male person. And that accounts for 2.5% of the questions.  So it's basically a long tail distribution that, you know, you're not going to make much progress by saying I'll look at each answer type. For these answer types, I'll build up some table that stores all the information about that answer type and so on. Right? So basically, you know, the domain is broad and you're not going to make much headway looking at, you know, looking at the head of the distribution, okay? So the focus of the system was basically, you know, it's a challenge in building NLP technology, right? Natural Language Processing Technology where you're trying to read natural language text and trying to extract the answers out of this and being able to know, you know, how to answer questions based on all this fairly large amounts of text data, right? And, you know, structured sources are used but they are sort of just used to sort of help interpret the text and a lot of the text, a lot of the structured, a lot of structure is derived from just natural language text and that's sort of the main source of information that is used to answer these questions.  Of course, the challenge is, you know, we want to be, we don't want to return a document, we want to return the answer and it has to be, you know, the top one, otherwise you don't win, right? And just as an example though of, you know, how keyword evidence can lead you astray. So this is an example question, right, on the top left. In May 1898, Portugal celebrated the 400th anniversary of this explorer's arrival in India, right? And I think most of us know the answer but, you know, somewhere out there there's this other sentence, right? In May, Gary arrived in India after he celebrated his anniversary in Portugal. Now, there's a lot of words that sort of match up, right? But obviously, Gary is not the right answer that we're looking for to this question, right? So, you know, this is basically the challenge, right? Of going beyond keywords and sort of getting a deeper understanding of the text to be able to score the likelihood that Gary is the answer to that question, right? And this, the challenge, of course, is that this stronger evidence is much harder to find and there's no single thing that, you know, tells you that's very strong evidence, right? So one of the things behind this architecture that was built is that it allows you to put in, throw in lots of types of information which is then combined in sort of an optimal way, right?  So the event happened in 1498. There's some sort of, you need to know that, you know, landed in is the same as arrived in, right, or arrival in, right? So because, you know, the sentence that's giving you evidence that the right answer is Vasco da Gama is using the word landed in, right, instead of arrived in. And then you also need to know, for example, that sentence talks about Kappad beach and you need to know that that's in India, right? Because the question asks about, you know, the arrival in India, right? So there's, first thing is the, you know, keywords are good, good source of evidence, but it's not nearly enough. And there's all these other kinds of things that you need to handle to play jeopardy well, right? You need to reason about time, some amount of geospatial reasoning and so on. So there's lots of special things that you need to do to play jeopardy well. So, I mean, just some other examples, right, of the complexity of what happens in jeopardy. So, you know, this question, when 60 minutes premiered, this man was a U.S. president. So here, you know, there's two parts to the question and to figure out the answer, you need to sort of separate these two parts. You need to know when 60 minutes this TV show premiered and, you know, then you need to say who was the president in that year, right? The year that 60 minutes premiered. So basically, one of the things is this deep QA architecture that plays jeopardy, you know, it attempts different decompositions of the question.  And, you know, in this example, you needed to put it back together in a certain way, right? One of the answers was this year and then you need to say who was the president in this year. So that's the way you're putting it back together. And another example that, you know, of the kind of stuff you need to do. So this is a clue, right? A long tiresome speech delivered by a frothy pie topping. And, again, you need to split it into two parts. But in this case, the answer is, you know, just the combination of the answers to those two parts. So, I mean, you need to split these sentences, questions up sometimes. You need to then figure out how are you going to combine these things back to create the right answer. And, you know, in this case, like the category was edible rhyme time. So it's kind of indicating what sort of thing you want for the answer, but it's pretty, you know, it's pretty tricky to know what it is. Another example of sort of the complexity of this thing is because, so often you don't have text containing all of the pieces of the answer, right? So in this question, I mean, just on that top figure, you know, you may, sort of thing that it tries to do is that shirts have buttons. So do TV remote controls and telephones, right? So in this question, on hearing of the discovery of George Mallory's body, he told reporter he still thinks he was first, right? And you may not find any text which puts, you know, the right answer to this is actually Edmund Hillary. And you may not find any text which sort of has all these pieces together. And so you need to piece together this graph that, you know, links George Mallory to Mount Everest and also Edmund Hillary to Mount Everest, right? So, okay, so I guess I've convinced you that the game is fairly hard to play for a computer, right? And this chart here just shows basically the performance. So, okay, the two axes are, you know, what fraction of questions did a player answer? And that's on the x-axis. On the y-axis is the precision, right? Given that he answered 100 questions, what fraction did he answer correctly? Now, the red dots are sort of the grand champion performance that the system was targeting to beat, right? So those red dots, all those dots on the top, you know, top here are basically human players' performance. The red dots are grand champions. And all of these are actually winning performances, right? So these are winning performances. And, you know, the red dots are sort of the champion players. So they answer a lot of questions, you know, roughly maybe 70% of them. When they do answer, they are 90% correct. And when IBM started... So when IBM started with this, IBM was already participating in these question-answering competitions, right? Which were, you know, which were happening at that time. And in 2007, this was sort of the brown curve there was the performance of the system, right? So it was quite a way below, you know, where we needed to get, right? This was sort of the state of the art. I mean, IBM systems then used to participate and be in the top few systems of all the, you know, competitors in these competitions, right? So there was a long way to go, right?  That's the red curve. And the other curve, you know, the blue curve is just doing sort of tech search with, you know, essentially keyword matching. So basically, both of those approaches, I mean, this is on a small domain sort of thing where the structured knowledge base had some reasonable coverage. Basically, you see, you know, it's still way below this, you know, where we want to get to. This is just illustrating the fact that neither keyword search nor, you know, trying to build a database of which contains all these answers is sort of a viable approach, right? Okay, so this sort of is the high level, you know, architecture of the system, right? So the question comes in on the left here. You know, there's an analysis of the question which includes things like deciding if you want to split this question up into parts, decides, you know, what is the answer type that's being asked for. So he landed in India, that means answer type is he, right? So that's the sort of thing that this question and topic analysis module deals with. And, you know, once it's done, like I said, you know, the question is perhaps decomposed into many sort of sub-questions and each of these is handled in parallel, right? So all of the parts are sort of handled in parallel and that happens, you know, at all stages, right? So at the question analysis stage, you may come up with several different sub-questions that you need to answer in parallel. While looking at, you know, so, okay, this, so, okay, let's just go through this first. So this candidate answer generation box here, that sort of looks at the keywords or whatever, extract some things from the question that, and then looks up what might be candidate answers, right? So you do a primary search, which is essentially a keyword-based search. You get some top-ranking documents and from those top-ranking documents, you try and pick out what are candidate answers, right? Once you do this, you're then looking at more detail evidence. So I mean, the way this is going is that initially you do some sort of lightweight, more lightweight processing, try to get some candidates and then do more sort of detailed processing. But now you've sort of restricted your candidate set to a smaller set so you can actually do more detailed processing, right? So this first step is just doing sort of a keyword search and then trying to get, bring up some documents which may contain the right answers and trying to pick out where the right answers are in those documents. The next box here, which is about, you know, hypothesis and evidence scoring, that's sort of evaluating different sorts of evidence. So one of the evidence might be, like, what is the keyword match between... So what is done at this stage is you put the answers back, the candidate answer back along with the keywords in the question, do another search and come back with passages that contain all of this information and then sort of do a more detailed evaluation of those passages. So you could look at, for example, the keyword overlap between that passage and, you know, your original question and things like that as one of the sources of evidence. But I'll sort of discuss that, you know, there's many more sources of evidence that need to go into this to make, sort of, to make the system better. The synthesis module is trying to then combine these different pieces, right? So you might have split your question up into these different parts. You're trying to then combine those pieces, you know, in the synthesis module to sort of come up with the one answer, right? That might involve just putting together the answers of these different parts. It might involve other things.  You've computed these different evidence scores and then you're trying to like, you know, rank all of these merge all... So you may have duplicate answers, right? You may have Albert Einstein in there. You might have A Einstein and you might have some evidence with the name A Einstein and some other evidence with Albert Einstein. You need to figure out these two are the same and sort of merge those two things before comparing it with your other candidate answers, right? So this final step is doing the merging of the candidate answers and doing a final ranking based on all your evidence that you have sort of collected, you know, in the previous steps, right? So this is sort of at a high level, you know, the kind of stuff that's done. I mean, the main thing here is that things are done in parallel. So, you know, once you evaluate... once you sort of split up the questions into these different parts, you do it all separately, once you figure out... once you retrieve some different candidate passages and from each of those, you get some candidate answers. The evidence for each of those can, you know, then again be done in parallel. It's only at the end that you need to combine this in sort of together. And, you know, the number given here... I believe it was like a million lines of code and, you know, it says thousands of natural language processing algorithms, right? So there's basically what was found is that, you know, there's no one bullet and actually the work that was done in building the system, there's a series of papers that came out in, you know, last month in the IBM Journal for Research and Development which sort of describes these various parts of the system. So if you're interested, you know, there's sort of details that have been published just last month. Yeah, and so this is what I was talking about, right? So there's this explosion of things as you, you know, each of these modules, you know, generates possibilities and you sort of keep calculating on all of them, pruning them down and sort of the pruning is, you know, as fast as possible, we try to keep it at the end, right? Okay, and just, you know, to illustrate again, once again, the difficulty of this task, this lists some early answers, right? The things in green are the correct answers and the things in red are the wrong answers that an early version of the system was giving, right?  And it's kind of hard to figure out, you know, to get to that 80%, 90% precision while answering about 70% of the questions was actually fairly hard. Just to illustrate sort of the processing that's going on in that pipeline that I showed, right? So this is a question, right? So the first step is to just analyze the question so you might extract keywords, you might extract the fact that, you know, the answer type in this case is a Comet Discoverer and there's a date mentioned in the question 1698 and so on and there are some relationships, you know, there's a ship that was, you know, more pink was the name of the ship. So there's some relations that are mentioned in the question. You do a primary search which is, you know, essentially a keyword search plus, you know, slightly more structured based on these things you've extracted from the question and you come up with candidate answers, right? So in this case, you know, it was a Comet Discoverer. You may not want to use it at this early stage. So anyway, these were the sort of candidate answers that the system came up with based on all the keywords. You then go and put these answers, candidate answers back in the question, do further searches to, you know, find passages that provide evidence about each of those possible answers, right? So you might plug Isaac Newton back with all those other, you know, words in the question, search for passages and come back with other potential answers. Find a comeback with passages that indicate that this is a potential answer, right? You then, these are sort of the evidence profiles that I mentioned, right? I'll talk a little more about what these are. But one of those, for example, would be keyword evidence, right? And then you have several others. And then you merge and, you know, combine all these back and in the end you have, you know, Edmund Haley ranking at the top and you have an 84% confidence in this answer, right? One of the things, one of the key parts of the system is this part that actually automatically learns from reading documents, right? So its input is large amounts of text and the output, you know, you get some sort of semantic knowledge, you know, for example, that a fluid is a liquid, that inventors, patent inventions, that official submit resignations and things like this, right? So this is basically one of the knowledge bases that's automatically extracted from the text from large amounts of text that is then used for several things in the system, right? So one of the things I'll show in the next slide is it's used to give evidence that, you know, of an answer type. So there's an answer type that you're looking for in the question and you want to know if there's evidence that, so for example, if Albert Einstein is a scientist, right? So the question might mention this scientist and, you know, one of the candidate answers Albert Einstein and you want to know is there evidence somewhere that Einstein was a scientist, right? So that's the sort of stuff that this knowledge base is used to provide information about. So, I mean, the way this is done is, you know, you read the plain text, you sort of use standard, at this point, standard natural language processing technologies like parsers and, you know, entity extractors, so which, you know, for example, know that Einstein is a person and a scientist, 1921 is a year and so on. And then you have a parse of the sentence which sort of gives you, you know, the relations between the different words.  So this sort of information is used, for example, you know, to answer such questions, right? In cell division, you know, there's this question and you're looking for this liquid and you have some candidate pass, you know, one of the candidate answers is cytoplasm and it's mentioned that cytoplasm is a fluid surrounding the nucleus, right? So if you go and look up on WordNet, a fluid is not a liquid, right? So a liquid is a fluid, but a fluid is not a liquid, strictly speaking, but often these two words are used interchangeably, right?  But, you know, based on just reading all this amount of text, you can figure out that essentially in natural language, people use fluid and liquid interchangeably and, you know, all things that were referred to as fluids were also referred to as liquids, right? So this is the sort of stuff that basically you can extract by just looking at large amounts of text, right? A little bit about this evidence profiles, right? I mean, I've been saying that keywords is one thing that's, you know, part of this evidence profile. There's other things, right? You know, just things like source reliability. If you get a stuff off of some blog page, it's less reliable than if it's on Wikipedia. Things like that. I mean, I won't talk much about this, but I'll just give an example of the sort of thing that the way the system was developed, right? So, you know, you have these different sort of evidence profiles. This is a question, right? You will find Bethel College and a seminary in this holy Minnesota city. And there is actually a Bethel College and a seminary in both cities, right? In St. Paul and South Bend, right? And basically all the evidence that was in the system at the time wasn't able to distinguish between these two answers, right? And so what was actually done in this case was to add a pun relation, you know, score, effectively. So there's basically this information, right? It's saying holy Minnesota city which sort of indicates that the answer is St. Paul because of this pun relation score, right?  You say, okay, how can I figure out that this thing is the right answer and not this other answer that I'm currently generating? And you may end up adding, you know, a different evidence sort of mechanism that indicates, you know, that right answer. One thing also which I mentioned before is that categories, you know, are not often that simple, right? So, I mean, just to give an example. So, you know, this category, and so what the system actually does is while playing, it's trying to figure out what this category type means, right? So in this example, like the category was celebrations of the month. And so initially it's not clear what is the answer type. After observing, like, a couple of answers to a couple of questions in the round, right? So these are the first few answers that, you know, so the Watson's answer is shown in red for the first three questions, right? And, you know, the correct answer based on what happened, you know, was these, right? June, November, and May.  And so there's some amount of online learning that's happening that allows the system to get better, right? So on the next two answers, it was able to, you know, on the next two questions in that category, it was able to get the right answer because it's figured out the right answer type, okay? This is sort of, I mean, I guess I've talked about most of these things. This is just sort of, you know, some of the highlights of the system. I'll just skip over that actually, okay? Okay, this is sort of, you know, a progress chart as a function of time, right? So we started, you know, at the bottom brown curve when, you know, when the project was started. And these other curves are sort of the progress as, you know, basically as a function of time, right? So there's the time labels on each of those. And so by November in 2010, you know, the system was up in that, in the same cloud, sort of at least partially overlapping with where all the red dots are, right? So at least some of the red dots are below the blue line, right? And so what is happening in all of this time was like various different things were being tried out to see if it actually improves the performance of the system, looking at sort of an error analysis of what is happening. What things is the system getting wrong and what sort of somewhat general things can you capture to get sort of a next fraction of answers, right? Just a little bit about the, you know, the... So the system is built on UEMA. So, okay. Okay, so the system is built on UEMA. UEMA is a framework that's now out there in the open source. It allows to build sort of text analytics applications where, you know, you can have several modules that talk to each other and it sort of makes it easy to do. And given the fact that there were so many different modules that are computing so many different things, this was sort of essential. And UEMA AS allows for scale-out. So you can then parallelize a lot of these computations that can actually happen in parallel. And that allows you to get to, you know... In this case, it allowed us to get to answering the question in the time we needed to, right? So basically, you know, you sort of need to buzz in in three seconds after... Watson got the question as it was flashed on the screen and basically you need to buzz in in sort of three seconds pretty much. And so the actual amount of computation that Watson was doing to answer a single question was about two hours, right? And basically, using this parallelism, it basically then ends up answering a question in, you know, two to six seconds. There are some other parts of, you know, of the system that we haven't talked much about, you know. The natural language processing is the main aspect. But there's also basically this game strategy, right? When do you decide...  Which questions do you decide to choose? How do you decide when to answer and when not to and so on? So I'll skip over those. I have only a little time left, so I'll just talk about a little bit about, you know, the difference between Watson and a search engine, right? Like, and some possible applications that we are working on right now. So, you know, we all use search engines and, you know, as a decision maker, you know, if you need to find out about something, you have some need in mind. You distill that to a few keywords. You go and do a search, and then you look at the documents that come back. You may modify your query, find more documents.  What Watson is enabling, in principle, is that you just ask a natural language question and the system comes back with a set of potential answers, right? A lot of the stuff that we normally do is being done by the system, right? And one of the things that we looked at is sort of a medical application, right? An application in the healthcare domain. So here what has been found is that a lot of the errors that happen in healthcare are due to diagnostic errors. And one of the reasons for that is that, you know, the doctors make up their mind too soon. Basically, based on the evidence they see, they might come up with a diagnosis that's reasonable, but there may be like one or two other possibilities that they have sort of overlooked.  You pose a question to the system and it comes back with this list of answers. And although the top one is probably what the doctor suspects anyway, he can get to look at these other things and then sort of in his mind either rule them out or maybe order additional tests to sort of, you know, to eliminate those. Okay? You know, sort of another application, possible application as technical support, right? You know, lots of people are just on phones answering questions people have about some product they bought or something like that. You know, can computers just automate this task, right? That's, can Watson automate this task? That's one question. There's similar knowledge management challenges inside enterprises, right? Search works quite well. Google search works really well for information out there. Like typically search in enterprises works far, you know, far more poorly. There's usually much less duplication of information. It's, there's many, and so, you know, for example, if you put in the wrong keyword, you'll find nothing on Google. You'll, you know, find some other page that uses the same keyword that you put in, right? So, just search inside enterprises as a task. That's potentially an application. So, you know, I'll, since I'm out of time, I'll end here. I'll just go to my last chart which has a picture of all the people involved just to show you that it was a large team involved over several years, right? These are some of the people who worked on the system. So, I'll take questions now. Questions? My question is, how important is the curation and selection of the sources that was used to create the database knowledge base or whatever? And one more question is, if speech-to-text were also part of the sort of problem to be solved, how much more difficulty does it add? Yeah, so speech-to-text, we didn't solve in this, and it would make it much more difficult, I believe. I mean, that's the reason we left our IBM has been working on speech-to-text for a long time, but at the state of the art, I mean, I don't know if you have numbers to say, you know, where that curve would go if you had to do the...  There was another question, right? Yeah, so the sources are quite important. So, for example, when you want to then go and build it for healthcare, you need to figure out, I mean, the sources that were used for jeopardy are clearly not adequate. You need to go and think about what sources would be more appropriate. So the selection of sources are important, not so much... Then it's pretty much the processing is fairly automated, right? No, so one of the papers that I mentioned is actually looking at identifying knowledge gaps. So if you have a set of questions that sort of represent the sort of things you need to deal with, you can then go and look, you know, are my documents adequate or not and sort of, you know, come up with these ones which you're not able to answer and then think about how you're going to get... So then you can think about doing Google searches with some of those keywords and picking up some common, you know, sites that contain a lot of that information and think about whether... So, yeah, it is a problem deciding what to put in. And that's pretty much done fairly manually, there is a, you know, process that tries to go and find what we are missing and then selecting more stuff based on that. Hi, I have two questions actually. So one is, was there any category or topic in which you found that Watson wasn't doing particularly well? And if so, was there any particular reason for that? Second one is, so you mentioned earlier that the first part of Watson was after the question was passed and the components were figured out, it would basically do an answer matching, answer search with an existing structure, right? So could you talk a bit more about how this structure was stored? It's obviously not how a traditional search engine would probably index this thing because here it's more like a graph where different... You need to build relationships between the different objects, right? Yes. So is there any existing literature that talks about that? If not, could you briefly mention? So for the initial search, it's pretty much the way standard search engines are done because you just need to go over a lot of documents and get the, you know, candidates. Once you have the candidate answers and you have a smaller set of passages and the more detailed evaluation of potential answers, then uses custom data structures to, you know, do sort of the evaluation. So the initial search is still pretty much keyword based because you put it in a usual index, sort of index, two or three different ones were used with two or three different sort of standard scoring functions. I think those are mentioned in the papers, you know, which have come out since then. Whether there was a particular... I don't think there was at the end any one particular category, right? Because that was sort of... The development over several years, that's what was happening is to go and look for these patterns of things that it gets wrong and then sort of, you know, solve that. That sort of category that was still left at the end. I mean, these categories are very sort of, there's a long tail, right? There aren't, first of all, categories that are huge, right? So I wouldn't say that at the end there was any sort of particular things. I mean, they were obviously things that we knew the system should be doing that it wasn't doing. Like for example, it once gave the same wrong answer as one of the... So a person answered first, he gave an answer and then Watson gave the same wrong answer. So this was sort of, for example, a pattern that was known. We wanted to fix it. This requires speech to text, right? You need to know what the person said, but it just wasn't done in time to be a part of the system. And there were other things, right? So, you know, I think one of the... It answered a Canadian city instead of a U.S. city when the category said U.S. city. And this is obviously because it waits, it has all these features and it has sort of a machine learning approach and there is, you know, the category type and there's some wait for that category type. But, you know, it's still doing things that humans wouldn't do, but, you know, I don't think there was sort of patterns that are at least easily solvable at that point. Last question. Hi, up here. A follow-up to the previous question, can you give us a flavor of what kind of documents or corpora you used just as a sample? Yeah, so the main corpus for the Jeopardy game is Wikipedia. That's the single biggest... single most useful corpus. Then there were things done like going and crawling a bunch of books and even like indexing. Yeah, so there was a lot of stuff, but the single, I mean, I don't know the exact numbers, but like you would have gotten quite a way up there as the final system if you had just used Wikipedia. Great. Thanks, Karthik. We'll be back at 11.30.


What's up everybody? JC here for jazzy's case breaks.com shows the 19 tops five-star baseball eight box case break picketing number 33 sold out Here it is. I believe there's no d-backs or Diamondbacks or Rockies. So there you go. Lee. I'm getting the Brewers last spot mojo Again tough break to hit in but if you do it's very nice Remember only two autos per box And eight boxes so pretty much only half the league if anything may hit, but it's always a fun break All right, so after fires that would do quick sapphire and then we do prison blasters and then we end off with Supreme Hart Hort And have a good night guys J cave to the Minnesota Twins Minnesota Twins Derek And we got Tony Perez 19 out of 25 Reese McGuire that is a blue Jace and Daniel and Jacob de Grom to 50 one off the jersey number 47 out of 50 for the Mets Winner Joseph Cedric Mullins we got Dennis Eckersley two out of 25 That is Oakland Oliver Miles straws to 25 Houston Astros Liam Carter Keeboom Thanks for Bryce Wilson and cow right to 15 I wasn't gonna be Tyler, but I just felt a little obligation to stay as late as I could and With the family emergency and stuff. I was able to stay an extra hour. So I decided to just stay All right next box Everything's a little bit better. So Didn't have to rush out of here, although I couldn't just leave but I was like at least I only stayed in town, but extra hours, okay Josh hater To 50 With Maryfield All right two more and wow look at how nice this card is Aussie Smith like a little shadow box 12 out of 25 Thanks AJ Steven Matz our last box guys Paul de Jong Cardinals gonna X line and Steven Duggar. All right, and there you go guys This was five star eight box case for Pikachu number 33 on Jasper's case breaks calm again Really tough break to hit him, but when you do these are very very nice clean on card Autograph cards that are very very nice So appreciate it guys coming up next is sapphire


I am Igor Spanos, and this is a pre-recorded presentation for the paper called Security Under Message-Drived Keys, Signed Cription in iMessage. It is a joint work done with Mihir Belare while at UCSD. In the wake of his learning about the existence of NSA's Prism program, the security of private messengers has been put in the spotlight. Nowadays, the instant messengers are very widely used, and a number of them claim to provide end-to-end encryption. The question you want to answer is, are these instant messengers really secure? And how secure they are? It is not so easy to tell. These applications include new cryptography, which deserves analysis by cryptographers, and of course the overall security involves a lot beyond cryptography. Prior work is given definitions, schemes, and analysis for a technique called ratcheting, which is widely used in instant messaging. This work is similarly motivated by iMessage. In 2019, it was estimated to have 1.3 billion active users, and it provides end-to-end encryption. Our analysis of iMessage is based on the protocol description that is available at Apple Ios Security webpage. However, some details are missing from this description. In order to fill in the missing details, we also refer to the prior reverse engineering efforts. Let us start from examining the old end-to-end encryption protocol that was used by iMessage in iOS version 9 prior to 2016. In order to send a message, the sender encrypted with AES-CTR using an ephemeral encryption key sampled uniformly at random. It didn't encrypt the symmetric key itself using the recipient's RSA public key. Finally, the sender signs the hash of the produced cybertext using its own signing key, and pucks the three values into a single cybertext. In 2016, Garmin, Green, Kaptichuk, Meyers and Ruschenan found a practical chosen cybertext attack against this scheme, which resulted in being able to recover encrypted messages. This vulnerability was acknowledged by Apple, and it was fixed starting from version 9.3 of Apple Ios. In order to prevent the attack, the current scheme no longer samples the AES key uniformly at random. Instead, it samples an 88-bit long HMAC key, and then computes a 40-bit HMAC tag by hashing the public keys of the sender and of the recipient, along with the message that needs to be encrypted. The AES key is then produced by concatenating the 88-bit long HMAC key with the 40-bit long HMAC output. The rest of the encryption algorithm remains the same as before. The main question you want to answer is whether the new scheme is secure, and specifically has the 2016 attack been thwarted. On the more theoretical side, we observed that iMessage encrypts a message under a key that is itself a function of this message. This is an interesting technique, providing encryption under a message-derived key. To answer the question about the security if iMessage we need to start by identifying the security goal targeted by the iMessage design. Our answer to that is the goal is Syncryption. Syncryption was introduced by Zeng in 1997, and its security was formalized by An, Dodis and Rabin in 2002. Syncryption combines encryption with signatures to build a single primitive that simultaneously provides both the privacy and the authenticity of the syncrypted messages. An, Dodis and Rabin define two types of syncryption security. An adversary attacking the insider security is assumed to have its own pair of syncryption keys that belong to the user network. An adversary attacking the outsider security does not possess its own key pair in the network. To summarize, syncryption can be thought of as the asymmetric analog of symmetric authenticated encryption. Interestingly, neither any Apple documents we found nor the 2016 attack paper explicitly identify syncryption as the goal. But identifying that as the goal provided us with some insights. First, its original iMessage implemented a variant of the encrypt-then-sign composition that was proposed by An, Dodis and Rabin back in 2002. Furthermore, the 2016 attack against iMessage is a clever practical rendition of the generic attack on the insider privacy that was also explained by An, Dodis and Rabin. So it is clear that the current iMessage scheme also aims to provide insider security. Not that we have identified syncryption as the goal, let me summarize our contributions. On the theoretical side, first we give syntax and security definitions for syncryption in the messaging setting. We also define a new symmetric primitive called encryption under message-drapped keys, abbreviated as EMDK. Next, we give general constructions of a syncryption scheme from EMDK, public key encryption, and signatures. Finally, we prove the insider security of our scheme. On the practical side, we can now instantiate our theoretical construction to recover the iMessage protocol. This lets us obtain the security proof for iMessage and derive a quantitative security balance for it. Going back to the theoretical side, we provide attacks that much declined lower bounds of the practical construction. We expand the standard syntax of a syncryption scheme to the multi-recipient setting, and we pass the user identities as explicit inputs to some of the algorithms of the syncryption scheme. This key generation algorithm produces a key pair that can be used with any user identity. The syncryption algorithm SIG-ENG takes a plaintext message, the identity and the key pair of the sender, and the set containing each recipient's identity and public key. It returns a set of cybertexts where each cybertext encrypts the plaintext message for a distinct recipient's identity. Then the unsyncryption algorithm VerDec takes the cybertext, the sender's identity and public key, and the recipient's identity and the key pair. It returns the decrypted plaintext message. It calls the standard security definitions for syncryption as defined by Ando, Desin, Robin. The privacy of syncryption is an INDCCA-style security definition, where the adversary is given access to the left-to-right syncryption oracle, and to the unsyncryption oracle. The adversary is required to guess the challenge bit used by the left-to-right oracle. The authenticity of syncryption is an UFCMA, or Cybertext Integrity-style definition, where the adversary is given access to the syncryption oracle and to the unsyncryption oracle. The adversary is required to forge a new cybertext. We provide separate definitions of privacy and authenticity, and we also unify them into a single security definition that simultaneously captures most of them. We provide all security definitions into a multi-user setting, where the adversary has full control over the network and is allowed to expose user's secret keys. Our definitions allow to capture both the insider and the outsider's security notions of syncryption by considering different classes of adversaries. Finally, we parameterize all of our security notions by relations that determine which queries to the unsyncryption oracle are considered valid. This results in a definitional framework where choosing different relations allows us to capture different security notions for syncryption in a fine-grained way. Next, we define a new primitive called encryption under message-drive keys. This new primitive captures a special type of symmetric encryption. We'll refer to it using its abbreviation, an EMDK scheme. The encryption algorithm of an EMDK scheme generates a secret key that can depend on the plaintext message that is being encrypted. The decryption algorithm of an EMDK scheme uses the standard syntax of symmetric encryption schemes. We modeled the core part of the IMSH protocol as an EMDK scheme. The encryption algorithm of the scheme generates the secret key as follows. Half of the key called R0 is chosen uniformly at random. The other half of the key called R1 is produced by hashing the first half together with the message. The two halves as in concatenated together and used to encrypt the plaintext message M with the counter-mode of the AES blockcyper. Our goal is to analyze the security of the scheme, so let us start by defining the two necessary security notions. First, we define the authenticated encryption security of an EMDK scheme. The security game provides the adversary with an access to the left-to-right oracle and to the decryption oracle. Each call to the left-to-right oracle generates a distinct secret key, and therefore each call to the decryption oracle has to indicate the index I of the secret key that needs to be used for decryption. The adversary has to guess the challenge bit that is used by the left-to-right oracle, and the adversary is not allowed to trivialize the game by calling its decryption oracle in a cybertext that was returned by the left-to-right oracle to gather with the index of the corresponding secret key. The second security notion we consider is the robustness of an EMDK scheme. The security game provides the adversary with an access to the encryption oracle that encrypts arbitrary messages. The goal of the adversary is to find the key that decrypts any of the obtained cybertexts into a message that is different from the plaintext message that was originally encrypted to produce this cybertext. At the beginning of this presentation, we already discussed the current design of the iMessage protocol. We will now revisit it, defining a encryption scheme that formally captures it in a very modular way. Our encryption scheme is based on the Digital C-Nature scheme DS and on a multi-recipient public key encryption scheme MRPK. The key generation algorithm of our encryption scheme separately runs the key generation algorithms of both underlying schemes and groups together the corresponding secret and public key outputs. The encryption algorithm of our scheme creates a payload M-star by encoding the plaintext message, the sender's identity, and the set of recipient identities with the corresponding public keys. It generates the MRPKE encryption algorithm to produce a distinct cybertext for each of the recipient identities, where all cybertexts encrypt the same payload M-star. Finally, each of these cybertexts is independently signed and the resulting signature is combined with the corresponding MRPKE cybertext. In our paper, we prove that this encryption scheme has authenticity if DS is enforceable and if MRPKE is robust. We also show that this encryption scheme has privacy if MRPKE is INDCCA secure. In the iMessage design, the Digital C-Nature scheme DS is instantiated with ECDSA and we will now define the construction of the multi-recipient public key encryption scheme MRPK. We define the MRPKE scheme roughly as a hybrid encryption scheme, combining an encryption scheme under the under message-derived keys EMDK and a public key encryption scheme PKE. To encrypt the plaintext message M-star, it first runs an encryption algorithm of EMDK to produce a symmetric cybertext with the corresponding secret key. It then uses PKE encryption to separately encrypt the secret key to each of the recipient public keys. It then combines each of the resulting public key cybertext with the single symmetric cybertext. We prove that this MRPKE scheme is robust if either of the two underlying schemes is robust. We prove that this MRPKE scheme is INDCCA secure if the PKE scheme provides INDCCA security and if the EMDK scheme provides authenticated encryption. In the iMessage design, the public key encryption scheme PKE is instantiated with RSA or AEP and we will now discuss the construction of the EMDK scheme. We can define the EMDK scheme in different ways in order to recover the design of either the legacy version of iMessage or the current version of iMessage. We are interested in the current version and we already discussed the construction of the current EMDK scheme on the previous slide. Formally, in the definition of this EMDK, we model HMAC SHA256 as a function family F and we model ASCTR as a symmetric encryption scheme SE. We prove the robustness and the authenticated encryption security of this EMDK scheme based on several assumptions about the function family and the symmetric encryption scheme. Some of these proofs are done in the random oracle model. I'll make the detailed discussion about these reductions here, but you can find them in our full paper. We obtained a sequence of security reductions, each of them proven in the concrete setting. In the paper, we instantiated this sequence of proofs with the specific real-world primitives used in iMessage. This allowed us to deduce a lower bound for the concrete security of iMessage. As a result, we claimed that the iMessage design provides at least 71 bits of security with respect to authenticity and at least 39 bits of security with respect to privacy. For simplicity, when calculating this bit security in lower bounds, we modeled function family F as the random oracle and we modeled symmetric encryption scheme SE as the ideal cyber. Finally, we showed that our derived concrete security bounds are tied by defining theoretical attacks against the encryption scheme. I will make the description of the attacks here, but you can find them in our full paper. Recall that from the start of the presentation, that the design of the iMessage scheme was changed in response to the 2016 attack by Garmin Green, Kaptichuk, Myers and Ruschenan. The initial EMDK scheme that was used prior to 2016 simply generated a uniformly random key independently of the plaintext message that had to be encrypted. It was then replaced in version 9.3 of IOS with a more sophisticated scheme where the key depends on the plaintext message. This might raise a question of why Apple did not replace the entire scheme with a more standard construction of secure sign encryption. The answer to this question is that it was necessary to preserve backwards compatibility and Apple confirmed it in a conversation with us. This means that any messages sent by the current iMessage version should be decryptable by the old iMessage version. This explains the non-standard design choices that are used in the current iMessage version. When analyzing the current scheme, we also attempted to find better ways to fix the legacy scheme while still preserving the backwards compatibility. In the end, we could not come up with a backwards compatible scheme that would provide security that is better than that of the current iMessage scheme. We confirmed with Apple that the definition of our sign encryption scheme captures the design of iMessage with one minor but important difference. Recall that our construction of the sign encryption scheme uses multi-recipient public encryption to encrypt the payload mStar. In our model, mStar contains the plaintext message, the identity of the sender and the set of recipient identities and public keys. As opposed to our model in the actual implementation, this payload also includes a uniformly random CDAR. This makes two of the three attacks we present in our paper less efficient than claimed. However, the third attack is not affected and as a result, our overall security, concrete security bounds still remain the same. Finally, note that the original attack from 2016 had constant time theoretical complexity, but its implementation required 2 to the power 18 queries and 235 hours. Furthermore, version 9.3 euphios besides changing the design of iMessage also added ad-hots implementation level mitigations to prevent further attacks. In this work, we focused on the theoretical analysis of the iMessage design. We showed that the lower bound for the concrete privacy of the current design is 2 to the power 39. This means that there do not exist more efficient attacks against the formal model that captures the iMessage design. We emphasized that we did not have access and hence did not attempt to analyze the actual implementation of iMessage. Furthermore, we do not know whether our theoretical results can be used to implement practical attacks against iMessage. This question was the outside of the scope of our project. But it is likely that any theoretical attacks like the ones presented by us would incur a substantial slowdown when implemented, possibly comparable or exceeding the slowdown that affected the original 2016 attack. Thank you for listening and you can find our full paper on ePrint at the provided link.