Quantifying Information | Summer School 2026 | Mathematics Club IIT-M

[00:01:48]Hello.

[00:02:08]>> Yeah. Hi. Hello.

[00:02:13]coming back.

[00:02:34]Okay.

[00:03:26]Yeah.

[00:06:19]So hello everyone. We'll be starting in 5 minutes. Uh we'll be displaying the attendance form now. Do mark your attendance.

[00:07:16]For those of you who have come um newly, please uh give your attendance in this form. Please scan the QR code and give your attendance.

[00:11:08]Yeah. So hello everyone.

[00:11:11]Uh myself Harish and my colleague here Ani Pai. And today we'll be teaching a session on quantifi our session quantifying information a session on information theory. So the attendance form will be open till uh for 10 minutes. Please, whoever has come new, please uh give your attendance.

[00:11:56]All right.

[00:11:58]So, let's go. So hi, I'm Harish and today I'll be taking a taking over the session quantifying information which is a wonderful which is an introduction to the wonderful world of information theory.

[00:12:14]So in this session we'll be taking these topics right. So first we'll have start with the fundamentals of information theory which is Claude Shannon who is called the forefather of information theory with this 1948 paper and then we'll play a small game in order to get uh get an we'll play a small game to get introduced to the concept of bits. Then we have entropy and Shannon entropy.

[00:12:46]Then we have the applications of all these concepts that is Huffman coding and the Shannon communication theorems.

[00:12:53]Then we'll have a we'll have a module where we we will see the we will see how this concept is used in AI that is scale divergence labeler divergence uh token generation and temperature and we'll have a conclusion where I'll give you the overview resources and we'll take questions.

[00:13:16]Right. So section one introduction.

[00:13:22]So yeah, you may mark your here. So before we start everything, let's play a game, right?

[00:13:31]So I want you guys to guess a number. So I'll be thinking of a number between 1 and 1,024.

[00:13:40]So you you should be so the constraint here is that you should be guessing that number within 10 question. So how will you do it?

[00:14:00]Okay, someone said 236.

[00:14:02]Nice. that no that's one question already.

[00:14:14]So how would you go about solving this question? How about how would you go about like uh asking me questions such that you will be able to get the answer to this?

[00:14:27]I mean someone already got it binary search algorithm but again so what what is that actually what what are we doing there express it in binary for yes oh yes yes exactly Yeah. So I guess many people already know this. So we so what we'll do basically here is that we we we will ask we will ask like uh how do I say we we will ask whether the number is less than a given number that is high plus low by two. So that is that is basically asking each digit of the number in binary right.

[00:15:25]Yes, exactly. Just like DX said, assuming low equal to zero, high equal to 12,24 initial. Keep updating the guess, right? So, what are we do? What are we doing here? We are asking a question that is is the number less than a given uh which is basically what we said. You are guessing the binary digit every time. Here we're checking the uh most significant binary digit. So we asked a question yes or no whether it is below.

[00:15:58]So if it's below then we assign zero if it's above then we assign one. So we asked a question what happens is that we got information about the answer which is binary information either that or this right and this narrowed us down our search space by some amount it. So basically here it narrowed down by half but generally these in these kind of questions you'll narrow down by some amount right and compounding the effects of all the questions we will later come to a conclusion that yes this is our number right so before we go into uh information like the crux of information theory let's start with a small probability recap for people who uh are a bit near the probability.

[00:16:52]Yes.

[00:16:55]Is this the most optimal? Yes, that is the most optimal.

[00:17:05]So, uh probability of event most probably everyone will know.

[00:17:11]Yeah. Probability of an event most probably everyone will know. expected uh favorable outcomes by total total outcomes. Probability of two events occurring together that are independent events. You will know that uh P of A intersection B that is the event both of them occurring together equal to P of A into P of B if both of them are independent. Yeah, most probably mostly we'll be seeing only independent events.

[00:17:40]We won't be seeing dependent events in this course. So yeah, so this formula will be valid and we'll use mostly this formula for many of the formulas many of the derivations that we'll be doing. Now expected values. So expected values this might be a bit new to everyone. So expected value of a quantity let's say I of X a function Y I of X is basically the sum of all the so all the variables times that function right and the sum for all X belongs to that probability distribution that is expected value. So if you have a probability distribution that all the for all the discrete values the sum of this value x into i of x is expected value right. So yeah and then logarithms I think most probably everyone will know. So if uh we have a power bal c then we can define the log as log base a of c equal to b.

[00:18:50]Right? Everyone understood?

[00:19:00]uh you you can say that expectation is same as average but then not always right it's it expectation of the variable X is average the mean basic right any so I guess many people will know this already. So I guess this is more.

[00:19:34]>> So let's start at the fundamentals of information theory. So let's start with the introduction to information theory.

[00:19:42]Let's just get into it the humble bit.

[00:19:46]So overview of information theory is basically the let me give you a small overview. It is a field where information from verbal statements is represented mathematically. So basically the field of information theory deals with how uh how you can how uh certain conditions divide search spaces by a certain number basically. So what we did in ourh previous question is that we asked a question that divided our search space into a much more clear a much more uh smaller space that we can search easily. Right? So that's what we did here.

[00:20:26]The surprise and information from a yes or no question is studied and quantified. So basically here we have taken a yes or no question. Right? So is the number less than a given number.

[00:20:38]Let's say 5 to 12. Then we say yes we have some other thing. No means we have some other we have we have another space. So these are yes or no questions.

[00:20:47]These are studied and quantified. So this is information. This is information.

[00:20:52]Again you also will be studying how the probability of an event corresponds to the information that it will be give it'll be giving. So if a prob uh depending on the probability how much information will it give.

[00:21:09]So how do we quantify this information right?

[00:21:16]Oh, one second.

[00:21:50]Aa aa I apologize it isn't x here I'm so sorry it's uh x p of x into f of x sorry my apologies f of p of x p of x right so this is your expected value I'm terribly sorry. Uh so this is your expected value, right?

[00:22:20]So the this definition of the expected value correlate with the sum of each value.

[00:22:26]Yeah.

[00:22:30]Multiply by probability of occurrence of each value. Yeah. So that's just the mean, right? So X = P of X into X, right? So that's your V.

[00:22:42]Let's continue.

[00:22:45]So how do we quantify this information?

[00:22:49]Uh the humble bit. So what we doing here is that we defining the humble bit.

[00:22:55]So the bit was not a new term when Shannon was uh describing it. He he used the term for the first time in his paper a mathematical theory of communication which is basically what the what spawned this whole uh field basically. So a mathematical theory of communication is like the bible of information theory. It is it's it's it's what spawned this whole field. A bit is a unit of measurement for information.

[00:23:27]It can also be called a channel. Right.

[00:23:30]So in essence what we can say is that a bit is how much information you get when you choose an event that divides the search space in half. So if so for example if you have a number between 0 let's take the previous example and you have a number between 0 and24 right so let's say I ask the question is it less than 512 so if it is less than 512 then uh then you have given yourself one bit of information why because when you give one bit uh when you have one bit of information then you are divide essentially what you're doing is that you're dividing this entire search space into two two spaces that is 0 to 51 and 512 to,024 effectively you're dividing the whole search space into two right so how do we mathematically define the information right so Shannon proposed these three uh laws that information has to um information has to follow a definition of information has to follow.

[00:24:41]Let's say we have I of X right our function I of X. So information is additive. So the most important property here is the first one information is additive. That is the sum that you get from uh the sum that you uh the sum of information from each.

[00:25:04]The information that you get from two events is the sum of the information you get from each. Basically you have two events. let's say A and B.

[00:25:13]So the information that you get from A and B both of them happening is the sum of information from each of them.

[00:25:23]Yeah, that's the first probab property. Second property here is if an outcome is more likely, it gives less information. If you think about it, let's say let's take our example 0 to 2024.

[00:25:42]Then what are examp uh let's say we take a very highly very highly likely event that is uh 750 right less than 750.

[00:25:56]So what we're doing here is that we're dividing it in two for two search spaces that are less than 750 and greater than 750.

[00:26:06]Right?

[00:26:07]So if we know that this statement is true then we have divided it into search base that is not as efficient as what we did with 500 because this is less likely and this is more likely. So more likely meaning that if the uh we have divided we have not uh done as much as as much removal as much uh rejection as much as we've done with 500 this one 500. So we have got less information. You guys understand?

[00:26:49]Uh hello.

[00:26:55]So and then we also make sure that it should be continuous without certain terms like it should be a continuous function. So if so information of an event is inversely proportional to probability.

[00:27:15]So do you guys think which function can sol can satisfy all these definitions?

[00:27:48]There it is.

[00:27:51]Are you here?

[00:28:17]what is information?

[00:28:21]Well, when you are so basically when you are uh well, I'll I'll I'll start with I'll I'll make a proper definition like then this right So, so which function satisfies all three conditions? So, we have a hint. It breaks products into sums.

[00:29:11]So, now, now that we thought about it, let's see. So we want we have let us formalize our uh properties of information. So you have information of A and B both happening is information of A plus information of B information that you get from B. So information that you get from person is information of that you get from two events happening is the same as information that you get from each of the events added up.

[00:29:46]In if an outcome is more likely it will give it will give less information. So information of an event is proportional to one by one by the probability of it or basically as information increases probability decreases. So as probability decreases information increases.

[00:30:10]So let's what? Let's use this property.

[00:30:17]The probability of an event happening is P of A dot P of B. Right? The probability of two events happening together is the the product of each of the probabilities. Right? So if we use this then we want we can see that information in inverse relation I mean it's not exactly inverse relation you can say that it is um it is uh in if information increases probability decreases so basically that's what I meant by inverse relation again Yeah.

[00:31:00]>> So what we have here is information can be written as some log logarithm of the probability. Don't you think?

[00:31:26]So we have information is some log logarithm base some random base a p of x and then we have a minus sign because we want to have this right we have in if an outcome is more likely it gives less information. So we have we have a minus so if an outcome is more likely it will give less information.

[00:31:58]Yeah.

[00:32:01]So now instead of we having a so basically information can be anything.

[00:32:07]It can be minus log base a of p of x.

[00:32:15]But then we taking two because we as we know the most efficient uh the most efficient way of dividing a search space is dividing it into two as we said. So this is the formula for information that you get from a probability happening. You can also call it the surprise of the probability surprise of the event happen.

[00:32:42]Everyone understood.

[00:33:05]Yeah. So let's >> so what exactly y log two and not log or ln okay we explain inverse relation it's not inverse relation so it's like it's basically if an outcome is more likely it gives less information it need it's not in inverse exactly it is like in information of a is prop if information increases probability decreases if information decreases probability increases right so that's what that's what I meant I didn't mean inverse exactly but then if an outcome is more likely it can give less information right so why log log base 2 specifically and not log or ln so we are basically explaining everything in binary terms right we are saying this or that which is the simplest way and in the simplest way if you take it like this then we can say that log base 2 makes more sense other logarithms also work but then the definitions of all the other quantities that we'll be using will change other logarithms will work but then they won't be called bits they'll be called for this one it'll be called right and I'll leave this as an exercise check out for natural logarithm as Right. So let's continue. Let's take a simple example of a distribution and apply this. Right?

[00:34:52]So let's let's start with a small example.

[00:34:56]uh find the information content of getting an A. So let's say this is a probability distribution and we have five letters that can randomly occur. So if you if you have a chance of choosing a letter then you have uh five letters each with these probabilities. So the probability of getting an A is 0.125.

[00:35:17]Probability of getting a no and 0.37 and so on and so forth.

[00:35:22]So what we'll be doing here is that uh we want to find the information content of getting a so what is the information content? So what is the formula for information content? I of X is basically minus log of log base 2 of P of X, right? Yes.

[00:35:45]So let's let's see log base 2 of P of X means P of X is 0.125 0.125 is 1 by 8. So log base 2 of 1 to 8 which is log base 2 of 8 which is yes three bits.

[00:36:09]Yeah.

[00:36:11]So basically the information that you're getting from saying getting an a is three bits right three bits of that is with uh you can say that basically with three or three yes or no questions you can get to you can get that answer a you can say. So one information is basically one yes or no question. So if you ask one yes or no question then you'll get the answer.

[00:36:53]That means it is one bit of information.

[00:36:59]Right? Next. So let's say let's take an example of find the information content of getting an R. That's it.

[00:37:10]Yes.

[00:37:24]Yeah. So I guess we continue. So yeah, this is the information content which is three. So let's say what is IFR?

[00:37:55]Yeah. So if you take I of R means let's take log base 2 of 0.1875 which is log log base 2 of yeah log base 2 of 3 by 16 which is yes 4 minus log 3 right everyone seems to have got the answer so 4 - log 3 is the answer log log 3 base 2.

[00:38:30]So you will have to take 4 minus log 3 base 2 yes or no questions at uh at maximum you need to uh ask four yes or no four yes or no questions for getting an R.

[00:38:48]So, let's let's uh let's let's segue into the next section with a little bit of a game, right? So, have you guys ever heard of world?

[00:38:59]If you have if you're not, let's play.

[00:39:03]Let's play.

[00:39:08]So we will go with word.

[00:39:14]So we have as we can see we have six chances to get a guess a fivelet word.

[00:39:22]Okay.

[00:39:24]So let's start right.

[00:39:29]So, what do you think will be a good uh opener for this?

[00:39:57]Yes, money. Okay, let's start with money.

[00:40:03]Now we have O is O is green and all the others are great. So we have a it has given us some specific information about the secret word.

[00:40:16]Let's go with audio.

[00:40:19]Oh, someone said late. Interesting.

[00:40:27]Nice.

[00:40:29]Oh, nice. So, we have V O are correct.

[00:40:34]And then you have O and D is gray.

[00:40:38]Oh, audio.

[00:40:41]Well, now now we can check all the other words with which have B and O in the start.

[00:40:49]and uh have other letters other than m n e y u n d a i. So now because of all these in so because of all these guesses we are getting some information that this letter is not there in the word. This letter is there in the word but it's in a different uh different different space and this letter is in the correct space.

[00:41:17]some boxes. Let's go to boxes.

[00:41:22]Oh, boxes.

[00:41:27]So, now let's let's go with the correct answer.

[00:41:40]Books is not not the correct answer.

[00:41:43]Nice.

[00:41:45]Yes.

[00:41:50]Yes. Both.

[00:41:52]Yes sir. So now we have the answer both.

[00:41:58]So what have we done here? Let's take this.

[00:42:05]So what did we have? What happened in word? So what did we do here? We gave a guess.

[00:42:15]We basically gave our first guess.

[00:42:23]Okay. We basically gave our first guess money. Now money what happened is that we we had our uh O as Greek which mean that it's in the same place and the letter is correct. All the others were gray. So so those letters were not there in the world.

[00:42:46]Okay. Then we had uh we had some other guesses. All the other guesses they gave us information that this event uh that this letter is not there in the word.

[00:42:58]This letter is there in the word but it's not uh but it's not in the correct place and this letter is there in the correct place. So because of that we got we got to our answer.

[00:43:10]Right.

[00:43:13]So that's that's how we are that's how we will be solving the word. So what we doing is that we are giving a guess we are getting information about the guess we are getting information about the secret in secret word by giving that by the information that the guest gives that is the sequence at which uh the uh the gray boxes green boxes and yellow boxes give and later we using that information in order to guess another better guess right so that's What are we doing here? We had a guess and it gave us one of 3 ^ 5 that is 243 possibilities.

[00:43:54]A little more formalized here, is it?

[00:43:56]Let's say for the word slate, we have 243 different possibilities.

[00:44:04]So to out of each of the 243 different possibilities.

[00:44:09]So if you take one word for example, then the configuration of If our secret our secret word is proof, right? So the configuration of slate with respect to proof is that there is no S, there is no L, there is no A, there is a T and it's in the correct direction. So you'll get a green green green uh letter and you there is no E.

[00:44:37]So basically our configuration will be this one. Uh where is it?

[00:44:44]Yes.

[00:44:46]about this one.

[00:44:52]>> Yeah. So, yes, there's the shortest branches. Yeah, I'll get to that. I'll get to why Slate is the best opener.

[00:45:13]So what we have here is that uh not exactly you can't see. So we have slate right slate our configuration is this. So there is a specific configuration of words that this configur uh this configuration is common with right there is no s there is no s there is no a there is no e and there is a t there is a t and it's in the correct place again. So what we're doing is that this slate uh groups everything into groups such that they 243 groups where each group has a certain certain set of words that that when you give a gift give to the word it will give the same configuration as sl when are the secret word will give this configuration this configuration the specific configuration So to minim optimize and minimize the amount of words used, what will we do?

[00:46:17]Right?

[00:46:21]Yeah. So how do we solve this? So every word divides the space by a certain amount. By a certain amount. So what we have here is that if you have a word you have the word dividing into 243 different branches where each branch has a certain set of words. What we want to do is that we want to we want to make sure that many all of the branches are more equally split and that we can get we'll have what is we we need less amount of words to find out the answer. So there there needs to be less amount of splits right.

[00:47:06]So what happens is that when we have when we uh when we guess another word that is our first word then it will have one of 243 different possibilities.

[00:47:18]Again we want to make sure that this is done in the fastest way.

[00:47:23]So the words that on average divide the search space the most should be used.

[00:47:30]And then that leads us to entropy.

[00:47:34]And no not the thermodynamics entropy.

[00:47:37]It is it has some similarities but it's not exactly the thermodynamics entropy.

[00:47:45]So what is entropy?

[00:47:47]The measure of the average amount of information that you can get out of an event is entropy. So entropy here is sorry entropy here is basically it will be represented with h as you know from thermodynamics. It will be represented with H.

[00:48:04]It'll be represented with H. And it is the average amount of information.

[00:48:10]Now, average amount of information is basically expected value, right?

[00:48:15]Expected value of the information function. Right? In statistics, this is obtained by using the expected value. Yes. So therefore, the entropy of the word is the expected value of information.

[00:48:32]Again it's not that uh it's it's not what it exactly is in uh chemistry but it is something similar.

[00:48:44]So how do we solve this? So entropy equal to the entropy of event which is equal to expected value of the information function. Now we know the information function is minus log 2 base p of x.

[00:48:59]So now the expected value will be min - x minus p of x into log base 2 of p of x. So what is the value of our expected value of any function is uh the sum of probability of the function and the and the value of the function for all the values of x all the values of x in the distribution.

[00:49:27]So we now have this formula over here entropy = minus log sigma p of x log x to p of x.

[00:49:38]So as we know this is our information part. Now we have the expected value that is p of x into log p.

[00:49:47]Again the formula of entropy is so and so. If you want you can write it.

[00:49:57]Now let's take an example of how to use it. Find the average average information content. So what we can say basically is that entropy is the average information content that a letter can have [clears throat] in this distribution.

[00:50:14]That also we can say as a definition of entropy. Entropy is basically average information content of any element in the distribution.

[00:50:24]So let's take let's take this example.

[00:50:28]So the average information presented is entropy basically h of x which is equal to sigma x uh p of x log log 2 of p of x. And I hope everyone understood what 10 rupee is. Any doubts.

[00:51:12]Everyone understood right.

[00:51:20]So let's start with this. So the entropy basically here is summation of P of X log P of X. Now if you make the summation let's say 0.125 log log base to 0.125 plus 0.375 log log base to 0.375 0.25 log 0.25 25 plus 0.185875 log base to 0.1875 plus 0.0625 log base to 0.0625 0625 right so let's try solving this this is again sorry minus here I completely forgot the minus no entropy is positive entropy is positive I forgot the minus entropy is positive so I forgot minus here minus p of x log p of x so as you can see here this This is - 3.

[00:52:38]This is uh 3 into so - 3 + log 3.

[00:52:48]Now - 3 - log base 2 of 3.

[00:52:54]This is - 2.

[00:52:57]This is uh - 4.

[00:53:05]So this is 3 by 16 just plus log base 2 of 3 right uh no again sorry plus log here again here we have 0.0625 0625. So divided by - 5 - 4 we have right.

[00:53:29]So we have the sum equals let me write here sum= - 3 - 3 - log base 2 of 3 - plus log base 2 3 - 2 - 4 + log log 3 + - So as you can see you can calculate that out here this is your entropy so - 3 - 6 14. So 14 + 2 log 3.

[00:54:06]So the average entropy here is 14 + Oh no, not 14. What is this? What am I done? God, I'm so sorry.

[00:54:20]I completely forgot the weights. - 0.375 - plus - 0.375 into - 3 + log base 2 of 3 + 0.25 25 - 2 + 0.1875 into 4 - 4 - 4 + log 2 log base 2 of 3 plus 0.0625 into log uh which is - 4. Now the calculations will be done in the next slide. So this is your probability distribution. These are your calculations, right? So if you do the substitute the log values back you'll have this this log log value this log value this log value this is your log value. So you'll get around 2 21084 bits of bits per letter.

[00:55:25]Do you guys understand?

[00:55:47]Yeah.

[00:55:50]Yeah. So basically 3 - 9 by 16 log log 2 base 3 which is you're getting around 2.108 bits per letter. So the average information content of the next letter is approximately 2.1084 bits. Apologies for the last time I forgot to take the probability.

[00:56:15]It means that every letter has this many bits of information. Every letter needs at least this many bits of information.

[00:56:26]Correct?

[00:56:31]This many bits of information, right?

[00:56:36]So, how do we use this for our word example? Right?

[00:56:42]How do we use this for our word example?

[00:56:46]Let's just try understanding with this example.

[00:56:52]What does it mean?

[00:56:59]So, so let's see. So, which guess is most appropriate? So what we'll do here is let's take crane snake slate and points right.

[00:57:28]So which case is most appropriate? So what we doing is that we want to ensure that uh which guess reduces the possibilities a lot. So which guess uh which guess can help us find the answer more easily. So crane. So if you find crane then we will have a few possibilities right.

[00:57:52]So with snake our possibilities are A is correct, E is correct. A is correct, E is correct. N is not correct. So let's say N is not correct. N is correct but it's in the wrong position. So let's put it with this. These two are not there. So you're having this configuration with uh sorry slate.

[00:58:21]With slate you'll have similar uh configuration except here the A is not there. This one is there. This one is not there. This one you're having this configuration with points you're having uh I is not there. P is not there. N is there wrong place. So let's put a circle. E is there wrong place. Circle not there. So we have this configuration right?

[00:58:51]for crane. So the probability of this config so if the words actually so let's see how do you think you can solve this question let's see let's see the chat right how do you think we can solve this Sorry.

[00:59:51]most entropy right not least entropy. So uh the d the ab 6641 asks so like for word we analyze so we'll take the most entropy so that we will be a we'll have the least uh we'll use the least words to uh find the most uh to easily find the uncertainty.

[01:00:20]Yeah.

[01:00:22]So just rain snake snake and pus.

[01:00:40]So if you say the see if we get get the guess crane then the probability of having snake is 1x3 right? So 1x 3 1x 3 1x 3 and the probability of you getting it all 1x4 actually 1x 4 1x4 1x4 yeah more coverage of possible branches.

[01:01:14]So what do we have here? We have if it's crane all correct then the possibility is 1x4.

[01:01:24]If it's snake then the possibility of having this uh this configuration a k e is 1x4.

[01:01:37]Then the possibility of having slay is um what do you have here?

[01:01:50]Just a sec. Anyway, uh let's what do you guys think?

[01:01:58]Anyway, let's keep this as an assignment.

[01:02:01]So, okay, let's take a break for doubts at rest.

[01:02:07]Okay.

[01:02:09]So I'll take around I leave around 10 to 15 Well, more entropy means less information, right?

[01:03:30]More entropy means less information.

[01:03:40]What's it? I'll get that.

[01:03:54]On one second I uh cosine theta asks uh can you explain why more entropy means more information?

[01:04:05]Well, I'll I'll get back to you.

[01:04:08]I will.

[01:04:10]That is an interesting question indeed.

[01:04:36]Okay.

[01:04:38]So to answer your question uh cosine theta uh if an unpredictable or a highly random message provides it because it provides more normal facts more facts like you can you it it reduces the search space by a lot that means your entropy is high so your information it gives you more information.

[01:05:06]But to answer your question, that's your that's your that's your doubt explain.

[01:07:29]Yes, exactly. So to answer Nan Kamala's question, take every word and then check number of tries for the shortest part to get to that word.

[01:07:39]Yes.

[01:07:44]Yes. Exactly.

[01:07:50]That's what that's what we're trying to find here by information like we trying to ensure that uh some words they will divide it by a lot some words they they will divide more some words they will divide in one into like very a very big uh a very big uh sample space the other one will will get very less. So basically you're saying that uh these words the uh these words uh so you want to divide the sample space more evenly. So that's that's what uh shorter spark means Yes.

[01:09:04]So, has everyone marked their attendance for the second part of the session?

[01:09:38]Okay.

[01:10:36]Any other notes, guys?

[01:11:48]Yes, exactly. So if all of these are discrete probability, but what if it's continuous probability means of course we'll be using inputs.

[01:12:22]Can you not see anything?

[01:12:31]Let's see.

[01:13:57]Yes. So we shall restart the session uh after this short break.

[01:14:06]So now that everyone has marked their attendance, let's go. Let's go to the second section. Section two the applications of all these all these elements and all these concepts and LLMs.

[01:14:22]Now yes LLMs this is this is how there is a very small connection to all of the all of these concepts and LLM. So we'll we'll keep that for the last applications where this wonderful branch can be applied. So to recap what we did is that we defined the information that is minus log base 2 of the probability of the event and then we find define the entropy that is the for each possibility the summation of the probability times the log of probability and then the minus at the end because information is so where can this wonderful branch be applied. So now that we know the basics, let's see where this wonderful branch can.

[01:15:14]How do we communicate effectively minimizing the amount of information needed to transmit? I'll give you guys a few minutes to answer this question in chat please.

[01:15:38]Okay, so we have a doubt here.

[01:15:43]>> Yes, natural language processing is also work. But we have a doubt here. How does entropy end up being an integral? Then mod sums concerning different intervals corresponding surprise. Well, that is an integral in basically what we're doing here is that instead of uh using when you have summation and as the intervals get closer and closer together see instead of using in uh summation we use we we just use an integral. So basically the summation as the intervals tends to very very small number intervals to zero is just an integer.

[01:16:41]So how so coming back to the question how do we communicate effectively minimizing the amount of information needed to transmit I'll give you a hint so in our previous distribution we had every every element had a certain probability of occurring right so can we say that that element can be described with that probability with that amount of uh bits right so let's say we have a that is 0.125 probability of happening. So we would need to ask at least two yes or at least two yes or no questions to get to a. So to to uh to ensure uh to define a we need to ask at least two yes or no questions to check whether the given element is an eight. Right?

[01:17:38]And then this leads us to Huffman encoding. Right? So Huffman encoding is uh an encoding system that is basically basically rooted in this entire uh zero uh zeros and ones and this uh binary information.

[01:17:57]Right? So it basically says like how many yes or no questions do you need to get into that a right? Yes. Three questions. I'm sorry my bad. Three questions. I'm so sorry.

[01:18:10]Three questions.

[01:18:14]Now coming to Huffman encoding. Huffman encoding is a lossless encoding algorithm. Meaning all the information that you have in your data will not be lost.

[01:18:26]There will there won't be any loss there won't be any missing information in your encoding system. So instead of like using very very long very uh uh voluminous data we are we are bringing it down to a certain compressed data. So it is a compression algorithm. So this is a lossless encoding algorithm where information theory is used to maximize compression and be efficient with communication.

[01:18:54]Now in essence what Huffman encoding basically does is that what we what we will normally think when we want to when we want to encode something we if we want to encode something then we want the free most frequent elements to be to be encoded with shorter uh codes. So for example, if E occurs very often, then we want to ensure that that occurs with uh only one or depend the shortest amount of u shortest amount of data that uh that that encodes the letter. So it assigns assigns shorter codes to frequently used characters or tokens and ensures maximum brush. Right? So let's see let's see how it's work how it works. Now this is a little bit of a detour into CS territory. So please so yes so how does it work basically is that it first counts all the all the frequencies of all the characters in the text and notes it out on a list. Now if you know a little bit of DSA then you can say it's a priority priority queue where like because we want the minimum to be first right so we want to be easily access so yeah on a second but yeah it knows down in a list ordered by the frequency of the letters smallest to largest so this is very important this is how we build that this is how the this is the main thing how the encoding algorithm works so it's ordered by the frequency of uh smallest to largest.

[01:20:36]The smallest two elements are joined into a larger node and the value of the node is the sum of the frequencies.

[01:20:44]The process repeats until there is only one node in the list. Later directions are assigned zero or one and each node has a pathway in a graph. So for example, let's see how it works by giving an example.

[01:20:58]So let's say we have a word that is let's say we take the word booth itself right so if you take the word then the probability of each of those happening not boot let's say some uh boot legs right so boot legs so we have B the probability of B occurring is 1 in 8 which is 0.125 or 0.25 because there are two holes T L E G S or 0.125 right 0.125 0.125 0.125 0.1 Right. So basically what we're doing here is that ordered by the frequency of the letters smallest to largest. So this one this frequency goes down. I hope everyone can see and understand it.

[01:22:23]Yes, everyone understood right.

[01:22:48]Yeah.

[01:22:50]So now what we'll do here is that the smallest two elements are joined into a larger node that is B and T. Let's say we have B and T.

[01:23:01]B and T.

[01:23:03]Gibberish has a lesser probability so it should have more information. Yes.

[01:23:08]Basically that's that's how that's how we make it into gibberish right. So gibberish has a lesser probability so it should have more information. Yes. True.

[01:23:26]So bootlegs. So B and T are joined into one node with the value of the node is the sum of the frequencies that is 0.125 0.125.

[01:23:42]Yes, exactly. The least least used characters are placed f further down the path and require longer paths through the system and the more frequently used ones are placed at the top. So they're away. Yes, exactly.

[01:23:55]So that's what we've done here. B and D B and T. Then again we'll do we'll take the lowest possible nodes. So we'll we'll add it here. So BT 0.25 25 and then we have LN E which is 0.125 0.125 so 0.25 again same story 0 E N G 0.25 then we have uh E and G S and O which is not 0.25 25.

[01:24:36]Uh, this is it. O T L E G S.

[01:24:44]Okay.

[01:24:47]A check.

[01:24:52]Yeah. Okay. Yeah. SN O SN O SN O which is 0.375.

[01:25:02]Again the probability sum should be one minus G S okay GS never mind PTLE GS apologies this eraser and we have a node O with 0.25 25.

[01:25:25]Now we'll be combining these two into a node of 0.5 and we'll be combining these two to a node of 0.5 and so on and so forth until you have a tree. Now I'll show you it uh I'll show you it as a demonstration.

[01:25:46]So let's go with this.

[01:25:51]I hope everybody can see the screen.

[01:25:54]The Huffman coding algorithm visualization.

[01:26:08]So let's type the letter boots. Let's type bootlex and see what the graph gives.

[01:26:17]Right.

[01:26:20]Let's let's see. Let's build the tree.

[01:26:24]Now as you can see now as you can see here it sorts based on the frequencies and what we did it first one it it merged the it merged the least amount uh it it merged the elements with the least amount of frequency together. So it merged this one and this one because these two have the least frequency into into a node of two frequenc frequency two. Same thing here. It'll also do the same thing next.

[01:26:55]So E and L also will go together. Now O and the this node will go together.

[01:27:00]These two nodes will go together and these two nodes will go together. So you're having this this tree.

[01:27:08]So what we can do here is that using this we can assign a direction to we can assign a direction a certain binary number that is zero or one. So let's say we take left as zero and right as one.

[01:27:21]So what would be the encoding of O and what would be the encoding of T Yeah. So basically what you can say is that uh 8 the encoding for O will be we're going right one. So 1 one so encoding of O will be 1 one. The encoding of T will be 0 0 1 because you're going left right.

[01:28:31]So let's go back to our uh presentation.

[01:28:35]Let's try to build that same tree for this text. Right? So let's take this text. So our frequency table is given right over here. So if we take this frequency table and we write nodes, we write the nodes then it will be D E H Q and so on and so forth. So what we can do here is match it with the frequencies Q and so on right. So now what we can do is that we'll try to build the tree. So our tree is like this. So if you take if you want to take for example the encoding for u what we're doing here is that we'll assume left is zero right is one. So 0 1 1.

[01:29:28]So our algorithm for U for our code for U is 0 0 1 1 0 1 1. For example, if you want to take underscore underscore will be 0 0 0 because it is the highest it has a much uh higher probability of occurring. It has a higher uh higher frequency. So what we're saying here is that 0 0 0 we are having a shorter code for a code with a higher frequency.

[01:30:02]So how is information theory used here?

[01:30:05]The most information a character or token can carry is defined by surprise.

[01:30:09]This is a fact. So the most information a character or token that it that is needed to uh define it or describe it is its surprisal or information. What we surprisal is information over here log base 2 of p of x.

[01:30:30]If I = to log uh I equal to log log base to pfi is the minimum information needed to carry the element without information pass then the min minimum average information for each element cannot be less than the entropy right.

[01:30:47]Yes. So basically what we can say here is that the expected value so the minimum average information cannot be less than the expected value right which is entropy which is true.

[01:30:59]Huffman encoding approximates close to the entropy limit that Shannon predicted. So the so the Huffman encoding is one of the earliest most uh efficient algorithms to encode information way before even even computer science systems uh developed to that level.

[01:31:21]So the entropy limit that Shannon predicted is the theoretical maximum at which the theoretical max uh minimum number of bits that can be uh that can be used without losing information in order to describe an event. Right?

[01:31:41]So Hoffman encoding approximates close rate. This is a good and efficient compression algorithm used alongside other algorithms. Uh, I hope everyone understood.

[01:32:17]Yes. So let's continue. So the uses of Huffman coding is zip files.

[01:32:24]Huffman coding is one stage of the deflate algorithm. So there is an algorithm called deflate where many many compression algorithms like zip, gzip and bg use this algorithm in order to compress data. So Huffman coding is one stage of that algorithm typically applied after something called as LZ7 style pattern matching pass.

[01:32:49]The same thing goes for JPEG JPEG images. You compress JPEG images as well. Uh the after you lose a lot after the lossy part which throws away visual details humans don't notice much. So basically there will there will be some parts of uh an image where uh even if they are not even if they're not uh in the final product you will be able to understand you won't m it wouldn't matter much so that is the lossy part the remaining data is halfman encoding as a final lossless compression box and many other compression algorithms like MP3 and PDF files use Huffman coding as a Huffman or Huffman derived input So I'm just putting this one theorem here. So so Shannon's source code source coding theorem is basically what we what we saw uh earlier for a collection of n random variables each with entropy h of x. The minimum number of bits required to describe the information is n of h of x. Now how this how this u how this theorem came about is beyond the scope of this course. So I'm just I'm just putting this for your information. It's it's a really interesting read if you want to know about it.

[01:34:13]So what do you think is the most information you can pack in a channel?

[01:34:18]A small introduction to a small topic that we have the noisy channel coding theory.

[01:34:26]So the noisy channel coding theorem is one of the two theorems that was proposed by Shannon in his paper. So which says that for any channel there will always be noise involved. So if you want to communicate something for example from a point A to a point B then a channel will definitely have at least some noise into right.

[01:34:53]So some there will definitely be some noise which will change the data right.

[01:34:59]So there will always be some noise invacity C. So a capacity is basically how much information it can reliably carry with with having error connection codes without uh without any information being lost to chance or to this loss.

[01:35:18]So if your transmission information transmission rate is below C that is R there will always be a code that can communicate information the closest to zero error that you want. So if you have any yes there so if you have any channel with with a channel rate R if you're transmitting information with the rate R then you can ensure that any you can ensure that you can bring a lossless you can bring zero loss into this and there will always be a code that will ensure But if it is above C, this rate is above C, then it is impossible to reliably transmit information. Right?

[01:36:08]And a small footnote here, the Sharon Hartley theorem, the maximum capacity of a channel that has a bandwidth B, a signal strength S, and a noise which is active white Gaussian noise. So active white goate noise means white here mimics the uh mimics uh uh uniform probability distributions.

[01:36:32]Gaussian is our gossian distribution basically this distribution over here or normal distribution noise is unwanted data of power.

[01:36:43]So this is our formula. Now do read upon this. It's also a very interesting read.

[01:36:51]So Ani will take take on from here. Uh he'll be taking a brief intro to machine gun and then Yeah. Harish could you stop presenting for me presenting?

[01:37:44]Yeah. So I hope everybody can see my screen. So my name is Anerut Pai and Harish talked about information theory and how like bits and all that is connected and he talked about burden and I think he told a lot about entropy too.

[01:38:01]So now uh all this is done for encoding however when you're working in real life you need to talk about data and data is sparse. It can be of any format and usually the data that we need is in the form of numbers. So an aspect of how we can like turn these numbers into bits comes under machine learning and the way to analyze these numbers also falls under machine learning. So now let's look at what machine learning is.

[01:38:33]So let's say you have something like let's say you have a function but the function is not specified. You're given with a set of data points and you're given with something that's y. So y can be termed as the output and obviously you'll know the input for this given y also.

[01:38:56]So machine learning if I want to represent it mathematically it means I need to find a function f ofx using these data points and these data points over here represent x y.

[01:39:10]All right and from that I need to specify what f is usually and in a broad sense I can say that machine learning is identifying what this function f of x is. Now f ofx is just taken here for simplicity. You can have multiple inputs like you can have some X comma Y comma Z as the inputs and some O as the output.

[01:39:35]So it doesn't matter it just matters about what we're doing taking the inputs and outputs and deciphering a function from them.

[01:39:43]Now there are three types of machine learning. So the first one is the most general sense which comes under the other two as well. So we given a label data point X I being the input Yi being the output and you want to learn a mapping of X I to Yi. Now such a mapping is called a function or a relation depends on how it's phrased. So usually it's a function the same one as in mathematics. So this is how supervised learning occurs like you're given a given set of data points and from this you try to encode what the function is and this is an example which is very abstract predicting house prices from house features and another one is uh let's say we're given like a multiple set of data points and we want to find like a given structure or something. So maybe we need to plot a graph like for example if you're calculating if you have a like set where you're plotting the heights of like students in your class you just have the our labels XI and you'll have its frequencies.

[01:40:56]So this is an example of unsupervised learning.

[01:41:01]So I hope these two are cleared.

[01:41:05]So the third one is reinforcement learning. So reinforcement learning is a bit different from the first two and it occurs in the form of you know positive or negative feedback mechanism.

[01:41:20]So how it occurs is let's say you have a given stimulus like take your own human body for example. So your human body is a wonderful depiction of how reinforcement learning occurs. So you have an external stimulus and you have an environment and based on that all your organs and bodily functions happen.

[01:41:39]So based on your like external agent A and the environment E the function has a state S let's say and based on a given action B done on the state by the agent under the effects of the environment your state changes and from this you get to find what the action does and from this you try depicting what the function actually is it's a bit complicated. We don't have to go into depth for this but classically that's how we describe.

[01:42:18]Now I hope I hope this is clear.

[01:42:25]Okay.

[01:42:29]Now let's talk about an example of machine learning. One great example would be linear regression.

[01:42:38]So what is regression?

[01:42:41]Well, if we have to talk about it in a brief sense.

[01:42:46]Uh regression means we're trying to plot a graph for a given set of points and this comes under super supervised supervised learn the first time where we have a given label x i y and we're trying to predict something from that a function.

[01:43:01]So let's say we have a graph over here um and these data points are arbitrary 20 40 60 80 and all that. Just imagine we have a graph and we had to have a set of points that are sparsed in this way and as you can see clearly like let's say you have to plot a function but you want the function to be simple and we have these two constraints. So why do we want it to be simple? obviously because uh it'll take lesser computation time.

[01:43:32]It requires lesser memory and lesser number of bits as we know in information theory. So from this you want to plot a function. So the simplest thing that I can think of is a constant function.

[01:43:46]But as you can clearly see neither of these values are constant. So what's the next best thing? A linear function. like I'm going in the terms of like polomial because polomials are the easiest functions to work with.

[01:44:04]So hence I'm thinking of a polinomial.

[01:44:06]So the easiest function over here is a degree 1 polinomial which is a linear graph. So I can see that I can plot a linear graph and all of these values fit in and around the linear graph that I'm plotting.

[01:44:19]And I'm also given with the input and the output value.

[01:44:23]All I need to do is find a mapping f to this. And here I'm choosing my function f to be a linear map. And also note here one thing I can choose my function to be anything. And based on these values I can find a function that satisfied.

[01:44:43]So what is linear regression as I told but mathematically let's say your input value is x and your output value is y I can say that some ycap is equal to wx + b which is the required line.

[01:45:07]Okay. However, y - ycap is not equal to 0. Why? I mean it need not be equal to zero because obviously if you have like many data points, it's not true that all the points pass through the line. Some might or might not. So this has some error in this and let's call that error epsilon.

[01:45:34]So what is the actual y?

[01:45:38]The actual y can be written as y is equal to ycap plus epsilon.

[01:45:45]And what is ycap?

[01:45:49]Your assumed value of y given the function f which is the linear map wx + b.

[01:45:57]So B is the bias which means the coefficient of X and W is the constant which can be we can call as the weight of the line.

[01:46:06]So here are some key points which you need to note. The sole way of assuming a linear function is because of the way this the data points are set like they're all centered along around this line. Now let's say the data points rose up here as well.

[01:46:22]then assuming a line would give me an error because these points don't satisfy this line even by a little bit. Your point is not to make it exactly satisfy you need to minimize this error epsilon tending to zero.

[01:46:37]That is our main goal.

[01:46:41]And like I said the line need not be perfect and even pass through these.

[01:46:47]Now how is this correlated with machine learning? So this is my initial set of data points which is called as the training model training training set for the model and the learning happens based on this present data set and from this present data set I get a function f now this function f like let's say you have a set of thousand points and out of these I extract only 50 from these 50 points I'll determine a function f.

[01:47:21]Now again I take this function f and I apply it on another set of 50 points such that the two sets are completely exhausted.

[01:47:32]Now applying this function f I might get some wrong answers or correct answers based on how well my model is. Now if it's wrong my model autocorrects itself based on how wrong it is on how er like how much error is there. So that is what happens.

[01:47:52]So we'll come to that later.

[01:47:56]So now one question is how do we calculate W and V?

[01:48:00]So this is your predictive output value and this is your error EI which is like the real value minus the uh assumed value.

[01:48:12]So the best case scenario over here is when the error each error is zero that all the points lie on the line.

[01:48:20]However, is that possible? Well, no, it's not possible. So what you need is each error minimizing itself to like a very low value or it should limit tending to zero.

[01:48:35]However, we want the value to be at minima like I said and also note one more thing. We cannot take the direct sum of the errors like if you want the d like we need a function of these errors to be zero.

[01:48:49]Let's say some g of e to be zero but we can't take the direct sum of the errors.

[01:48:58]Well, the reason being let's say we have a line and let's say we have points over here.

[01:49:11]Let's say these points are equidistant from the line. Now this will have a positive error. This will have a negative error. This will have a positive error. This will have a negative error. Effectively cancelelling all the sum of the errors to be zero.

[01:49:27]But we know that this line is a terrible fit for these points which are lying over here. Like it's absolutely terrible. So what does that mean? Taking the sum of the errors to be zero. We cannot do that. So we need another function g of ei to be zero and g of ei is not equal to sigma ei.

[01:49:54]Now what function of errors do we minimize?

[01:50:02]Well, apart from the linear function, apart from directly adding the fun directly adding the errors, one might think that we can take the modulus of the errors, right? That is true. We can take the modus of the errors because that way everything is of the same sign and the errors does error does not you know propagate.

[01:50:24]Now somebody asking what what about like standard deviation?

[01:50:28]Well, you can take a standard deviation as well but that will give you no like you know easy method and technically what we're doing here is taking the square. So that is some form of the standard deviation.

[01:50:43]So okay one another thing which we could do is take the modulus of the errors but the modus of the errors will not work because okay as we learned in calculus long back um the easiest way to find a minima function is by differentiating that function and equating it to zero at its inflection point.

[01:51:09]Now for a modulus function it's not differentiable and this actually kind of breaks a few rules and because of that we do not use the modus function.

[01:51:22]Now what like we need all the errors to be of the same sign and the simplest way to do a function of the errors is a polomial function. So since degree 1 deg degree 1 does not work and modulus also does not work we'll go to degree 2.

[01:51:43]Why does degree 2 work?

[01:51:46]Because when we take squares what happens is this error evens out and we get it of the same sign. So we take the le squares. Okay. So somebody's asking why don't we take the weighted average of the modulus of errors. Well the same reason again because of issues with differentiability and if you if you differentiate a like linear function the only the point of non-ifferi can be treated as the minima but that does not give us any good information.

[01:52:24]So hence we take the second degree polinomial which is the error squared. So we take sigma error square which is this.

[01:52:37]So how do we find the values of w and b and we need to okay we need first of all we need to minimize this function. So how do we minimize it? We minimize it by differentiating. Now do note we need to differentiate with respect to a variable. Yi is a constant because it's given to us. Xi is also a constant because it's given to us.

[01:53:06]Well, somebody saying that a quadratic fits the data points better than a linear.

[01:53:13]Uh well, one could say that a quadratic will fit it. But the intention of the graph was to make everything as close to the line as possible. So a quadratic can also fit it. That is true.

[01:53:32]But here for simplicity we taking the linear function.

[01:53:39]So here like I was saying yi is a constant and x i is also a constant.

[01:53:46]So what are the only variables left? W and v. So we have a function j which is a variable which which is a function of two variables and both of these are independent w and v. So how do we minimize this function? We partially differentiate.

[01:54:04]So when we differentiate with respect to W we take B to be constant and when we differentiate with respect to B we take W to be constant and then we equate the derivative to zero.

[01:54:16]So this is differentiating J with respect to W taking B as constant and this is differentiating B with differentiating J with respect to B taking W as constant.

[01:54:32]So we equate this to zero.

[01:54:36]So now now what?

[01:54:39]So we have a summation of we have a summation of n things. We have a summation of n things. So this is one equation. This is also one equation. And we have two variables to find. So we have two equations and two variables. So now we can find w and b on the choice of x and y.

[01:55:04]Now again let me explain why le squares is taken. Number one all errors become positive and are hence easier to deal with and larger errors can be minimized further because you're squaring the errors right for like small errors.

[01:55:18]Let's say you take 0.1 and squaring it you'll get 0.01 like 0.1 is actually a very big error.

[01:55:29]Some might say it's a very small error but usually your error should be on the margin of 10^ minus 3 for like getting a good approximation.

[01:55:40]So the function is differentiable that is one key thing because we find the minima by differentiation and any even degree would work.

[01:55:53]So that is true because you need your errors to be of the same sign positive but obviously differentiating something [clears throat] like u x^ 4 would be much tougher than differentiating a square and we get a unique solution. Why is that? Because differentiation of a quadratic gives you a linear function and a linear function has only one solution. So that makes things much simpler.

[01:56:23]So how is this useful in machine learning? Well, now you have these 50 set of data points that your function operated on and you get some function f that f assumed. Now you determine this on another set of 50 points and you check how close or how further it is from your assumed function on the errors and then you determine another function FB on another set of 50 points and you keep doing this. Now what happens is every time you do an iteration there's some memory from the previous one retained.

[01:57:03]So ultimately f of a to f of b to f of c.

[01:57:18]Finally you get some function f ofx which will be much more closer to your actual function than any of these when you operate on multiple training data sets like this.

[01:57:35]So another important thing about machine learning is okay first of all I hope everything is clear if not you can put your doubts in the chat box.

[01:57:44]So okay first of now an interesting aspect of machine learning is cross entropy how we'll look into that.

[01:57:55]So essentially what is cross entropy?

[01:57:57]Well, Harish explained what entropy is.

[01:58:00]For a classic probability distribution, let's say you have some probability P of X. So for entropy for a given probability distribution P of X the entropy can be defined as P of X I log * Q of X I negative logarithm everything and you summate this over I.

[01:58:32]So now what is cross entropy?

[01:58:36]Well, let me explain from the next slide.

[01:58:40]Let's say you have a probability distribution P of X.

[01:58:44]Right? Now for this probability distribution, you don't know what the function like here I've taken only three points. But let's say you have around like 50 points. Let's say you have some discourse set of data points like this.

[01:58:59]Now for this probability distribution let's say you want to assume a function f.

[01:59:06]So for this function f let's say uh for some given x i you get some output as some yi cap.

[01:59:17]So this is the assumed probability with a given function with like not the given function with the function that you assume. So your assumed model you because you don't know the actual function you have to make an assumption like how we did in linear regression where we assume the function to be a line but it need not be a line it could be a quadratic based on your choice here you assumed it to be a line. So based on your assumed function uh you get a different model and that will have slightly different probabilities. Now here obviously the the difference is pretty drastic.

[01:59:55]Now since it's very drastic u that means like there'll be some error but let's say our function was flawed and we got a large error. Okay.

[02:00:07]So this is our real model. This is our assumed model.

[02:00:11]So this signifies the cross entropy between two models.

[02:00:18]Okay, so we want the cross entropy to tend to the actual entropy. That's when we know a model is nearing perfection.

[02:00:28]So this is a very nice way to gauge whether a model has like good standards or not. Now obviously one thing is okay it's not obvious but we'll need need it such that the cross entropy should not be equal to the real entropy.

[02:00:49]And why is that?

[02:00:52]Well, the main reason is let's say we change this model a little bit by adding like uh let's say 100 extra data points.

[02:01:02]Now if this 100 extra data now if this 100 extra data points is different from what the actual data points of H of P are then what will happen is H of P will give an error for this 100 data points and H of P of Q will also give an error if they are equal but you want the like models model Q such that it's susceptible to change and like any kind of error and noise. So hence we don't want it to be exactly equal but we want it to be as close as possible.

[02:01:33]So this is cross entropy.

[02:01:37]So this is our assumed this is our real model and this is our assumed model.

[02:01:43]So let's say we have this 25.5.25.1.4.5 then the cross entropy h of t of q is defined as this sum over x. So as you can see we do this summation and that we get it we get the average entropy to be 1.7414 bits and let's say you calculate it to be calculate like uh h of t you'll obviously get it to be different from h of t.

[02:02:22]I hope that's true.

[02:02:25]And yes, the thing that we use in linear regression is the root mean square of all the errors.

[02:02:33]That's correct.

[02:02:36]And I hope this is clear.

[02:02:40]And now uh Har should be giving a small introduction to LLMs and token generation.

[02:02:48]So I'll stop presenting.

[02:02:52]Right. So, I'll take it away from here.

[02:03:03]Right. So, let's take a let's see how let's see a a small introduction to LLM basic. So, what are LLMs? LLMs are large language models.

[02:03:21]Okay.

[02:03:26]Uh, why do we go for P of X?

[02:03:32]Log P of X.

[02:03:46]I mean that is also another way of like uh using cross entropy but then it is for like uh you're finding the dist uh you're finding the other you're finding the difference between the model data from the original data.

[02:04:06]Here you're saying the original data from the model data.

[02:04:11]So it's like you're you're having a different basis you will say.

[02:04:18]So for the first one the basis is your true data. The second one your basis is your model data. That's the difference.

[02:04:29]Anyway, large language models or LLMs basically are are artif uh are programs where they have learned they have learned been trained to mimic human uh human speech and text generation. So those are lls basically.

[02:04:54]So in a nutshell how they work is that they work on the principle of finding out the next token. So let's say you have a a certain sentence and you want to find out what the next possible token is. So LLMs work on the basic principle of trying to predict the next token after a sentence using the softmax probabilities and tuned in parameters that they have been trained previously.

[02:05:19]then assign probabilities to the next possible most probable token that will be chosen. Right? So that's how a large language model works. So if you have a sentence for example then then the next next word will be taken from this uh this list of probabilities and you'll you'll find out that it is that word next token. It will not be exactly a word. So for example if you have key it may not be exactly a key it might it will be a part of a word it can also be a part of it doesn't always have to be.

[02:05:53]So this data this probability data is taken from training the model over a large amount of human data and that assigns probabilities to these tokens.

[02:06:02]So that so there is an innate uh so there is an innate data set that assigns that has uh probabilities but then but then as it gets trained again and again it will with new newer and newer human data it will have it'll start mim mimicking human data.

[02:06:25]So as Anerod said, we have one one uh one error correction method for uh for uh artificial machine learning programs is uh not MSSE here exactly the mean squared error or the gradient descent method. But that is not the only error correction method. So the MSE is not the only error uh finding method in an L.

[02:06:52]There's also the cross entropy. So the cross entropy is a very useful error correction error correction term that signals that signals that how far the true sorry how far the model is from the true distribution. So that is your cross entropy.

[02:07:11]So cross entropy is a metric used for measuring the error between the AI model and expected human text. So our expected human text is P of X and our AI model has a probability distribution of Q of X. So like mean square error it is an error error function that is minimized during training in order to ensure the accuracy of the model to human generated text. So as I said P is a distribution of word property for human and Q for the A.

[02:07:41]So let's take this as an example. So this is a true human distribution where the words error have a for so let's say we have a sentence for example and then the next word has has been has from human data is this so the probability distribution of the next word from the human data is you have a 14% chance of error 65.2% chance of the uh 1 10.2% 2% of hello and 10.6% of link. Now the AI after training a lot it it gets this probabilities. So this this set of probabilities for the same sentence. There are two AIs that have been trained differently. So that one AI gets this probability distribution. One another AI gets this probability distribution.

[02:08:35]So let's try to find out the cross entropy for each of the models. So this is our human model. This is AI1 and this is AI2.

[02:08:45]So the calculations are given below. So as we said the formula for our cross entropy is h of pq equal to 1 second for all the for all the data point for all the events all the words in the distribution.

[02:09:08]H of PQ is the summation of P of X log log base 2 of Q of X for all the words for all the words X in the distribution.

[02:09:18]Right? So calculation for model one. Now if you do the calculation for the model one that is the word error the hello and like then you'll get to somewhere around 1.479 bits of difference. So basically what we're saying is that the extra amount of information required to describe Q as a as uh from as an encoding system with P. So basically you have P you have P as an encoding system. So the extra amount of surprise that the AI gets is Q is HPQ.

[02:09:58]This is 1.479 bits. That is the difference between the AI model and the normal model. Now for model two we have using the human data we do the same thing. So you have one the probabilities times the logarithm logarithm base 2 of the probabilities of the AI model. So when we do that for the second model we get a difference of 1.497 bits. So here it's more it's tiny bit more but it's not that much more right. So we want to make sure that the the function is most minimal. So which which model do you think has the is the closest to mimicking human data?

[02:10:47]Yes, that's right. The sec the first model is closest to human data. The second model is a little bit farther away. Not that farther away but little farther away. So basically as you can see here the differences between both the models are very great. So there is almost a 0.05 difference in the probability for error 2. Same here 0.05 difference. But again the other two are same. So again even even with this large uh 5% difference the number of bits difference is not that much right.

[02:11:27]So uses of cross entropy are loss functions for LLMs as a as an mentioned this is a very uh prominent function for used for the loss function of LLM to train the LLM into mimicking human data.

[02:11:43]Next word prediction tokens are assigned probabilities cross and penalizes the model if it's wrong. So if you have if you have a certain sentence and you have a yeah and the model thinks that there is a there is a word that comes in afterwards then if the word is wrong then using cross entropy we can kind of penalize the model and we can make sure that it turns uh turns back to normal and then it uh becomes more and more uh accurate to human data. Perplexity. Now perplexity is a small uh small metric that we use for uh LLMs to ensure correctness. Now perplexity is just two power H of PQ. Right? So perplexity as a metric is just two power H two power the cross entropy between P and Q. Now some other uh uh nonAI related uh uses for cross entropy you have optimal versus suboptimal coding. So remember that I told you about Huffman coding right? So there will be some other encoding mechanisms that may not be as good as the optimal encoding. So what you want to do is that you want to find the difference between cross entropy. So the optimal size is entropy as I said but the uses but the not every uh algorithm can go as much as entropy. There is a certain limit that you can go. So when you create this we want to if you want to find the difference you have to use cross entropy again uh an extension of this is like the cross entropy penalty.

[02:13:22]So basically what it says is that this uh this uh this message is uh this encoding system is this much uh less accurate than the uh optimal encoding system. It tells you the average length of the message using a suboptimal scheme Q. Right? So if you have a true scheme P and you have a suboptimal scheme Q, then the cross entropy is basically average length of the message using a suboptimal using the scheme Q.

[02:13:58]Now a small footnote of addition to cross entropy, we have KL divergence or the Kulbach liver.

[02:14:09]I hope everyone understood cross entropy.

[02:14:32]Yes.

[02:14:33]So, so KL divergence is also another metric used for the error correction mechanisms of but first let's give a small intro.

[02:14:45]So, Kulba liler divergence is basically the quantified difference between the true distribution and another distribution. So when you have two distributions let's say this and let's say this the difference between these two like not exact per se but then like it's a metric of difference another metric of difference between two probability distributions P of X and Q of X now the probability sorry the formula for KL divergence is given below so DKL so The the KL divergence is denoted as divergence KL P paral of Q equal to min the same almost similar to cross entropy except instead of Q of X you have P of X by Q of X right so your formula is summation for all X in the distribution P of X log P of X by Q of X so you have one probability distribution P of X. One probability distribution P of X. So P of X. So the K divergence between both of the probability distributions is P of X log P of X by Q of X summation for all X. You guys understand?

[02:16:10]So yeah looking at the formula you guys might realize that there is a very important relation between cross entropy and KL divergence which you can think of. So I'll give you a few minutes. Just think about it.

[02:16:32]So param says so here. Yes basic.

[02:16:41]Yes. So param says so k divergence is basically true entropy. Sorry basically difference between true entropy and cross entropy. Right. Well, I'll come to that. I'll come to that.

[02:16:58]So, if you if you got that uh the cross entropy equal to entropy through entropy plus the K d you are absolutely right.

[02:17:09]So cross entropy cross entropy equals to entropy plus uh difference between entropy. So to answer the question, yes. So KL divergence is basically the difference between two entropy and cross entropy.

[02:17:25]So the role of KL divergence. So in LLM models, KL divergence is used to be the safety rates. So for example, if you so there might be a chance that an LL model in order to uh ensure in order to be close uh close to as uh human readable human readable text what it can do is that it will it it will it might take some cheating mechanisms. it might cheat its way and use some other improper mechan improper uh probability distribution q of x q dash of x that may be very very different from our original uh our human probability distribution. So what it does what this scale divergence does is that it it ensures that the these kind of issues do not happen and uh you can it shows how off your model is from the actual data. So basically you can see it as a safety rates.

[02:18:48]Yes. So everyone understood this part.

[02:19:03]Yes.

[02:19:05]So yes. So for two distributions you can say that the KL divergence is set to be the surprise that you get. So the more information you have more information that you get when you describe one distribution with the information matrix of the other.

[02:19:22]So let's take the same example right. So how do how do we find the KL divergence?

[02:19:30]Let's see.

[02:19:35]Let's see how we find the KL divergence.

[02:19:37]So the formula for KL divergence is DKL or P of Q model equal to sigma X P of X log base to Q P of X by Q of X.

[02:19:57]Right? So everyone understood this part at least.

[02:20:06]So let's go to the calculation in the other side. So as we said this is our formula over here. So calculation for model one when we substitute in the log values you will get a certain value of 0.8 bits that is the difference from the true entropy.

[02:20:25]the difference of the model from the true entropy that is 0.008 for the model two we have 0 0180. So as you can see for the model two for model two the the difference the difference metric is basically almost two orders of magnitude two orders of magnitude greater than the uh difference for the model one. So basically as we can see the model one is much much closer to cuban data than model. So as you can see here it is 08.

[02:21:07]Oh no 0.00008.

[02:21:09]Okay. So almost three degrees of magnitude is lower than 0.0180.

[02:21:17]Model one loses less information relative to the human data. So and is therefore the superior model representation as you can see. Right? So that's our uh calculation for uh KL divergence.

[02:21:35]So some limitations of KL divergence as you may have noticed DKL of P Q not equal to DKL of Q and P.

[02:21:51]Now as you can see this is a very important problem that many people then that this people then that KL divergence has. It is an asymmetric divergence. It is not a true distance metric. It is an asymmetric.

[02:22:09]So as you can see cross entropy also is not uh cross entropy also is not equal.

[02:22:14]Same way uh there is a asymmetry in kback li divergence as well.

[02:22:23]So for example there's also another there may also be another distribution where any if for example q of x is assigned zero. So for any word if we know that the word cannot come out after this word like for example we can't say the right. So we can say that the probability of a the word the token uh uh a coming up after the word the is basically zero. So when you use this token, when you use this uh distribution, it the computation breaks because as you can see in the formula q of x is should not be equal to zero. Right?

[02:23:12]No matter what q of x not should not be equal to z. P of x need not be zero.

[02:23:20]Q of x should not equal to z.

[02:23:24]So here but it says that Q of X equal to Z. So the computation breaks so you cannot find the KBA label divergence.

[02:23:34]Right? So that is one uh issue that Kalbar this uh metric has.

[02:23:42]So yeah thank you. That concludes this uh wonderful session. I hope you had fun. I hope you had fun learning about this new topic. Uh if if you have any doubts or questions, please let us know in the chat. Thank you.