Python Ranking Search Engine Implementation (Part 3)
- Transfer
In the previous part, we learned how to perform a query on a built index and now we can get links to documents that contain what we requested. But there is a problem: this is just a list of documents in which, perhaps, there is what we need. It is not sorted by importance, for us, the information contained in the document. We will talk about this problem in this part.
The final step in building a search engine is to create a system for ranking documents by their relevance to the query. This is the most difficult part, because it does not have a direct technical solution: it requires creativity and your own look. In this we implement TF-IDF ranking (from the English TF - term frequency (word frequency) and IDF - inverse document frequency (reverse frequency of the document)), which is one of the simplest ways to sort our documents. There will be no code in this part, but you can learn the final version of the engine on GitHub . We will only study the theory of TF-IDF, and its implementation is quite simple, and most of the work is done during the construction of the index.
So is the term “frequency” the first part of our ranking system? Well, that’s exactly what comes to mind when you hear it: the number of times each word appears in a particular document. The term frequency, as a metric, does not take into account the query: it assumes that the document is just an ambivalent set of markers, and you can get an accurate idea of it only by counting how many times each marker (word) occurs. This is not an exact assumption, but it is widely used in the field of document classification. Formally, it is better known as the “bag of words” model.
One simple representation of the word bag model is vectorization of documents. That is, we decompose the document into a vector of length N , where N is the total number of unique terms in the document, and each record is the number of times that a particular term appears in this document. For multiple documents, a more convenient way to determine N is the number of unique words in all documents in the search space. This allows us to represent each document as a vector, and all these vectors have equal dimensions.
But wait! There is currently a big flaw in our model. Consider these two documents: “The way they eat the cake” and “Let them eat the torus.” The way they eat the cake. " They are the same, except for the fact that the second is just a repeating first, but their vector representation is very different: [1, 1, 1, 1] compared to [2, 2, 2, 2]. To solve this problem, we turn each vector into a unit vector by dividing its value (calculated by extracting the square root of the sum of the squares of each record in the vector), “normalize” it. This will turn our previous vectors into [½, ½, ½, ½] and [½, ½, ½, ½], making them what we intend.
However, this is still not enough. The frequency of the word is a fatal flaw (it is harmony for any Greek tragedy). This drawback is that the “bag” considers each term to be equally important in the presentation of documents. But this is not so: the word “and” tells us much less about the document than the words “Shakespeare” or “chlamydia”. But the word “and” occurs much more often than the word “chlamydia” (at least in the documents that I read), which creates a false semblance of similarity between documents (since almost all of them contain the word “and”).
To avoid this, we need to add something to our ranking system: the reverse frequency of the document. We define the frequency with which the word occurs in the document as Dt , and t- as the frequency with which the word occurs in all indexed documents. Then, if we have K documents, then the inverse frequency of the document ( Lt ) of this word will be the ratio of K to Dt : the total number of documents divided by the number of documents in which this word occurs.
There is one last nuance: it corrects too much. If we have 10 documents ( K= 10) and one word appears in these documents 10 times, and another word only 1 time, it turns out that the second word is 10 times more important than the first. The linear behavior of this function is too radical, and will artificially reduce the similarity due to too much adjustment. To fix this, we simply add the function of the natural logarithm, which will "align" our function, making its correction smoother. Now our function looks like this: in a set of K documents, for some word t , Lt = ln (K / Dt) , where Dt is the frequency of the document of the word t , and ln is the function of the natural logarithm.
Implementation Note: as you can see, none of these values depends on the query, and both of them can (and should) be calculated for each marker (word, term) and document in advance!
Now, to combine the terms word frequency (in the document) and the inverse frequency of the document into one metric, we can simply multiply them. That is, the weight of each marker (word, term) in our set of documents is defined as Tt × Lt : the frequency with which the word occurs in the document and the inverse frequency of the document.
Now, if we have a set of K documents and all these documents have a total number N of unique terms, then our documents will be presented as vectors, each of length N, where the value of each record (which corresponds to the term) is equal to the frequency with which the term occurs in the document, multiplied by the inverse frequency of the document for this term in the set of documents. Each vector will have a value of 0 for terms not found in the document (remember that our vectors represent all unique terms in the entire set of documents). The reverse frequency of the document will never be 0, because this is the level of metrics collection.
Now we will do the same for queries: we will represent it as a vector in N- dimensional space, like documents, and calculate TF-IDF for each term in the query. Obviously, this will be rarer (scattered) than in documents.
A small digression. Let's try to calculate the similarity indicator between the query and its result set, and to rank the documents in the result set due to this. There are many different approaches to this, but I will use here what is called the cosine similarity coefficient, which essentially just takes the scalar product of the query and the document vector in the resulting set and divides it by the product of the values of these two vectors, which returns the cosine angle between these vectors (I could incorrectly explain the formula “in words”, so if you are interested, you can read the Wikipedia article and this questionon StackOverflow for clarification). This is a particularly useful indicator, since it does not take into account the magnitude of two vectors when calculating the similarity (as opposed to, say, the Euclidean distance), which is very important when you have one very sparse vector (query) and another much less sparse vector (our document).
So, to rank the results, this is what we will do:
And boom, we did everything!
Creating a search engine that can scale to the size of Google is incredibly difficult. But, making it easy for personal use (or even as a proof of concept) is not at all so difficult. In fact, the way to build search engine indexes, ranking and querying documents is very clear, and building the engine is an exercise worth doing.
The model bag of words that we used here is evident everywhere. Another great module for the search engine is the spam filter, or the document classifier, or the recommendation of articles, or any other module. This is a very cool concept, and it is worth considering how you will use it to implement any of the above (or something cooler).
Like it or not, this is the end of the article. If you have any feedback or questions, you can leave a comment on the original article or write to the author by e-mail / facebook / any other new-fangled social network that your children currently use.
Ranking query results
The final step in building a search engine is to create a system for ranking documents by their relevance to the query. This is the most difficult part, because it does not have a direct technical solution: it requires creativity and your own look. In this we implement TF-IDF ranking (from the English TF - term frequency (word frequency) and IDF - inverse document frequency (reverse frequency of the document)), which is one of the simplest ways to sort our documents. There will be no code in this part, but you can learn the final version of the engine on GitHub . We will only study the theory of TF-IDF, and its implementation is quite simple, and most of the work is done during the construction of the index.
So is the term “frequency” the first part of our ranking system? Well, that’s exactly what comes to mind when you hear it: the number of times each word appears in a particular document. The term frequency, as a metric, does not take into account the query: it assumes that the document is just an ambivalent set of markers, and you can get an accurate idea of it only by counting how many times each marker (word) occurs. This is not an exact assumption, but it is widely used in the field of document classification. Formally, it is better known as the “bag of words” model.
One simple representation of the word bag model is vectorization of documents. That is, we decompose the document into a vector of length N , where N is the total number of unique terms in the document, and each record is the number of times that a particular term appears in this document. For multiple documents, a more convenient way to determine N is the number of unique words in all documents in the search space. This allows us to represent each document as a vector, and all these vectors have equal dimensions.
But wait! There is currently a big flaw in our model. Consider these two documents: “The way they eat the cake” and “Let them eat the torus.” The way they eat the cake. " They are the same, except for the fact that the second is just a repeating first, but their vector representation is very different: [1, 1, 1, 1] compared to [2, 2, 2, 2]. To solve this problem, we turn each vector into a unit vector by dividing its value (calculated by extracting the square root of the sum of the squares of each record in the vector), “normalize” it. This will turn our previous vectors into [½, ½, ½, ½] and [½, ½, ½, ½], making them what we intend.
However, this is still not enough. The frequency of the word is a fatal flaw (it is harmony for any Greek tragedy). This drawback is that the “bag” considers each term to be equally important in the presentation of documents. But this is not so: the word “and” tells us much less about the document than the words “Shakespeare” or “chlamydia”. But the word “and” occurs much more often than the word “chlamydia” (at least in the documents that I read), which creates a false semblance of similarity between documents (since almost all of them contain the word “and”).
To avoid this, we need to add something to our ranking system: the reverse frequency of the document. We define the frequency with which the word occurs in the document as Dt , and t- as the frequency with which the word occurs in all indexed documents. Then, if we have K documents, then the inverse frequency of the document ( Lt ) of this word will be the ratio of K to Dt : the total number of documents divided by the number of documents in which this word occurs.
There is one last nuance: it corrects too much. If we have 10 documents ( K= 10) and one word appears in these documents 10 times, and another word only 1 time, it turns out that the second word is 10 times more important than the first. The linear behavior of this function is too radical, and will artificially reduce the similarity due to too much adjustment. To fix this, we simply add the function of the natural logarithm, which will "align" our function, making its correction smoother. Now our function looks like this: in a set of K documents, for some word t , Lt = ln (K / Dt) , where Dt is the frequency of the document of the word t , and ln is the function of the natural logarithm.
Implementation Note: as you can see, none of these values depends on the query, and both of them can (and should) be calculated for each marker (word, term) and document in advance!
Now, to combine the terms word frequency (in the document) and the inverse frequency of the document into one metric, we can simply multiply them. That is, the weight of each marker (word, term) in our set of documents is defined as Tt × Lt : the frequency with which the word occurs in the document and the inverse frequency of the document.
Now, if we have a set of K documents and all these documents have a total number N of unique terms, then our documents will be presented as vectors, each of length N, where the value of each record (which corresponds to the term) is equal to the frequency with which the term occurs in the document, multiplied by the inverse frequency of the document for this term in the set of documents. Each vector will have a value of 0 for terms not found in the document (remember that our vectors represent all unique terms in the entire set of documents). The reverse frequency of the document will never be 0, because this is the level of metrics collection.
Now we will do the same for queries: we will represent it as a vector in N- dimensional space, like documents, and calculate TF-IDF for each term in the query. Obviously, this will be rarer (scattered) than in documents.
A small digression. Let's try to calculate the similarity indicator between the query and its result set, and to rank the documents in the result set due to this. There are many different approaches to this, but I will use here what is called the cosine similarity coefficient, which essentially just takes the scalar product of the query and the document vector in the resulting set and divides it by the product of the values of these two vectors, which returns the cosine angle between these vectors (I could incorrectly explain the formula “in words”, so if you are interested, you can read the Wikipedia article and this questionon StackOverflow for clarification). This is a particularly useful indicator, since it does not take into account the magnitude of two vectors when calculating the similarity (as opposed to, say, the Euclidean distance), which is very important when you have one very sparse vector (query) and another much less sparse vector (our document).
So, to rank the results, this is what we will do:
- First, you need to pre-calculate the value of TF and IDF for each term, and build a vector of length N for each document, using the product of TF by IDF as a record.
- Then, we calculate the request, and get as a result a set of relevant documents (using the previously described methodology).
- After that, we compute the query vector, which also has length N and uses the product TF × IDF as each of these records.
- Then, we calculate the similarity of the query and each document in the result set (through the Otiai coefficient), and get a score for each document.
- We sort documents by this score.
And boom, we did everything!
Conclusion
Creating a search engine that can scale to the size of Google is incredibly difficult. But, making it easy for personal use (or even as a proof of concept) is not at all so difficult. In fact, the way to build search engine indexes, ranking and querying documents is very clear, and building the engine is an exercise worth doing.
The model bag of words that we used here is evident everywhere. Another great module for the search engine is the spam filter, or the document classifier, or the recommendation of articles, or any other module. This is a very cool concept, and it is worth considering how you will use it to implement any of the above (or something cooler).
Like it or not, this is the end of the article. If you have any feedback or questions, you can leave a comment on the original article or write to the author by e-mail / facebook / any other new-fangled social network that your children currently use.
