[MUSIC] This lecture is about, how we can evaluate a ranked list? In this lecture, we will continue the discussion of evaluation. In particular, we are going to look at, how we can evaluate a ranked list of results. In the previous lecture, we talked about, precision-recall. These are the two basic measures for, quantitatively measuring the performance of a search result. But, as we talked about, ranking, before, we framed that the text of retrieval problem, as a ranking problem. So, we also need to evaluate the, the quality of a ranked list. How can we use precision-recall to evaluate, a ranked list? Well, naturally, we have to look after the precision-recall at different, cut-offs. Because in the end, the approximation of relevant documents, set, given by a ranked list, is determined by where the user stops browsing. Right? If we assume the user, securely browses, the list of results, the user would, stop at some point, and that point would determine the set. And then, that's the most important, cut-off, that we have to consider, when we compute the precision-recall. Without knowing where exactly user would stop, then we have to consider, all the positions where the user could stop. So, let's look at these positions. Look at this slide, and then, let's look at the, what if the user stops at the, the first document? What's the precision-recall at this point? What do you think? Well, it's easy to see, that this document is So, the precision is one out of one. We have, got one document, and that's relevent. What about the recall? Well, note that, we're assuming that, there are ten relevant documents, for this query in the collection, so, it's one out of ten. What if the user stops at the second position? Top two. Well, the precision is the same, 100%, two out of two. And, the record is two out of ten. What if the user stops at the third position? Well, this is interesting, because in this case, we have not got any, additional relevant document, so, the record does not change. But the precision is lower, because we've got number [INAUDIBLE] so, what's exactly the precision? Well, it's two out of three, right? And, recall is the same, two out of ten. So, when would see another point, where the recall would be different? Now, if you look down the list, well, it won't happen until, we have, seeing another relevant document. In this case D5, at that point, the, the recall is increased through three out of ten, and, the precision is three out of five. So, you can see, if we keep doing this, we can also get to D8. And then, we will have a precision of four out of eight, because there are eight documents, and four of them are relevant. And, the recall is a four out of ten. Now, when can we get, a recall of five out of ten? Well, in this list, we don't have it, so, we have to go down on the list. We don't know, where it is? But, as convenience, we often assume that, the precision is zero, at all the, the othe, the precision are zero at all the other levels of recall, that are beyond the search results. So, of course, this is a pessimistic assumption, the actual position would be higher, but we make, make this assumption, in order to, have an easy way to, compute another measure called Average Precision, that we will discuss later. Now, I should also say, now, here you see, we make these assumptions that are clearly not, accurate. But, this is okay, for the purpose of comparing to, text methods. And, this is for the relative comparison, so, it's okay, if the actual measure, or actual, actual number deviates a little bit, from the true number. As long as the deviation, is not biased toward any particular retrieval method, we are okay. We can still, accurately tell which method works better. And, this is important point, to keep in mind. When you compare different algorithms, the key's to avoid any bias toward each method. And, as long as, you can avoid that. It's okay, for you to do transformation of these measures anyway, so, you can preserve the order. Okay, so, we'll just talk about, we can get a lot of precision-recall numbers at different positions. So, now, you can imagine, we can plot a curve. And, this just shows on the, x-axis, we show the recalls. And, on the y-axis, we show the precision. So, the precision line was marked as .1, .2, .3, and, 1.0. Right? So, this is, the different, levels of recall. And,, the y-axis also has, different amounts, that's for precision. So, we plot the, these, precision-recall numbers, that we have got, as points on this picture. Now, we can further, and link these points to form a curve. As you'll see, we assumed all the other, precision as the high-level recalls, be zero. And, that's why, they are down here, so, they are all zero. And this, the actual curve probably will be something like this, but, as we just discussed, it, it doesn't matter that much, for comparing two methods. because this would be, underestimated, for all the method. Okay, so, now that we, have this precision-recall curve, how can we compare ranked to back list? All right, so, that means, we have to compare two PR curves. And here, we show, two cases. Where system A is showing red, system B is showing blue, there's crosses. All right, so, which one is better? I hope you can see, where system A is clearly better. Why? Because, for the same level of recall, see same level of recall here, and you can see, the precision point by system A is better, system B. So, there's no question. In here, you can imagine, what does the code look like, for ideal search system? Well, it has to have perfect, precision at all the recall points, so, it has to be this line. That would be the ideal system. In general, the higher the curve is, the better, right? The problem is that, we might see a case like this. This actually happens often. Like, the two curves cross each other. Now, in this case, which one is better? What do you think? Now, this is a real problem, that you actually, might have face. Suppose, you build a search engine, and you have a old algorithm, that's shown here in blue, or system B. And, you have come up with a new idea. And, you test it. And, the results are shown in red, curve A. Now, your question is, is your new method better than the old method? Or more, practically, do you have to replace the algorithm that you're already using, your, in your search engine, with another, new algorithm? So, should we use system, method A, to replace method B? This is going to be a real decision, that you to have to make. If you make the replacement, the search engine would behave like system A here, whereas, if you don't do that, it will be like a system B. So, what do you do? Now, if you want to spend more time to think about this, pause the video. And, it's actually very useful to think about that. As I said, it's a real decision that you have to make, if you are building your own search engine, or if you're working, for a company that, cares about the search. Now, if you have thought about this for a moment, you might realize that, well, in this case, it's hard to say. Now, some users might like a system A, some users might like, like system B. So, what's the difference here? Well, the difference is just that, you know, in the, low level of recall, in this region, system B is better. There's a higher precision. But in high recall region, system A is better. Now, so, that also means, it depends on whether the user cares about the high recall, or low recall, but high precision. You can imagine, if someone is just going to check out, what's happening today, and want to find out something relevant in the news. Well, which one is better? What do you think? In this case, clearly, system B is better, because the user is unlikely examining a lot of results. The user doesn't care about high recall. On the other hand, if you think about a case, where a user is doing you are, starting a problem. You want to find, whether your idea ha, has been started before. In that case, you emphasize high recall. So, you want to see, as many relevant documents as possible. Therefore, you might, favor, system A. So, that means, which one is better? That actually depends on users, and more precisely, users task. So, this means, you may not necessarily be able to come up with one number, that would accurately depict the performance. You have to look at the overall picture. Yet, as I said, when you have a practical decision to make, whether you replace ours with another, then you may have to actually come up with a single number, to quantify each, method. Or, when we compare many different methods in research, ideally, we have one number to compare, them with, so, that we can easily make a lot of comparisons. So, for all these reasons, it is desirable to have one, single number to match it up. So, how do we do that? And, that, needs a number to summarize the range. So, here again it's the precision-recall curve, right? And, one way to summarize this whole ranked, list, for this whole curve, is look at the area underneath the curve. Right? So, this is one way to measure that. There are other ways to measure that, but, it just turns out that,, this particular way of matching it has been very, popular, and has been used, since a long time ago for text And, this is, basically, in this way, and it's called the average precision. Basically, we're going to take a, a look at the, every different, recall point. And then, look out for the precision. So, we know, you know, this is one precision. And, this is another, with, different recall. Now, this, we don't count to this one, because the recall level is the same, and we're going to, look at the, this number, and that's precision at a different recall level et cetera. So, we have all these, you know, added up. These are the precisions at the different points, corresponding to retrieving the first relevant document, the second, and then, the third, that follows, et cetera. Now, we missed the many relevant documents, so, in all of those cases, we just, assume, that they have zero precisions. And then, finally, we take the average. So, we divide it by ten, and which is the total number of relevant documents in the collection. Note that here, we're not dividing this sum by four. Which is a number retrieved relevant documents. Now, imagine, if I divide by four, what would happen? Now, think about this, for a moment. It's a common mistake that people, sometimes, overlook. Right, so, if we, we divide this by four, it's actually not very good. In fact, that you are favoring a system, that would retrieve very few random documents, as in that case, the denominator would be very small. So, this would be, not a good matching. So, note that this denomina, denominator is ten, the total number of relevant documents. And, this will basically ,compute the area, and the needs occur. And, this is the standard method, used for evaluating a ranked list. Note that, it actually combines recall and, precision. But first, you know, we have precision numbers here, but secondly, we also consider recall, because if missed many, there would be many zeros here. All right, so, it combines precision and recall. And furthermore, you can see this measure is sensitive to a small change of a position of a relevant document. Let's say, if I move this relevant document up a little bit, now, it would increase this means, this average precision. Whereas, if I move any relevant document, down, let's say, I move this relevant document down, then it would decrease, uh,the average precision. So, this is a very good, because it's a very sensitive to the ranking of every relevant document. It can tell, small differences between two ranked lists. And, that is what we want, sometimes one algorithm only works slightly better than another. And, we want to see this difference. In contrast, if we look at the precision at the ten documents. If we look at this, this whole set, well, what, what's the precision, what do you think? Well, it's easy to see, that's a four out of ten, right? So, that precision is very meaningful, because it tells us, what user would see? So, that's pretty useful, right? So, it's a meaningful measure, from a users perspective. But, if we use this measure to compare systems, it wouldn't be good, because it wouldn't be sensitive to where these four relevant documents are ranked. If I move them around the precision at ten, still, the same. Right. So, this is not a good measure for comparing different algorithms. In contrast, the average precision is a much better measure. It can tell the difference of, different, a difference in ranked list in, subtle ways. [MUSIC]
