CMPT 621 Lecture 5b: Ranked Retrieval & Vector Space Model

[00:00:04]any question about tfidf waiting if you don't ask are you last time why do we call this best match this way of of scoring not specifically to tf idf but this way of scoring why why do we call it best match remember in boolean river we call it exact match okay this is best match why is that not exactly problem ah okay not all query terms are required to be in the um in the in the document okay as as we have more query terms the score will get higher okay this is when when when did we say that when did we see that we require all terms to be in the document now before we talked about that before body retrieval when with the end operation with the end operation okay type if now you think about this one and we talked about also ranked boolean right which ranked boolean form is very similar or is similar to some extent to what we are doing here all who said oh hey yes all okay all with remember when we talked about ranked boolean we said that each term would have a weight right what was the weight in the assignment the first assignment the time frequency was the lower table of term frequency okay so all is very similar to this because all we are adding if you remember it was the uh actually it was not adding it was the the maximum right it was the maximum okay so it's not exactly like what we are doing here but it's the most similar probably okay but here we just add the uh the term weight uh term widths within the query term widths within the document no we're not getting the no no it's not about ranking the best match because we are trying to match as many as possible of the quality in in the document type back to our example okay and before we we ask the the same questions again can you tell me for the for the green for the green word what is the collection frequency of the clean word collection frequency okay i heard three i heard four any two any five why is it four yeah because that's the sum of the occurrences right how about document frequency three why is that it's at it appeared in three uh documents how about term frequency ah okay you have to ask me which document okay you have to ask me which document because the frequency depends on on the very good type now is it if we think about the f idf ranking function now asking the same question again what is the least relevant and what is the most relevant remember we have two sources of evidence right we talked about so far what is the first one the term frequency the frequency of determinant in the document and the second idf okay or document frequency which is a measure of informativeness as idf increases informative informativeness increases or decreases okay increases okay don't don't be confused inverse document frequency is the informativeness score okay so as it increases informativeness increases or importance increases now which of these if this is the query which of these terms have higher informativeness higher idf without calculations which one red and green why red appeared in three documents green appeared in three documents yellow five documents okay so idf of the green and the the red are the same and they are higher than the the yellow one okay type questions which one is the least element now if we use dfidf no what do you mean by yellow which one is the least relevant document d d2 why is that because the yellow term has low informativeness and also the tf is is relatively low okay so d2 is probably the least so if we rank them then it will be ranked fifth okay this is just a an example of a query type what should be fourth the second lowest second least value d1 d3 why is it d3 but but red appeared twice and red has a higher importance okay or at least the same importance like green right but it appeared twice so it might be so we need to calculate this right we need to calculate it so this one appeared to be the fourth and d3 will be the third which one will be the second among these two which one is that is the most relevant among these two d5 d5 why it has green twice and and red right the other one has the green ones and the red ones okay we can't judge but probably it is let's see yes it is you need to calculate it yes because maybe maybe the contribution of the of the is it the case what is idea for the what is not with us right what is idf zero log which is zero right so zero so the yellow doesn't contribute at all right because zero times the tf is zero okay so clearly is d5 here we don't need to calculate clearly d5 is is better we will have the highest quality type is it actually based on the scores if we use tf idf this will be the the rank of the of the documents does that mean that really document number five is most relevant really can we tell why not how long because based on the idea yes exactly okay so this is just a scoring function that we use hoping that it will match the actual relevance okay so this is like an estimated relevance but in reality if we look at the other words in the document other evidence from the document we might see whether uh document five actually is relevant to the query or not okay that's very important point now we switch to another model which is called vector space model do you remember which issue we didn't cover yet we discussed three issues earlier the length the length of the document okay or length normalization we don't have any length of normalization here right so far in dfidf is there any length there's no consideration of the length at all right i mean if you look at the scoring function nothing about the length of the document here if if the query terms appear as they are in the document if the document only has the query terms it will get the same score as the document that has all the creators plus so many other terms right we didn't consider any any document type now we saw two versions of this matrix we saw the incidence metrics and the count methods now we can using the idea of term weighting we can think of a weight methods okay now each cell here instead of having zero one in in the case of incidence or the term frequency in the case of count now we have the term weight okay so here anthony has a weight of 3.18 scissor head has the weight 2.54 and so on so each document now can be represented as a real valued vector this is a new notion that we didn't discuss before okay we earlier we said each document is is what huh no no no before that back of words each document was a bag of words okay now each document is a vector this is very different okay it's a real valid vector of term weights it happened that so far we used tfidf but as i said earlier dfidf is just one term waiting functions there are many terminology functions here we are talking about generally any term within function okay maybe we can use tfidf for now so each document will be a vector what do you mean by a vector remember in linear algebra in the golden age 67 years ago when with when we we started in algebra okay yes it has a value and direction yes at each vector and we have a vector what we call vector space okay the vector space has multiple dimensions right okay so the vector is a vector in in a vector space that's why we actually call this vector space model so here is the what we mean by documents as vectors let's assume just for now just for simplicity because it's harder to imagine higher spaces just we have a two-dimensional space we imagine that we have in the collection just two words jealous and gossip just just as an example okay now if a document has more gossip than jealous then the vector would be like that if the vector if the document has more gellers than gossip then the vector would be like that the document will be represented like that okay so each document will be represented as a vector now the vector has a value for each dimension in the space so what is the space that we are talking about the space of words each dimension here will be a word in the collection okay so the value in that dimension of the document will be the weight of that word in that document okay so here the weight if i give you an example here so how about this document document one where is the weight of jealous in document one this part this is the weight of jealous and what is the weight of gossip almost one yes okay so each document now the document is a vector of weights okay some of these are zeros by the way why are zeros why are they zeros because they don't appear in the document right if a term didn't appear in the document then the weight of that term in the document is zero so most of them are zeros but there are some non-zero values which are for the terms that appear in the document okay so now we can represent we can we have a vector space that space has how many dimensions in that example two dimensions but generally if i have a collection number of words in what in the document in the collection okay so that we call it we had we had that we had a name for that before what is the number of words in the collection direction huh our vocabulary size okay we say we call it the vocabulary size that's the number of unique terms that appear in the in the collection so each dimension is representing one term okay which means that each document now as a vector will have a value in each dimension that value is the term weight is the weight of that term in that document okay type which which document among all of these has higher weight for gelas d2 right d2 has higher weight which one has the lowest weight for gossip d3 e3 d3 okay so now this is a way of representing documents uh in in the vector space um of course as you know we can we can view it as a vector okay viewed as a point which is the head of the or the vector as you know from from linear algebra but the point that the terms are the axis of the space this is very important you have to understand that each x here represents a third which is each dimension actually a dimension it represents a term and documents are points or vectors in this space that they see it's a different different story different world when this is off okay now how about this in in real collections of course the space is huge right because we have millions of of of terms right and and thus we have millions of axes or dimensions okay so we call this very high dimension very high dimension tens of millions of dimensions if we are talking about the web for example so these are eventually very sparse vectors most of the enters are zeros of course right because the document will have maybe one thousand word ten thousand words out of ten million or hundred millions because most of the all the values are zeros and this is what we call vector space model okay vectors in vector space model we represent documents as as as vectors okay and the dimensions are the terms we'll we'll keep it supposed yes for now it will keep its pass time if we represent documents as vectors how about queries can we represent also the queries as vectors so we can right we can deal with the query as a document same same way okay the query has terms okay each term has a width in the query what is the weight in the of the term in the query as as any using any term waiting function right like if i did we can compute by the etf idf for a term in the query right just viewing the query as a document that's it it's exactly the same thing so queries also will be represented in the same space okay so the query that's the vector space model now is not only about documents is about queries okay so both the documents and the queries will be represented as vectors yes we'll get to that you will get an answer if not ask me okay so the key idea the first first idea here is to represent queries as vectors as we do exactly like the live documents the second idea if we do this if we represent queries and documents as vectors then then the similarity between the query and the document can be measured by the similarity between the vectors right right so if if the vectors are close to each other that means that they have close weights of terms okay and that means that they are more more similar okay and we tend to use similarity as an indication of relevance if the query and the document are similar that that's an indication of evidence okay so we will use we will then rank the documents according to their proximity okay how far they are if if two vectors for example here okay if if we are talking about d1 and d3 they are far from each other right so probably they are not as similar as d1 and d4 you look at d1 d1 and d3 not really far from each other right if we look at d1 and d4 they are more similar than from then d1 and d3 right so we can use this notion of proximity as an indication of similarity which is used as an indication of of elements so that's the second idea now the question is how how can we measure similarity of vectors okay so the first first idea is to use the distance you know ingredient distance right okay so you euclidean distance is to compute the distance between for example if i'm talking about so now we can represent the query also right so now i can compute the distance between d1 and q so this sorry this distance i can compute it this is what we we call euclidean distance right okay and you know how to to compute you create a distance over vectors assume that we can also compute that for every [Music] document right so i can compute the distance between q and d2 q and d3 and q and d1 now i can rank the documents based on their distance right fine how about the vectors now these vectors have different lengths right yes question yes of course when when we talk about euclidean distance it includes the magnitude right yeah as the vector no this distance if that if that vector is smaller the distance will change of course right so euclidean distance inherently takes the length into consideration this is exactly the point that that we will address now okay type now this will be large if as you just i think asked about this will be large for vectors of different lengths okay so look at um let's say that i want to compute distance between q and d2 which one will be any which one will be more similar to q d1 or d2 if i use the euclidean distance d1 right d1 because this distance probably is smaller than this distance right okay type let me discuss with you a hypothetical example let's yes very good so we'll get to that okay we'll get to that so you you started to think about that the the length of the vectors will be completely uncomfortable right okay we'll get to that type let me let me give you this experiment let's say that we take a document and we append it to itself and we copy the document and append it to it to itself okay so we have the original document and now we have the new document which is just two copies of the original document what do you think about the similarity the actual similarities between these two documents they should be the same right should be exactly the same because they have the same words exactly if we used the vector space model the way that we started so far using the incredible distance okay what will happen will we get perfect similarity the distance will not be zero right actually what will happen is something like this we will have this vector for the original document and double the size of the of the document of the vector will be the new the new document okay now what is the distance to the two yeah not not that no two it's the magnitude of the original of the original documents but that's not what we want right so it seems like euclidean distance is not the thing that that we want okay type based on this this experiment we have a suggestion of the similarity that we should look at how can we get these two documents d and d prime to be the most similar documents yes yes the angle the angle here is zero right or something that is inversely inversely proportional to the angle right because the angle is zero we don't we don't want some light to be zero here actually when the angle is zero we want the similarity to be one which is the maximum if one is the max okay so instead of the euclidean distance we need to think about the angle the angle between two documents is zero that should correspond to to correspond to the maximum similarity the measure that we can do with the with the angle to to get to give us that notion is the cosine cosine of the angle okay so this is the cosine function if the if the angle is zero then the cosine will be sorry the sun will be one okay which is what we want right if the angle if both if they have the same direction exactly and this is i think answering uh phobos question if they have the same direction then the similarity would be one because we we would consider cosine the angle between them which would give us one if they are in opposite or if as as as they move apart from each other the angle increases what happens to the cosine function decrease okay it will be zero if they are orthogonal right if they are completely orthogonal then it will be zero and it will be minus one if they are completely opposite if the angle is 180 then it would be minus okay that was that was my next question why will it happen to have 180 degree with with dfidf we cannot get negative numbers anyway okay but with other uh weighting functions we might okay so that's a general notion here for tfidf at why it will not happen because the weights are always positive okay so we are always working on the uh the right the yeah the first quarter the right the top right uh quarter of the space if we think about two dimensions only of course okay so if we are able to compute the cosine of the angle between two vectors which are the query in the document and we do that for every document then we can rank the documents in increasing order of the cosine similarity so in increasing order of the angle which is decreasing order of the science internet because we want the top the the most similar to be at the top okay is that clear any question about this okay so what will be the scoring function now is it euclidean distance no the cosine of the angle okay the sine of them so the next question is how to compute that if you remember from linear algebra there is an easy way to do it to do to compute the angle we need to normalize the length of the vector okay so length normalization in vector algebra we divide the vector by its length okay and usually we use the el tuna which is the square root of the summation of the squares of the values in each dimension so if we have a vector x the l2 norm will be the square root of the summation of the individual values of of the vector over the different dimensions okay if now if we have the if we divide x by its length what will we get if you remember we'll get what we call a unit vector now the length of that new vector is one if we take the length of this we'll get one because the rate of this is the length of x over length of x which is one okay so that's that's why we call this length normalization okay so if we do that for every vector then the length of all vectors will be one so we will not care about the length okay now okay so i didn't say anything new here this is something that you should have studied area if we have a vector like this and let's say that this length is three okay the length of that vector is three how can we compute the length by this but this is one way is is to use l2 norm that's the length of the vector okay now if i divide the individual components of the vector by that number the new vector will have a length of one okay so let's say let's say this vector was uh three one three here and one here okay now if i divide that by the length of that vector whatever the length was i have two new components right a new vector that vector has the same direction of the original vector but it has a length of one and i will tell you now why we are doing that but let's just get into this we can do length normalization of all documents by dividing each the vector of each document by its own length if we do that then all documents now will uh will have the length of one now if we do that to our experiment that we had in the previous slide or two slides okay when we doubled the the content of of one document to itself now these two documents the original one and the previous and the and the new one okay if we do length normalization what will happen to the vectors of these two documents you will both will be over each other okay you'll be exactly the same if they are exactly the same then of course uh they are the most similar and this is what we want yes yes exactly after we do length normalization then computing the angle will be very easy if you remember from linear algebra then um the computing the angle will be just the dot product okay we will see that in the next slide but there is one one one comment here uh if by by doing the length normalization now we have comparable length between the query and all documents okay because all of them actually have that one now okay so this is what we mean by length normalization now if we do that then the cosine of the angle between the two vectors is just the dot product sorry what happens it's just the dot product between the two vectors what is the dot product we just multiply the corresponding values so if i have these two vectors x y okay of course they have the same dimensions okay what is the dot product between these two vectors we take the value here multiplied by the value here plus the multiplication of these two values plus the notation of these two values and so on so that's that's the dot product between the vectors now if if we do that when the vectors are unit length then this value is the cosine of the angle between the two vectors okay is that clear if you remember it is straightforward okay we of course we don't need to to study now why is that okay but it is the case that if we uh if we just take the dot product now if the two vectors are already normalized which means that they are unit length by what we saw in the previous slide then the dot product now is the cosine of the angle between the two vectors why do we care about this because that's the scoring function now this is now the scoring function okay if i have the query vector and the document vector and compute the cosine between these two vectors then this is the scoring that's that's the score of document d given the query queue and this score is between zero and one if if we are if you are using tf idf assuming that the weights are always positive then you will get a square between zero and one zero if the two vectors are orthogonal if the angle between the two vectors is 90 degree and one if the angle is c it is in in this case as i said earlier in this case if we use tfidf all the values are positive are zero positive so we know there will be no way to get an angle more than 90 degree okay originally if the the vectors are not normalized then this is the cosine computation okay so you see here we normalize each vector and once we normalize that then the dot product will be the cosine similarity we call this cosine similarity by the way it's the cosine of the angle between the vectors we call it cosine similarity okay because now the similarity is computed as the cosine of the angle between the two vectors okay so if the two vectors are normalized we just do the dot product if they are not normalized we have to normalize them and then we do the dot product which is what we have here okay we don't have to of course um because these are scalars we can just multiply them together and then we do we do the in the numerator we do just the dot product okay so eventually it will be the dot product of the of the two vectors the original vectors divided by the length of the first one times the length of the second one okay so this is how it is computed any question about this so this is called again cosine similarity yes oh that has nothing to do with this okay how to how to compute the the values okay ah okay why is that different from the document let's let's say that the query is my favorite query what is my my favorite query qatar university okay khata university is the query right okay this is the document the document has two words qatar universe can you compute the vector for this document now was it why is it kind of why it's not why it's not for sure it has just two words what is the weight for qatar okay let's do it what is the weight for qatar tf is one right and idf is whatever what is the word for university again tf is one and idf is whatever the idf for university that's it so the vector of the query how many nonzero values will be in the vector of that query only two for qatar and university the others will be zeros okay now i think it's clear exactly yes it's hard to imagine one yes it is in the plane that has these thoughts yes more than three dimensions you cannot we have millions of dimensions here okay any any question yes yes what do you mean that's uh beyond the scope of this course i don't know if it can be represented yes okay okay okay let me open this question so the question is do we have millions of dimensions really or it's just the dimensions of the query the number of dimensions here is the vocabulary size because we first because we don't know which query will you will have and because the document representation should not depend on the specific way so we have a document representation already given the words that appear in the query and then when we have the query we represent it as a vector and we compute the cosine similarity okay any other questions type then let's see how we can compute cosine similarity in reality okay so this is a function that will give back the top k documents ah let me before that before that let me ask you a question um given the cosine similarity function this is a scoring function now right when when can we get zero for that function when we have 90 degree okay i understand this geometrically in reality when can when will we get this zero look at look at the computation here look at the the how the function is computed where can we get zero here huh yeah so yeah okay forget about relevancy here we have we don't know this is what we want to estimate we don't know in advance which which one is relevant and which one is not okay what are we doing here we are estimating the relevance by similarity okay so we don't know elements in advance otherwise we don't need to do anything right if we know which documents are relevant tell us done okay this is what we want to get so again look at the computation here and tell me when can we get zero yes when the terms of the query don't match what do you mean by don't match yes when there is no no not similar when there is no common terms exactly if if that that's something this is the numerator right is the numerator zero done this numerator will be zero if q i and d i what is q i on the i here we didn't actually discuss this this is sigma over all dimensions over all terms okay for each component that the weight in the query and the width in the document when can we get zero from here if all of these are zeros type when can we get all of the all of the values of that summation okay now of course some of the components in the document will be non-zero and some of the components in the query will be nonzero okay when can we get zero sum in this case if at least one of them is zero okay but that has to happen in every dimension okay this is this will only happen if there is no at all any common term between the query and the document that means that if the document has no query terms the cosine similarity between that document and the query will be will be zero okay is it is it the case like the previous scoring functions what was the previous calling functions dfidf when we sum over the common words also okay get back this one this one right this one was adding the weights of the query terms in the document only if we have common words right we said that if we don't have any common terms between the query and the document the score would be zero it is also the same in cosine simulate okay so most of the documents will have zero scores only the documents that have at least one creator will have a non-zero score otherwise we will have zero scores is that clear is that clear what does this smile mean okay you are watching the video now by the way you are live okay it's simple okay let me say it again look at look at this look at this do you agree with me that this is how we compute cosine similarity right okay we have two vectors we have a vector for the query and we have a vector for the document right these two vectors let's say that we have just three dimensions let's say that this is the document and this is the query okay and we have some values here we have some values here and we have some values here when can the dot product this is the dot product between them right you know the dot product right you know the dot product okay so when can the dot product be zero when can this be zero this is the summation of this multiplied by that and this multiplied by that and then this multiplied by that so to get zero here we have to get the three zeros out of the multiplications right how can we get zero out of this multiplication if one of these is zero how can we get non-zero it is the only only one case to get non-zero out of any dimension here if we have non-zero here and non-zero there right which means that the query and the document have this term otherwise if we don't have any common term then there will be zero here or there and thus the sum will be zero i hope that it's clear now is it clear now i know that when you watch the video you might be confused no i think it will be clear but i i i hope that now it is at least mostly muhammad you have a question or you wanted to answer no no no okay good i'm trying to be better at that any other questions okay good now let's look at um how the how we can compute cosine scores okay look at this algorithm and and see what happens first we we initialize all the scores of all documents to be zero okay and then we get the length of we initialize also also a length matrix just to to we will store the length of the documents there because we want we want to normalize remember here the cosine similarity has we have to divide by this right okay so we just initialize it we just get here we assume that we have the length already of each document okay that's pre-computed now if you look at this at line three you will see that we have a loop over what over the query terms why do we only loop over query terms not document terms because we because of what we just mentioned that the document will have a non-zero score only if it has some of the queries so we should not care about any other terms than the query terms type for each creator what will we do we will calculate the weight first we'll calculate the weight of the term in the query that's the weight of the term in the query why do we need that yeah because that's the component of the of that term in the query vector okay and then we get the posting list for that term now again imagine my favorite query qatar university so what happens now is that i will compute the weight for qatar let's say that the weight for qatar is i don't know 5.3 how did i calculate it using tfidf okay type now i will fetch the posting list let's say that this is the posting list for qatar i hope now that you are very familiar with posting lists after the first assignment okay so each posting now has a document id and positions and the new operation okay now for each pair document and tf so here we have the document let's say that we have two things we have the document id and we have the tf the term frequency of of the term okay and from that we can compute this co contribution the contribution of that term for the score of every document in the posting list why is that we said that only the documents that have the query terms will have non-zero score right right so that means that every creditor if it appeared in the document will contribute to the score of that document what are the documents that have the the creator these are the documents in the posting list right that's in the index we have them already okay so these are the documents that have the term qatar that means that qatar will will contribute to the score of that document and will contribute to the score of that document and will contribute to the score of that document and so on what is that contribution remember the summation here this submission is the dot product right so that will be the weight what is q i that's the weight of the term i in the query what is the i that's the weight of the term i in the document d okay so that's the contribution this part by itself this is the contribution of the term i in the document d okay then q i in document d so in this algorithm we are accumulating [Music] partial contributions okay turn by turn we don't take a document and compute the score for it immediately okay this is different from what we saw before what we saw before we when we talked about how we how we get the remember the merge algorithm when we when when we wanted to get the uh the results from the end operation we did measure with right we we said that this is called document at the time evaluation right because we get the score for each document at once this is not the case we call this term at a time we talk that we will talk about it at the end in java so now we compute the the contribution of term t in document d what is that contribution that's the weight of the term in the query times the weight of the term in the document this is the dot product but only at the dimension of the term t okay uh i think this is this is just a type yeah just okay okay is that clear are you with me now if we do that for all the query terms each query term we get it we compute the weight of it in the query and then we add contribution of that term for every document in the posting list at the end we computed the scores of all documents because if if a document doesn't have any of these query terms what would be the score for that document it should be zero right will that algorithm give us zero here why yeah because initially it is zero and then will it appear here somewhere it will not act because we assume that it doesn't have any of the query terms so it will not appear in the posting list of any of these query terms right okay so eventually the the documents that have no query terms will have zero scores what is remaining then up to this line up to this line what did we compute we computed only the numerator by the way we didn't compute the we didn't do anything with the with the length normalization okay so now what we should what should we do we should divide by by this right what is this this is the length of each document times the length of the query let's look at the code and see if if we actually do that or not look at it and tell me do we actually divide by the length of the document times the length of the query what do we do here we read we read the length array and for each document we divide the score of that document by the render of the document where is the length of the query and we don't do anything after that by the way at the end of this line we are done with the scores with with scoring this line is just getting the top k of them just to turn back the the top key where is the length of the query we don't divide by the end of the query here right is that a mistake why not hashem hall of sliding okay the length is the length of a vector not at a okay so the length of the coil you said that it will always be one that's not the case also it's not the case that the component for each term is one the the term frequency would be one probably but idf is not one okay so the length of the query might not be one generally but we dropped it here y type think with me the scores let's say that these are the scores of all documents without dividing by the length of the query okay let's say that after this after this step we got these scores for all documents okay and let's see that now this document is the highest and this one is the second highest okay if i divide this array now by the length of the query what will change the numbers will change the order will will change that's exactly why we don't divide by the equivalence yes the equivalent will give us the exact cosine similarity which will be between zero and one okay but what we care in search engine is not the scores we care about the ranking the ranking will not change so why should we divide by the number we should save time of division and just ignore that because and this is exactly because the equivalent is the is a constant for all documents right so it's like dividing dividing these numbers by a constant that will not change the uh the ranking the order of the of the values it will change the values themselves but we don't care we care more about the ranking is that clear is it clear and this is what we call term at a time not not the issue of dividing by the query length but i mean this way of uh of query evaluation is called term at a time why is it term at a time not document at a time because we are taking one term at a time and compute all the partial contributions of that term in all the documents so we don't get a score of our document at once we'll get the scores of documents all at the end after we are done with all terms okay this is is that what we actually do in the assignment in the code of the assignment no we do document at a time right okay so that's the difference any question about this okay now um we talked about cosine similarity and we and i tried my best to tell you that cosine similarity doesn't mean that we will use tf idf right the way that we we started it was just an example of a term weighting function but it will work with any term weighting function even with simple tf if you want as long as we have the weights of the terms have we have a waiting function for the terms we can use cosine similarly having said that there are many variants of tfidf weighting in fact for the three [Music] major components of of tfidf in general we have multiple variants so we have multiple variants for terminal frequency multiple variance for the document frequency multiple variance of doing normalization okay so all of these possibilities are different term weighting functions okay there is in in ir there is a terminology called smart notation smart is a name of a system that participated in trek so many times earlier um and they use the notation of three letters for the document and three letters for the query and these letters indicate one of the letters in in in order so for example if i used lnc dot ltc that that indicates a specific term waiting function how is that that means that the first three letters here let me change this the first three letters here belong to the document okay and the second three letters belong to the query so now what it means to be l for the first character it means this one for term frequency and then this one for document frequency and then c which is the cosine for the normalization so that defines the weighting function exactly and that means also that there are you can also weight the terms in the query different differently from the weights in the document you don't we don't have to be the same okay so you can play with that but as long as we have weights here and where it's there then we can compute the cosine similarity right is that clear so we call that a smart notation and lnc.ltc is a very standard waiting scheme in ir okay in the last 10 minutes let me introduce a variant also of tf-idf which is very common or very well known also in ir it's called ocapi bm25 ranking function and this ranking function is based on this waiting function if you look at this weighted function it has two components very similar to tf idf but it's a bit more complicated okay so look at maybe the idf first idf part so this is again waiting this is a terminating function okay so the idf component if you remember in tf idf in standard dfidf what was the the idf component yes n it was not n over df log n over df okay so this is very similar to it it just subtract the f from the numerator and add half here just to make sure that we will not get zeros if if the df is n just to compare it between the classic this is the classic one you'll see that with changing the value of df they are very similar there is some slight difference but they are very similar okay so that's just the idf part so idf part of of bm25 is very similar to the classical one but what is really different is the tf part okay so let's see what are the components here of tf the classic one is one if just to remind you it is one plus log tf okay that's the classic the classic one now this one it has the f also but over 1.5 and then this term didn't appear at all in tf idf l d is the length of the document okay and l bar is the average length of documents in the collection so we assume here that again we we represent our documents as vectors and each document has a length actually actually let me let me let me get this back okay the length here is is not the length of a vector is the number of terms in the in the document okay that's the length the array length of the document okay no it's not a vector length okay so that's the number of terms in the document and that's the average length of of all documents so this part is the is the length normalization part in bm25 okay now let's look at how this this is different from the classic tf part if not not exactly with the classic but when when the this ratio changes when when the issue between the length of the document and the average length of the document changes if this issue is one which means that the document that we are looking at now has average length in the collection this is the value of that this the solid black okay as we increase tf this is the function this is the value of that component are you with me the last 10 minutes in the of the lecture so this part is when l is equal to l l bar so the length of the document is exactly like the average length in the collection type now if if that ratio is 2 which means that l is greater than the average then we'll get something like this so now this is l is to elbow what happens the the curve is below the other one which means that the value of tf component is lower does that mean that this is good for long documents or short documents short right because as we go longer actually if you go shorter than the average it is higher and this is when l is half the average okay so as the document gets shorter this component the value of this component will get higher that means that we are favoring short documents which has a has a logic if if the document has the query terms and but it is very short it probably it's more relevant than a document that has the query terms but it's much longer okay so this is how a bm25 weighting function is is handling this this case okay now why is it called ocapi bm25 okay because the team that started this that proposed this function is it was called okapi bm25 i think i don't remember now why is it called bm but 25 what i remember is that they tried multiple waiting functions and they tried and they evaluated these functions and this is that was the best at the time okay so the best was the 25th function that they tried something like that okay but being 25 is very well known in ir it is even used in commercial search engines it was shown to be very effective in many ir applications now this is the weighting function that's this is the term weighting function where is the ranking function the scoring function itself it is still the same one that we saw before just the summation of these weights okay any question about this in fact bm25 has two parameters this is the default this is the function when we use the default values of these parameters but in reality it has two parameters k1 and v but if k1 is 2 and v is 0.75 we will get the the function that we saw in the previous slide so it's parameterized you can you can change these values and if you change these values then the term weights will be different and you might get different results you will play with that inshallah in the second assignment stay tuned yes okay any questions right what is the summary of what we discussed in terms of vector space model we present queries and documents as vectors okay we we compute the cosine similarity between these vectors to indicate similarity of the queries and between the query and the documents we rank based on this score we can rank documents and then we can just look at the top key and provide them to the user this is this is something that we couldn't do with the standard boolean retrieve right we didn't have a way to to score documents