Search Engines, Data Retrieval & Term Frequency: How They Work

[00:00:00]How does a search engine work? That's a hard question with a long answer because uh it's hard because Google doesn't really want you to know how it works because whenever they tell you, spammers try and use all the knowledge to kind of make their results go higher and higher up the list. So you you don't want to they don't want us to know how it works.

[00:00:16]And it's a long answer because there's been 60 years of research into information retrieval, how to find documents in computers. And before that there was hundreds of years of research into libraries for how do you index a library? A library being that place where you have real physical books in it.

[00:00:34]What's the link to libraries? Libraries were a big place full of books you wanted to find and there's no way you should look in the library to find them.

[00:00:40]You created an index and you just read through that index and go okay I need to go to the fifth floor. It's over there.

[00:00:45]So then when we started search through computers that was a big digital space with lots of files in it and to know where we should look to find the file we wanted again it creates an index to say go over there into that folder. And then when it comes to search engines, uh the web is a massive digital place and then to know where we should look in the web for the things we want to find again they create an index. So the history of how things were done in libraries affect how we do how we search the computers and that affects how we search through the web. Google is a huge dewy decimal system. Is that right? Uh it works in a bit differently but there have been doimal type approaches to do different things like category browsing rather than web searching. Let's go back to the 60s and 70s when people were thinking how can we quickly go through files in computers. Uh so let's imagine we have five documents here. So here we have five files which we're trying to search through to find out which one is most about someone talking about their horse.

[00:01:36]So we've searched for the words my horse hoping that there's people talking about their horses. And these five documents have those words in different amounts of time. So document one has got the word mine it 25 times. Two has got mine it five times but neither of them mention the word horse. Document three says my and horse both 10 times. Document four has 18 m and five horses. And document five is only about the word mine, not about horses. And so the first thing you would do is just do term frequency, TF, term frequency. And you're measuring just how many times each word is mentioned in there. So this gets a score of 25, 5, 20, and so on, which is fine in principle, and the idea makes sense.

[00:02:08]But in this set, the word my is overwhelming everything. So in fact, document one is the most relevant one with a score of 25 because it's got the word mine in it more than this one has my and horse put together. So this is a problem. This is not the one that's most about horses, but it's the one with the highest score. So the next most obvious step for many people will say, well, let's say, okay, it needs to have both of those words in it for us to give it anything. So now this makes a bit more sense. These two are the only ones that get a good score and they both mention the word horses, which is great. So another approach to this would have been just to rather than say okay we'll do some logic and say that's the best way of doing it we'll try a different approach where we say why don't we undermine how important the word my is so my is in every document so doesn't really help us with anything so if we just divide the score that the word my produced for each one by the number of documents it's in then we suddenly have a much lower score for the word my my has less of an impact and we call this inverse document frequency so as we're dividing it by the number of documents You do this for every search term. So my divided by five, horse divided by two cuz it's only in two documents. So this means that this one, which is really about my but not about horses, suddenly only gets a score of five. Then the next one suddenly goes down to one cuz there's five documents in there. This gets cut down to a seven. This one gets cut down as well and we end up with a score of 6.1. And then this one goes right down to three cuz it's not important. And this works really well because now the two which are about my and horse get a bigger score and the ones that were just about my get a much lower score. But we're still open to the fact that a really important one about my which only mention horses once might come up rather than just cutting things out. So if it's in lots of documents then we just care about it less and the score it creates has a lesser impact on whether we choose it as the most relevant document. The other good thing this has done is that it's added slightly more weight to the word horse.

[00:03:53]So the fact that this word the word horse is mentioned more in document 3 gives it a higher score now than document 4 than what we had before. So it's prioritized the document that's more about horse as well as undermining the amount of my in there. So then what a search engine uh has now done is it's found all the documents decided how many words each of them is uh how many times each word is in there and then given it a score and cut it down by the number of documents it's in so it's not too much too influential if it's not important.

[00:04:19]And this is actually really easy. You can do this in 50 lines of Python. Uh it's just not very fast. Um so the question is how do you make this faster?

[00:04:29]And so what they do to make this faster is they build this thing called an index which we mentioned earlier. Uh they build a text file which uh just has all of these numbers pre-programmed into it.

[00:04:38]And so in fact it counts how many times every word that they know about is in document one. And they're all in a table ready to access. And they can just uh use that. And so then every time you search, they don't have to read all the documents again, count the number of words in there again because that's the slowest bit. They just uh look at the pre-calculated numbers for everything.

[00:04:57]And so this index is an important aspect of keeping track of all the documents and which words are in there. And that index will have all of these numbers we've calculated so far uh in there. So how many documents the word horse is in, which is two, and how many times it's in each of those documents. So because this approach is pretty simple, there's a number of things which are wrong with And so there's a number of things we can do to make it even better. One major problem obviously is if you have really really long documents like this one might be really long which is why it has the word mine at semi times then they're just going to likely get a bigger score than all the rest cuz they're longer. Um so then what you can do is you can calculate the proportion of the document that's about the horse rather than the exact number of times it's mentioned.

[00:05:37]And so then you're comparing every document on an equal proportion rather than allowing big documents to change it.

[00:05:43]You can uh use stop words is another approach. So stop words say well there's not even any point in searching for the word the because it is and everything.

[00:05:51]Same with the word to and and they're going to get a low score whatever you do so let's just not even bother checking for it cuz that saves us time. You can also look at stemming. So one major challenge we often get is that you want to find uh documents that are about running uh but you search for the word run and you want the word running to come back or vice versa. So if you search for running you want all the ones about run in there. So you just have all of those merged down just the word run and then you search for that concept every time regardless of what they type in run or running. You might also want to know about how near the words are to each other. So it might well be that this document over here which has got 10 for my 10 for horse is not really about my horse. It's about my cat and someone else's horse. And so you give a boost to the scores if they happen to be near to each other. So if every time my and horse come together at the same time, you give them a bonus point. Then if this was only came together at one time, my horse, and that's only got a bonus point of one, it's up to eight. But if every time horse is mentioned there, it came with my, you'd get five bonus points and that's now 11.5. And suddenly this is the more relevant document because it said my and horse together, not just at random times. So this means that if you the documents which say my horse get a bigger score than documents that say my lovely horse which gets a bigger score than the documents which say my friend looks like a horse because they're further and further away and so they're less and less joined together in what you want. Then the final thing that you find some search engines might do is they might start to search for concepts rather than uh specific words. So it might be that um a document which has the word pony in it comes back regularly all the time with my pony, my pony, my pony. And so that's kind of like the one that's my horse, my horse, my horse. So it might be more relevant to the one that only had my horse once in it. So you can start to say, well, if we had one which was uh my pony document six for which there's not much space and that had mine in it six times, pony six times. So when you divide it by the number of documents, my only got a small score. So with TFDF, we're at 4.2. But because it said my pony together every time, you get some bonus points. You end up with a score that's actually making that one more relevant than this one cuz that said my horse once. that said my pony six times. That one said my horse five times. And so you're getting scores which promote uh words which are similar but not exactly the same. In order to find words which are similar to each other to do this uh to bring pony in rather than just horse, what they need to do is something called latent semantic analysis or other forms of looking back through your index. And what they do is they say uh the index for pony is looking a lot index for horse. Every time pony comes up it's also with field and horse is always with field. Pony is always with show. Horses always with show. Um, pony is always with pet. Horses always with pet. So, these seem to be very similar concepts in our index. So, let's just merge them together into a super concept. I mean, does that have flaws for pitfalls? Yeah, there's many opportunities for that to go wrong. And so, what I the way I explained it is kind of a simple way of explaining latent semantic analysis, but there's many more advances to kind of deciding how much of a similarity do you need for them to be considered probably related. And there's other ways to consider them to be properly related. Uh so they're similar words in a dictionary or some other thesaurus which puts them close together. Does humor ever get involved in this to check things or um so there are also uh semantic indexes where people have said these words are conceptually related and so you can use those to help you understand which concepts are related. This TF analysis of documents has kind of been a major stage in the 60 years of history of information retrieval. And so there's a lot more I could tell you about how they've improved this. They started calculating probabilities that this document is about this word rather than counts. And so there's a whole probabilistic approach to it. There's much more complicated models about language which we could go into, but again we could do whole videos about those two topics. Um, so what we're really interested in this point now is how does a search engine use this type of algorithm and is this the only thing they use? What other metrics do they use? And so what we'll go into next is analyzing how search engines work and how they can uh benefit from how web pages are designed.

[00:09:51]But if I just sent out an image of my dog and I never sent out the original that the camera took, no one's going to know that it's been imperceptibly changed because they haven't got a reference. in a narrower environment, a precursor of open source and in the jargon of a few years later it was egoless programming uh in the sense that I wrote the code but if somebody else can do it better go ahead.